时间片轮转算法资料

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

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

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

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

5、ntDeQueue(LinkQueue &Q,QElemType e):当进程完成后，输出链表中元素。5) intQueueEmpty(LinkQueue &Q):判断链表是否为空。6) voidchioce(struct PCB pcb,intn):对于输入链表中数的按关键字到达时间用选择法从小到大进行进行排序。7) voidcaidan():主菜单，包含：进程的创建和结果和结束。8) voidcreate():进程的创建。9) voidmain()：实现函数调用的总控制。相关数据类型1) typedefint QElemType 自定义类型，定义 QEIemTyp为 int

6、 型。2) typedefstruct QNode QElemType data;struct QNode *n ext;QNode,*QueuePtr;采用结构体变量，存队列的相关信息：QElemTypedata、 struct QNode *next。同时定义结构体指针*QueuePtr，便于之后书写开辟空 间级表示。系统调用时，每次分配一个 QNode那么大的空间进行存储。3) typedef struct PCB char name10;/ 进程名struct PCB *n ext; /循环链指针int n eed_time; / int worked_time; / char con

7、 diti on; / int flag; /要求运行时间已运行时间，初始为0进程状态，只有“就绪”和“结束”两种状态 进程结束标志，用于输出PCB; PCB *fron t,*rear; /循环链队列的头指针和尾指针int N; N 为进程数定义循环链表的头指针和尾指针。QueuePtr front ，QueuePtr rear。4) struct PCB int ArrivalTime; int ServiceTime;har nu mber;mMaxNum;采用结构体数组，创建一个进程，包含进程相关信息：进程名称、进程到达 时间、进程服务时间。总体设计程序总体设计：首先选择1创建进程，输

8、入进程总数，进程的名称，各进程 到达的时间，各进程服务的时间，以及时间片q的值，运行出结果。选择2将结 束运行，如图1所示。AAA到眠时达时时片间闫图1系统总体设计出 运 n果盥入进程數主程序的流程图主程序流程如图2所示YNYNNY是否完成是否所有进程 都完成时间片是否用宀完NY是否有新进程 到达NY输入时间片进程是否输入宀完分配给执行队列队首时间片时间片-1时间片+1服务时间-1将为完成的插入队尾将新到进程插入队尾退 出输入进程数输入进程图2主程序的流程图程序说明处理器调度总是选择指针指示的进程运行。由于本实验是模拟处理器调度的 功能，所以，对被选中的进程并不实际的启动运行，而是执行：已运行

9、时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。4.2详细设计首先每一个进程用一个进程控制块 PCB来代表。进程控制块的格式如表 3 所示。表3 PCB控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。已运行时间一一假设进程已经运行的单位时间数，初始值为“ 0”。状态一一有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“ R' 表示。当一个进程运行结束后，它的状态为“结束”，用“E”表示。每次运行所设计的处理器调度程序前， 为每个进程任意确定它的“要求运行 时间”。把五个进程按顺序排成循环链队列，用指针指出队列连接情况。用指针 表示轮到运行的进

10、程，如表4描述述所示表4进程队列PCB1PCB2PCB3PCB4PCB54.3程序详细设计步骤首先建立PCB的数据结构，为了便于正确输出，加上了进程结束标志flag 。输入进程信息(包括进程名和要求运行的时间)，并为每个进程创建一个PCB并初始化形成一个循环链队列，用函数 creatPCB()来实现。建立函数judge()用来判断进程全部运行结束标志，即当所有进程的状态变 为e'(即完成状态)后，循环结束，表示所有进程都已运行成功。建立时间片轮转算法 creatProcess ()对进程进行轮转运行，首先指针s指向第一个进程PCB即s=front，判断该进程的状态是否为r'(就

11、绪状态)， 即if(s->condition = 'r')，若是则表示此进程尚未执行结束，则执行s->worked_time+ 且 s->need_time- ，if(s->need_time=0) ，贝U表示此进程已 运行结束，将其状态置为结束，即s->co nditio n='e'，并根据状态位输出完成信息，且以后不会再运行此进程。将指针指向下个进程，s=s->next，并判断所有进程是否已全部运行结束，没有则重复上面算法。当所有进程的状态位都变成 e'表示所有进程运行完成，则循环结束。建立主函数main(),输入

