时间片轮转算法课程设计

《时间片轮转算法课程设计》由会员分享，可在线阅读，更多相关《时间片轮转算法课程设计（9页珍藏版）》请在金锄头文库上搜索。

1、本课程设计以 Windows 操作系统为实验平台，进行源代码分析和修改。通过 该课程设计，使学生掌握 Windows 操作系统各部分结构、实现机理和各种典型算 法；系统地了解操作系统的设计和实现思路，运用内核开发环境实现对内核的修 改，培养学生的系统设计能力，并了解操作系统的发展动向和趋势。二、实验内容1分析设计内容，给出解决方案（要说明设计实现的原理，采用的数据结构）。2画出程序的基本结构框图和流程图。3对程序的每一部分要有详细的设计分析说明。4源代码格式要规范。5设计合适的测试用例，对得到的运行结果要有分析。6设计中遇到的问题，设计的心得体会。7按期提交完整的程序代码、可执行程序和课程设计

2、报告。三、实验步骤1、任务分析：时间片轮转的主要思想就是按顺序为每一个进程一次只分配一个时间片 的时间。算法要完成的功能就是将各个进程按照时间片轮转运行的动态过程显示 出来。时间片轮转算法的主要实现过程是首先为每一个进程创建一个进程控制 块，定义数据结构，说明进程控制块所包含的内容，有进程名、进程所需运行时 间、已运行时间和进程的状态以及指针的信息。实现的过程即运用指针指向某一 个进程，判断当前的进程是否是就绪状态r”如果是，则为该进程分配一个时 间片，同时，已运行时间加一且要求运行的时间减一，如此循环执行，当某一个 进程的所需要运行的时间减少至0时，则将该进程的状态设置为“e”然后，将指针指

3、向下一个未运行完成的进程，重复判断，直至所有的进程都运行结束2、概要设计：（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 为进程数（2）主程序的流程图开始L,JYY输入进程数NY输入各进程信息（3

4、）程序说明：处理器调度总是选择指针指示的进程运行 模拟处理器调度的功能，所已运行时间+1来模拟进程的一次运形成一表示进程已经运行过一个单位的时间由于本实验是实际的启动运行，而是执行:3、详细设计1（1）首先每一个进程用一个进程控制块链队B来代表。进程控制块的格式为:指针进行已运行时间列第一个进程进程名其中，进程名指针 进程按顺序排成的首地址，最后1运行状态+1且剩余时间-1、Q2 等。出下一个进程的进程控制块 个进程的指针指出第一个进程的进程控制块首地址。作为进程的将进程状态置为e（完指针指向队列中下个进程要求运行时间假设进程需要运行的单位时间数。已运行时间假设进程已经运行的单位时间数，初始值

5、为“0”。状态一一有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R” 表示。当一个进程运行结束后，它的状态为“结束”，用“E”表示。(2)每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要 求运行时间”。把五个进程按顺序排成循环链队列，用指针指出队列连接情况。用指针表示轮到运行的进程，如下图描述所示：a. 首先建立PCB的数据结构，为了便于正确输出，加上了进程结束标志flag。 输入进程信息(包括进程名和要求运行的时间)，并为每个进程创建一个 PCB 并初始化形成一个循环链队列，用函数creatPCB()来实现。b. 建立函数judge()用来判断进程全部运行结束标志，即

6、当所有进程的状态 变为e(即完成状态)后，循环结束，表示所有进程都已运行成功。c. 建立时间片轮转算法creatProcess()对进程进行轮转运行，首先指针s 指向第一个进程PCB，即s=fron t,判断该进程的状态是否为r(就绪状态)， 即 if(s-condition = r) ，若是则表示此进程尚未执行结束，则执行 sworked_time+且 s-need_time， if(sneed_time二二0)，则表示此进程已 运行结束，将其状态置为结束，即s-condition二e，并根据状态位输出完成 信息，且以后不会再运行此进程。将指针指向下个进程，s=s-next，并判断所 有进程

7、是否已全部运行结束，没有则重复上面算法。当所有进程的状态位都变 成 e 表示所有进程运行完成，则循环结束。d. 建立主函数main(),输入进程数N，调用初始化循环链队列函数creatPCB() 和时间片轮转算法creatProcess(N)，每次选中进程的进程名以及运行一次后进 程队列的变化，实现处理器的调度。4、调试分析：a. 调试过程中遇到的问题及解决方案开始运行到Q5运行完成后显示错误，如下图所示：原因：经检查程序发现语句if(s-condition=e )printf(进程%s已经 运行完成！ nn,s-name);有错误，因为当某个进程运行完成后，其状态标志 已修改为e，所以再次循

