时间片轮转算法

1、一、实验目的（1）在单处理器情况下按时间片轮转算法实现处理器调度，输出运行动态变化过程。（2）通过算法的实现加深了解处理器调度的工作。二、实验内容输入实现现处理器器调度的的几个进进程信息息，任意意确定一一组“要求运运行时间间”，启动动所设计计的处理理器调度度程序，显示逐逐次被选选中进程程的进程程名以及及进程控控制块的的动态变变化过程程。实验步骤骤1、任务务分析：时间片片轮转的的主要思思想就是是按顺序序为每一一个进程程一次只只分配一一个时间间片的时时间。算算法要完完成的功功能就是是将各个个进程按按照时间间片轮转转运行的的动态过过程显示示出来。时间片片轮转算算法的主主要实现现过程是是首先为为每一个

2、个进程创创建一个个进程控控制块，定义数据据结构，说明进进程控制制块所包包含的内内容，有有进程名名、进程程所需运运行时间间、已运运行时间间和进程程的状态态以及指指针的信信息。实实现的过过程即运运用指针针指向某某一个进进程，判判断当前前的进程程是否是是就绪状状态“r”，如果果是，则则为该进进程分配配一个时时间片，同时，已运行行时间加加一且要要求运行行的时间间减一，如此循循环执行行，当某某一个进进程的所所需要运运行的时时间减少少至0时时，则将将该进程程的状态态设置为为“e”。然后，将指针针指向下下一个未未运行完完成的进进程，重重复判断断，直至至所有的的进程都都运行结结束。2、概要要设计：（1）所所用

3、数据据结构及及符号说说明typeedeff sttrucct PPCBchaar nnamee100; /进进程名strructt PCCB *nexxt; /循循环链指指针intt neeed_timme; /要要求运行行时间intt woorkeed_ttimee; /已已运行时时间，初初始为00chaar ccondditiion; /进进程状态态，只有有“就绪”和“结束”两种状状态intt fllag; /进进程结束束标志，用于输输出PCBB;PCB *frrontt,*rrearr; /循环环链队列列的头指指针和尾尾指针int N; /N为进程程数（2）主主程序的的流程图图：开始输入

4、进程数N输入各进程信息为每个进程创建PCB并初始化形成一个循环链队列指针指向循环链队列第一个进程进程是否r运行时间+1且剩余时间-1 Y剩余时间=0？ Y将进程状态置为e（完成）指针指向队列中下个进程所有进程是否完成 N 结束 Y（3）程程序说明明：处理理器调度度总是选选择指针针指示的的进程运运行。由由于本实实验是模模拟处理理器调度度的功能能，所以以，对被被选中的的进程并并不实际际的启动动运行，而是执执行：已已运行时时间+11来模拟拟进程的的一次运运行，表表示进程程已经运运行过一一个单位位的时间间。3、详细细设计（1）首首先每一一个进程程用一个个进程控控制块PPCB来来代表。进程控控制块的的格

5、式为为：进程名指针要求运行行时间已运行时时间状态其中，进进程名作为为进程的的标识，如Q11、Q2等。指针进程按按顺序排排成循环环链队列，用指针针指出下下一个进进程的进进程控制制块的首首地址，最后一一个进程程的指针针指出第第一个进进程的进进程控制制块首地地址。要求运行行时间假设设进程需需要运行行的单位位时间数数。已运行时时间假设进进程已经经运行的的单位时时间数，初始值值为“0”。状态有两种种状态，“就绪”和“结束”，初始始状态都都为“就绪”，用“R”表示。当一个个进程运运行结束束后，它它的状态态为“结束”，用“E”表示。（2）每每次运行行所设计计的处理理器调度度程序前前，为每每个进程程任意确确定

6、它的的“要求运运行时间间”。把五个进进程按顺顺序排成成循环链链队列，用指针针指出队队列连接接情况。用指针针表示轮轮到运行行的进程程，如下下图描述述所示：K1Q1K2Q2 K3Q3 K4Q4 K5Q5K2K3K4K5K12431200000RRRRRPCB11PCB22PCB33PCB44PCB55（3）程程序详细细设计步步骤：a.首先先建立PPCB的的数据结结构，为为了便于于正确输输出，加加上了进进程结束束标志fflagg。输入入进程信信息（包包括进程程名和要要求运行行的时间间），并并为每个个进程创创建一个个PCBB并初始始化形成成一个循循环链队队列，用用函数ccreaatPCCB()来实现现

