实验一 进程管理 昆工版

1、昆明理工大学信息工程与自动化学院学生实验报告（ 2013 2014 学年 第二学期 ）课程名称：操作系统 开课实验室：信自楼444 2014 年3月25日年级、专业、班计科122班学号201210405204姓名邹华宇成绩实验项目名称进程管理指导教师杨云飞教师评语教师签名： 年 月 日 一、实验目的通过编写进程管理的算法，要求学生掌握整个进程管理的各个环节，进程的数据结构描述，进程的各种状态之间的转换，以及进程的调度算法。以加深对进程的概念及进程调度算法的理解，并且提高链表的应用能力，达到提高编程能力的目的。二、实验原理及基本技术路线图（方框原理图）用C语言或C+语言开发。需要定义PCB的数据

2、结构，用链表的形式管理进程，采用多级反馈队列调度的算法模拟进程的控制。要求有创建、撤销、调度、阻塞、唤醒进程等功能。事件发生剥夺处理机调度选中等待终止创建创建就绪运行结束等待事件进程的状态转换图：各原语句的功能说明：进程创建原语：进程创建是调用创建原语来实现。创建原语扫描系统的PCB链表，在找到一定PCB链表之后，填入调用者提供的有关参数（这些参数包括：进程名、进程优先级P0、进程正文段起始地址d0、资源清单R0等），最后形成代表进程的PCB结构。进程撤销（终止）：撤消原语首先检查PCB进程链或进程家族，寻找所要撤消的进程是否存在。如果找到了所要撤消的进程的PCB结构，则撤消原语释放该进程所占

3、有的资源之后，把对应的PCB结构从进程链或进程家族中摘下并返回给PCB空队列。如果被撤消的进程有自己的子进程，则撤消原语先撤消其子进程的PCB结构并释放子进程所 占用的资源之后，再撤消当前进程的PCB结构和释放其资源。阻塞原语：当发生引起阻塞的事件时，该原语被该进程自己调用来阻塞自己。阻塞原语在阻塞一个进程时，由于该进程正处于执行状态，故应先中断处理机和保存该进程的CPU现场。然后将被阻塞进程置“阻塞”状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行。唤醒原语：当等待队列中的进程所等待的事件发生时，等待该事件的所有进程都将被唤醒。一个处于阻塞状态的进程不可能自己唤醒自己。唤醒一个

4、进程有两种方法：一种是由系统进程唤醒。另一种是由事件发生进程唤醒。当由系统进程唤醒等待进程时，系统进程统一控制事件的发生并将“事件发生”这一消息通知等待进程。从而使得该进程因等待事件已发生而进入就绪队列。等待进程也可由事件发生进唤醒。由事件发生进程唤醒时，事件发生进程和被唤醒进程之间是合作关系。因此，唤醒原语既可被系统进程调用，也可被事件发生进程调用。我们称调用唤醒原语的进程为唤醒进程。多级反馈队列调度算法的描述：多级队列调度算法也称多级反馈队列调度算法，它是时间片调度算法与优先数调度算法的结合。实行这种调度算法时，系统中将维持多个就绪队列，每个就绪队列具有不同的调度级别，可以获得不同长度的时

5、间片。例如，系统维持N个就绪队列，第1级就绪队列中进程的调度级别最高，可获得的时间片最短，第N级就绪队列中进程的调度级别最低，可获得的时间片最长。具体的调度方法是：创建一个新进程时，它的PCB将进入第1级就绪队列的末尾。对于在第1级到第N-1级队列中的进程，如果在分配给它的时间片内完成了全部工作，那么就撤离系统；如果在时间片没有用完时提出了输入/输出请求或要等待某事件发生，那么就进入相应的阻塞队列里等待。在所等待的事件出现时，仍回到原队列末尾，参与下一轮调度（也就是每个队列实行先来先服务调度算法）；如果用完了时间片还没有完成自己的工作，那么只能放弃对CPU的使用，降到低一级队列的末尾，参与那个

6、队列的调度。对位于最后一个队列里的进程，实行时间片轮转调度算法。整个系统最先调度1级就绪队列；只有在上一级就绪队列为空时，才去下一级队列调度。当比运行进程更高级别的队列中到达一个进程（可以肯定，在此之前比运行进程级别高的所有队列全为空）时，系统将立即停止当前运行进程的运行，让它回到自己队列的末尾，转去运行级别高的那个进程。流程图：进程调度处理机空转从就绪队列取下一进程正确取得就绪进程执行进程的时间片减1释放处理机放完成队列释放处理机放等待队列处理资源请求进程优先级减1进程优先级减1放入就绪队列让处理机NNNNNYYYYYY正确取得就绪进程N进程结束是否有更高优先级进程时间片用完数据结构定义：c

