昆明理工大学进程管理组织实验报告.doc

《昆明理工大学进程管理组织实验报告.doc》由会员分享，可在线阅读，更多相关《昆明理工大学进程管理组织实验报告.doc（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、,昆明理工大学信息工程与自动化学院学生实验报告（ 2010 2011 学年 第 二 学期 ）课程名称：操作系统 开课实验室： 年 月 日年级、专业、班学号姓名成绩实验项目名称进程管理指导教师杨云飞教师评语 教师签名： 年 月 日目录一、实验目的1二、实验原理及基本技术路线图21.进程的状态转换图22.各原语的功能说明23.多级反馈队列调度算法的描述34.程序功能结构图45.流程图46.数据结构定义57.主要变量的说明68.函数的说明6四、实验方法、步骤6五、实验过程原始记录18六、实验结果、分析和结论21一、 实验目的通过编写进程管理的算法，要求学生掌握整个进程管理的各个环节，进程的数据结构描

2、述，进程的各种状态之间的转换，以及进程的调度算法。以加深对进程的概念及进程调度算法的理解，并且提高链表的应用能力，达到提高编程能力的目的。二、 实验原理及基本技术路线图（方框原理图）用C语言或C+语言开发。需要定义PCB的数据结构，用链表的形式管理进程，采用多级反馈队列调度的算法模拟进程的控制。要求有创建、撤销、调度、阻塞、唤醒进程等功能。1. 进程的状态转换图：2. 各原语的功能说明: -进程创建原语：进程创建是调用创建原语来实现。创建原语扫描系统的PCB链表，在找到一定PCB 链表之后，填入调用者提供的有关参数（这些参数包括：进程名、进程优先级P0、进程正文段起始地址d0、资源清单R0等）

3、，最后形成代表进程的PCB结构。 -进程撤销（终止）: 撤消原语首先检查PCB进程链或进程家族，寻找所要撤消的进程是否存在。 如果找到了所要撤消的进程的PCB结构，则撤消原语释放该进程所占有的资源之后，把 对应的PCB结构从进程链或进程家族中摘下并返回给PCB空队列。如果被撤消的进程有自己的子进程，则撤消原语先撤消其子进程的PCB结构并释放子进程所 占用的资源之后，再撤消当前进程的PCB结构和释放其资源。 -阻塞原语：当发生引起阻塞的事件时，该原语被该进程自己调用来阻塞自己。阻塞原语在阻塞一 个进程时，由于该进程正处于执行状态，故应先中断处理机和保存该进程的CPU现场。然后将被阻塞进程置“阻塞

4、”状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行。 -唤醒原语：当等待队列中的进程所等待的事件发生时，等待该事件的所有进程都将被唤醒。一个 处于阻塞状态的进程不可能自己唤醒自己。唤醒一个进程有两种方法：一种是由系统进程唤醒。另一种是由事件发生进程唤醒。当由系统进程唤醒等待进程时，系统进程统一控制事件的发生并将“事件发生”这一消息通知等待进程。从而使得该进程因等待事件已发生而进入就绪队列。等待进程也可由事件发生进唤醒。由事件发生进程唤醒时，事件发生进程和被唤醒进程之间是合作关系。因此，唤醒原语既可被系统进程调用，也可被事件发生进程调用。我们称调用唤醒原语的进程为唤醒进程。3. 多

