时间片轮转算法

1、(1)在单处理器情况下按时间片轮转算法实现处理器调度,输出运行动态变化过程.(2)通过算法的实现加深了解处理器调度的工作.二、实验内容输入实现处理器调度的几个进程信息,任意确定一组“要求运行时间,启动所设计的处理器调度程序,显示逐次被选中进程的进程名以及进程限制块的动态变化过程.三、实验步骤1、任务分析：时间片轮转的主要思想就是按顺序为每一个进程一次只分配一个时间片的时间. 算法要完成的功能就是将各个进程根据时间片轮转运行的动态过程显示出来.时间片轮 转算法的主要实现过程是首先为每一个进程创立一个进程限制块,定义数据结构,说明 进程限制块所包含的内容,有进程名、进程所需运行时间、已运行时间和进

2、程的状态以 及指针的信息.实现的过程即运用指针指向某一个进程,判断当前的进程是否是就绪状 态“r,如果是,那么为该进程分配一个时间片,同时,已运行时间加一旦要求运行的时 间减一,如此循环执行,当某一个进程的所需要运行的时间减少至0时,那么将该进程的状态设置为“ e.然后,将指针指向下一个未运行完成的进程,重复判断,直至所有的 进程都运行结束.2、概要设计：(1)所用数据结构及符号说明typedef struct PCBchar name10; / struct PCB *next; / int need_time; / int worked_time; / char condition; /

3、int flag;/PCB;PCB *front,*rear; / int N; /N为进程数(2)主程序的流程图：进程名循环链指针要求运行时间已运行时间,初始为0进程状态,只有“就绪和“结束两种状态 进程结束标志,用于输出循环链队列的头指针和尾指针0由于本实验是模拟处理器调度的功能,所以,对被选中的进程并不实际的启动运行,而是执行：已运行时间+1来模拟进程的一次运行,表示进程已经运行过一个单位的时间.(1)首先每一个进程用一个进程限制块 PC眯代表.进程限制块的格式为:3、详细设计址,最后一个进程的指针指出第一个进程的进程限制块首地址.要求运行时间一一假设进程需要运行的单位时间数.已运行时间

4、一一假设进程已经运行的单位时间数,初始值为“0.状态一一有两种状态,“就绪和“结束,初始状态都为“就绪",用" R'表示. 当一个进程运行结束后,它的状态为“结束,用“ E表示.(2)每次运行所设计的处理器调度程序前,为每个进程任意确定它的“要求运行时问把五个进程按顺序排成循环链队列,用指针指出队列连接情况.用指针表示轮到运行的进程,如下列图描述所示:Q4PCB2QK4Q4K5Q5K4K5Ki312000RRRPCB3PCB4PCB5K3(3)程序详细设计步骤:a.首先建立PCB勺数据结构,为了便于正确输出,加上了进程结束标志flag .输入进程信息(包括进程名和要

5、求运行的时间),并为每个进程创立一个PCB并初始化形成一个循环链队列,用函数creatPCB()来实现.b.建立函数judge()用来判断进程全部运行结束标志,即当所有进程的状态变 为e'(即完成状态)后,循环结束,表示所有进程都已运行成功.c.建立时间片轮转算法creatProcess ()对进程进行轮转运行,首先指针 s指向第 一个进程PCB即s=front ,判断该进程的状态是否为r'(就绪状态),即 if(s->condition = 'r'),假设是那么表示此进程尚未执行结束,那么执行 s->worked_time+ 且s->need

6、_time- , if(s->need_time=0),那么表示此进程已运行结束,将其状态置为结 束,即s->condition='e',并根据状态位输出完成信息,且以后不会再运行此进程.将 指针指向下个进程,s=s->next ,并判断所有进程是否已全部运行结束,没有那么重复上面 算法.当所有进程的状态位都变成e'表示所有进程运行完成,那么循环结束.d.建立主函数main(),输入进程数N,调用初始化循环链队列函数creatPCB()和时间 片轮转算法creatProcess(N),每次选中进程的进程名以及运行一次后进程队列的变化, 实现处理器的调度

