时间片轮转详解

1、时间片轮转,成员：斯奇能,叶怀培,柳超峰,时间片轮转概念,?,时间片轮转调度是一种最古老，最简单，,最公平且使用最广的算法。每个进程被分,配一个时间段，称作它的时间片，即该进,程允许运行的时间。如果在时间片结束时,进程还在运行，则,CPU,将被剥夺并分配给另,一个进程。如果进程在时间片结束前阻塞,或结束，则,CPU,当即进行切换。调度程序所,要做的就是维护一张就绪进程列表，当进,程用完它的时间片后，它被移到队列的末,尾。,时间片轮转调度中存在的问题,?,从一个进程切换到另一个进程是需要一定,时间的,-,保存和装入寄存器值及内存映像，,更新各种表格和队列等。假如进程切换,(process swi

2、tch) -,有时称为上下文切换,(context switch),，需要,5,毫秒，再假设时间,片设为,20,毫秒，则在做完,20,毫秒有用的工,作之后，,CPU,将花费,5,毫秒来进行进程切换,。,CPU,时间的,20%,被浪费在了管理开销上。,如何提高,CPU,效率？,?,分析：我们可以将时间片设为,500,毫秒。这,时浪费的时间只有,1%,。但考虑在一个分时,系统中，如果有十个交互用户几乎同时按,下回车键，将发生什么情况？假设所有其,他进程都用足它们的时间片的话，最后一,个不幸的进程不得不等待,5,秒钟才获得运行,机会。多数用户无法忍受一条简短命令要,5,秒钟才能做出响应。同样的问题在

3、一台支,持多道程序的个人计算机上也会发生。,?,时间片设得太短会导致过多的进程切换，,降低了,CPU,效率；而设得太长又可能引起对,短的交互请求的响应变差。将时间片设为,100,毫秒通常是一个比较合理的折衷。,时间片轮转算法的主要实现过程,?,首先为每一个进程创建一个进程控制块，定义数,据结构，说明进程控制块所包含的内容，有进程,名、进程所需运行时间、已运行时间和进程的状,态以及指针的信息。实现的过程即运用指针指向,某一个进程，判断当前的进程是否是就绪状态,“,r,”，如果是，则为该进程分配一个时间片，同,时，已运行时间加一且要求运行的时间减一，如,此循环执行，当某一个进程的所需要运行的时间,

4、减少至,0,时，则将该进程的状态设置为“,e,”。然,后，将指针指向下一个未运行完成的进程，重复,判断，直至所有的进程都运行结束,所用数据结构及符号说明,?,?,?,?,?,?,?,?,?,?,typedef struct PCB,char name10; /,进程名,struct PCB *next; /,循环链指针,int need_time; /,要求运行时间,int worked_time; /,已运行时间，初始为,0,char condition; /,进程状态，只有“就绪”和,“结,束”两种状态,int flag; /,进程结束标志，用于输出,PCB;,PCB *front,*re

5、ar; /,循环链队列的头指针和尾指针,int N; /N,为进程数,主程序的流程图,程序说明,?,处理器调度总是选择指针指示的进程运行,。由于本实验是模拟处理器调度的功能，,所以，对被选中的进程并不实际的启动运,行，而是执行：已运行时间,+1,来模拟进程,的一次运行，表示进程已经运行过一个单,位的时间。,程序详细设计步骤,?,a.,首先建立,PCB,的数据结构，为了便于正确,输出，加上了进程结束标志,flag,。输入进程,信息（包括进程名和要求运行的时间），,并为每个进程创建一个,PCB,并初始化形成一,个循环链队列，用函数,creatPCB(),来实现。,?,b.,建立函数,judge()

6、,用来判断进程全部运行结,束标志，即当所有进程的状态变为,e,（,即完成状态）后，循环结束，表示所有进,程都已运行成功。,?,c.,建立时间片轮转算法,creatProcess,（）对进程进,行轮转运行，首先指针,s,指向第一个进程,PCB,，即,s=front,，判断该进程的状态是否为,r,（就绪状,态），即,if(s-condition = r),，若是则表示此进程,尚未执行结束，则执行,s-worked_time+,且,s-,need_time-,，,if(s-need_time=0),，则表示此进,程已运行结束，将其状态置为结束，即,s-,condition=e,，并根据状态位输出完成

7、信息，且,以后不会再运行此进程。将指针指向下个进程，,s=s-next,，并判断所有进程是否已全部运行结束,，没有则重复上面算法。当所有进程的状态位都,变成,e,表示所有进程运行完成，则循环结束。,?,d.,建立主函数,main(),输入进程数,N,，调用初,始化循环链队列函数,creatPCB(),和时间片轮,转算法,creatProcess(N),，每次选中进程的进,程名以及运行一次后进程队列的变化，实,现处理器的调度。,实验源程序,?,?,?,?,?,?,?,?,?,?,?,#includestdio.h,#includeconio.h,#includemalloc.h,#include

8、string.h,#define NULL 0,typedef struct PCB,char name10; /,进程名,struct PCB *next; /,链指针,int need_time; /,要求运行时间,int worked_time; /,已运行时间,char condition; /,进程状态，只有“就绪”和,“结束”两种状态,?,?,?,?,?,?,?,?,?,?,?,?,?,?,队列,int flag; /,进程结束标志,PCB;,PCB *front,*rear;,int N; /N,为进程数,void creatPCB(),/,为每个进程创建一个,PCB,并初始化形

9、成一个循环链,PCB *p,*l;,l = (PCB *)malloc(sizeof(PCB);,printf(Please enter process name and timen);,scanf(%s%d,l-name,l-condition = r; /,进程初始状态为就绪,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

10、(%s%d,p-name,p-condition = r;,p-worked_time = 0;,p-flag=0;,l-next = p;,l=l-next;,rear=l;rear-next=front;,void 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;,prin

11、tf(n);,int judge(PCB *p) /,判断所有进程运行结束,int flag = 1;,for(int i=0;iN;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(n-n);,output();,printf(Press any key to continue.nn);,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