7、har name20;/*进程的名字*/ int supernumber;/*进程的优先级*/ int round;/*分配CPU的时间片*/ int cputime;/*CPU执行时间*/ int needtime;/*进程执行所需要的时间*/ char state;/*进程的状态，W就绪态，R执行态，F完成态*/ int count;/*记录执行的次数*/ struct node *next;/*链表指针*/主要变量的说明：PCB *run=NULL,*finish=NULL; /*定义三个队列，就绪队列，执行队列和完成队列*/ ReadyQueue *Head = NULL;/*定义第一

8、个就绪队列*/ int num;/*进程个数*/ int ReadyNum;/*就绪队列个数*/ 函数的说明：void Output();/*进程信息输出函数*/ void InsertFinish(PCB *in);/*将进程插入到完成队列尾部*/ void Insertsupernumber(ReadyQueue *in);/*创建就绪队列，规定优先数越小，优先级越低*/ void supernumberCreate();/*创建就绪队列输入函数*/ void GetFirst(ReadyQueue *queue);/*取得某一个就绪队列中的队头进程*/ void InsertLast(P

9、CB *in,ReadyQueue *queue);/*将进程插入到就绪队列尾部*/ void ProcessCreate();/*进程创建函数*/ void RoundRun(ReadyQueue *timechip);/*时间片轮转调度算法*/ void MultiDispatch();/*多级调度算法，每次执行一个时间片*/三、所用仪器、材料（设备名称、型号、规格等）。计算机一台四、实验方法、步骤# include <stdio.h># include <stdlib.h># include <math.h># include <string.h

10、>typedef struct node/*进程节点信息*/ char name20;/*进程的名字*/ int supernumber;/*进程的优先级*/ int round;/*分配CPU的时间片*/ int cputime;/*CPU执行时间*/ int needtime;/*进程执行所需要的时间*/ char state;/*进程的状态，W就绪态，R执行态，F完成态*/ int count;/*记录执行的次数*/ struct node *next;/*链表指针*/ PCB; typedef struct Queue/*多级就绪队列节点信息*/ PCB *LinkPCB;/*就

11、绪队列中的进程队列指针*/ int supernumber;/*本就绪队列的优先级*/ int round;/*本就绪队列所分配的时间片*/ struct Queue *next;/*指向下一个就绪队列的链表指针*/ ReadyQueue;PCB *run=NULL,*finish=NULL;/*定义三个队列，就绪队列，执行队列和完成队列*/ ReadyQueue *Head = NULL;/*定义第一个就绪队列*/ int num;/*进程个数*/ int ReadyNum;/*就绪队列个数*/ void Output();/*进程信息输出函数*/ void InsertFinish(PCB

12、 *in);/*将进程插入到完成队列尾部*/ void Insertsupernumber(ReadyQueue *in);/*创建就绪队列，规定优先数越小，优先级越低*/ void supernumberCreate();/*创建就绪队列输入函数*/ void GetFirst(ReadyQueue *queue);/*取得某一个就绪队列中的队头进程*/ void InsertLast(PCB *in,ReadyQueue *queue);/*将进程插入到就绪队列尾部*/ void ProcessCreate();/*进程创建函数*/ void RoundRun(ReadyQueue *ti

13、mechip);/*时间片轮转调度算法*/ void MultiDispatch();/*多级调度算法，每次执行一个时间片*/ void Output()/*进程信息输出函数*/ ReadyQueue *print = Head;PCB *p;printf("进程名t优先级t轮数tcpu时间t需要时间t进程状态t计数器n");while(print)if(print ->LinkPCB != NULL)p=print ->LinkPCB;while(p)printf("%st%dt%dt%dt%dtt%ctt%dn",p->name,p

14、->supernumber,p->round,p->cputime,p->needtime,p->state,p->count);p = p->next;print = print->next;p = finish;while(p!=NULL)printf("%st%dt%dt%dt%dtt%ctt%dn",p->name,p->supernumber,p->round,p->cputime,p->needtime,p->state,p->count);p = p->next;p

15、 = run;while(p!=NULL)printf("%st%dt%dt%dt%dtt%ctt%dn",p->name,p->supernumber,p->round,p->cputime,p->needtime,p->state,p->count); p = p->next; void InsertFinish(PCB *in)/*将进程插入到完成队列尾部*/ PCB *fst;fst = finish;if(finish = NULL)in->next = finish;finish = in;elsewhile

