时间片轮转算法

1、NO.16课 程 设 计 说 明 书时间片轮转算法1. 课程设计的目的通过操作系统课程设计，通过对作业调度算法的设计，深入理解作业调度的原理，从原理分析、物理设计，到功能分析和应用程序的最终实现，让我亲自动手参与一个操作系统的模拟设计，真正理解和掌握操作系统的有关内容，加深对操作系统，软件工程，程序设计语言的理论知识的理解和应用水平；在理论和实验教学基础上进一步巩固已学基本理论及应用知识并加以综合提高；学会将知识应用于实际的方法，提高分析和解决问题的能力，增强对手能力；并更好的理解和消化课本所学的知识，为毕业设计和以后工作打下必要基础。2. 课程设计的开发语言 在本次课程设计中，我们选择了C+

2、语言作为我们所使用的开发语言，开发工具则选用了Microsoft Visual C+ 6.0。MFC借助C+的优势为Windows开发开辟了一片新天地，同时也借助ApplicationWizzard使开发者摆脱离了那些每次都必写基本代码，借助ClassWizard和消息映射使开发者摆脱了定义消息处理时那种混乱和冗长的代码段。更重要的是利用C+的封装功能使开发者摆脱Windows中各种句柄的困扰，只需要面对C+中的对象，这样一来使开发更接近开发语言而远离系统。正因为MFC是建立在C+的基础上，所以我强调C/C+语言基础对开发的重要性。利用C+的封装性开发者可以更容易理解和操作各种窗口对象；利用C

3、+的派生性开发者可以减少开发自定义窗口的时间和创造出可重用的代码；利用虚拟性可以在必要时更好的控制窗口的活动。而且C+本身所具备的超越C语言的特性都可以使开发者编写出更易用，更灵活的代码。 3. 功能描述时间片轮转的主要思想就是按顺序为每一个进程一次只分配一个时间片的时间。算法要完成的功能就是将各个进程按照时间片轮转运行的动态过程显示出来。时间片轮转算法的主要实现过程是首先为每一个进程创建一个进程控制块，定义数据结构，说明进程控制块所包含的内容，有进程名、进程所需运行时间、已运行时间和进程的状态以及指针的信息。实现的过程即运用指针指向某一个进程，判断当前的进程是否是就绪状态“r”，如果是，则为

4、该进程分配一个时间片，同时，已运行时间加一且要求运行的时间减一，如此循环执行，当某一个进程的所需要运行的时间减少至0时，则将该进程的状态设置为“e”。然后，将指针指向下一个未运行完成的进程，重复判断，直至所有的进程都运行结束。4. 方案论证4.1 概要设计4.1.1各模块功能1)int InitQueue(LinkQueue &Q)：输入进程时，初始化输入的链表。2)int DestroyQueue(LinkQueue &Q)：运行完后，销毁链表。3)int EnQueue(LinkQueue &Q,QElem

5、Type e)：将进程插入循环队列中。4)int DeQueue(LinkQueue &Q,QElemType e)：当进程完成后，输出链表中元素。 5)int QueueEmpty(LinkQueue &Q)：判断链表是否为空。6)void chioce(struct PCB pcb,int n)：对于输入链表中数的按关键字到达时间用选择法从小到大进行进行排序。7)void caidan()：主菜单，包含：进程的创建和结果和结束。8)void create(

6、)：进程的创建。9)void main()：实现函数调用的总控制。4.1.2 相关数据类型1)typedef int QElemType：自定义类型，定义QElemType为int型。2)typedef struct QNode QElemType data;struct QNode *next;QNode,*QueuePtr;采用结构体变量，存队列的相关信息：QElemType data、struct QNode *next。同时定义结构体指针*QueuePtr，便于之后书

7、写开辟空间级表示。系统调用时，每次分配一个QNode那么大的空间进行存储。3)typedef struct PCB char name10; /进程名struct PCB *next; /循环链指针int need_time; /要求运行时间int worked_time; /已运行时间，初始为0char condition; /进程状态，只有“就绪”和“结束”两种状态int flag; /进程结束标志，用于输出PCB; PCB *front,*rear; /循环链队列的头指针和尾指针 int N; /N为进程数定义循环链表的头指针和尾指针。QueuePtr front，QueueP

8、tr rear。4)struct PCB int ArrivalTime;int ServiceTime;har number;mMaxNum;采用结构体数组，创建一个进程，包含进程相关信息：进程名称、进程到达时间、进程服务时间。4.2.3 总体设计程序总体设计:首先选择1创建进程，输入进程总数，进程的名称，各进程到达的时间，各 进 程 服 务 的 时 间 ， 以 及 时 间 片q的 值 ，运行出结果。选择2将结束运行，如图1所示。图1 系统总体设计4.2.4 主程序的流程图主程序流程如图2所示。YNYNYY退 出输入进程数

