时间片轮转算法.doc

《时间片轮转算法.doc》由会员分享，可在线阅读，更多相关《时间片轮转算法.doc（9页珍藏版）》请在三一文库上搜索。

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

2、时间和进程的状态以及指针 的信息。实现的过程即运用指针指向某一个进程，判断当前的进程是否是就绪状态“r ”，如果是，则为该进程分配一个时间片，同时，已运行时间加一且要求运行的时间减一，如 此循环执行，当某一个进程的所需要运行的时间减少至 0时，则将该进程的状态设置为 “e” 然后，将指针指向下一个未运行完成的进程，重复判断，直至所有的进程都运行结束。2、概要设计：typedef struct PCB char name10; / struct PCB *next; / int need_time; / int worked_time; / char condition; / int flag;

3、 /（1）所用数据结构及符号说明进程名循环链指针 要求运行时间 已运行时间，初始为 0 进程状态，只有“就绪”和“结束”两种状态 进程结束标志，用于输出PCB;PCB *front,*rear; / 循环链队列的头指针和尾指针 int N; /N 为进程数（2）主程序的流程图：开始输入进程数 N输入各进程信息为每个进程创建 PCB并初始化形成一个循环链队列+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。3、详细设计1）首先每一个进程用一个进程控制块 PCB来代表。进程控制块的格式为：址，最后一个进程的指针指出第一个进程的进程控制块首地址。 要求运行时间假设进程需要运行的单位时间数。

4、 已运行时间假设进程已经运行的单位时间数，初始值为“0”。状态有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。当一个进程运行结束后，它的状态为“结束”，用“ E”表示。（2）每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时 间”。把五个进程按顺序排成循环链队列，用指针指出队列连接情况。 的进程，如下图描述所示：用指针表示轮到运行K1Q1K2Q2K3Q3K4Q4K5Q5K2K3K4K5K124312PCB1 PCB2 PCB3 PCB4 PCB5(3) 程序详细设计步骤：a. 首先建立 PCB的数据结构，为了便于正确输出，加上了进程结束标志flag 。输入

5、进程信息(包括进程名和要求运行的时间)，并为每个进程创建一个PCB并初始化形成一个循环链队列，用函数 creatPCB() 来实现。b. 建立函数 judge() 用来判断进程全部运行结束标志， 即当所有进程的状态变为 e (即完成状态)后，循环结束，表示所有进程都已运行成功。c. 建立时间片轮转算法 creatProcess ()对进程进行轮转运行，首先指针 s 指向第一 个进程 PCB，即 s=front ，判断该进程的状态是否为 r (就绪状态)，即 if(s-condition = r) ，若是则表示此进程尚未执行结束， 则执行 s-worked_time+ 且 s-need_time

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

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

8、 已经运行完成！ nn,s-name);s-flag=0;，这样在前面进程运行完成输出后，后面再循环时就不会重新输出一遍了。b改进设想：本实验较简单，但还不够完善，如未实现插入进程功能，即进程在运 行过程中可以插入其他的进程再运行。还有未进行进程优先级判别，本实验默认进程的优 先级按输入的先后顺序从大到小排列的， 还有其他功能等， 希望在以后的实验中逐步完善。5、测试结果：a首先输出五个进程的初始状态b开始从进程 Q1开始按时间片轮转运行进程， Q4先运行完成c. 接着 Q1运行完成d. 接着 Q5运行完成e. 再 Q3运行完成f. 最后 Q2运行完成四、实验总结因在早期的时间片轮转法中，系统

9、将所有的就绪进程按照先来先服务的原则排成一个 队列，每次调度是，把 CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用 完时，调度程序停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配 给就绪队列中新的队首进程，同时也让它执行一个时间片。在时间片轮转算法中，时间片 的大小对系统性能有很大的影响。如果选择很小的时间片将有利于短作业，因为它能较快 地完成，但会频繁的发生中断、进程上下文的切换，从而增加系统的开销；反之，如果选 择太长时间片，使得每个进程都能在一个时间片内完成，所以，一般定为时间片略大于一 次典型地交互所需要的时间。在完成时间片轮转算法的实现过程中， 我们遇到

10、了一些问题， 比如怎样运用循环队列， 如何设计结构体等等，也积极配合并思考进行解决。整体来说，我们的算法虽然实现了体 现进程动态运行变化的过程，但是相对而言比较简单。实验中，我们小组不断讨论对算法 进行优化，使得运行结果看起来更容易理解，也达到了处理机调度的功能。做实验让我们 对于时间片轮转的思想理解的更加透彻，巩固了理论知识的学习。实验心得体会： 首先，我们认为这次课程设计是对学习 操作系统 的一次综合考察， 锻炼我们综合分析问题、解决问题的能力。初次得到课程设计的题目时，为程序本身的简单而窃喜过；实验过程中也出现了一些 难题需要解决，为此去苦苦探索过。课程设计期间，几乎有几天我们完全投入进

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

12、真诚的帮助过和 无私的付出过。团队的协作和彼此心的交流让我们彼此丰厚起来，这也是我们成长中必不 可失的重要部分。最后，我认识到了自己的不足。平心而论，以前真的没有认真的学习过，即使是在听 课，可是后来却没有对学习中出现的问题而仔细分析过。 得过且过， 迷失了我前进的方向， 而现在却又重新敞开了。不论是以后的学习还是工作，我想这都是很重要的，我们需要不 断进步的动力。总的说来知识上的收获很是重要，精神上的丰收也是更加可喜的，让我知道了学无止 境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰的后面 还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课程设计必将成为

13、我 人生旅途上一个非常美好的回忆。五、附录 实验源程序如下： #includestdio.h #includeconio.h #includemalloc.h #includestring.h #define NULL 0 typedef struct PCB char name10; / 进程名 struct PCB *next; / 链指针 int need_time; /要求运行时间 int worked_time; /已运行时间 char condition; /进程状态，只有 “就绪”和“结束 ”两种状态 int flag; / 进程结束标志PCB;PCB *front,*rear;

14、int N; /N 为进程数void creatPCB()/为每个进程创建一个 PCB 并初始化形成一个循环链队列PCB *p,*l;l = (PCB *)malloc(sizeof(PCB); printf(Please enter process name and timen); scanf(%s%d,l-name,&l-need_time); l-condition = r; / 进程初始状态为就绪 l-worked_time = 0;l-next=NULL;l-flag=0; front=l; for(int i = 1;i name,&p-need_time); p-conditio

15、n = r; p-worked_time = 0;p-flag=0;l-next = p; l=l-next; rear=l;rear-next=front;void output() /进程输出函数 printf(name runtime needtime staten);for(int j=1;jname,front-worked_time,front-need_time,front-co ndition);printf(n);int judge(PCB *p) /判断所有进程运行结束int flag = 1;for(int i=0;icondition != e) flag = 0; b

16、reak; p=p-next;return flag;void creatProcess(int n) /时间片轮转算法PCB *s,*p;int i,j,flag1=0;s = (PCB *)malloc(sizeof(PCB);s=front;printf(nn);output();printf(Press any key to continue.nn);getch(); /按任意键继续s=front;while(flag1 != 1)if(s-condition = r) s-worked_time+; s-need_time-; if(s-need_time=0) s-condition=e; output(); printf(Press any key to continue.nn); getch();if(s-condition=e & s-flag=0)printf( 进程 %s 已经运行完成！ nn,s-name); s-flag=1;s=s-next;flag1=judge(s);printf(n);void main()printf(Please enter process numbern); scanf(%d,&N);creatPCB();creatProcess(N);