5、级反馈队列调度算法的描述：(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。 第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍。 图 3-5 是多级反馈队列算法的示意。 (2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度

6、程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。 (3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行； 仅当第1(i-1) 队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。

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

8、队列和完成队列*/ ReadyQueue *Head = NULL; /*定义第一个就绪队列*/ int num; /*进程个数*/ int ReadyNum; /*就绪队列个数*/ 8. 函数的说明：void Output(); /*进程信息输出函数*/ void InsertFinish(PCB *in); /*将进程插入到完成队列尾部*/ void Insertsupernumber(ReadyQueue *in); /*创建就绪队列，规定优先数越小，优先级越低*/ void supernumberCreate(); /*创建就绪队列输入函数*/ void GetFirst(ReadyQ

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

10、e 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 *Lin

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

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

13、 RoundRun(ReadyQueue *timechip); /*时间片轮转调度算法*/ 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-s

14、upernumber,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 = run; while(p!=NULL) printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-supernum

15、ber,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; else while(fst-next != NULL) fst = fst-next; in -next = fst -next; fst -next = in; void Insertsupernumber(ReadyQueue *in

16、) /*创建就绪队列，规定优先数越小，优先级越低*/ ReadyQueue *fst,*nxt; fst = nxt = Head; if(Head = NULL) /*如果没有队列，则为第一个元素*/ in-next = Head; Head = in; else /*查到合适的位置进行插入*/ if(in -supernumber = fst -supernumber) /*比第一个还要大，则插入到队头*/ in-next = Head; Head = in; else while(fst-next != NULL) /*移动指针查找第一个别它小的元素的位置进行插入*/ nxt = fst

17、; fst = fst-next; if(fst -next = NULL) /*已经搜索到队尾，则其优先级数最小，将其插入到队尾即可*/ in -next = fst -next; fst -next = in; else /*插入到队列中*/ nxt = in; in -next = fst; void supernumberCreate() /*创建就绪队列输入函数*/ ReadyQueue *tmp; int i;static int j=0; printf(输入就绪队列的个数：n); scanf(%d,&ReadyNum); printf(每个就绪队列的CPU时间片：(优先级和时间片

18、成反比)n); for(i = 0;i 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(ReadyQueue *queue) /*取得某一个就绪

19、队列中的队头进程*/ 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,&num); for(i = 0;i name); getchar(); printf(输入%d进程时间：n,j+);/*吸收回车符号*/ scanf

20、(%d,&(tmp-needtime); tmp -cputime = 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-Li

21、nkPCB; if( queue-LinkPCB = NULL) in-next = queue-LinkPCB; queue-LinkPCB = in; else while(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(flag) run-count+; run-cputime+

22、; 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 = 1; GetFirst(timechip); void MultiDispatch() /*多级调度算法，每次执行一个时间片*/ int f

23、lag = 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) /*进程执行完毕*/ run -state = F; InsertFinish(run); flag = 0; else if(run-count = run-round)/*时

24、间片用完*/ run-state = W; run-count = 0; /*计数器清零，为下次做准备*/ if(point -next!=NULL) run -round = point-next -round;/*设置其时间片是下一个就绪队列的时间片*/ InsertLast(run,point-next); /*将进程插入到下一个就绪队列中*/ flag = 0; else RoundRun(point); /*如果为最后一个就绪队列就调用时间片轮转算法*/ break; flag = 1; if(point -LinkPCB = NULL)/*就绪队列指针下移*/ point =poi

25、nt-next; if(point -next =NULL) RoundRun(point); break; GetFirst(point); int main( ) printf(tttt进程管理n);supernumberCreate(); /*创建就绪队列*/ ProcessCreate();/*创建就绪进程队列*/ printf(tttt进程调度n);for(int i=0;i80;i+) printf(*);printf(n);MultiDispatch();/*算法开始*/ Output(); /*输出最终的调度序列*/ return 0; 五、 实验过程原始记录(数据、图表、计算

26、等)六、 实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸）很多进程调度方法都有一定的局限性，如短进程优先的调度法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则段进程优先和基于进程长度的抢占调度算法，都将无法使用，而多级反馈队列调度算法，则不必事先知道各种进程所需的时间，而且还可以满足各种类型进程的需要，因而它是目前被公认为的一种较好的进程调度算法。同时通过编写进程管理的算法，我大体掌握整个进程管理的各个环节，基本描述进程的数据结构，进程的各种状态之间的转换，以及进程的调度算法。加深了对进程的概念及进程调度算法的理解，并且提高链表的应用能力，达到提高编程能力的目的在制作这个程序时，对于链表知识的欠缺是一个十分大的阻碍，在参照数据结构的同时我完成了这个实验，对我而言这是一个突破。同时也加深我对程序编写的兴趣。