时间片轮转调度算法设计与实现

1、郑州轻工业学院实验报告课程名称：操作系统姓 名：学 号：专业班级：任课教师：黄伟2016 年 11 月 2 日实验报告成绩评定表评定项目内容满分评分总分实验态度态度端正、遵守纪律、出勤情况20实验过程按要求完成算法设计、代码书写、注释清晰、运行结果正确40报告撰写报告书写规范、内容条理清楚、表 达准确规范、上交及时。40评语：指导老师签字：年 月曰实验报告正文实验二时间片轮转调度算法设计与实现一、实验目的目的：了解并掌握时间片轮转调度算法的理论，熟悉并掌握时间片设置的大小对系统的影响。任务：模拟实现时间片轮转调度算法。二、实验内容任务描述1）时间片轮转调度算法问题简介时间片轮转的主要思想就是按

2、顺序为每一个进程一次只分配一个时间片的时间。算法 要完成的功能就是将各个进程按照时间片轮转运行的动态过程显示出来。时间片轮转算法的 主要实现过程是首先为每一个进程创建一个进程控制块，定义数据结构，说明进程控制块所 包含的内容，有进程名、进程所需运行时间、已运行时间和进程的状态以及指针的信息。实 现的过程即运用指针指向某一个进程，判断当前的进程是否是就绪状态”，如果是，则为 该进程分配一个时间片，同时，已运行时间加一且要求运行的时间减一，如此循环执行，当 某一个进程的所需要运行的时间减少至0时，则将该进程的状态设置为e”。然后，将指针 指向下一个未运行完成的进程，重复判断，直至所有的进程都运行结

3、束。2）设计任务简介模拟实现时间片轮转调度算法，具体如下：设置进程体：进程名，进程的到达时间，服务时间，进程状态（W等待,R 运行,F完成），进程间的链接指针进程初始化：由用户输入进程名、服务时间进行初始化，同时，初始化进程的状态 为W。显示函数：在进程调度前、调度中和调度后进行显示。排序函数：对就绪状态的进程按照进入就绪队列的时间排序，新到达的进行应优先 于刚刚执行过的进程进入就绪队列的队尾。注意考虑到达时间调度函数：每次从就绪队列队首调度优一个进程执行，状态变化。并在执行一个时 间片后化，服务时间变化，状态变化。当服务时间为0时，状态变为F。删除函数：撤销状态为F的进行。调度问题的表示方案

4、首先每一个进程用一个进程控制块PCB来代表。进程控制块的格式为:进程名指针要求运行时间已运行时间 一状态其中，进程名一一作为进程的标识，如Q1、Q2等。指针一一进程按顺序排成循环链队列，用指针指出下一个进程的进程控制块的首地址， 最后一个进程的指针指出第一个进程的进程控制块首地址。要求运行时间一一假设进程需要运行的单位时间数。已运行时间一一假设进程已经运行的单位时间数，初始值为“0”。状态一一有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。 当一个进程运行结束后，它的状态为“结束”，用“E”表示。抽象描述这里采用流程图来详细描述时间片轮转调度算法三、测试1. 方案每次运行所

5、设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。把 五个进程按顺序排成循环链队列，用指针指出队列连接情况。用指针表示轮到运行的进程，如下图描述所示:PCB25PCB5首先建立PCB的数据结构，为了便于正确输出，加上了进程结束标志flag。输入进 程信息(包括进程名和要求运行的时间)，并为每个进程创建一个PCB并初始化形成一个循 环链队列，用函数creatPCB()来实现。建立函数judge()用来判断进程全部运行结束标志，即当所有进程的状态变为 e (即完成状态)后，循环结束，表示所有进程都已运行成功。建立时间片轮转算法creatProcess()对进程进行轮转运行，首先指针s

6、指向第一 个进程PCB，即s=front，判断该进程的状态是否为 r(就绪状态)，即if(s-condition =r)，若是则表示此进程尚未执行结束，则执行s-worked_time+且 s-need_time， if(s-need_time=0)，则表示此进程已运行结束，将其状态置为结束，即s-condition=e， 并根据状态位输出完成信息，且以后不会再运行此进程。将指针指向下个进程，s=s-next， 并判断所有进程是否已全部运行结束，没有则重复上面算法。当所有进程的状态位都变成 e表示所有进程运行完成，则循环结束。建立主函数main()，输入进程数N，调用初始化循环链队列函数cre

7、atPCB()和时间片 轮转算法creatProcess(N)，每次选中进程的进程名以及运行一次后进程队列的变化，实现 处理器的调度。2. 结果实例进程名ABCDE平均到达时间01234服务时间62598RRQ=2完成时间164153029周转时间16319272518带权周转 时间2.671.53.833.132.82RRQ=4完成时间206213029周转时间20519272519.2带权周转 时间3.332.53.833.133.15Q=2Q=4忌暗入曲过间什粕转进程队列为:Nan* Ml hUneBHune-CriajFie9E*rrivttirw-0Artivfit irw 旦1 a

8、rr ivet ine -2 ftrriu*ctiic-3runtime =6 runt infr-2 runt int-5funtstateR stalw-R stateR SttC-R stateR请置入时间片轮转调度的时间片为:4 时刻进程运行后的敏态4 A R R C寸刻&进畋行始原进程职转时间 5皿常t阴转时间16141S时刻，成运行结柬髓程建琵1礼弟皿.帝任胃转时由二 TOC o 1-5 h z 21CC时刻21进华运作结束总程硒转时间W槌叭带枚.周转时斗25IRG 0C2.13时刻及进理演行拮束,进程瞭转时间翡5投罔转时间G请稿入时间片轮转调度的可间片为I时割 进程 运行后的状态

