多级反馈队列.docx

《多级反馈队列.docx》由会员分享，可在线阅读，更多相关《多级反馈队列.docx（19页珍藏版）》请在三一办公上搜索。

1、山东理工大学计算机学院课程设计（操作系统）班级 姓名 学号 指导教师二。年六月二十四日课程设计任务书及成绩评定课题名称 基于多级反馈队列的进程管理系统的设计1、题目的目的和要求:巩固和加深对操作系统(OS)原理的理解，初步掌握操作系统组成模块 和应用接口的使用方法，提高进行工程设计和系统分析的能力；通过选做 上面的课题，实现OS最基本模块的管理功能，重点放在数据结构设计、文 档规范化和程序设计风格。口、设计进度及完成情况日期内容6.13-6.15选取参考书，查阅有关文献资料，完成课程设计说明 书内容1部分。完成课程设计说明书内容2-4部分6.166.20创建相关数据结构，录入源程序6.216.

2、22调试程序并记录调试中的问题，完成课程设计说明书 第5部分。6.23系统测试，演示设计成果，考核成绩。6.24整理课程设计说明书，上午11时，由学习委员交课 程设计说明书(计算机科学系9#213或直接交给指导 教师)虬主要参考文献及资料1 汤子赢等.计算机操作系统（第二版）.西安电子科技大学出版社，2006.82 冯耀霖等.操作系统，西安电子科技大学出版社.19923 张尧学等.计算机操作系统教程（第2版）.清华大学出版社,2001.44 谭耀铭.操作系统.中国人民大学出版社,2003.45 Abraham Silberschatz,Peter Galvin & Greg Gagne,App

3、lied Operating System Concepts,Higher Education Press,2002M成绩评定：设计成绩：（教师填写）指导老师：（签字）二。年六月二十四日第一章概述1第二章系统分析2第三章 系统设计3第四章程序设计流程图或N-S图4第五章调试过程中的问题及系统测试情况5第六章结束语6附录7第_章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可 以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程 设计是让同学对所学的课程更全面的学习和应用，理解和掌握课程的相关 知识。计算机操作系统一门重要的专业课，是开发操作系统和软件系 统的理论和应

4、用基础。第二章系统分析很多进程调度方法都有一定的局限性，如短进程优先的调度法，仅照 顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则段进程优 先和基于进程长度的抢占调度算法，都将无法使用，而多级反馈队列调度 算法，则不必事先知道各种进程所需的时间，而且还可以满足各种类型进 程的需要，因而它是目前被公认为的一种较好的进程调度算法。在米用多 级反馈队列调度算法的系统中，调度算法的实施过程如下：（1）应设置多个就绪队列，并为各个队列赋予不同的优先级，第一个 队列的优先级是最高，第二个队列次之，其余各队列的优先权逐个降低， 该算法赋予各个队列中进程执行时间片，例如，第二个队列的时间片要不 第一

5、个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列 的时间片长一倍。（2）当一个新进程进入内存后，首先将它放入第一队列的结尾，按 FCFS原则排队等待调度，当论到该进程执行时，如它能在该时间片后内 完成，便可准备撤离系统，如果它在一个时间片结束尚未完成，调度程序 便将该进程转入第二个队列的结尾，再同样地按FCFS原则等待调度执行； 如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三个 队列，如此下去，当第一长作业（进程）从第一队列依次降到第n 队列后，在第n队列中便采用取按时间片轮转的方式运行。（3）仅当第一个队列空闲时，调度程序才调度第二个队列中的进程运 行，仅当第1（i

6、-1）队列均空闲时，才会调度第I个队列中为某进程服务 时，又有新进程进入优先权比较高的队列（第1（i-1）中的任何一个队列）， 则此时新进程将 抢占在运行进程的处理机，即由调度程序把在运行的进程 放回到第I队列的结尾，把处理机分配给新到的高有限权进程。第三章系统设计实现多级反馈队列的模拟。当一个新进程进入内存后，首先将它放入 第一队列的结尾，按FCFS原则排队等待调度，当论到该进程执行时，如 它能在该时间片后内完成，便可准备撤离系统，如果它在一个时间片结束 尚未完成，调度程序便将该进程转入第二个队列的结尾，再同样地按FCFS 原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再 依

7、次将它放入第三个队列，如此下去，当第一长作业（进程）从第 一队列依次降到第n队列后，在第n队列中便采用取按时间片轮转的方式 运行。仅当第一个队列空闲时，调度程序才调度第二个队列中的进程运行， 仅当第1（i-1）队列均空闲时，才会调度第I个队列中为某进程服务时， 又有新进程进入优先权比较高的队列（第1（i-1）中的任何一个队列）， 则此时新进程将 抢占在运行进程的处理机，即由调度程序把在运行的进程 放回到第I队列的结尾，把处理机分配给新到的高有限权进程。就绪队列1S1+-就绪队列2S户就绪队列3 S 3 就绪队列nA至CPU至CPU至CPU至CPU（时间片：s s s） 12-3 -用VB模拟的

8、时候，可以用list来显示进程。第四章程序设计流程图或N-S多级反馈轮转调度算法（抢占式）页面1第五章调试过程中的问题及系统测试情况本系统主要可视的模拟了多级反馈队列的工作过程，多级反馈队列的 工作过程如下：便五就绪队列的个数:扁入每个就绪队列的啊时间片;24入进程的个数M进程名字和进程所需时间：a15 b 4 e812派程名优先级轮数cpu时间需要时间进程状态计数翡b46204USe4429&U0147283U6s4220SWeF382012WeJ4123WBh342816Wsi332017Usa352015Rs第六章结束语这次操作系统课程设计，在编写过程中，遇到很多难题，特别是在操 作系统

9、实验中不曾注意到的问题，也有许多新的问题，在实际反复调试运 行中，不断加深了对操作系统的理解，也很大地程度上提高了编程的能力， 由于对重要概念的把握程度还不够深入，在实际理解编写时遇到很多不该 发生的问题。不过，都很好的解决并牢牢地掌握住了。通过做多级目录文 件系统，我知道了多级目录文件系统的工作原理，在打开文件时系统是如 何进行操作的，并加深了理解。希望在以后的学习中，继续保持这份昂扬 的斗志，继续努力学习计算机方面的知识，永不懈怠。通过这次课程设计，不仅让我了解了多级反馈队列的进程管理系统， 更重要的还让我学会了、或者说是验证了“做事一定要有次序和对事物的 总体把握”这句话。这次操作系统实

10、习，不仅让我对操作系统这门课程有 了更深入的研究、对很多重要的概念有了巩固和掌握，还给了我今后做事 的启示。做事要塌实，不能想着一步登天，要有计划，有目的的进行做事。 盲目真的不应该再在我们新一代的大学生身上出现了，我们应该认真找到 自己的缺点并且及时改正。在这里，我感谢老师的教导。“活到老，学到 老”，这也是我整个学习过程中的一次经验、一次总结，我相信它肯定会 给我今后的学习有所启示和指导作用。附录：源代码#include #include #include typedef struct node/*进程节点信息*/(char name20;/*进程的名字*/int prio;/*进程的优先

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

12、 /*指向下一个就绪队列的链表指针*/ReadyQueue;PCB *run=NULL,*finish=NULL; /*定义三个队列，就绪队列，执行队列和完成队列*/ReadyQueue *Head = NULL; /*定义第一个就绪队列*/int num; /*进程个数*/int ReadyNum; /*就绪队列个数*/void Output();/*进程信息输出函数*/void InsertFinish(PCB *in);/*将进程插入到完成队列尾部*/void InsertPrio(ReadyQueue *in);/*创建就绪队列，规定优先数越小，优先级越低*/void PrioCrea

13、te();/*创建就绪队列输入函数*/void GetFirst(ReadyQueue *queue);/*取得某一个就绪队列中的队头进程*/void InsertLast(PCB *in,ReadyQueue *queue);/*将进程插入到就绪队列尾部*/void ProcessCreate();/* 进程创建函数*/void RoundRun(ReadyQueue *timechip);/*时间片轮转调度算法*/void MultiDispatch();/*多级调度算法，每次执行一个时间片*/int main(void)(PrioCreate(); /*创建就绪队列*/ProcessCr

14、eate();/*创建就绪进程队列*/MultiDispatch();/* 算法开始*/Output(); /*输出最终的调度序列*/return 0;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-prio,p-round,p-cputi

15、me,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-prio,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-prio,p-round,p-cputime,p-needtime,p-state,p-count)

16、;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 InsertPrio(ReadyQueue *in) /*创建就绪队列，规定优先数越小，优先级越低*/(ReadyQueue *fst,*nxt;fst = nxt = Head;

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

18、xt;fst -next = in;else /*插入到队列中*/(nxt = in;in -next = fst;void PrioCreate() /*创建就绪队列输入函数*/(ReadyQueue *tmp;int i;printf(输入就绪队列的个数：n);scanf(d，&ReadyNum);printf(输入每个就绪队列的CPU时间片：n);for(i = 0;i round); /*输入此就绪队列中给每个进程所分配的CPU时间片*/tmp -prio = 50 - tmp-round; /*设置其优先级，时间片越高，其优先级越低*/tmp -LinkPCB = NULL;/*初始

19、化其连接的进程队列为空*/tmp -next = NULL;InsertPrio(tmp);/*按照优先级从高到低，建立多个就绪队列*/void GetFirst(ReadyQueue *queue) /*取得某一个就绪队列中的队头进程*/ (run = queue -LinkPCB;if(queue -LinkPCB != NULL)(run -state = R;queue -LinkPCB = queue -LinkPCB -next;run -next = NULL;void InsertLast(PCB *in,ReadyQueue *queue) /*将进程插入到就绪队列尾部*/

20、(PCB *fst;fst = queue-LinkPCB;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 ProcessCreate() /*进程创建函数*/(PCB *tmp;int i;printf(输入进程的个数：n);scanf(d,&num);printf(输入进程名字和进程所需时间：n);for(i = 0;i name);

21、getchar();/*吸收回车符号*/scanf(d，&(tmp-needtime);tmp -cputime = 0;tmp -state =W;tmp -prio = 50 - tmp-needtime; /*设置其优先级，需要的时间越多，优先级越 低*/tmp -round = Head -round;tmp -count = 0;InsertLast(tmp,Head);/*按照优先级从高到低，插入到就绪队列*/void RoundRun(ReadyQueue *timechip)/*时间片轮转调度算法*/(int flag = 1;GetFirst(timechip);while(

22、run != NULL)(while(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 = 1;GetFirst(timechip);void Multi

23、Dispatch()/*多级调度算法，每次执行一个时间片*/(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) /*进程执行完毕*/(run -state = F;InsertFinish(run);flag = 0;else if(run

24、-count = run-round)/* 时间片用完*/(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;+k;if(k = 3)(ProcessCreate();flag = 1;if(point -LinkPCB = NULL)/* 就绪队列指针下移*/ point =point-next;if(point -next =NULL)(RoundRun(point);break;GetFirst(point);