12、进程数N,调用初始化循环链队列函数 creatPCB() 和时间片轮转算法creatProcess(N)，每次选中进程的进程名以及运行一次后进 程队列的变化，实现处理器的调度。5. 程序的运行及结果1 )主菜单：输入选项1:进程创建及结果2:结束，如图5所示。图5主菜单2）运行过程：选择1,创建进程。输入进程总数，进程的名称a 、b,各进程到达的时间，各进程服务的时间，以及时间片q的值。当输入进程为2时，各进 程到达时间为3,2，各进程服务时间为2,3，以及时间片q=2时的情况，输入 情况如图6所示。图6创建进程3）输入成功后，按回车键，进程在程序中的具体实现情况即：时间轮转情况。进程在调度算

13、法中，计算出的具体的完成时间，周转时间，带权时间，平均周转时间，平均带权周转时间，如图 7所示。亡 *: Pr oe ra& FxLesHicrosof ± VasuaX StudiioX ArProi ec1t sddXDebucX d.d« dzq图7进程运行结果名iT-nr:rI行一 辿1苗- 在右在在存- 止正7F1L讦一 » ft 11 e 一一 d WVJ1J卢.JJV一 卅'JI讲肯讲一 - s SB HB 一一 TTTTT3）选择2:退出界面，如图&图8退出界面6心得体会首先，我认为这次课程设计是对学习操作系统的一次综合考察

14、， 锻炼我综合 分析问题、解决问题的能力。初次找到课程设计的题目时，为程序本身的简单而 窃喜过；实验过程中也出现了一些难题需要解决， 为此去苦苦探索过。课程设计 期间，曾多次登录网站浏览网页，为了弥补一些知识上的纰漏，一次次实践。当 我的想法得到实现，又学会了新的知识的时候，心中满是欣喜，或许这是实践出 真知的真实验证，有付出就有回报的真实写照吧。其次，我们感受了真诚的友谊。在实验中，遇到的问题是多方面的，而且有 那么一部分是以前学过的问题，但是已经忘却或是以前没有真正的理解过。但是你会发现就在你的身边，会有那么一批人在背后热心的帮助你，这好像是人生的 一种历程，团队的协作和彼此心的交流让我们

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

16、计算机操作系统的认识J.改革与开放,2011,04:140. 汤小丹.计算机操作系统（第4版）M.西安：电子科技大学出版社.2014.5附录：#in clude<iostream.h>#i nclude<ioma nip.h>#in clude<malloc.h>typedef int QEIemType;static const int MaxNum=100;typedef struct QNode QElemType data;struct QNode *n ext;QNode,*QueuePtr;typedef struct QueuePtr fron

17、t;QueuePtr rear;Lin kQueue;struct PCB int ArrivalTime;int ServiceTime;char nu mber;mMaxNum;int Ini tQueue(L in kQueue &Q);int DestroyQueue(L in kQueue &Q);int En Queue(L in kQueue & Q,QElemType e);int DeQueue(L in kQueue & Q,QElemType e);int QueueEmpty(L in kQueue &Q);void chioce

18、(struct PCB pcb,int n);void caida n();void create();int n ,q,Fi ni shedTimeMaxNum,WholeTimeMaxNum;double WeightWholeTimeMaxNum,Average_WT=0,Average_WWT=0; Lin kQueue Q;void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q);void mai n() while(1) / system("cls");cout<<e

19、ndl;caida n();int n;cout<<" 请选择(1-2): "<<endl;cin»n;if(n <1| n>2)cout<<" 输入有误，请重新输入 "<<e ndl;switch( n) case 1:create();break; case 2:retur n ;RR算法的具体实现void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q)int coun tTime=0,e;chioc

20、e( m,n);if(ArrivalTimeO=O)coun tTime=0;elsecoun tTime=mO.ArrivalTime;int STimeMaxNum,pushedMaxNum;for(i nt i=0;i <n ;i+) STimei=mi.ServiceTime;pushedi=0;Ini tQueue(Q);En Queue(Q,0);pushed0=1;int time=mO.ArrivalTime;while(QueueEmpty(Q)=false)e=DeQueue(Q,e);if(STimee>q)STimee=STimee-q;coun tTime

