实验二时间片轮转RR进程调度算法

1、实验二 时间片轮转RR进程调度算法 一：需求分析程序的设计的任务和目的：设计程序模拟进程的时间片轮转RR调度过程。假设有n个进程分别在T1, ,Tn时刻到达系统，它们需要的服务时间分别为S1, ,Sn。分别利用不同的时间片大小q，采用时间片轮转RR进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。(1) 输入的形式和输入值的范围 为避免测试时频繁输入数据，将测试数据放在txt文件中采用读文件方法读取数据。在同目录下的txt文件

2、中输入数据，第一行为进程到达时间，中间用空格隔开，第二行为进程服务时间，不同进程的服务时间之间用空格隔开。(2) 输出的形式输出每个时刻的进程运行状态，并且输出计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。（详见运行截图）(3) 程序所能达到的功能；能够模拟进程的时间片轮转RR调度过程，可以输入时间片大小，然后采用时间片轮转RR进程调度算法进行调度，可以模拟调度过程，输出每个时刻的进程运行状态，另外也实现了输出计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。(4) 测试数据，包括正确的输入及其输出结果和含有错误的

3、输入及其输出结果。 作业时间片进程名ABCDE平均到达时间01234服务时间435242完成时间813181017周转时间8121671311.2带权周转时间243.23.53.253.194完成时间47181317周转时间461610139.8带权周转时间123.253.252.89详见运行结果截图2、 概要设计使用链表创建队列，用链表方法实现时间片轮转调度。主要有主函数，时间片轮转调度函数void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q)和输出函数void print(int n,int array)，void

4、 print(int n,double array)；三：详细设计YYNNNY退出结束将未完成的插入队尾是否所有进程都完成时间片是否用完是否完成将新到进程插入队尾新进程是否到达时间片-1时间+1分配给执行队列队首时间片服务时间-1开始时间片轮转算法流程图：程序主要设计思想：（1）创建进程，使用链表的方法，链表中的每个结点相当于一个进程。（2）读入文件中进程数据（进程的到达时间和服务时间）。（3）创建一个进程单链表，作为进程队列。 （4）请用户输入时间片大小。（5）创建执行队列。（6）定义时间轴，初始化时间轴和执行队列。（7）当进程数不为零时，分配给执行队列队首一个时间片。继续有未完成进程时进程

5、队列的队首进程是否到达，若到达，将其插入到执行队列的队尾。执行队列不为空时，执行队列的队首进程的，判断是否执行完。执行完，该进程退出执行队列。（8）执行队列队首是否得到过一个完整的时间片，若有则该进程插入到执行队列的队尾。 （9）执行队列不为空时，转到第（7）步。当执行队列和进程队列都为空时，转到第（6）步。当两队列都为空时，所有进程运行完，模拟结束。 四：调试分析调试过程中遇到的问题即在时间片轮转算法中由于循环使用不当导致无法实现预期的结果，后通过问同学，网上查找资料解决。算法改进：可加一个循环将读入的进程按到达时间从先至后排列。经验体会：通过这次实验，又熟悉了链表的使用方法，加深了对进程概

6、念的理解，进一步掌握了进程状态的转变、进程调度的策略及对系统性能的评价方法。五：用户使用说明1、 在同目录的txt文件中输入进程到达时间和服务时间，第一行为进程到达时间，中间用空格隔开，第二行为进程服务时间，不同进程的服务时间之间用空格隔开。2、 运行时按指示输入，如“请输入时间片长度”时输入时间片大小，若退出按0，继续则继续输入时间片大小。六：测试结果时间片长度为2时：时间片长度为4时：七：附录源程序：#include#include#include#includeusing namespace std;typedef int QElemType;#define OK 1#define ER

7、ROR 0#define OVERFLOW -1typedef int Status;typedef struct QNode/定义队列节点QElemType data;struct QNode *next;QNode,*QueuePtr;typedef struct/定义队列QueuePtr front;QueuePtr rear;LinkQueue;Status InitQueue(LinkQueue &Q);/初始化队列Status DestroyQueue(LinkQueue &Q);/删除队列Status EnQueue(LinkQueue &Q,QElemType e);/进入队列

8、int DeQueue(LinkQueue &Q,QElemType e);/离开队列bool QueueEmpty(LinkQueue &Q);/判读队列是否为空LinkQueue Q;/创建队列Qstatic const int MaxNum=100;int n,q,ArrivalTimeMaxNum,ServiceTimeMaxNum,FinishedTimeMaxNum,WholeTimeMaxNum;/定义进程调度中的时间变量double WeightWholeTimeMaxNum,Average_WT,Average_WWT;void print(int n,int array);

9、void print(int n,double array);void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q);void main()/读文件，到达时间和完成时间int ia,ib,i,q;ifstream in(test.txt);string s;getline(in, s); istringstream sin(s);for(i=0; sinia;i+) ArrivalTimei=ia;getline(in, s); istringstream sinn(s);for(i=0; sinnib;i+)Serv

10、iceTimei=ib;int n=i;/输出进程数、到达时间、服务时间cout输入进程数(n):nendl;coutArrival time:;print(i,ArrivalTime);coutService time:;print(i,ServiceTime);/输入时间片长度coutq;cout时间片轮转算法RRendl;RR(ArrivalTime,ServiceTime,n,q,Q);while(q)/循环输入时间片长度q,直到q=0结束coutendl0 or 输入时间片大小:;cinq;if(q=0)return;RR(ArrivalTime,ServiceTime,n,q,Q)

11、;void RR(int*ArrivalTime,int*ServiceTime,int n,int q,LinkQueue &Q)/-初始化模块-int countTime=0,e;int STimeMaxNum,pushedMaxNum;for(int i=0;iq)STimee=STimee-q;countTime+=q;elsecountTime+=STimee;STimee=0;FinishedTimee=countTime;while(time0)cout时刻setw(2)time:进程e正在运行endl;time+;for(i=1;in;i+)if(STime!=0&i!=e&A

12、rrivalTimei0)EnQueue(Q,e);/-计算模块-Average_WT=0,Average_WWT=0;for(i=0;in;i+)WholeTimei=FinishedTimei-ArrivalTimei;WeightWholeTimei=(double)(WholeTimei*1.000000/ServiceTimei); Average_WT+=WholeTimei;Average_WWT+=WeightWholeTimei;Average_WT/=n;Average_WWT/=n;/-输出模块-cout完成:;print(n,FinishedTime);cout周转:;

13、print(n,WholeTime);cout带权周转时间：;print(n,WeightWholeTime);cout平均周转时间为：Average_WTendl;cout平均带权周转时间为:Average_WWTnext=NULL;return OK;Status DestroyQueue(LinkQueue &Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;Status EnQueue(LinkQueue &Q,QElemType e) QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;int DeQueue(LinkQueue &Q,QElemType e)QueuePtr p;if(Q.front=Q.rear) return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);ret