8、环运行未完成的进程时，当运行到此句时仍会将前 面已完成的进程重新输出一遍完成信息，导致输出错误。解决方案：为每个进程加上一个结束标志flag，并赋初值为0，当进程运行 完成后， 将 flag 改为 1， 再将后面输出改为 if(s-condition=e | s-flag=0 )printf(进程s 已经运行完成！ nn,s-name);s-flag=O;， 这样在前面进程运行完成输出后，后面再循环时就不会重新输出一遍了。b. 改进设想：本实验较简单，但还不够完善，如未实现插入进程功能，即 进程在运行过程中可以插入其他的进程再运行。还有未进行进程优先级判别，本 实验默认进程的优先级按输入的先后

9、顺序从大到小排列的，还有其他功能等，希 望在以后的实验中逐步完善。5、测试结果：a 首先输出五个进程的初始状态b 开始从进程Q1开始按时间片轮转运行进程，Q4先运行完成c. 接着Q1运行完成d. 接着 Q5 运行完成e. 再Q3运行完成f. 最后 Q2 运行完成四、实验总结因在早期的时间片轮转法中，系统将所有的就绪进程按照先来先服务的原则 排成一个队列，每次调度是，把 CPU 分配给队首进程，并令其执行一个时间片。 当执行的时间片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末 尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时 间片。在时间片轮转算法中，时间片的大

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

11、解的更加透彻， 巩固了理论知识的学习。实验心得体会：首先，我们认为这次课程设计是对学习操作系统的一次 综合考察，锻炼我们综合分析问题、解决问题的能力。初次得到课程设计的题目时，为程序本身的简单而窃喜过；实验过程中也出 现了一些难题需要解决，为此去苦苦探索过。课程设计期间，几乎有几天我们完 全投入进去了，就像是在做一个相当重要的项目一样的感觉。曾经跑过图书馆几 次，只是为了一种新的想法得到实现，也曾多次登录网站浏览网页，为了弥补一 些知识上的纰漏，为此曾洒下了真实的汗水。当我们的想法得到实现，又学会了 新的知识的时候，心中满是欣喜，或许这是实践出真知的真实验证，有付出就有 回报的真实写照吧。其次

12、，我们感受了真诚的友谊。在实验中，遇到的问题是多方面的，而且有 那么一部分是以前学过的 C 问题，但是已经忘却或是以前没有真正的理解过。 但是你会发现就在你的身边，会有那么一批人在背后热心的帮助你，让你身处困 境却感到无限希望。这好像是人生的一种历程，风风雨雨中我们一起走过，然后 为了一些坑坑洼洼彼此真诚的帮助过和无私的付出过。团队的协作和彼此心的交 流让我们彼此丰厚起来，这也是我们成长中必不可失的重要部分。最后，我认识到了自己的不足。平心而论，以前真的没有认真的学习过，即 使是在听课，可是后来却没有对学习中出现的问题而仔细分析过。得过且过，迷失了我前进的方向，而现在却又重新敞开了。不论是以后

13、的学习还是工作，我想 这都是很重要的，我们需要不断进步的动力。总的说来知识上的收获很是重要，精神上的丰收也是更加可喜的，让我知道了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰的后面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课程设计必将成为我人生旅途上一个非常美好的回忆。五、源程序实验源程序如下：#includes tdio.h#includeconio.h#includemalloc.h#includestring.h#define NULL 0typedef struct PCBchar name10;/进程名st ruc t PCB *

14、nex t; /链指针int need _ti me;/要求运行时间int worked _ti me; /已运行时间char condi tion;/进程状态，只有就绪和结束两种状态int flag;/进程结束标志PCB;PCB *front,* rear;int N; /N为进程数void creatPCB()/为每个进程创建一个PCB并初始化形成一个循环链队列PCB *p, *l;l = (PCB *)malloc(sizeof(PCB);prin tf(请输入各进程名和要求运行时间n); scanf(%s%d,l-name，&l-need _ti me);l-condi tion = r; /进程初始状态为就绪l-worked_time = 0;l-next二NULL;l-flag=0;front=l;for(i nt i 二 l;i name，& p-need _ti me);p-cond ition 二r;pworked_time = 0;p-flag=0;lnext 二 p;l=lnext;rear=l;rearnext二front;void out pu t