时间片轮转算法

一、实验目的（1）在单办理器状况下准时间片轮转算法实现办理器调动，输出运转动向变化过程。（2）经过算法的实现加深认识办理器调动的工作。二、实验内容输入实现办理器调动的几个进度信息，随意确立一组“要求运转时间”，启动所设计的办理器调动程序，显示逐次被选中进度的进度名以及进度控制块的动向变化过程。三、实验步骤1、任务剖析：时间片轮转的主要思想就是按次序为每一个进度一次只分派一个时间片的时间。算法要达成的功能就是将各个进度依据时间片轮转运转的动向过程显示出来。时间片轮转算法的主要实现过程是第一为每一个进度创立一个进度控制块，定义数据构造，说明进度控制块所包含的内容，有进度名、进度所需运转时间、已运转时间和进度的状态以及指针的信息。实现的过程即运用指针指向某一个进度，判断目前的进度是不是就绪状态“r”，假如是，则为该进度分派一个时间片，同时，已运转时间加一且要求运转的时间减一，这样循环履行，当某一个进度的所需要运转的时间减少至0时，则将该进度的状态设置为“e”。而后，将指针指向下一个未运转达成的进度，重复判断，直至所有的进度都运转结束。2、纲要设计：（1）所用数据构造及符号说明typedefstructPCB{charname[10];//进度名structPCB*next;//循环链指针intneed_time;//要求运转时间intworked_time;//已运转时间，初始为0charcondition;//进度状态，只有“就绪”和“结束”两种状态intflag;//进度结束标记，用于输出}PCB;PCB*front,*rear;//循环链行列的头指针和尾指针intN;//N为进度数（2）主程序的流程图：开始输入进度数N输入各进度信息为每个进度创立PCB并初始化形成一个循环链行列指针指向循环链队Y列第一个进度进度能否’r’运转时间+1且节余时间-1Y节余时间=0？将进度状态置为’e’（达成）指针指向行列中下个进度N所有进度能否达成Y（3）程序说明：办理器调动老是选择结指束针指示的进度运转。因为本实验是模拟办理器调动的功能，因此，对被选中的进度其实不实质的启动运转，而是履行：已运转时间+1来模拟进度的一次运转，表示进度已经运转过一个单位的时间。3、详尽设计（1）第一每一个进度用一个进度控制块PCB来代表。进度控制块的格式为：进度名指针要求运转时间已运转时间状态此中，进度名——作为进度的表记，如Q1、Q2等。指针——进度按次序排成循环链行列，用指针指出下一个进度的进度控制块的首地点，最后一个进度的指针指出第一个进度的进度控制块首地点。要求运转时间——假定进度需要运转的单位时间数。已运转时间——假定进度已经运转的单位时间数，初始值为“0”。状态——有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。当一个进度运转结束后，它的状态为“结束”，用“E”表示。（2）每次运转所设计的办理器调动程序前，为每个进度随意确立它的“要求运转时间”。把五个进度按次序排成循环链行列，用指针指出行列连结状况。用指针表示轮到运转的进度，以下列图描绘所示：K1

Q1

K2

Q2

K3

Q3

K4

Q4

K5

Q5K2

K3

K4

K5

K12

4

3

1

20

0

0

0

0R

R

R

R

RPCB1PCB2PCB3PCB4PCB5（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)，每次选中进度的进度名以及运转一次后进度行列的变化，实现办理器的调动。4、调试剖析：a．调试过程中碰到的问题及解决方案开始运转到Q5运转达成后显示错误，以下列图所示：原由：经检查程序发现语句if(s->condition=='e'){printf("进度%s已经运转达成！\n\n",s->name);}有错误，因为当某个进度运转达成后，其状态标记已改正为’e’，因此再次循环运转未达成的进度时，当运转到此句时仍会将前面已达成的进度从头输出一遍达成信息，致使输犯错误。flag

解决方案：为每个进度加上一个结束标记flag，并赋初值为0，当进度运转达成后，将改为1，再将后边输出改为if(s->condition=='e'||s->flag==0){printf("进度%s已经运转达成！\n\n",s->name);s->flag==0;}循环时就不会从头输出一遍了。