21、+=q;elsecou ntTime+=STimee;STimee=0;Fin ishedTimee=cou ntTime;while(time<co un tTime)if(STime>0)cout<<" 时刻"<<setw(2)<<time<<":进程"<<e<<"正在运行"<<endl;time+;for(i=1;i< n;i+)if(STime!=O&&i !=e&&mi.ArrivalTime

22、<cou ntTime&&pushedi=O|STime!= 0&&i!=e&&mi.ArrivalTime=co un tTime)En Queue(Q,i);pushedi=1;if(STimee>0)判断进程e是否已执行完En Queue(Q,e);for(i=0;i <n ;i+) /求周转时间和带权周转时间WholeTimei=Fi nishedTimei-mi.ArrivalTime;WeightWholeTimei=(double)(WholeTimei*1.000000/mi.ServiceTime); Aver

23、age_WT+=WholeTimei;Average_WWT+=WeightWholeTimei;-Average_WT/= n; 求平均周转时间Average_WWT/= n;求平均带权周转时间/ 输出cout<<""<<e ndl;cout<<e ndl; cout<<e ndl;cout<<"进程运行的结果是："<<endl;cout<<"-"<<e ndl;cout<<"进程名称:"<<&

24、quot;"for(i=0;i <n ;i+)cout<<setw(8)<<mi. nu mber <<"" cout<<e ndl;cout<<"到达时间："<<""for(i=0;i <n ;i+)cout<<setw(8)<<mi.ArrivalTime<<"" cout<<e ndl;cout<<"服务时间:"<<"

25、;"for(i=0;i <n ;i+)cout<<setw(8)<<mi.ServiceTime<<""cout<<e ndl;cout<<"完成时间:"<<""for(i=0;i< n;i+)cout<<setw(8)< <Fini shedTimei<<""cout<<e ndl;cout<<"周转时间:"<<"&qu

26、ot;for(i=0;i< n;i+)cout<<setw(8)<<WholeTimei<<""cout<<e ndl;cout<<"带权周转："<<""for(i=0;i< n;i+)cout<<setw(8)<<setiosflags(ios:fixed)<<setprecisi on( 2)<<WeightWholeTimei<<"II.5cout<<e ndl;c

27、out<<"-"<<e ndl;cout<<"平均周转时间为："<<Average_WT<<endl;cout<<"平均带权周转时间为:"<<Average_WWT<<endl; DestroyQueue(Q); -/初始化链队列Qint Ini tQueue(L in kQueue &Q)Q.fro nt=Q.rear=(QueuePtr)malloc(sizeof(QNode);Q.fro nt-> next=NULL;r

28、eturn 1;销毁链队列Qint DestroyQueue(L in kQueue &Q)while(Q.fro nt)Q.rear=Q.fro nt-> next;free(Q.fro nt);Q.fro nt=Q.rear;return 1;/入队int En Queue(L in kQueue & Q,QElemType e)QueuePtr p=(QueuePtr)malloc(sizeof(QNode);p->data=e;p->n ext=NULL;Q.rear- >n ext=p;Q.rear=p;return 1;/出队，并用e返回出队

29、节点的元素值int DeQueue(L in kQueue & Q,QElemType e)QueuePtr p;if(Q.fr on t=Q.rear)return 0;p=Q.fr ont->n ext;e=p->data;Q.front->n ext=p->n ext;if(Q.rear=p)Q.rear=Q.fro nt;free(p); return e;/判断链队列Q是否为空int QueueEmpty(L in kQueue &Q) if(Q.fron t=Q.rear) return true;else return false;/选择排

30、序，对结构体中的关键字到达时间，按从小到大的顺序排列 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 caida n()cout<<"*"<<e ndl;cout<<"*1.创建及结果*"<<e ndl;cout<<"*2.结束*"<<e ndl;void create() cout<<"请输入进程总数 n的值(0