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

1、采用时间片轮转算法调度程序学 号：姓 名：专 业：指导教师:日 期：目录一、需求分析31、设计要求：32、解决方案：3二、课程设计简介 41、课程设计题目42、课程设计目的43、课程设计内容44、时间安排4三、概要设计41、基本原理42、算法思想设计 53、数据结构及模块说明： 5四、主要函数及其说明6五、调试分析71、调试过程及步骤72、结果分析（以三个进程数为例） 8六、总结及参考文献 91、总结： 92、参考文献9附录：程序源代码9、需求分析1、设计要求：在多道程序或多任务系统中，系统同时处于就绪状态的进程有若十个。为了使系 统中各进程能有条不紊地进行，必须选择某种调度策略，以选择一进程

2、占用处理 机。要求用时间片轮转算法模拟单处理机调度，以巩固和加深处理机调度的概念。2、解决方案：(1) 、假设系统有5个进程，每个进程用一个进程控制块 PCB来表示。PCB包 括：进程名、链接指针、到达时间、估计运行时间和进程状态。其中，进程名即 进程标识。链接指针指出下一个到达进程的进程控制块地址，按照进程到达的顺 序排队，统设置一个队头和队尾指针分别指向第一个和最后一个进程，新生成的进程放队尾。估计运行时间：可由设计者任意指定一个时间值。到达时间：进程 创建时的系统时间或由用户指定，调度时，总是选择到达时间最早的进程。进程 状态：为简单起见，假定进程有三种状态，就绪、等待和完成，并假定进程

3、一创 建就处于就绪状态，用R表示，当一个进程运行结束时，就将其置成完成状态， 用F表示。当一个进程未运行完成并且时间片不足时，就将其置成等待状态， 用W表小。(2) 、为每个进程任意确定一个要求运行时间和到达时间。(3) 、按照进程到达的先后顺序排成一个循环队列。再设一队首指针指向第一 个到达进程的首址。(4) 、执行处理机调度时，开始选择队首的第一个进程运行。另外再设一个当 前运行进程的指针，指向当前正运行进程。(5) 、由于本实验是模拟实验，所以对被选中进程并不实际启动运行，而只是 执行：a)、估计运行时间减时间片长度；b)、输出当前运行进程的名字。 用 这两个操作来模拟进程的一次运行(即

4、一个时间片)。(6) 、进程运行一次后，以后的调度则将当前指针依次下移一个位置，指向下一个进程，即调整当前运行指针指向该进程的链接指针所指进程，以指示应运行进程。同时还应判断该进程的剩余运行时间是否为零。 若不为零，则等待下一轮 的运行；若该进程的剩余运行时间为零，则将该进程的状态置为完成状态F,并退出循环队列插入完成队列。、若就绪队列不空，则重复上述(5)和(6)步骤直到所有进程都运行完 为止。(8)、在所有设计的调度程序中，应包含显示或打印语句，以便显示或打印每 次选中进程的名称及运行一次后队列的变化情况。二、课程设计简介1、课程设计题目采用时间片轮转算法调度程序2、课程设计目的操作系统课

5、程设计是计算机专业重要的教学环节，它为学生提供了一个既动手 乂动脑，将课本上的理论知识和实际有机的结合起来， 独立分析和解决实际问题 的机会。(1) 进一步巩固和复习操作系统的基础知识。(2) 培养学生结构化程序、模块化程序设计的方法和能力。(3) 提高学生调试程序的技巧和软件设计的能力。(4) 提高学生分析问题、解决问题以及综合利用 C语言进行程序设计的能力。3、课程设计内容(1) 每一个进程有一个 PCB其内容可以根据具体情况设定。(2) 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定。(3) 可读取样例数据(要求存放在外部文件中)进行进程数、进入内存时间、 时间片长度、进

6、程优先级的初始化。(4) 可以在运行中显示各进程的状态：就绪、执行(由于不要求设置互斥资源 与进程间的同步关系，故只有两种状态)(5) 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状 态以及相应的阻塞队列。(6) 有性能比较功能，可比较同一组数据在不同调度算法下的平均周转时间4、时间安排1) 分析设计贮备阶段(1天)2) 编程调试阶段(7天)3) 写课程设计报告、考核(2天)三、概要设计1、基本原理采用时间片轮转算法的进程调度程序原理：系统将所有的输入进程按照先来 先服务的原则进行排序并且保存在ready中。系统调用该算法时,由于输入进程 不可能只有一个，故首先将ready中

7、第一个数据赋值给执行队列run中，每执行 一个时间片后都要判断未执行进程中是否有进程到达时间小于系统当前时间， 若 有则插入执行队列中。然后继续执行一个时间片，直至所有进程执行完毕。2、算法思想设计(1) 按先来先服务算法将进程排成就绪队列ready(2) 执行一个时间片后，系统时间加上时间片长度，进行必要判断。(3) 未执行队列中依次把到达时间与系统当前时间判断，若小于则表示已到， 插入执行队列run中。(4) 判断当前执行队列是否已完成，如果完成，则显示完成后，将执行队列中后面元素覆盖前面元素。如果没有，则重复(2)(3)和(4),直至所有进程都执行完毕。(5) 判断是否继续调用别的算法，