7、。b.建立立函数jjudgge()用来判判断进程程全部运运行结束束标志，即当所所有进程程的状态态变为e（即完完成状态态）后，循环结结束，表表示所有有进程都都已运行行成功。c.建立立时间片片轮转算算法crreattProocesss（）对进程程进行轮轮转运行行，首先先指针ss指向第第一个进进程PCCB，即即s=ffronnt，判判断该进进程的状状态是否否为r（就绪绪状态），即if(s-conndittionn = rr)，若是则表表示此进进程尚未未执行结结束，则则执行ss-wworkked_timme+且s-neeed_ttimee-，if(s-neeed_ttimee=00)，则则表示此此进程

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

9、4、调试试分析：a调试试过程中中遇到的的问题及及解决方方案开始运行行到Q55运行完完成后显显示错误误，如下下图所示示：原因：经经检查程程序发现现语句iif(ss-ccondditiion=ee )prrinttf(进程%ss已经运运行完成成！nnn,s-naame);有有错误，因为当当某个进进程运行行完成后后，其状状态标志志已修改改为ee，所所以再次次循环运运行未完完成的进进程时，当运行行到此句句时仍会会将前面面已完成成的进程程重新输输出一遍遍完成信信息，导导致输出出错误。解决方案案：为每每个进程程加上一一个结束束标志fflagg，并赋赋初值为为0，当进进程运行行完成后后，将fflagg改为1

10、，再将将后面输输出改为为if(s-conndittionn=e | s-flaag=0 )prrinttf(进程%ss已经运运行完成成！nnn,s-naame);s-fllag=0;，这这样在前前面进程程运行完完成输出出后，后后面再循循环时就就不会重重新输出出一遍了了。b改进进设想：本实验验较简单单，但还还不够完完善，如如未实现现插入进进程功能能，即进进程在运运行过程程中可以以插入其其他的进进程再运运行。还还有未进进行进程程优先级级判别，本实验验默认进进程的优优先级按按输入的的先后顺顺序从大大到小排排列的，还有其其他功能能等，希希望在以以后的实实验中逐逐步完善善。5、测试试结果：a首先先输出五

11、五个进程程的初始始状态b开始始从进程程Q1开始始按时间间片轮转转运行进进程，QQ4先运运行完成成c.接着着Q1运行行完成d.接着着Q5运行行完成e.再QQ3运行行完成f.最后后Q2运行行完成四、实验验总结因在早期期的时间间片轮转转法中，系统将将所有的的就绪进进程按照照先来先先服务的的原则排排成一个个队列，每次调调度是，把CPPU分配配给队首首进程，并令其其执行一一个时间间片。当当执行的的时间片片用完时时，调度度程序停停止该进进程的执执行，并并将它送送往就绪绪队列的的末尾；然后，再把处处理机分分配给就就绪队列列中新的的队首进进程，同同时也让让它执行行一个时时间片。在时间间片轮转转算法中中，时间间

12、片的大大小对系系统性能能有很大大的影响响。如果果选择很很小的时时间片将将有利于于短作业业，因为为它能较较快地完完成，但但会频繁繁的发生生中断、进程上上下文的的切换，从而增增加系统统的开销销；反之之，如果果选择太太长时间间片，使使得每个个进程都都能在一一个时间间片内完完成，所所以，一一般定为为时间片片略大于于一次典典型地交交互所需需要的时时间。在完成时时间片轮轮转算法法的实现现过程中中，我们们遇到了了一些问问题，比比如怎样样运用循循环队列列，如何何设计结结构体等等等，也也积极配配合并思思考进行行解决。整体来来说，我我们的算算法虽然然实现了了体现进进程动态态运行变变化的过过程，但但是相对对而言比比

13、较简单单。实验验中，我我们小组组不断讨讨论对算算法进行行优化，使得运运行结果果看起来来更容易易理解，也达到到了处理理机调度度的功能能。做实实验让我我们对于于时间片片轮转的的思想理理解的更更加透彻彻，巩固固了理论论知识的的学习。实验心得得体会：首先，我们认为这这次课程程设计是是对学习习操作作系统的一次次综合考考察，锻锻炼我们们综合分分析问题题、解决决问题的的能力。初次得到到课程设设计的题题目时，为程序序本身的的简单而而窃喜过过；实验验过程中中也出现现了一些些难题需需要解决决，为此此去苦苦苦探索过过。课程程设计期期间，几几乎有几几天我们们完全投投入进去去了，就就像是在在做一个个相当重重要的项项目一

