时间片轮转算法.docx
《时间片轮转算法.docx》由会员分享，可在线阅读，更多相关《时间片轮转算法.docx（14页珍藏版）》请在冰点文库上搜索。
时间片轮转算法
时间片轮转算法
〔1〕在单处理器情形下按时刻片轮转算法实现处理器调度，输出运行动态变化过程。
〔2〕通过算法的实现加深了解处理器调度的工作。
二、实验内容
输入实现处理器调度的几个进程信息，任意确定一组〝要求运行时刻〞，启动所设计的处理器调度程序，显示逐次被选中进程的进程名以及进程操纵块的动态变化过程。
三、实验步骤
1、任务分析：
时刻片轮转的要紧思想确实是按顺序为每一个进程一次只分配一个时刻片的时刻。
算法要完成的功能确实是将各个进程按照时刻片轮转运行的动态过程显示出来。
时刻片轮转算法的要紧实现过程是第一为每一个进程创建一个进程操纵块，定义数据结构，说明进程操纵块所包含的内容，有进程名、进程所需运行时刻、已运行时刻和进程的状态以及指针的信息。
实现的过程即运用指针指向某一个进程，判定当前的进程是否是就绪状态〝r〞，假如是，那么为该进程分配一个时刻片，同时，已运行时刻加一且要求运行的时刻减一，如此循环执行，当某一个进程的所需要运行的时刻减少至0时，那么将该进程的状态设置为〝e〞。
然后，将指针指向下一个未运行完成的进程，重复判定，直至所有的进程都运行终止。
2、概要设计：
〔1〕所用数据结构及符号说明
typedefstructPCB{
charname[10];//进程名
structPCB*next;//循环链指针
intneed_time;//要求运行时刻
intworked_time;//已运行时刻，初始为0
charcondition;//进程状态，只有〝就绪〞和〝终止〞两种状态
intflag;//进程终止标志，用于输出
}PCB;
PCB*front,*rear;//循环链队列的头指针和尾指针
intN;//N为进程数
〔2〕主程序的流程图：
Y
Y
N
Y
〔3〕程序说明：
处理器调度总是选择指针指示的进程运行。
由于本实验是模拟处理器调度的功能，因此，对被选中的进程并不实际的启动运行，而是执行：
已运行时刻+1来模拟进程的一次运行，表示进程差不多运行过一个单位的时刻。
3、详细设计
〔1〕第一每一个进程用一个进程操纵块PCB来代表。
进程操纵块的格式为：
进程名
指针
要求运行时刻
已运行时刻
状态
其中，进程名——作为进程的标识，如Q1、Q2等。
指针——进程按顺序排成循环链队列，用指针指出下一个进程的进程操纵块的首地址，最后一个进程的指针指出第一个进程的进程操纵块首地址。
要求运行时刻——假设进程需要运行的单位时刻数。
已运行时刻——假设进程差不多运行的单位时刻数，初始值为〝0〞。
状态——有两种状态，〝就绪〞和〝终止〞，初始状态都为〝就绪〞，用〝R〞表示。
当一个进程运行终止后，它的状态为〝终止〞，用〝E〞表示。
〔2〕每次运行所设计的处理器调度程序前，为每个进程任意确定它的〝要求运行时刻〞。
把五个进程按顺序排成循环链队列，用指针指出队列连接情形。
用指针表示轮到运行的进程，如以下图描述所示：
K1
Q1
K2
Q2
K3
Q3
K4
Q4
K5
Q5
K2
K3
K4
K5
K1
2
4
3
1
2
0
0
0
0
0
R
R
R
R
R
PCB1
PCB2
PCB3
PCB4
PCB5
〔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，并赋初值为0，当进程运行完成后，将flag改为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运行完成
f.最后Q2运行完成
四、实验总结
因在早期的时刻片轮转法中，系统将所有的就绪进程按照先来先服务的原那么排成一个队列，每次调度是，把CPU分配给队首进程，并令其执行一个时刻片。
当执行的时刻片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时刻片。
在时刻片轮转算法中，时刻片的大小对系统性能有专门大的阻碍。
假如选择专门小的时刻片将有利于短作业，因为它能较快地完成，但会频繁的发生中断、进程上下文的切换，从而增加系统的开销；反之，假如选择太长时刻片，使得每个进程都能在一个时刻片内完成，因此，一样定为时刻片略大于一次典型地交互所需要的时刻。
在完成时刻片轮转算法的实现过程中，我们遇到了一些问题，比如如何样运用循环队列，如何设计结构体等等，也积极配合并摸索进行解决。
整体来说，我们的算法尽管实现了表达进程动态运行变化的过程，然而相对而言比较简单。
实验中，我们小组不断讨论对算法进行优化，使得运行结果看起来更容易明白得，也达到了处理机调度的功能。
做实验让我们关于时刻片轮转的思想明白得的更加透彻，巩固了理论知识的学习。
实验心得体会：
第一，我们认为这次课程设计是对学习«操作系统»的一次综合考察，锤炼我们综合分析问题、解决问题的能力。
初次得到课程设计的题目时，为程序本身的简单而窃喜过；实验过程中也显现了一些难题需要解决，为此去苦苦探究过。
课程设计期间，几乎有几天我们完全投入到里面去了，就像是在做一个相当重要的项目一样的感受。
曾经跑过图书馆几次，只是为了一种新的方法得到实现，也曾多次登录网站扫瞄网页，为了补偿一些知识上的纰漏，为此曾洒下了真实的汗水。
当我们的方法得到实现，又学会了新的知识的时候，心中满是欣喜，或许这是实践出真知的真实验证，有付出就有回报的真实写照吧。
其次，我们感受了真诚的友谊。
在实验中，遇到的问题是多方面的，而且有那么一部分是往常学过的C问题，然而差不多忘却或是往常没有真正的明白得过。
然而你会发觉就在你的周围，会有那么一批人在背后热心的关心你，让你身处逆境却感到无限期望。
这看起来是人一辈子的一种历程，风风雨雨中我们一起走过，然后为了一些坑坑洼洼彼此真诚的关心过和无私的付出过。
团队的协作和彼此心的交流让我们彼此丰厚起来，这也是我们成长中必不可失的重要部分。
最后，我认识到了自己的不足。
平心而论，往常确实没有认确实学习过，即使是在听课，但是后来却没有对学习中显现的问题而认真分析过。
得过且过，迷失了我前进的方向，而现在却又重新放开了。
不论是以后的学习依旧工作，我想这差不多上专门重要的，我们需要不断进步的动力。
总的说来知识上的收成专门是重要，精神上的丰收也是更加可喜的，让我明白了学无止境的道理。
我们每一个人永久不能满足于现有的成就，人一辈子就像在爬山，一座山峰的后面还有更高的山峰在等着你。
挫折是一份财宝，经历是一份拥有。
这次课程设计必将成为我人一辈子旅途上一个专门美好的回忆。
五、附录
实验源程序如下：
#include"stdio.h"
#include"conio.h"
#include"malloc.h"
#include"string.h"
#defineNULL0
typedefstructPCB{
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;ip=（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;iif（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\n"）;
getch（）;
}
if（s->condition=='e'&&s->flag==0）{
printf（"进程%s差不多运行完成！
\n\n",s->name）;
s->flag=1;
}
s=s->next;
flag1=judge（s）;
}
printf（"--------------------------------------------\n"）;
}
voidmain（）{
printf（"Pleaseenterprocessnumber\n"）;
scanf（"%d",&N）;;
creatPCB（）;
creatProcess（N）;
}
升级会员 