9、 TOC o 1-5 h z 4AR&口c时刻6进程B运行结来.进程R周转时间M 5.0带权冏转时间 2.5010CR14DRIBER2BAC时刻德进笛运行拮束，进程周转时间跪血,带校周转时间 3-33g jGg时剽就捱程C运行结基迸程瑚转时间 .卵滞极周转时间 3.802&bR29*EC时刻网进程E运行始来湖程E周转时间志一皿带视周转时间-3.1JJBbC与刻捆进程。运行堵束展程。周转时问营.昵带机周转时（Bl- 3.M 华期周待时间F.曲.翔蚩权内林时即1.1SPress ad9 *4iy to cant inu*四、总结与讨论通过本次实验了解到算法很重要，又更加明白算法本身可以节约时间，

10、而且不同 的函数之间在调用的时候要注意很多的问题。意识到自己的不足，代码在运行过程中， 无法运行，错误很多，。通过本次实验，我更加了解了时间片轮转调度算法，通过翻看 课本，对其的理解更加的深刻了，在以后的学习中，我会更加努力的学习操作系统的 相关课程。当然，实验中也遇到了问题，但都不是理论上的问题，而是编程的问题，根 本原因还是编程基础不牢。以后会在编程方面努力。五、附：程序模块的源代码RR.h#include#include#include#include#include#define MaxNum 100typedef struct pcbchar NameMaxNum;int arriv

11、etime;int runtime;int wholetime;int FinishTime;double WeightTime;double WeightWholeTime;char state;struct pcb *next;PCB;int N;double SumWT;double SumWWT;double AverageWT;double AverageWWT;typedef struct PCB *front,*rear;queue;queue *init()queue *head;head=(queue*)malloc(sizeof(queue);head-front=NULL

12、;head-rear=NULL;return head;int empty(queue *head)return (head-front?0:1);queue *append(queue *head,char cMaxNum,int a,int r,char s) PCB *p;p=(PCB *)malloc(sizeof(PCB);strcpy(p-Name,c);p-arrivetime=a;p-runtime=r;p-wholetime=r;p-state=s;/p-FinishTime=0;/p-WeightTime=0;/p-WeightWholeTime=0;p-next=NULL

13、;if(empty(head)head-front=head-rear=p;elsehead-rear-next=p;head-rear=p;return head;queue *creat(queue *head)char cMaxNum;char s=R;int a,r,i;printf(请输入共有几个进程：n);scanf(%d”,&N);for(i=1;ifront;if(!p)printf(时间片轮转调度队列为空!n”);while(p)printf(Name=%s arrivetime=%d runtime=%d state=%c”,p-Name,p-arrivetime,p-ru

14、ntime,p-state);printf(n);p=p-next;void RR(queue *head,int q)int t=head-front-arrivetime, lt=head-rear-arrivetime;if(head-front-runtimefront-runtime;elset=t+q;while(!empty(head)PCB *p1,*p2;printf (-n时刻 进程运行后的状态n);while(tfront;printf(%2d %s”,t,p1-Name);p1-runtime=p1-runtime-q;if(p1-runtimestate=C;prin

15、tf( %cn”,p1-state);p1-FinishTime=t;p1-WeightTime=p1-FinishTime-p1-arrivetime;p1-WeightWholeTime=p1-WeightTime/p1-wholetime;SumWT+=p1-WeightTime;SumWWT+=p1-WeightWholeTime;printf(时刻%2d进程%s运行结束，进程%s周转时间=%5.2f,带权周转时间=%5.2fn”,t,p1-Name,p1-Name,p1-WeightTime,p1-WeightWholeTime);head-front=p1-next;free(p1

16、);elseprintf( %cn”,p1-state);p2=p1-next;while(p2-next & p2-arrivetime != t)p2=p2-next;/2.找位置往后插入if(p2-arrivetime != t)PCB *p3=p1,*p4; while(p3-next & p3-arrivetimenext;if(p3-arrivetimet)if(p4!=p1)/p1 插在 p4 后，头为 p1-nexthead-front=p1-next;p1-next=p4-next;p4-next=p1;else 不做操作p4=p3=p2=NULL;elsep4=p3=p2=

17、NULL;elsehead-front=p1-next;p1-next=p2-next;p2-next=p1;if(head-front-runtimefront-runtime;elset=t+q;while(t=lt)p1=head-front;printf(%2d %s”,t,p1-Name);p1-runtime=p1-runtime-q;if(p1-runtimestate=C;printf( %cn”,p1-state);p1-FinishTime=t;p1-WeightTime=p1-FinishTime-p1-arrivetime;p1-WeightWholeTime=p1-W

18、eightTime/p1-wholetime;SumWT+=p1-WeightTime;SumWWT+=p1-WeightWholeTime;printf(时刻%2d进程%s运行结束，进程%s周转时间=%5.2f,带权周转时间 =%5.2fn”,t,p1-Name,p1-Name,p1-WeightTime,p1-WeightWholeTime);/printf(时刻2d 进程s 运行结束，t,p1-pname);head-front=p1-next;free(p1);elseprintf( %cn”,p1-state);if(!p1-next)head-front=p1;/若原队列有多个进程 elsehead-front=p1-next;head-rear-next=p1;head-rear=p1;p1-next=NULL;if(empty(head)return;elseif(head-front-runtimefront-runtime;elset=t+q;Main.cp