采用时间片轮转算法调度程序.docx

1、采用时间片轮转算法调度程序采用时间片轮转算法调度程序 学号: 姓名: 专业: 指导教师: 日期: 一、需求分析 . 3 1、设计要求: . 3 2、解决方案: . 3 二、课程设计简介 . 4 1、课程设计题目. 4 2、课程设计目的. 4 3、课程设计内容. 4 4、时间安排 . 4 三、概要设计 . 4 1、基本原理 . 4 2、算法思想设计. 5 3、数据结构及模块说明: . 5 四、主要函数及其说明 . 6 五、调试分析 . 7 7 1、调试过程及步骤 .2、结果分析(以三个进程数为例) . 8 六、总结及参考文献 . 9 1、总结: . 9 2、参考文献 . 9 附录:程序源代码 .

2、 9 一、需求分析 1、设计要求: 在多道程序或多任务系统中，系统同时处于就绪状态的进程有若干个。为了使系统中各进程能有条不紊地进行，必须选择某种调度策略，以选择一进程占用处理机。要求用时间片轮转算法模拟单处理机调度，以巩固和加深处理机调度的概念。 2、解决方案: (1)、假设系统有5个进程，每个进程用一个进程控制块PCB来表示。PCB包括:进程名、链接指针、到达时间、估计运行时间和进程状态。其中，进程名即进程标识。链接指针指出下一个到达进程的进程控制块地址，按照进程到达的顺序排队，统设置一个队头和队尾指针分别指向第一个和最后一个进程，新生成的进程放队尾。估计运行时间:可由设计者任意指定一个时

3、间值。到达时间:进程创建时的系统时间或由用户指定，调度时，总是选择到达时间最早的进程。进程状态:为简单起见，假定进程有三种状态，就绪、等待和完成，并假定进程一创建就处于就绪状态，用R表示，当一个进程运行结束时，就将其置成完成状态，当一个进程未运行完成并且时间片不足时，就将其置成等待状态，用F表示。用W表示。 (2)、为每个进程任意确定一个要求运行时间和到达时间。 (3)、按照进程到达的先后顺序排成一个循环队列。再设一队首指针指向第一个到达进程的首址。 (4)、执行处理机调度时，开始选择队首的第一个进程运行。另外再设一个当前运行进程的指针，指向当前正运行进程。 (5)、由于本实验是模拟实验，所以

4、对被选中进程并不实际启动运行，而只是执行: a)、估计运行时间减时间片长度; b)、输出当前运行进程的名字。 用这两个操作来模拟进程的一次运行(即一个时间片)。 (6)、进程运行一次后，以后的调度则将当前指针依次下移一个位置，指向下一个进程，即调整当前运行指针指向该进程的链接指针所指进程，以指示应运行进程。同时还应判断该进程的剩余运行时间是否为零。若不为零，则等待下一轮的运行;若该进程的剩余运行时间为零，则将该进程的状态置为完成状态F，并退出循环队列插入完成队列。 (7)、若就绪队列不空，则重复上述(5)和(6)步骤直到所有进程都运行完为止。 (8)、在所有设计的调度程序中，应包含显示或打印语

5、句，以便显示或打印每次选中进程的名称及运行一次后队列的变化情况。 二、课程设计简介 1、课程设计题目 采用时间片轮转算法调度程序 2、课程设计目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 (1)进一步巩固和复习操作系统的基础知识。 (2)培养学生结构化程序、模块化程序设计的方法和能力。 (3)提高学生调试程序的技巧和软件设计的能力。 (4)提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 3、课程设计内容 (1)每一个进程有一个 PCB，其内容可以根据具体情况设定。 (2

6、)进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定。 (3)可读取样例数据(要求存放在外部文件中)进行进程数、进入内存时间、时间片长度、进程优先级的初始化。 (4)可以在运行中显示各进程的状态:就绪、执行(由于不要求设置互斥资源与进程间的同步关系，故只有两种状态) (5)采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列。 (6)有性能比较功能，可比较同一组数据在不同调度算法下的平均周转时间。 4、时间安排 1)分析设计贮备阶段(1 天) 2)编程调试阶段(7 天) 3)写课程设计报告、考核(2 天) 三、概要设计 1、基本原理 采用时间片轮转算