7、.4、调试分析:a.调试过程中遇到的问题及解决方案开始运行到Q5运行完成后显示错误,如下列图所示：原因：经检查程序发现语句if(s->condition='e' )printf("进程s已经运行完成！ nn,s->name);有错误,由于当某个进程运行完成后,其状态标志已修改为e',所以再次循环运行未完成的进程时,当运行到此句时仍会将前面已完成的进程重新输出 一遍完成信息,导致输出错误.解决方案：为每个进程加上一个结束标志flag ,并赋初值为0,当进程运行完成后,将 flag 改为 1,再将后面输出改为 if(s->condition=&#

8、39;e' | s->flag=0 )printf(" 进程$已经运行完成！ nn",s->name);s->flag=0;,这样在前面进程运行完成输出后, 后面再循环时就不会重新输出一遍了.b.改良设想：本实验较简单,但还不够完善,如未实现插入进程功能,即进程在运 行过程中可以插入其他的进程再运行.还有未进行进程优先级判别,本实验默认进程的 优先级按输入的先后顺序从大到小排列的,还有其他功能等,希望在以后的实验中逐步 完善.5、测试结果：a.首先输出五个进程的初始状态b.开始从进程Q1开始按时间片轮转运行进程,Q4先运行完成c.接着Q1运行完成d

9、.接着Q5运行完成e.再Q3运行完成f.最后Q2运行完成四、实验总结因在早期的时间片轮转法中,系统将所有的就绪进程根据先来先效劳的原那么排成一 个队列,每次调度是,把 CPU分配给队首进程,并令其执行一个时间片.当执行的时间 片用完时,调度程序停止该进程的执行,并将它送往就绪队列的末尾；然后,再把处理 机分配给就绪队列中新的队首进程,同时也让它执行一个时间片.在时间片轮转算法中, 时间片的大小对系统性能有很大的影响.如果选择很小的时间片将有利于短作业,由于 它能较快地完成,但会频繁的发生中断、进程上下文的切换,从而增加系统的开销；反 之,如果选择太长时间片,使得每个进程都能在一个时间片内完成,

10、所以,一般定为时 问片略大于一次典型地交互所需要的时间.在完成时间片轮转算法的实现过程中,我们遇到了一些问题,比方怎样运用循环队 列,如何设计结构体等等,也积极配合并思考进行解决.整体来说,我们的算法虽然实 现了表达进程动态运行变化的过程,但是相对而言比拟简单.实验中,我们小组不断讨 论对算法进行优化,使得运行结果看起来更容易理解,也到达了处理机调度的功能.做 实验让我们对于时间片轮转的思想理解的更加透彻,稳固了理论知识的学习.实验心得体会：首先,我们认为这次课程设计是对学习?操作系统?的一次综合考 察,锻炼我们综合分析问题、解决问题的水平.初次得到课程设计的题目时,为程序本身的简单而窃喜过；

11、实验过程中也出现了一 些难题需要解决,为此去苦苦探索过.课程设计期间,几乎有几天我们完全投入进去了, 就像是在做一个相当重要的工程一样的感觉.曾经跑过图书馆几次,只是为了一种新的 想法得到实现,也曾屡次登录网站浏览网页,为了弥补一些知识上的维漏,为此曾洒下 了真实的汗水.当我们的想法得到实现,又学会了新的知识的时候,心中满是欣喜,或 许这是实践出真知的真实验证,有付出就有回报的真实写照吧.其次,我们感受了真诚的友谊.在实验中,遇到的问题是多方面的,而且有那么一 局部是以前学过的C问题,但是已经忘却或是以前没有真正的理解过.但是你会发现就 在你的身边,会有那么一批人在背后热心的帮助你,让你身处困

12、境却感到无限希望.这 好似是人生的一种历程,风风雨雨中我们一起走过,然后为了一些坑坑洼洼彼此真诚的帮助过和无私的付出过.团队的协作和彼此心的交流让我们彼此丰厚起来,这也是我们 成长中必不可失的重要局部.最后,我熟悉到了自己的缺乏.平心而论,以前真的没有认真的学习过,即使是在 听课,可是后来却没有对学习中出现的问题而仔细分析过.得过且过,迷失了我前进的 方向,而现在却又重新敞开了.不管是以后的学习还是工作,我想这都是很重要的,我 们需要不断进步的动力.总的说来知识上的收获很是重要,精神上的丰收也是更加可喜的,让我知道了学无 止境的道理.我们每一个人永远不能满足于现有的成就,人生就像在爬山,一座山

13、峰的 后面还有更高的山峰在等着你.挫折是一份财富,经历是一份拥有.这次课程设计必将 成为我人生旅途上一个非常美好的回忆.五、附录实验源程序如下：#include"stdio.h"#include"conio.h"#include"malloc.h"#include"string.h"#define NULL 0typedef struct PCBchar name10;进程名struct PCB *next; /链指针int need_time; 要求运行时间int worked_time; 已运行时间char c

14、ondition;/进程状态,只有 就绪和 结束"两种状态int flag;/进程结束标志PCB;PCB *front,*rear;int N; /N为进程数void creatPCB()/为每个进程创立一个PCB并初始化形成一个循环链队列PCB *p,*l;l = (PCB *)malloc(sizeof(PCB);printf("Please enter process name and timen");scanf("%s%d",l->name,&l->need_time);l->condition = T; 进程

15、初始状态为就绪l->worked_time = 0;l->next=NULL;l->flag=0;front=l;for(int i = 1;i < N ;i +)p = (PCB *)malloc(sizeof(PCB);scanf("%s%d",p->name,&p->need_time);p->condition = 'r'p->worked_time = 0;p->flag=0;l->next = p;l=l->next;rear=l;rear->next=front;v

16、oid output()进程输出函数printf("name runtime needtime staten");for(int j=1;j<=N;j+)printf(" %-4st%-4dt%-4dt%-cn",front->name,front->worked_time,front->need_time,front-> condition);front=front->next;printf("n");int judge(PCB *p)/判断所有进程运行结束int flag = 1;for(int

17、 i=0;i<N;i+)if(p->condition != 'e')flag = 0;break;p=p->next;return flag;void creatProcess(int n) /时间片轮转算法PCB *s,*p;int i,j,flag1=0;s = (PCB *)malloc(sizeof(PCB);s=front;printf("nn");output();printf("Press any key to continuenn");getch();/按任意键继续s=front;while(flag1 != 1)if(s->condition = 'r')s->worked_time+;s->need_time-;if(s->need_time=0)s->condition='e'output();printf("Press any key to continue.nn");getch();if(s