昆明理工大学信息工程与自动化学院学生实验报告
(2012 —2013 学年第二学期)
课程名称:操作系统开课实验室:信自楼445 2011 年 4 月 18 日
一、实验要求:
对一个非抢占式多道批处理系统采用以下算法的任意两种,实现进程调度,并计算进程的开始执行时间,周转时间,带权周转时间,平均周转时间,平均带权周转时间
1.先来先服务算法
2.短进程优先算法
3.高响应比优先算法
二、实验目的
通过编写进程管理的算法,要求学生掌握整个进程管理的各个环节,进程的数据结构描述,进程的各种状态之间的转换,以及进程的调度算法。以加深对进程的概念及进程调度算法的理解,并且提高链表的应用能力,达到提高编程能力的目的。
三、实验原理及基本技术路线图(方框原理图)
用C语言或C++语言开发。需要定义PCB的数据结构,用链表的形式管理进程,采用多级反
四、所用仪器、材料(设备名称、型号、规格等)。计算机一台
五、实验方法、步骤
源代码:
#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#define NULL 0
#define false 0
#define true 1
bool _state=0;
struct PCB
{
int ID;
int priority;
int CPUtime;
int ALLtime;
int State;
PCB* next;
};
void init();/*产生idle进程,输入用户进程数目,调用insert()*/
void print(PCB *pcb);/*输出进程属性信息*/
void print_init(PCB *pcb);/*输出所有PCB的初始值*/
void insert();/*生成进程属性信息,插入进程就绪队列*/
void Run_priority(PCB *pcb);/*运行进程,随机阻塞进程、产生新进程,插入就绪队列,唤醒阻塞进程*/
void block(PCB *pcb);/*调用destroy()将进程插入阻塞队列*/
void wakeup();/*唤醒进程,插入就绪队列*/
void proc_priority();/*优先权调度算法模拟*/
//void Run_loop(PCB *pcb);
void proc_loop();/*轮转法调度算法模拟*/
void update(PCB *pcb);/*更新进程信息*/
void pushback_queue(PCB *queue,PCB *item);/*将item插入到队列的尾部*/
void insert_queue(PCB *queue,PCB *item);/*将item插入到队列中,使得插入后,队列中按照优先级从高到低有序*/
void sort_queue(PCB *&queue);/*对queue中的结点进行排序,按照优先级从大到小*/
PCB *ready_queue,*block_queue,*idleprocess;/*就绪队列,阻塞队列及闲逛进程指针变量*/
int main(int argc, char* argv[])
{
int i=0;
while(1)
{
cout<<"\\**********PROCESS**********/";
cout<<("\n Please select a num in(1,2,0) ");
cout<<("\n 1--priority ");
cout<<("\n 2--loop ");
cout<<("\n 0-- exit\n");
cout<<"Please select a num:";
cin>>i;
while(i)
{
if(i==1)
{
cout<<("\n This is a example for priority processing: \n ");
init();
proc_priority();
}
else if (i==2)
{
cout<<("\n This is a example for round robin processing: \n ");
init();
proc_loop();
}
else
{
cout<<"Please select a num in(1,2,0)\n";
}
cout<<"Please select a num:";
cin>>i;
}
return 0;
}
}
void print_init(PCB *pcb)//输出所有PCB的初始值
{
PCB* temp=pcb->next ;
cout<<("\nID priority CPUtime ALLtime State");
while(temp!=NULL)
{
cout<<"\n"<
if(temp->State==0)
cout<<(" ready");
else if(temp->State ==1)
cout<<(" running");
else
cout<<(" blocked");
temp=temp->next;
}
}
void print(PCB *pcb)//输出进程属性信息
{
PCB *temp;
temp=pcb;
if(pcb->ID==0)
cout<<("\nThe idle peocess id running!");
else
{
cout<<"\n"<
if(temp->State==0)
cout<<(" ready");
else if(temp->State ==1)
cout<<(" running");
else
cout<<(" blocked");
}
}
void insert_queue(PCB *queue,PCB *item)//将item插入到队列中,使得插入后,队列中按照优先级从高到低有序
{
PCB *p,*q;
q=queue;p=q->next;
while(p!=0&&p->priority>=item->priority)
{
q=p;
p=p->next;
}
if(p==0)
{
item->next =0;
q->next=item;
}
else
{
item->next =p;
q->next =item;
}
}
void pushback_queue(PCB *queue,PCB *item)//将item插入到阻塞队列的尾部
{
PCB *p,*q;
q=queue,p=q->next;
while(p!=0)
{
q=p;
p=p->next;
}
item->next =q->next ;
q->next =item;
}
void sort_queue(PCB *&queue)//对queue中的结点进行排序,按照优先级从大到小{
PCB *temp=new PCB;
temp->next =0;
while(queue->next )
{
PCB *p;
p=queue->next;
queue->next =p->next ;
insert_queue(temp,p);
}
queue->next =temp->next ;
delete temp;
}
void insert()//生成进程属性信息,插入进程就绪队列,显示进程信息
{
PCB *newp=0;
static long id =0;
newp=new PCB;
id++;
newp->ID =id;
newp->State=0;
newp->CPUtime=0;
newp->priority=rand()%3+1;
newp->ALLtime=rand()%3+1;
newp->next =NULL;
pushback_queue(ready_queue,newp);
//print(newp);
//cout<<("建立: Creating -> ready\n");
}
void insert(int n)//生成n个进程属性信息,插入进程就绪队列,显示进程信息{
for(int i=0;i insert(); } void init()//产生idle进程,输入用户进程数目,调用insert() { block_queue=new PCB; block_queue->next=0; ready_queue=new PCB; ready_queue->next=0; int i=0,pcb_number=-1;/*闲逛进程放入就绪队列*/ idleprocess=NULL; idleprocess=(PCB *)malloc(sizeof(PCB)); idleprocess->ID=0; idleprocess->State=0; idleprocess->CPUtime=0; idleprocess->priority=0; idleprocess->ALLtime=0; idleprocess->next=NULL; idleprocess->next=ready_queue->next;/*闲逛进程放入就绪队列*/ ready_queue->next=idleprocess; //也可以假定初始时系统中只有一个idle进程 //输入初始进程的个数 while(pcb_number<0) { cout<<("Input the number of PCB to be start:"); cin>>pcb_number; } cout<<("\nID priority CPUtime ALLtime State\n"); for(;i insert(); cout<<"*就绪队列初始化成功"< ::print_init(ready_queue); cout< } void block(PCB *pcb)//调用destroy()将进程插入阻塞队列{ pcb->State=2; pcb->CPUtime-=2; if(pcb->CPUtime<=0) { pcb->CPUtime+=2; } cout<<"\nThe process no"< print(pcb); cout<<(" 变迁2:running -> blocked\n"); pcb->next=block_queue->next; block_queue->next =pcb; } void update(PCB *pcb)//更新进程信息,就绪队列中进程的优先级均增加1 { PCB *temp=pcb->next; while(temp&&temp->next ) { temp->priority++; temp=temp->next; } } void wakeup()//唤醒进程,插入就绪队列 { if(block_queue->next==0)/*此时没有阻塞的进程,无所谓的唤醒*/ return ; PCB *q,*p; while(true) { q=block_queue; p=q->next; while(p&&rand()%20!=1) { q=p; p=p->next; } if(p!=0) { q->next =p->next ; break; } } p->State=0; cout< print(p); cout<<" 变迁3: blocked -> ready"< insert_queue(ready_queue,p); } void Run_priority(PCB *pcb)//运行进程,随机阻塞进程、产生新进程,插入就绪队列,唤醒阻塞进程{ if(pcb->ID==0) { insert_queue(ready_queue,pcb); print(pcb); cout<<"变迁1: ready -> running\n"; } else { pcb->State=1; pcb->CPUtime+=4; pcb->priority=pcb->priority -3;/*每运行一个时间片,其优先数减3*/ if(pcb->priority <1) pcb->priority=1; print(pcb); printf("变迁1: ready -> running\n"); if(rand()%3==1)/*PCB不是闲逛进程,满足条件侧阻塞此进程*/ { if(pcb->CPUtime-2 block(pcb); else/*已执行完毕,应该销毁进程*/ { cout<<'\n'; cout<<"The process no"< delete pcb; } } else/*否则看该进程是否执行完毕,如果执行完,则释放,否则再次放入就绪队列*/ { if(pcb->CPUtime>=pcb->ALLtime)/*释放*/ { cout<<'\n'; cout<<"The process no "< delete pcb; } else { ::insert_queue(::ready_queue,pcb); } } } update(ready_queue);/*更新就绪队列的优先级数*/ if(rand()%5==1) { insert(3); ::sort_queue(ready_queue); } if(rand()%7==1) wakeup(); } void Run_loop(PCB *pcb)//运行进程,随机阻塞进程、产生新进程,插入就绪队列,唤醒阻塞进程 { if(pcb->ID==0) { insert_queue(ready_queue,pcb); print(pcb); cout<<"变迁1: ready -> running\n"; } else { pcb->State=1; pcb->CPUtime=pcb->ALLtime; print(pcb); printf("变迁1: ready -> running\n"); if(rand()%3==1)/*PCB不是闲逛进程,满足条件侧阻塞此进程*/ { _state=1; block(pcb); } else { cout<<'\n'; cout<<"The process no "< delete pcb; } } if(rand()%5==1) { insert(3); } if(rand()%7==1) wakeup(); } void proc_priority()//优先权调度算法模拟 { sort_queue(ready_queue); PCB *temp=0,*running=0; int times=0; cout<<"*调度前:"; ::print_init(ready_queue); for(;times<5;times++) { running=ready_queue->next; ready_queue->next =running->next ; cout< cout<<"*调度开始"< Run_priority(running); } cout<<"\n*本次调度结束。"< } void proc_loop()//轮转调度算法模拟 { PCB *temp=0,*running=0; int times=10; cout<<"*调度前:"; ::print_init(ready_queue); while(1) { running=ready_queue->next; ready_queue->next =running->next ; cout< if(times>0) { times=times-running->ALLtime;/*每次运行一个进程减去ALLtime;*/ if(times>=0) { Run_loop(running); } else if(_state) /*如果运行时被阻塞,则运行2个时间单位*/ { times=times+2; _state=0; cout<<"5487584574389574 fgfgfgfgf gfgfg38954378954375894378954375"; } else pushback_queue(block_queue,running);/*时间不过,则阻塞该进程,放到阻塞队列*/ } else if(times<=0) { cout<<"\n*本次调度时间片到!"; break; } } cout<<"\n*本次调度结束。"< } 六、实验过程原始记录(数据、图表、计算等) 运行截图: 七 、 实 验 结 果 、 分 析 和 结 论 (误差分析与数据处理、成果总结等。其中,绘制曲线图时必须用计算纸)此次实验是编写进程管理的算法,程序包括了创建、撤销、调度、阻塞、唤醒进程等功能,该程序使用C++语言。由于基础知识的不牢固以及没有对所学知识的即使复习,在做的过程中有很大的难度,因此,又对C++的一些运用进行了复习,重新看了一遍有关进程的相关知识,加深了对C++知识的运用以及进程知识的了解。 在此次程序中,我们主要运用的还是函数的调用以及队列的运用,因此,此次试验还运用了很多数据结构的知识,需充分的利用我们所学知识。在编写程序过程中,我们首先对变量进行初始化,然后建立进程函数、输出进程属性信息函数、输出所有PCB的初始值、生成进程属性信息,插入进程就绪队列、运行进程,随机阻塞进程、产生新进程,插入就绪队列,唤醒阻塞进程等等,然后对这些函数进行调用,我们才能编写出一个完整的程序,最后再对程序进行调试。在调试的过程中,出现了很多的错误,但都是一些常见的错误,因此通过软件的提醒都能够自己解决。此次程序包含的内容很多,是学习程序语言来很少遇到的一次挑战。但在程序的辨析过程中也学到了很多,不但把自己遗忘的进行了复习,而且还学到了新的知识,虽然不是把每个方面都理解透彻了,但是至少能够理解它的相关功能以及需要实现的目的。