7、法的进程调度程序原理:系统将所有的输入进程按照先来先服务的原则进行排序并且保存在ready中。系统调用该算法时，由于输入进程不可能只有一个，故首先将ready中第一个数据赋值给执行队列run中，每执行一个时间片后都要判断未执行进程中是否有进程到达时间小于系统当前时间，若有则插入执行队列中。然后继续执行一个时间片，直至所有进程执行完毕。 2、算法思想设计 (1)按先来先服务算法将进程排成就绪队列ready (2)执行一个时间片后，系统时间加上时间片长度，进行必要判断。 (3)未执行队列中依次把到达时间与系统当前时间判断，若小于则表示已到，插入执行队列run中。 (4)判断当前执行队列是否已完成，

8、如果完成，则显示完成后，将执行队列中后面元素覆盖前面元素。如果没有，则重复(2)(3)和(4)，直至所有进程都执行完毕。 (5)判断是否继续调用别的算法，如果是则重新开始，否则结束。 3、数据结构和流程图: (1)数据结构 typedef struct node char name20; int round; int cputime; int arrivetime; int needtime; int RTime; char state; int count; struct node*next; PCB; (2)流程图 开始 结束 输入进程数 输入进程 将未完成的插入队尾 N Y 进程是否输入

9、完, 是否所有进程N 都完成 Y Y 输入时间N 片 时间片是否用分配给执行队完 列队首时间片 N 退出 时间片-1 是否完成 Y N 服务时间-1 是否有新进程到达 Y 将新到进程插入队尾 四、主要函数及其说明 typedef struct node char name20; /进程名int round; /时间片 int cputime; /cpu时间 int arrivetime;/到达时间 int needtime; /需要服务时间 char state; /运行状态 int count; /计数 struct node *next; PCB; void GetFirst() /*取得

10、第一个就绪队列节点*/ void Output() /*输出队列信息*/ void InsertTime(PCB *in) /*将进程插入到就绪队列尾部*/ void InsertFinish(PCB *in) /*将进程插入到完成队列尾部*/ */ void TimeCreate() /*时间片输入函数void RoundRun() /*时间片轮转调度算法*/ 五、调试分析 1、调试过程及步骤 打开VC+6.0软件，将cpp源文件拖入程序主体中，运行，进入时间片轮转算法主界面。然后输入进程个数，各个进程的名称、到达时间及运行时间，同时还要定义时间片的大小。样例中输入的进程数为2个，进程信息分

11、别如下: 之后再进行三个进程的测试: 2、结果分析(以三个进程数为例) 首先，输入进程数、时间片大小和各个进程的进程名、运行时间及到达时间的信息，进程按照到达时间从小到达顺序，即先运行进程a，其状态为R。 时刻为1时，b进程进入内存。 时刻为2时，时间片用完，由于进程b先进入内存，故b进程开始运行。 时刻为3时，c进程进入内存。 时刻为4时，时间片用完，开始执行c进程。 时刻为6时，时间片用完，a进程继续执行。 时刻为7时，a进程执行完毕，b进程开始执行。 时刻为9时，b进程执行完毕，c进程开始执行。 时刻为11时，时间片用完，内存中仅剩c进程，故继续执行。 时刻为12时，c进程执行完毕，所有

12、进程执行完毕。 六、总结及参考文献 1、总结: 在本次课程设计中，由于C语言和数据结构课程有一段时间并未使用，有些生疏，所以造成了知道时间片轮转算法的内容和基本原理，但是程序不会编的后果，于是将课本温习并且查找相关资料，最后请教老师和同学，终于完成程序的编写。 在这次课程设计是对学习操作系统的一次综合考察，锻炼我们综合分析问题、解决问题的能力。平时上机课都是把代码给我们了，最多要我们修改错误，而现在要我们自己编写有点困难，并且这次课程设计是用C语言编写，C已经有一段时间并未频繁使用，在试验过程中再次捧起C语言的课本和资料。在和同学的合作和自己努力下，终于把试验给搞定。因此，要感谢我的指导老师老