8、如果是则重新开始，否则结束。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四、主要函数及其说明typedef struct node (char name20; / int round; / int cputime; /cpu int arrivetime;/ int needtime; / char state; /进程名

9、时间片时间到达时间需要服务时间运行状态int count; / struct node *next;PCB;计数void GetFirst() /*取得第一个就绪队列节点*/void Output() /*输出队歹0信息*/void InsertTime(PCB *in) /*将进程插入到就绪队列尾部*/void InsertFinish(PCB *in) /*将进程插入到完成队列尾部*/void TimeCreate() /*时间片输入函数*/void RoundRun() /*时间片轮转调度算法*/五、调试分析1、调试过程及步骤打开VC+6.0软件，将cpp源文件拖入程序主体中，运行，进入

10、时间片轮转 算法主界面。然后输入进程个数，各个进程的名称、到达时间及运行时间，同时 还要定义时间片的大小。样例中输入的进程数为 2个，进程信息分别如下：请输入要创建的进程数目，箱入送程名字到达时间进程所需时间时间片大小:w 0 S 4计数器 0 0 汁数稽 Q 8 计数器 3 0 计数器 3 1b 2 3 4进程名时间需要时间谜程状态baau皇程名：瞑时间髯要时间矗程状态a41WL03R进程名皿u时间需要时间讲程状态b30F&41R进程名牌u时闾需要时间避程状态b3QFa50F请按任意键继续.之后再进行三个进程的测试:请输入要创建的法程数目：嘉入迸程名字到达时间进程所需时间时间片大小,

11、a U 3 2 h 1 4 2独蠢京'G叩时间需要时间 bB4c05a03送程名皿时间需要时间 c05a21bQ4进程名印此寸间需要时间 a21b22cQ5进程名cm时间需要时间进程状态计数器UQUQR0迸程状态计数器U0R00进程状态计数器U0UQR0进程状态计数器U00Q进程名时间需要时间进程状态计数器c23wSa33F1b22R0进程名 叩U时间需要时间逃程状态计敷器a3BF1b40F2虽程名 二时间重要时间景程状态X敷器a3BF1b40F2c41R0进程名 皿时间需要时间避程状态计数器a3BF1b40F2c50F1请按任意键继续 .2、结果分析（以三个进程数为例）首先，输入进程

12、数、时间片大小和各个进程的进程名、 运行时间及到达时间 的信息，进程按照到达时间从小到达顺序，即先运行进程a,其状态为R。时刻为1时，b进程进入内存。时刻为2时，时间片用完，由丁进程b先进入内存，故b进程开始运行。时刻为3时，c进程进入内存。时刻为4时，时间片用完，开始执行c进程。时刻为6时，时间片用完,a进程继续执行。时刻为7时，a进程执行完毕，b进程开始执行。时刻为9时，b进程执行完毕，c进程开始执行。时刻为11时，时间片用完，内存中仅剩c进程，故继续执行 时刻为12时，c进程执行完毕，所有进程执行完毕。六、总结及参考文献1、总结：在本次课程设计中，由于C语言和数据结构课程有一段时间并未使

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

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

15、忆。2、参考文献操作系统宗大华，宗涛，陈吉人著北京：人民邮电出版社，2009数据结构严蔚敏，吴伟民 著 活华大学出版社，2010计算机操作系统（第三版）汤小丹 梁红兵等西安电子科技大学出版社附录：程序源代码#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct nodechar name20;int round;int cputime;int arrivetime;int needtime;char state;int count;struct node *next;PCB

16、;PCB *ready=NULL,*run=NULL,*finish=NULL;int num,i;void GetFirst();void Output();void InsertTime(PCB *in);void InsertFinish(PCB *in);void TimeCreate();void RoundRun();int main(void)printf("请输入要创建的进程数目：n");scanf("%d",&num);TimeCreate();RoundRun();Output();void GetFirst() /*取得第一

17、个就绪队列节点*/run = ready;if(ready!=NULL)run ->state = 'R'ready = ready ->next;run ->next = NULL;void Output() /*输出队歹0信息*/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->s tate

18、,p->count);p = p->next;p = finish;while(p!=NULL)printf("%st%dt%dtt%ctt%dn",p->name,p->cputime,p->needtime,p->s tate,p->count);p = p->next;p = run;while(p!=NULL)printf("%st%dt%dtt%ctt%dn",p->name,p->cputime,p->needtime,p->s tate,p->count);p =

19、 p->next;void InsertTime(PCB *in) /*将进程插入到就绪队歹0尾部*/PCB *fst;fst = ready;if(ready = NULL)in->next = ready;ready = in;elsewhile(fst->next != NULL)fst = fst->next;in ->next = fst ->next;fst ->next = in;void InsertFinish(PCB *in) /*将进程插入到完成队歹0尾部*/(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 TimeCreate()/*时间片输入函数*/(PCB *tmp;int i;printf("输入进程名字 到达时间 进程所需时间 时间片大小：n");for(i = 0;i