，这样在前面进度运转达成输出后，后边再b．改良假想：本实验较简单，但还不够完美，如未实现插入进度功能，即进度在运转过程中能够插入其余的进度再运转。还有未进行进度优先级鉴别，本实验默认进度的优先级按输入的先后次序从大到小摆列的，还有其余功能等，希望在此后的实验中逐渐完美。5、测试结果：a．第一输出五个进度的初始状态b．开始从进度Q1开始准时间片轮转运转进度，Q4先运转达成c.接着Q1运转达成d.接着Q5运转达成e.再Q3运转达成最后Q2运转达成四、实验总结因在初期的时间片轮转法中，系统将所有的就绪进度依据先来先服务的原则排成一个队列，每次调动是，把CPU分派给队首进度，并令其履行一个时间片。当履行的时间片用完时，调动程序停止该进度的履行，并将它送往就绪行列的末端；而后，再把办理机分派给就绪队列中新的队首进度，同时也让它履行一个时间片。在时间片轮转算法中，时间片的大小对系统性能有很大的影响。假如选择很小的时间片将有益于短作业，因为它能较快地达成，但会屡次的发生中止、进度上下文的切换，进而增添系统的开支；反之，假如选择太长时间片，使得每个进度都能在一个时间片内达成，因此，一般定为时间片略大于一次典型地交互所需要的时间。在达成时间片轮转算法的实现过程中，我们碰到了一些问题，比方如何运用循环行列，如何设计构造体等等，也踊跃配归并思虑进行解决。整体来说，我们的算法固然实现了表现进度动向运转变化的过程，但是相对而言比较简单。实验中，我们小组不停议论对算法进行优化，使得运转结果看起来更简单理解，也达到了办理机调动的功能。做实验让我们关于时间片轮转的思想理解的更为透辟，稳固了理论知识的学习。实验心得领会：第一，我们以为此次课程设计是对学习《操作系统》的一次综合观察，锻炼我们综合剖析问题、解决问题的能力。首次获得课程设计的题目时，为程序自己的简单而窃喜过；实验过程中也出现了一些难题需要解决，为此去苦苦探究过。课程设计时期，几乎有几日我们完整投入进去了，就像是在做一个相当重要的项目同样的感觉。以前跑过图书室几次，不过为了一种新的想法获得实现，也曾多次登录网站阅读网页，为了填补一些知识上的疏漏，为此曾洒下了真切的汗水。当我们的想法获得实现，又学会了新的知识的时候，心中尽是惊喜，也许这是实践出真知的真切考证，有付出就有回报的真切写照吧。其次，我们感觉了真挚的友情。在实验中，碰到的问题是多方面的，并且有那么一部分是从前学过的C问题，但是已经忘掉或是从前没有真切的理解过。但是你会发现就在你的身旁，会有那么一批人在背后热情的帮助你，让你身处窘境却感觉无穷希望。这仿佛是人生的一种历程，风风雨雨中我们一同走过，而后为了一些坑坑洼洼相互真挚的帮助过和无私的付出过。团队的协作和相互心的沟通让我们相互丰厚起来，这也是我们成长中必不行失的重要部分。最后，我认识到了自己的不足。平心而谈，从前真的没有认真的学习过，即便是在听课，但是此后却没有对学习中出现的问题而认真剖析过。苟且偷生，迷失了我行进的方向，而现在却又从头敞开了。无论是此后的学习仍是工作，我想这都是很重要的，我们需要不停进步的动力。总的说来知识上的收获特别重要，精神上的丰产也是更为可喜的，让我知道了学无止境的道理。我们每个人永久不可以知足于现有的成就，人生就像在登山，一座山岳的后边还有更高的山岳在等着你。挫折是一份财产，经历是一份拥有。此次课程设计势必成为我人生旅途上一个特别美好的回想。五、附录实验源程序以下：#include"stdio.h"#include"conio.h"#include"malloc.h"#include"string.h"#defineNULL0typedefstructPCB{charname[10];//进度名structPCB*next;//链指针intneed_time;//要求运转时间intworked_time;//已运转时间charcondition;//进度状态，只有“就绪”和“结束”两种状态intflag;//进度结束标记}PCB;PCB*front,*rear;intN;//N为进度数voidcreatPCB( ){//为每个进度创立一个PCB并初始化形成一个循环链行列PCB*p,*l;l=(PCB*)malloc(sizeof(PCB));printf("Pleaseenterprocessnameandtime\n");scanf("%s%d",l->name,&l->need_time);l->condition='r';//进度初始状态为就绪l->worked_time=0;l->next=NULL;l->flag=0;front=l;for(inti=1;i<N;i++){p=(PCB*)malloc(sizeof(PCB));scanf("%s%d",p->name,&p->need_time);p->condition='r';p->worked_time=0;p->flag=0;l->next=p;l=l->next;}rear=l;rear->next=front;}voidoutput( ){//进度输出函数printf("nameruntimeneedtimestate\n");for(intj=1;j<=N;j++){printf("%-4s\t%-4d\t%-4d\t%-c\n",front->name,front->worked_time,front->need_time,front->condition);front=front->next;}printf("\n");}intjudge(PCB*p){//判断所有进度运转结束intflag=1;for(inti=0;i<N;i++){if(p->condition!='e'){flag=0;break;}p=p->next;}returnflag;}voidcreatProcess(intn){//时间片轮转算法PCB*s,*p;inti,j,flag1=0;s=(PCB*)malloc(sizeof(PCB));s=front;printf("\n--------------------------------------------\n");output( );printf("Pressanykeytocontinue...\n\n");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("Pressanykeytocontinue...\n\