13、师、操作系统课程的任课老师还有我的同学。 对时间片轮转算法有了更深的了解:早期算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列。每次调度时，把CPU分配给队首进程，并令其执行一个时间片。其中，时间片的大小对系统性能有很大的影响;选择很小的时间片将有利于短作业，因为它能较快的完成，但会频繁地发生中断、进程上下文的切换，从而增加系统的开销;反之，时间片轮转算法则退化为FCFS算法，无法满足交互式用户的需求。 总的说来知识上的收获很是重要，精神上的丰收也是更加可喜的，让我知道了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰的后面还有更高的山峰在等着你。挫折是

14、一份财富，经历是一份拥有。这次课程设计必将成为我人生旅途上一个非常美好的回忆。 2、参考文献 操作系统宗大华，宗涛，陈吉人著北京:人民邮电出版社，2009 数据结构严蔚敏，吴伟民 著 清华大学出版社，2010 计算机操作系统(第三版) 汤小丹梁红兵等西安电子科技大学出版社 附录:程序源代码 #include #include #include typedef struct node char name20; int round; int cputime; int arrivetime; int needtime; char state; int count; struct node *next

15、; PCB; PCB *ready=NULL,*run=NULL,*finish=NULL; int num,i; void GetFirst(); void Output(); oid InsertTime(PCB *in); vvoid InsertFinish(PCB *in); void TimeCreate(); void RoundRun(); int main(void) printf(请输入要创建的进程数目:n); scanf(%d,&num); TimeCreate(); RoundRun(); Output(); void GetFirst() /*取得第一个就绪队列节点*

16、/ run = ready; if(ready!=NULL) run -state = R; ready = ready -next; run -next = NULL; void Output() /*输出队列信息*/ PCB *p; p = ready; printf(进程名tcpu时间t需要时间t进程状态t计数器n); while(p!=NULL) printf(%st%dt%dtt%ctt%dn,p-name,p-cputime,p-needtime,p-state,p-count); p = p-next; p = finish; while(p!=NULL) printf(%st%

17、dt%dtt%ctt%dn,p-name,p-cputime,p-needtime,p-state,p-count); p = p-next; p = run; while(p!=NULL) printf(%st%dt%dtt%ctt%dn,p-name,p-cputime,p-needtime,p-state,p-count); p = p-next; void InsertTime(PCB *in) /*将进程插入到就绪队列尾部*/ PCB *fst; fst = ready; if(ready = NULL) in-next = ready; ready = in; else while

18、(fst-next != NULL) fst = fst-next; in -next = fst -next; fst -next = in; void InsertFinish(PCB *in) /*将进程插入到完成队列尾部*/ PCB *fst; fst = finish; if(finish = NULL) in-next = finish; finish = in; else while(fst-next != NULL) next; fst = fst- in -next = fst -next; fst -next = in; void TimeCreate() /*时间片输入函

19、数*/ PCB *tmp; int i; printf(输入进程名字 到达时间 进程所需时间 时间片大小:n); for(i = 0;i name,&(tmp-arrivetime),&(tmp-needtime),&(tmp -round); getchar(); tmp -cputime = 0; tmp -state =W; / tmp-prio=0; tmp -count = 0; InsertTime(tmp); void RoundRun() /*时间片轮转调度算法*/ int flag = 1; GetFirst(); while(run != NULL) Output(); while(flag) cputime+ ; run-run-needtime-; run-count+; if(run-needtime = 0) run -state = F; InsertFinish(run); flag = 0; count = run-round) else if(run- run-state = W; run-count=0; InsertTime(run); flag = 0; flag = 1; GetFirst();