9、输入进程进程是否输入完输入时间片分配给执行队列队首时间片时间片-1时间片+1时间片是否用完是否所有进程都完成将为完成的插入队尾NY结 束将新到进程插入队尾是否完成服务时间-1N开 始是否有新进程到达N图2 主程序的流程图4.1.5 程序说明 处理器调度总是选择指针指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。4.2 详细设计首先每一个进程用一个进程控制块PCB来代表。进程控制块的格式如表3所示。表3 PCB控制块进程名指针要求运行时间已运行时间状态其中，进程名作为进程的标

10、识，如Q1、Q2等。指针进程按顺序排成循环链队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。已运行时间假设进程已经运行的单位时间数，初始值为“0”。状态有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。当一个进程运行结束后，它的状态为“结束”，用“E”表示。每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。把五个进程按顺序排成循环链队列，用指针指出队列连接情况。用指针表示轮到运行的进程，如表4描述述所示。表4进程队列K1Q1 K2Q2 K3Q3 K4Q4 K5Q5 K2 K3

11、60;K4 K5 K1 2 4 3 1 2 0 0 0 0 0 R R R R R PCB1 PCB2 PCB3 PCB4 PCB54.3 程序详细设计步骤首先建立PCB的数据结构，为了便于正确输出，加上了进程结束标志flag。输入进程信息（包括进程名和要求运行的时间），并为每个进程创建一个PCB并初始化形成一个循环链队列，用函数creatPCB()来实现。建立函数judge(

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

13、出完成信息，且以后不会再运行此进程。将指针指向下个进程，s=s->next，并判断所有进程是否已全部运行结束，没有则重复上面算法。当所有进程的状态位都变成e表示所有进程运行完成，则循环结束。建立主函数main(),输入进程数N，调用初始化循环链队列函数creatPCB()和时间片轮转算法creatProcess(N)，每次选中进程的进程名以及运行一次后进程队列的变化，实现处理器的调度。5. 程序的运行及结果 1）主菜单：输入选项1：进程创建及结果2：结束，如图5所示。图5 主菜单2)运行过程:选择1，创建进程。输入进程总数，进程的名称a 、b，各进程到达的时间，各 进 程 服

14、务 的 时 间 ， 以 及 时 间 片q的 值 。 当 输 入 进 程 为 2时，各 进 程 到 达 时 间为3,2，各进程服务时间为2,3，以及时间片q=2时的情况，输入情况如图6所示。图6创建进程 3）输入成功后，按回车键，进程在程序中的具体实现情况即：时间轮转情况。进程在调 度算法中，计算 出 的具 体 的 完 成时间，周转时间，带权时间，平均周转时间，平均带权周转时间，如图7所示。图7进程运行结果3）选择2：退出界面，如图8。图8退出界面6. 心得体会首先，我认为这次课程设计是对学习操作系统的一次综合考察，锻炼我综合分析问题、解决问题的能力。初次找到课程设计的题目时，为程序本身的简单而

15、窃喜过；实验过程中也出现了一些难题需要解决，为此去苦苦探索过。课程设计期间，曾多次登录网站浏览网页，为了弥补一些知识上的纰漏，一次次实践。当我的想法得到实现，又学会了新的知识的时候，心中满是欣喜，或许这是实践出真知的真实验证，有付出就有回报的真实写照吧。其次，我们感受了真诚的友谊。在实验中，遇到的问题是多方面的，而且有那么一部分是以前学过的问题，但是已经忘却或是以前没有真正的理解过。但是你会发现就在你的身边，会有那么一批人在背后热心的帮助你，这好像是人生的一种历程，团队的协作和彼此心的交流让我们彼此丰厚起来，这也是我们成长中必不可失的重要部分。最后，我认识到了自己的不足。平心而论，以前真的没有

16、认真的学习过，即使是在听课，可是后来却没有对学习中出现的问题而仔细分析过。得过且过，迷失了我前进的方向，而现在却又重新敞开了。不论是以后的学习还是工作，我想这都是很重要的，我需要不断进步的动力。7. 参考文献1 陈莉君等. Linux 操作系统原理与应用M. 北京:清华大学出版社.2012.12李龙来,吴杰,吕智慧,杨明. 基于Web服务的分布式文件系统管理与优化方案J. 计算机工程与设计,2012.3 庞丽萍，阳富民. 计算机操作系统(第2版)M. 北京：人民邮电出版社. 2014.14孙洪庆. 浅谈对计算机操作系统的认识J. 改革与开放,2011,04:140.5 汤小丹. 计算机操作系统

17、（第4版）M. 西安：电子科技大学出版社. 2014.5附录：#include<iostream.h> #include<iomanip.h> #include<malloc.h> typedef int QElemType; static const int MaxNum=100; typedef struct QNode QElemType data; struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front; QueuePtr rear; LinkQueue; struct P

