操作系统课程设计时间片轮转算法.doc

课程设计说明书 NO.16时间片轮转算法1. 课程设计的目的通过操作系统课程设计，通过对作业调度算法的设计，深入理解作业调度的原理，从原理分析、物理设计，到功能分析和应用程序的最终实现，让学生亲自动手参与一个操作系统的模拟设计，真正理解和掌握操作系统的有关内容，加深对操作系统，软件工程，程序设计语言的理论知识的理解和应用水平；在理论和实验教学基础上进一步巩固已学基本理论及应用知识并加以综合提高；学会将知识应用于实际的方法，提高分析和解决问题的能力，增强对手能力；并更好的理解和消化课本所学的知识，为毕业设计和以后工作打下必要基础。2. 课程设计的开发语言 Windows操作系统Microsoft VisualC+ 6.03. 功能描述时间片轮转的主要思想就是按顺序为每一个进程一次只分配一个时间片的时间。算法要完成的功能就是将各个进程按照时间片轮转运行的动态过程显示出来。时间片轮转算法的主要实现过程是首先为每一个进程创建一个进程控制块，定义数据结构，说明进程控制块所包含的内容，有进程名、进程所需运行时间、已运行时间和进程的状态以及指针的信息。实现的过程即运用指针指向某一个进程，判断当前的进程是否是就绪状态“r”，如果是，则为该进程分配一个时间片，同时，已运行时间加一且要求运行的时间减一，如此循环执行，当某一个进程的所需要运行的时间减少至0时，则将该进程的状态设置为“e”。然后，将指针指向下一个未运行完成的进程，重复判断，直至所有的进程都运行结束。4. 方案论证4.1 概要设计4.1.1所用数据结构及符号说明typedef struct PCBchar name10; /进程名struct PCB *next; /循环链指针int need_time; /要求运行时间int worked_time; /已运行时间，初始为0char condition; /进程状态，只有“就绪”和“结束”两种状态int flag; /进程结束标志，用于输出PCB;PCB *front,*rear; /循环链队列的头指针和尾指针 int N; /N为进程数4.1.2主程序的流程图图1：主程序的流程图4.1.3程序说明：处理器调度总是选择指针指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。4.2详细设计首先每一个进程用一个进程控制块PCB来代表。进程控制块的格式为：进程名指针要求运行时间已运行时间状态图2： PCB控制块其中，进程名作为进程的标识，如Q1、Q2等。指针进程按顺序排成循环链队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。已运行时间假设进程已经运行的单位时间数，初始值为“0”。状态有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。当一个进程运行结束后，它的状态为“结束”，用“E”表示。每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。把五个进程按顺序排成循环链队列，用指针指出队列连接情况。用指针表示轮到运行的进程，如下图描述所示： K1Q1 K2Q2 K3Q3 K4Q4 K5Q5K2K3K4K5K12431200000RRRRRPCB1PCB2PCB3PCB4PCB5图3：进程队列4.3程序详细设计步骤：a.首先建立PCB的数据结构，为了便于正确输出，加上了进程结束标志flag。输入进程信息（包括进程名和要求运行的时间），并为每个进程创建一个PCB并初始化形成一个循环链队列，用函数creatPCB()来实现。b.建立函数judge()用来判断进程全部运行结束标志，即当所有进程的状态变为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，并根据状态位输出完成信息，且以后不会再运行此进程。将指针指向下个进程，s=s-next，并判断所有进程是否已全部运行结束，没有则重复上面算法。当所有进程的状态位都变成e表示所有进程运行完成，则循环结束。d.建立主函数main(),输入进程数N，调用初始化循环链队列函数creatPCB()和时间片轮转算法creatProcess(N)，每次选中进程的进程名以及运行一次后进程队列的变化，实现处理器的调度。调试分析：5. 程序的运行及结果5.1错误调试开始运行到Q5运行完成后显示错误，如下图所示：图4：错误调试原因：经检查程序发现语句if(s-condition=e )printf(进程%s已经运行完成！nn,s-name);有错误，因为当某个进程运行完成后，其状态标志已修改为e，所以再次循环运行未完成的进程时，当运行到此句时仍会将前面已完成的进程重新输出一遍完成信息，导致输出错误。解决方案：为每个进程加上一个结束标志flag，并赋初值为0，当进程运行完成后，将flag改为1，再将后面输出改为if(s-condition=e | s-flag=0 )printf(进程%s已经运行完成！nn,s-name);s-flag=0;，这样在前面进程运行完成输出后，后面再循环时就不会重新输出一遍了。b改进设想：本实验较简单，但还不够完善，如未实现插入进程功能，即进程在运行过程中可以插入其他的进程再运行。还有未进行进程优先级判别，本实验默认进程的优先级按输入的先后顺序从大到小排列的，还有其他功能等，希望在以后的实验中逐步完善。5.2测试结果a首先输出五个进程的初始状态图5：进程状态b开始从进程Q1开始按时间片轮转运行进程，Q4先运行完成图6：Q4进程完成c.接着Q1运行完成图7：Q1进程完成d.接着Q5运行完成图8：Q5进程完成e.再Q3运行完成图9：Q3进程完成f.最后Q2运行完成图10：Q2进程完成6. 心得体会因在早期的时间片轮转法中，系统将所有的就绪进程按照先来先服务的原则排成一个队列，每次调度是，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。在时间片轮转算法中，时间片的大小对系统性能有很大的影响。如果选择很小的时间片将有利于短作业，因为它能较快地完成，但会频繁的发生中断、进程上下文的切换，从而增加系统的开销；反之，如果选择太长时间片，使得每个进程都能在一个时间片内完成，所以，一般定为时间片略大于一次典型地交互所需要的时间。在完成时间片轮转算法的实现过程中，我们遇到了一些问题，比如怎样运用循环队列，如何设计结构体等等，也积极配合并思考进行解决。整体来说，我们的算法虽然实现了体现进程动态运行变化的过程，但是相对而言比较简单。实验中，我们小组不断讨论对算法进行优化，使得运行结果看起来更容易理解，也达到了处理机调度的功能。做实验让我们对于时间片轮转的思想理解的更加透彻，巩固了理论知识的学习。实验心得体会：首先，我们认为这次课程设计是对学习操作系统的一次综合考察，锻炼我们综合分析问题、解决问题的能力。初次得到课程设计的题目时，为程序本身的简单而窃喜过；实验过程中也出现了一些难题需要解决，为此去苦苦探索过。课程设计期间，几乎有几天我们完全投入进去了，就像是在做一个相当重要的项目一样的感觉。曾经跑过图书馆几次，只是为了一种新的想法得到实现，也曾多次登录网站浏览网页，为了弥补一些知识上的纰漏，为此曾洒下了真实的汗水。当我们的想法得到实现，又学会了新的知识的时候，心中满是欣喜，或许这是实践出真知的真实验证，有付出就有回报的真实写照吧。其次，我们感受了真诚的友谊。在实验中，遇到的问题是多方面的，而且有那么一部分是以前学过的C问题，但是已经忘却或是以前没有真正的理解过。但是你会发现就在你的身边，会有那么一批人在背后热心的帮助你，让你身处困境却感到无限希望。这好像是人生的一种历程，风风雨雨中我们一起走过，然后为了一些坑坑洼洼彼此真诚的帮助过和无私的付出过。团队的协作和彼此心的交流让我们彼此丰厚起来，这也是我们成长中必不可失的重要部分。最后，我认识到了自己的不足。平心而论，以前真的没有认真的学习过，即使是在听课，可是后来却没有对学习中出现的问题而仔细分析过。得过且过，迷失了我前进的方向，而现在却又重新敞开了。不论是以后的学习还是工作，我想这都是很重要的，我们需要不断进步的动力。7. 程序源代码实验源程序如下：#includestdio.h#includeconio.h#includemalloc.h#includestring.h#define M 5 /物理页数#define Myprintf printf(|-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|n)typedef struct PCBint ID;int ReachTime;int TotalTime;PCB;/进程号，到达时间和服务时间typedef struct NOTE /备份int ID;int TotalTime;NOTE;PCB AM; /5个进程PCB aM;NOTE temp;int queue50; /记录调度的进程int K=0;/调度进程数组的标识void INIT()/初始化int i;for(i=0;iM;i+)Ai.ID=-1;int GetNum()/计算进程数int i,j=0;for(i=0;iM;i+)if(Ai.ID!=-1)j+;return j;int GetReach(int time)/找出到达进程号int i;for(i=0;iM;i+)if(ai.ReachTime=time)ai.ReachTime=100;return i;return -1;int GetInsert()/找出插入位置int i;for(i=0;iM;i+)if(Ai.ID=-1)return i;return -1;void Forward(int num)/前移int i;for(i=0;inum-1;i+)Ai.ID=Ai+1.ID;Ai.TotalTime=Ai+1.TotalTime;Anum-1.ID=-1;void Process()/执行进程queueK=A0.ID;K+;A0.TotalTime-;temp.ID=A0.ID;temp.TotalTime=A0.TotalTime;void main()int i;int time;int t=0;int reach;int insert;int num;printf(RR算法nn);INIT();for(i=0;iM;i+)printf(请输入进程ID：);scanf(%d,&ai.ID);printf(请输入到达时间：);scanf(%d,&ai.ReachTime);printf(请输入服务时间：);scanf(%d,&ai.TotalTime);for(i=0;iM;i+)/运行时间t=t+ai.TotalTime;for(i=0;i50;i+)/初始化queuei=-1;for(time=0;time=t;time+)reach=GetReach(time);if(reach!=-1)/有进程到达insert=GetInsert();Ainsert.ID=areach.ID;Ainsert.TotalTime=areach.TotalTime;num=GetNum();if(num=1)continue;/进程数为1else/进程数不为1Process();Forward(num);if(temp.TotalTime!=0)Anum-1.ID=temp.ID;Anum-1.TotalTime=temp.TotalTime;else/没有进程到达num=GetNum();if(num=1)/进程数为1Process();if(temp.TotalTime=0)A0.ID=-1;else if(num=0)continue;/进程数为0elseProcess();Forward(num);if(temp.TotalTime!=0)Anum-1.ID=temp.ID;Anum-1.TotalTime=temp.TotalTime;printf(n);printf(调度顺序为：n);Myprintf;for(i=0;i50;i+)if(queuei!=-1)printf(|%2d ,queuei);printf(|n