14、样样的感觉觉。曾经经跑过图图书馆几几次，只只是为了了一种新新的想法法得到实实现，也也曾多次次登录网网站浏览览网页，为了弥弥补一些些知识上上的纰漏漏，为此此曾洒下下了真实实的汗水水。当我我们的想想法得到到实现，又学会会了新的的知识的的时候，心中满满是欣喜喜，或许许这是实实践出真真知的真真实验证证，有付付出就有有回报的的真实写写照吧。其次，我我们感受受了真诚诚的友谊谊。在实实验中，遇到的的问题是是多方面面的，而而且有那那么一部部分是以以前学过过的C问问题，但但是已经经忘却或或是以前前没有真真正的理理解过。但是你你会发现现就在你你的身边边，会有有那么一一批人在在背后热热心的帮帮助你，让你身身处困境境

15、却感到到无限希希望。这这好像是是人生的的一种历历程，风风风雨雨雨中我们们一起走走过，然然后为了了一些坑坑坑洼洼洼彼此真真诚的帮帮助过和和无私的的付出过过。团队队的协作作和彼此此心的交交流让我我们彼此此丰厚起起来，这这也是我我们成长长中必不不可失的的重要部部分。最后，我我认识到到了自己己的不足足。平心心而论，以前真真的没有有认真的的学习过过，即使使是在听听课，可可是后来来却没有有对学习习中出现现的问题题而仔细细分析过过。得过过且过，迷失了了我前进进的方向向，而现现在却又又重新敞敞开了。不论是是以后的的学习还还是工作作，我想想这都是是很重要要的，我我们需要要不断进进步的动动力。总的说来来知识上上的

16、收获获很是重重要，精精神上的的丰收也也是更加加可喜的的，让我我知道了了学无止止境的道道理。我我们每一一个人永永远不能能满足于于现有的的成就，人生就就像在爬爬山，一一座山峰峰的后面面还有更更高的山山峰在等等着你。挫折是是一份财财富，经经历是一一份拥有有。这次次课程设设计必将将成为我我人生旅旅途上一一个非常常美好的的回忆。五、附录录实验源程程序如下下：#inccluddesstdiio.hh#inccluddecconiio.hh#inccluddemmallloc.h#inccluddesstriing.h#deffinee NUULL 0typeedeff sttrucct PPCBchaar

17、 nnamee100; /进进程名strructt PCCB *nexxt; /链链指针intt neeed_timme; /要要求运行行时间intt woorkeed_ttimee; /已已运行时时间chaar ccondditiion; /进进程状态态，只有有“就绪”和“结束”两种状状态intt fllag; /进进程结束束标志PCBB;PCB *frrontt,*rrearr; int N; /N为进进程数voidd crreattPCBB()/为每每个进程程创建一一个PCCB并初初始化形形成一个个循环链链队列PCBB *pp,*ll;l = (PPCB *)mmallloc(sizze

18、off(PCCB);priintff(PPleaase entter proocesss nnamee annd ttimeen);scaanf(%ss%d,l-naame,&l-neeed_timme);l-conndittionn = r; /进程程初始状状态为就就绪l-worrkedd_tiime = 00;l-nexxt=NNULLL;l-flaag=00;froont=l;forr(innt ii = 1;ii nnamee,&pp-nneedd_tiime);p-coondiitioon = rr;p-woorkeed_ttimee = 0;p-fllag=0; l-neext =

19、 pp;l=l-nexxt;reaar=ll;reear-neext=froont;voidd ouutpuut() /进程输输出函数数 priintff(nnamee ruuntiime neeedtiime staaten);for(intt j=1;jjnamme,ffronnt-worrkedd_tiime,froont-neeed_timme,ffronnt-conndittionn); frrontt=frrontt-nnextt;priintff(n);int juddge(PCBB *pp) /判断所所有进程程运行结结束intt fllag = 11;forr(innt ii=0;icoondiitioon != e)fflagg = 0;bbreaak;p=p-nexxt;retturnn fllag;