时间片轮转算法资料文档格式.docx
《时间片轮转算法资料文档格式.docx》由会员分享，可在线阅读，更多相关《时间片轮转算法资料文档格式.docx（17页珍藏版）》请在冰点文库上搜索。
6）void
chioce（struct
PCB
pcb[],int
n）：
对于输入链表中数的按关键字—到达时间用选择法从小到大进行进行排序。
7）void
caidan（）：
主菜单，包含：
进程的创建和结果和结束。
8）void
create（）：
进程的创建。
9）void
main（）：
实现函数调用的总控制。
4.1.2相关数据类型
1）typedef
int
QElemType：
自定义类型，定义QElemType为int型。
2）typedef
struct
QNode
{
QElemType
data;
QNode
*next;
}QNode,*QueuePtr;
采用结构体变量，存队列的相关信息：
data、struct
*next。
同时定义结构体指针*QueuePtr，便于之后书写开辟空间级表示。
系统调用时，每次分配一个QNode那么大的空间进行存储。
3）typedefstructPCB
{charname[10];
//进程名
structPCB*next;
//循环链指针
intneed_time;
//要求运行时间
intworked_time;
//已运行时间，初始为0
charcondition;
//进程状态，只有“就绪”和“结束”两种状态
intflag;
//进程结束标志，用于输出
}PCB;
PCB*front,*rear;
//循环链队列的头指针和尾指针intN;
//N为进程数
定义循环链表的头指针和尾指针。
QueuePtr
front，QueuePtr
rear。
4）struct
PCB
ArrivalTime;
ServiceTime;
har
number;
}m[MaxNum];
采用结构体数组，创建一个进程，包含进程相关信息：
进程名称、进程到达时间、进程服务时间。
4.2.3总体设计
程序总体设计:
首先选择1创建进程，输入进程总数，进程的名称，各进程到达的时间，各进程服务的时间，以及时间片q的值，运行出结果。
选择2将结束运行，如图1所示。
图1
系统总体设计
4.2.4主程序的流程图
主程序流程如图2所示。
图2主程序的流程图
4.1.5程序说明
处理器调度总是选择指针指示的进程运行。
由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，而是执行：
已运行时间+1来模拟进程的一次运行，表示进程已经运行过一个单位的时间。
4.2详细设计
首先每一个进程用一个进程控制块PCB来代表。
进程控制块的格式如表3所示。
表3PCB控制块
进程名
指针
要求运行时间
已运行时间
状态
其中，进程名——作为进程的标识，如Q1、Q2等。
指针——进程按顺序排成循环链队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。
已运行时间——假设进程已经运行的单位时间数，初始值为“0”。
状态——有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。
当一个进程运行结束后，它的状态为“结束”，用“E”表示。
每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。
把五个进程按顺序排成循环链队列，用指针指出队列连接情况。
用指针表示轮到运行的进程，如表4描述述所示。
表4进程队列
K1
Q1
K2
Q2
K3
Q3
K4
Q4
K5
Q5
K2
K3
K4
K5
2
4
3
1
R
PCB1
PCB2
PCB3
PCB4
PCB5
4.3程序详细设计步骤
首先建立PCB的数据结构，为了便于正确输出，加上了进程结束标志flag。
输入进程信息（包括进程名和要求运行的时间），并为每个进程创建一个PCB并初始化形成一个循环链队列，用函数creatPCB（）来实现。
建立函数judge（）用来判断进程全部运行结束标志，即当所有进程的状态变为’e’（即完成状态）后，循环结束，表示所有进程都已运行成功。
建立时间片轮转算法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’表示所有进程运行完成，则循环结束。
建立主函数main（）,输入进程数N，调用初始化循环链队列函数creatPCB（）和时间片轮转算法creatProcess（N），每次选中进程的进程名以及运行一次后进程队列的变化，实现处理器的调度。
5.程序的运行及结果
1）主菜单：
输入选项1：
进程创建及结果2：
结束，如图5所示。
图5主菜单
2）运行过程:
选择1，创建进程。
输入进程总数，进程的名称a
、b，各进程到达的时间，各进程服务的时间，以及时间片q的值。
当输入进程为2时，各进程到达时间为3,2，各进程服务时间为2,3，以及时间片q=2时的情况，输入情况如图6所示。
图6创建进程
3）输入成功后，按回车键，进程在程序中的具体实现情况即：
时间轮转情况。
进程在调度算法中，计算出的具体的完成时间，周转时间，带权时间，平均周转时间，平均带权周转时间，如图7所示。
图7进程运行结果
3）选择2：
退出界面，如图8。
图8退出界面
6.心得体会
首先，我认为这次课程设计是对学习操作系统的一次综合考察，锻炼我综合分析问题、解决问题的能力。
初次找到课程设计的题目时，为程序本身的简单而窃喜过；
实验过程中也出现了一些难题需要解决，为此去苦苦探索过。
课程设计期间，曾多次登录网站浏览网页，为了弥补一些知识上的纰漏，一次次实践。
当我的想法得到实现，又学会了新的知识的时候，心中满是欣喜，或许这是实践出真知的真实验证，有付出就有回报的真实写照吧。
其次，我们感受了真诚的友谊。
在实验中，遇到的问题是多方面的，而且有那么一部分是以前学过的问题，但是已经忘却或是以前没有真正的理解过。
但是你会发现就在你的身边，会有那么一批人在背后热心的帮助你，这好像是人生的一种历程，团队的协作和彼此心的交流让我们彼此丰厚起来，这也是我们成长中必不可失的重要部分。
最后，我认识到了自己的不足。
平心而论，以前真的没有认真的学习过，即使是在听课，可是后来却没有对学习中出现的问题而仔细分析过。
得过且过，迷失了我前进的方向，而现在却又重新敞开了。
不论是以后的学习还是工作，我想这都是很重要的，我需要不断进步的动力。
7.参考文献
[1]陈莉君等.Linux操作系统原理与应用[M].北京:
清华大学出版社.2012.1
[2]李龙来,吴杰,吕智慧,杨明.基于Web服务的分布式文件系统管理与优化方案[J].计算机工程与设计,2012.
[3]庞丽萍，阳富民.计算机操作系统（第2版）[M].北京：
人民邮电出版社.2014.1
[4]孙洪庆.浅谈对计算机操作系统的认识[J].改革与开放,2011,04:
140.
[5]汤小丹.计算机操作系统（第4版）[M].西安：
电子科技大学出版社.2014.5
附录：
#include<
iostream.h>
iomanip.h>
#include<
malloc.h>
typedefintQElemType;
staticconstintMaxNum=100;
typedefstructQNode
{QElemTypedata;
structQNode*next;
typedefstruct
{QueuePtrfront;
QueuePtrrear;
}LinkQueue;
structPCB
{intArrivalTime;
intServiceTime;
charnumber;
intInitQueue（LinkQueue&
Q）;
intDestroyQueue（LinkQueue&
intEnQueue（LinkQueue&
Q,QElemTypee）;
intDeQueue（LinkQueue&
intQueueEmpty（LinkQueue&
voidchioce（structPCBpcb[],intn）;
voidcaidan（）;
voidcreate（）;
intn,q,FinishedTime[MaxNum],WholeTime[MaxNum];
doubleWeightWholeTime[MaxNum],Average_WT=0,Average_WWT=0;
LinkQueueQ;
voidRR（int*ArrivalTime,int*ServiceTime,intn,intq,LinkQueue&
voidmain（）
{while
（1）
{//system（"
cls"
）;
cout<
<
endl;
caidan（）;
intn;
"
请选择（1-2）：
cin>
>
n;
if（n<
1||n>
2）
输入有误，请重新输入"
switch（n）
{case1:
create（）;
break;
case2:
return;
}
}
//RR算法的具体实现
Q）
{
intcountTime=0,e;
chioce（m,n）;
if（ArrivalTime[0]==0）
countTime=0;
else
countTime=m[0].ArrivalTime;
intSTime[MaxNum],pushed[MaxNum];
for（inti=0;
i<
i++）
{STime[i]=m[i].ServiceTime;
pushed[i]=0;
InitQueue（Q）;
EnQueue（Q,0）;
pushed[0]=1;
inttime=m[0].ArrivalTime;
while（QueueEmpty（Q）==false）
{
e=DeQueue（Q,e）;
if（STime[e]>
q）
STime[e]=STime[e]-q;
countTime+=q;
else
countTime+=STime[e];
STime[e]=0;
FinishedTime[e]=countTime;
while（time<
countTime）
if（STime>
0）
时刻"
setw
（2）<
time<
:
进程"
e<
正在运行"
time++;
for（i=1;
if（STime!
=0&
i!
=e&
m[i].ArrivalTime<
countTime&
pushed[i]==0||STime!
=
0&
m[i].ArrivalTime==countTime）
EnQueue（Q,i）;
pushed[i]=1;
if（STime[e]>
0）//判断进程e是否已执行完
EnQueue（Q,e）;
for（i=0;
{//求周转时间和带权周转时间
WholeTime[i]=FinishedTime[i]-m[i].ArrivalTime;
WeightWholeTime[i]=（double）（WholeTime[i]*1.000000/m[i].ServiceTime）;
Average_WT+=WholeTime[i];
Average_WWT+=WeightWholeTime[i];
Average_WT/=n;
//求平均周转时间
Average_WWT/=n;
//求平均带权周转时间
//----------------输出----------------
-------------------------------------"
进程运行的结果是：
-------------------------------------------------------------------------"
进程名称:
"
;
setw（8）<
m[i].number<
到达时间:
服务时间:
m[i].ServiceTime<
cout<
完成时间:
for（i=0;
FinishedTime[i]<
周转时间:
WholeTime[i]<
带权周转：
setiosflags（ios:
fixed）<
setprecision
（2）<
WeightWholeTime[i]<
--------------------------------------------------------------------------"
平均周转时间为：
Average_WT<
平均带权周转时间为:
Average_WWT<
DestroyQueue（Q）;
//初始化链队列Q
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
Q.front->
next=NULL;
return1;
//销毁链队列Q
while（Q.front）
Q.rear=Q.front->
next;
free（Q.front）;
Q.front=Q.rear;
//入队
Q,QElemTypee）
QueuePtrp=（QueuePtr）malloc（sizeof（QNode））;
p->
data=e;
p->
Q.rear->
next=p;
Q.rear=p;
//出队，并用e返回出队节点的元素值
QueuePtrp;
if（Q.front==Q.rear）
return0;
p=Q.front->
e=p->
Q.front->
next=p->
if（Q.rear==p）
Q.rear=Q.front;
free（p）;
returne;
//判断链队列Q是否为空
intQueueEmpty（LinkQueue&
returntrue;
else
returnfalse;
//选择排序，对结构体中的关键字到达时间，按从小到大的顺序排列
voidchioce（structPCBpcb[],intn）
inti,j;
structPCBt;
for（j=0;
j<
n-1;
j++）
{for（i=0;
n-1-j;
if（pcb[i].ArrivalTime>
pcb[i+1].ArrivalTime）
t=pcb[i];
pcb[i]=pcb[i+1];
pcb[i+1]=t;
voidcaidan（）
*************************主页***********************"
*******************1.进程创建及结果*****************"
*******************2.结束******************"
voidcreate（）
请输入进程总数n的值（0<
n<
=100）:
cin>
while（n<
0||n>
100）
你输入的n的值不正确，请重新输入！
请依次输入各个进程的名称：
for（inti=0;
m[i].number;
请依次输入各个进程的到达时间（ArrivalTime>
=0）：
for（i=0;
m[i].ArrivalTime;
while（m[i].ArrivalTime<
请依次输入各个进程的服务时间（ServiceTime>
m[i].ServiceTime;
while（m[i].ServiceTime<
升级会员 