16、(fst->next != NULL)fst = fst->next;in ->next = fst ->next;fst ->next = in;void Insertsupernumber(ReadyQueue *in)/*创建就绪队列，规定优先数越小，优先级越低*/ ReadyQueue *fst,*nxt;fst = nxt = Head;if(Head = NULL)/*如果没有队列，则为第一个元素*/ in->next = Head;Head = in;else/*查到合适的位置进行插入*/ if(in ->supernumber >

17、= fst ->supernumber)/*比第一个还要大，则插入到队头*/ in->next = Head;Head = in;elsewhile(fst->next != NULL)/*移动指针查找第一个别它小的元素的位置进行插入*/ nxt = fst;fst = fst->next;if(fst ->next = NULL)/*已经搜索到队尾，则其优先级数最小，将其插入到队尾即可*/ in ->next = fst ->next;fst ->next = in;else/*插入到队列中*/ nxt = in;in ->next =

18、fst;void supernumberCreate()/*创建就绪队列输入函数*/ ReadyQueue *tmp;int i;static int j=0;printf("输入就绪队列的个数：n");scanf("%d",&ReadyNum);printf("每个就绪队列的CPU时间片：(优先级和时间片成反比)n");for(i = 0;i <ReadyNum; i+)if(tmp = (ReadyQueue *)malloc(sizeof(ReadyQueue)=NULL)perror("malloc&q

19、uot;);exit(1);tmp->round=int(pow(2.0,(+j);/*输入此就绪队列中给每个进程所分配的CPU时间片*/ printf("%d n",tmp->round);tmp ->supernumber = 50 - tmp->round;/*设置其优先级，时间片越高，其优先级越低*/ tmp ->LinkPCB = NULL;/*初始化其连接的进程队列为空*/ tmp ->next = NULL;Insertsupernumber(tmp);/*按照优先级从高到低，建立多个就绪队列*/ void GetFirst

20、(ReadyQueue *queue)/*取得某一个就绪队列中的队头进程*/ run = queue ->LinkPCB;if(queue ->LinkPCB != NULL)run ->state = 'R'queue ->LinkPCB = queue ->LinkPCB ->next;run ->next = NULL;void ProcessCreate()/*进程创建函数*/ PCB *tmp;int i;static int j=1;printf("输入进程的个数：n");scanf("%d&q

21、uot;,&num); for(i = 0;i < num; i+)if(tmp = (PCB *)malloc(sizeof(PCB)=NULL)perror("malloc");exit(1);printf("输入%d进程名字：n",j);scanf("%s",tmp->name);getchar();printf("输入%d进程时间：n",j+);/*吸收回车符号*/ scanf("%d",&(tmp->needtime);tmp ->cputime

22、 = 0;tmp ->state ='W'tmp ->supernumber = 50 - tmp->needtime;/*设置其优先级，需要的时间越多，优先级越低*/ tmp ->round = Head ->round;tmp ->count = 0;InsertLast(tmp,Head);/*按照优先级从高到低，插入到就绪队列*/ system("cls");void InsertLast(PCB *in,ReadyQueue *queue)/*将进程插入到就绪队列尾部*/ PCB *fst;fst = queue

23、->LinkPCB;if( queue->LinkPCB = NULL)in->next = queue->LinkPCB;queue->LinkPCB = in;elsewhile(fst->next != NULL)fst = fst->next;in ->next = fst ->next;fst ->next = in; void RoundRun(ReadyQueue *timechip)/*时间片轮转调度算法*/ int flag = 1;GetFirst(timechip);while(run != NULL)while

24、(flag)run->count+;run->cputime+;run->needtime-;if(run->needtime = 0)/*进程执行完毕*/ run ->state = 'F'InsertFinish(run);flag = 0;else if(run->count = timechip ->round)/*时间片用完*/ run->state = 'W'run->count = 0;/*计数器清零，为下次做准备*/ InsertLast(run,timechip);flag = 0;flag

25、 = 1;GetFirst(timechip);void MultiDispatch()/*多级调度算法，每次执行一个时间片*/ int flag = 1;int k = 0;ReadyQueue *point;point = Head;GetFirst(point);while(run != NULL)Output();if(Head ->LinkPCB!=NULL)point = Head;while(flag)run->count+;run->cputime+;run->needtime-;if(run->needtime = 0)/*进程执行完毕*/ ru

26、n ->state = 'F'InsertFinish(run);flag = 0;else if(run->count = run->round)/*时间片用完*/ run->state = 'W'run->count = 0;/*计数器清零，为下次做准备*/ if(point ->next!=NULL)run ->round = point->next ->round;/*设置其时间片是下一个就绪队列的时间片*/ InsertLast(run,point->next);/*将进程插入到下一个就绪队列中*/ flag