操作系统实验：时间片轮转RR进程调度算法

题目：时间片轮转算法的实现

班级：软件工程2班 姓名：代其全 学号：1025111022 完成日期：2012/10/23

一． 需求分析

程序要实现时间片轮转进程调度算法

（1） 接收用户输入的进程数（n）,，各个进程的进程名，到达时间(T1…Tn)和

服务时间(S1….Sn)，以及时间片大小q。 （2） 输出各个进程首次运行的时间

（3） 输出各个进程的完成时间，周转时间，带权周转时间，所有进程的平均周

转时间，以及带权平均周转时间。

（4） 测试数据为: 进程数n为5, 各进程的名字，到达时间，服务时间分别

为：a 0 4 ; b 1 3; c 2 5; d 3 2; e 4 4。时间片大小q为1 和5。 二． 概要设计

抽象数据类型的定义：

int ArrivalTime[100];//到达时间 int ServiceTime[100];//服务时间 int FinishTime[100];//完成时间 int WholeTime[100];//周转时间

double WeightWholeTime[100];//带权周转时间 double AverageWT,AverageWWT; bool Finished[100];//完成标识

typedef struct QNode {

char name; //进程标识 int arrivaltime;//到达时间 int servicetime;//服务时间

int workedtime; //进程已经运行的时间

bool status; //表示进程的状态,1表示已经结束，0表示还未执行 struct QNode *next; }QNode, *QueuePtr;

typedef struct {

QueuePtr front;//队头指针 QueuePtr rear;//队尾指针 }LinkQueue;

主程序的流程：调用Init()函数初始化到达时间，服务时间，时间片等进程信息，调度RR（）函数实现轮转调度发，最后调度print()函数输出运算结果

三． 详细设计

1. 初始化函数 void init() {

int cputime;int x,y;char name; cout<<\"请输入进程的个数:\"; cin>>n; //进程个数 cout<for(int i=0;i>name>>x>>y;

node.name=name;

node.arrivaltime=ArrivalTime[i]=x; node.servicetime=ServiceTime[i]=y; node.workedtime=0; node.status=Finished[i]=0; node.next=NULL; array[i]=node; //cout<<\"队中增加一个元素\"<}//各个进程的到达时间和服务时间 cout<<\"请输入时间片大小:\"; cin>>cputime;

q=cputime;//时间片大小 }

2. RR()函数 void RR() {

int temp;QNode e;int count1=0;

//按到达时间先后排序进程信息数组 for(int i=0;iarray[i+1].arrivaltime) { temp=array[i].arrivaltime; array[i].arrivaltime=array[i+1].arrivaltime; array[i].arrivaltime=temp;

} } }//此时，array数组中的元素都是按到达时间从小到大排列的

for(i=0;ifor(int j=0;jif(count1!=0)//依然有进程未完成 {

for(int j=0;jif(q>=(*queue.front->next).servicetime)//时间片大于进程服务时间时，进程一次性执行完，进入下一进程 { //cout<<\"\"; cout<<\"时刻\"<next->name<<\"开始执行\"<next).servicetime;x++) { currentTime++; for(int y=0;y(*queue.front).status=1;//将此进程状态标注为已执行 // currentTime=currentTime+(*queue.front->next).servicetime;//更新当前时间 cout<<\"当前时间为:\"<}

else//时间片小于服务时间时 {

if((*queue.front->next).workedtime<(*queue.front->next).servicetime)//进程已工作时间小于服务时间时 { if((*queue.front->next).workedtime==0)//进程已工作时间为零时 { // cout<<\"\"; cout<<\"时刻\"<next).name<<\"开始执行\"<next).workedtime+=q;//更新进程已工作时间 DeQueue(queue,e);//将该进程出队 EnQueue(queue,e);//将该进程入队，加入到了队列的末尾 } else//进程工作时间不为零且未达到服务时间时 { for(int

i=0;inext).workedtime!=(*queue.front->next).servicetime;i++) { currentTime++;//当前时间加一 for(int j=0;jif((*queue.front->next).workedtime==(*queue.front->next).servicetime)//已工作时间达到要求的服务时间 { (*queue.front->next).status=1;

count++; Finished[count]=1; DeQueue(queue,e); FinishTime[count]=currentTime;//当前时间为完成时间，返回存放入FinishTime[]数组中 } } } } } } } }

3. 输出函数 void print(int n) {

cout<<\"完成时间:\"; for(int i=0;icout<WholeTime[0]+=WholeTime[i];

} AverageWT=double(WholeTime[0])/n; cout<<\"平均周转时间\"<4. 队列里封装的函数

int InitQueue(LinkQueue &q) {

q.front=q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!q.front) return 0;

q.front->next=NULL; return 1; }

int EnQueue(LinkQueue &q,QNode &e) {

QueuePtr p=(QueuePtr)malloc(sizeof(QNode)); if(!p) return 0;

p->name=e.name;

p->arrivaltime=e.arrivaltime; p->servicetime=e.servicetime; p->status=e.status;

p->workedtime=e.workedtime; p->next=NULL; q.rear->next=p; q.rear=p; return 1; }

int DeQueue(LinkQueue &q,QNode &e) {

if(q.rear==q.front) return 0;

QueuePtr p=q.front->next;

e.name=p->name;

e.arrivaltime=p->arrivaltime; e.servicetime=p->servicetime; e.status=p->status;

e.workedtime=p->workedtime;

q.front->next=p->next; if(q.rear==p) q.rear=q.front; free(p); return 1; }

四． 调试分析

在时间片大于所有进程的服务时间时，程序正常运行，当时间片小于某些进程的服务时间时，程序不能输出正确的运算结果。

五． 用户使用说明

1. 根据提示输入进程的个数，各进程的名字，到达时间，服务时间，时间

片大小等。

2. 按下回车键得到输出结果。

六． 测试结果

当输入进程信息，设定时间片大小q为5时，运行结果为:

当输入进程信息，设定时间片大小为1时，运行结果如下：

不能显示正确运行结果

七．RR.cpp文件