18、CB int ArrivalTime; int ServiceTime; char number; mMaxNum; int InitQueue(LinkQueue &Q); int DestroyQueue(LinkQueue &Q); int EnQueue(LinkQueue &Q,QElemType e); int DeQueue(LinkQueue &Q,QElemType e); int QueueEmpty(LinkQueue &Q); void chioce(struct PCB pcb,int n); void caidan(); vo

19、id create(); int n,q,FinishedTimeMaxNum,WholeTimeMaxNum; double WeightWholeTimeMaxNum,Average_WT=0,Average_WWT=0; LinkQueue Q; void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q); void main() while(1) / system("cls"); cout<<endl; caidan(); int n; cout<<"请

20、选择（1-2） ："<<endl; cin>>n; if(n<1|n>2) cout<<"输入有误，请重新输入"<<endl; switch(n) case 1:create();break; case 2:return ; /RR算法的具体实现 void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q) int countTime=0,e; chioce(m,n); if(ArrivalTime0=0) countTime=

21、0; else countTime=m0.ArrivalTime; int STimeMaxNum,pushedMaxNum; for(int i=0;i<n;i+) STimei=mi.ServiceTime; pushedi=0; InitQueue(Q); EnQueue(Q,0); pushed0=1; int time=m0.ArrivalTime; while(QueueEmpty(Q)=false) e=DeQueue(Q,e); if(STimee>q) STimee=STimee-q; countTime+=q; else countTime+=STimee; S

22、Timee=0; FinishedTimee=countTime; while(time<countTime) if(STime>0) cout<<"时刻"<<setw(2)<<time<<":进程"<<e<<"正在运行"<<endl; time+; for(i=1;i<n;i+) if(STime!=0&&i!=e&&mi.ArrivalTime<countTime&&pushe

23、di=0|STime!=0&&i!=e&&mi.ArrivalTime=countTime) EnQueue(Q,i); pushedi=1; if(STimee>0)/判断进程e是否已执行完 EnQueue(Q,e); for(i=0;i<n;i+) /求周转时间和带权周转时间 WholeTimei=FinishedTimei-mi.ArrivalTime; WeightWholeTimei=(double)(WholeTimei*1.000000/mi.ServiceTime); Average_WT+=WholeTimei; Average_W

24、WT+=WeightWholeTimei; Average_WT/=n;/求平均周转时间 Average_WWT/=n;/求平均带权周转时间 /-输出- cout<<"-"<<endl; cout<<endl; cout<<endl; cout<<"进程运行的结果是："<<endl; cout<<"-"<<endl; cout<<"进程名称:"<<" " for(i=0;i&l

25、t;n;i+) cout<<setw(8)<<mi.number <<" " cout<<endl; cout<<"到达时间:"<<" " for(i=0;i<n;i+) cout<<setw(8)<<mi.ArrivalTime<<" " cout<<endl; cout<<"服务时间:"<<" " for(i=0;i<

26、n;i+) cout<<setw(8)<<mi.ServiceTime<<" " cout<<endl; cout<<"完成时间:"<<" " for(i=0;i<n;i+) cout<<setw(8)<<FinishedTimei<<" " cout<<endl; cout<<"周转时间:"<<" " for(i=0;i<

27、;n;i+) cout<<setw(8)<<WholeTimei<<" " cout<<endl; cout<<"带权周转："<<" " for(i=0;i<n;i+) cout<<setw(8)<<setiosflags(ios:fixed)<<setprecision(2)<<WeightWholeTimei<<" " cout<<endl; cout<&l

28、t;"-"<<endl; cout<<"平均周转时间为："<<Average_WT<<endl; cout<<"平均带权周转时间为:"<<Average_WWT<<endl; DestroyQueue(Q); /初始化链队列Q int InitQueue(LinkQueue &Q) Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); Q.front->next=NULL; return 1; /销

29、毁链队列Q int DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; return 1; /入队 int EnQueue(LinkQueue &Q,QElemType e) QueuePtr p=(QueuePtr)malloc(sizeof(QNode); p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; return 1; /出队，并用e返回出队节点的元素值 in

30、t DeQueue(LinkQueue &Q,QElemType e) QueuePtr p; if(Q.front=Q.rear) return 0; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear=p) Q.rear=Q.front; free(p); return e; /判断链队列Q是否为空 int QueueEmpty(LinkQueue &Q) if(Q.front=Q.rear) return true; elsereturn false; /选择排序，对结构体中的关

31、键字到达时间，按从小到大的顺序排列void chioce(struct PCB pcb,int n) int i,j; struct PCB t; for(j=0;j<n-1;j+) for(i=0;i<n-1-j;i+) if(pcbi.ArrivalTime>pcbi+1.ArrivalTime) t=pcbi; pcbi=pcbi+1; pcbi+1=t; void caidan() cout<<"*主页*"<<endl; cout<<"*1.进程创建及结果*"<<endl; cout<<"*2. 结束 *"<<endl; void create() cout<<"