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

1.实验目的

通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。

2.实验内容

问题描述：

设计程序模拟进程的时间片轮转RR调度过程。假设有n个进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别利用不同的时间片大小q，采用时间片轮转RR进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
程序要求：
1）进程个数n；每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn；输入时间片大小q。
2）要求时间片轮转法RR调度进程运行，计算每个进程的周转时间和带权周转时间，并且计算所有进程的平均周转时间和带权平均周转时间；
3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；
4）输出：要求输出计算出来的每个进程的周转时间、带权周转时间、所有进程的平均周转时间以及带权平均周转时间。
实现提示：
用C++语言实现提示：
1）程序中进程调度时间变量描述如下：
int ArrivalTime[100];
int ServiceTime[100];
int PServiceTime[100];
int FinishTime[100];
int WholeTime[100];
double WeightWholeTime[100];
double AverageWT,AverageWWT;
bool Finished[100];
2）进程调度的实现过程如下：

  1. 变量初始化；
  2. 接收用户输入n，T1, … ,Tn，S1, … ,Sn；时间片大小q；
  3. 按照时间片轮转RR算法进行进程调度，计算进程的完成时间、周转时间和带权周转时间；
  4. 计算所有进程的平均周转时间和平均带权周转时间；
  5. 按格式输出调度结果。

实验要求：
1）上机前认真复习时间片轮转RR进程调度调度算法，熟悉进程调度的执行过程；
2）上机时独立编程、调试程序；
3）根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图、发现的问题以及解决方法）

3.程序主要构成部分及其算法说明

1.采用while循环对队列进行相应的处理，采用嵌套的for循环对q>1的情况做处理，将满足进程的到达时间小于当前时间的进程都进入队列

while(!PROqueue.empty()){for (int j=i;j<n;j++){if(PROarray[j].name!=NULL&&CurrentTime>= PROarray[j].ArrivalTime){ PROqueue.push(PROarray[j]);i++;} }

2.进程运行的顺序算法，分两部分处理，运行在队首的进程，当队首进程的服务时间小于或者等于0的时候，将队首元素出队列，反之，将队首元素插入到队尾（注意，要先将新到来的进程插入队尾后，再将队首元素插入队尾）。

if (PROqueue.front().ServiceTime>=q)tempTime = q;elsetempTime = PROqueue.front().ServiceTime; PROqueue.front().ServiceTime -= q;processName[a]= PROqueue.front().name;a++;Time[processNumber] = tempTime;processNumber++;if (PROqueue.front().ServiceTime <= 0)PROqueue.pop();else{ PROqueue.push(PROqueue.front());PROqueue.pop();} CurrentTime += tempTime;}

3.计算进程的完成时间：在队列过程处理中，将进程的执行时间记录在数组中，然后，在后续的处理过程中，利用while循环，按照一遇到重复的进程名就更新的原则进行处理，最后一次更新即是该进程的完成时间

for (int i=0;i<processNumber;i++){count = 0;while(PROarray[count].name!=processName[i] &&count<n){count++ ;} PROarray[count].FinishTime=time ;if (i<processNumber-1){time += Time[i+1];}}

4.运行结果

5.实验源码

#include #include #include #include using namespace std; //存放每个进程信息的结构体typedef struct{char name;double ArrivalTime;//到达时间double ServiceTime;//服务时间double FinishTime;//完成时间double WholeTime;//周转时间double WeightWholeTime;//带权周转时间}PRO; static queue<PRO>PROqueue;//用来模拟进程执行RR调度算法的队列static double SumWT=0,SumWWT=0,AverageWT =0,AverageWWT=0;//平均周转时间、平均带权周转时间static int q;//时间片数static int n;//进程个数static PRO PROarray[100];//进程结构体static PRO temp;//进程结构void Input();void RRArithmetic() ;void output() ;int main(){Input();RRArithmetic();output();return 0;} //输入时间片、到达时间、服务时间等void Input(){int i,j;cout<<"请输入进程个数: ";cin>>n;for (i=0;i<n;i++){PROarray[i].name=i+65;//自动将进程名字顺序编号为A、B、C、D、E等} cout<<"请输入到达时间: ";for (i=0;i<n;i++){cin>>PROarray[i].ArrivalTime;} cout<<"请输入服务时间: ";for (i=0;i<n;i++){cin>>PROarray[i].ServiceTime;} cout<<"请输入时间片q的大小: ";cin>>q;//根据达时间排序for(i=0;i<n;i++) {for(j=i+1;j<n;j++) {if(PROarray[i].ArrivalTime > PROarray[j].ArrivalTime) {temp = PROarray[i];PROarray[i] = PROarray[j];PROarray[j] = temp;}}}} //执行RR调度算法void RRArithmetic(){char processName[100]; //存储每个时间片p对应的进程名称 PROqueue.push(PROarray[0]); //第一个进程进队列int CurrentTime=0;//当前时间 int tempTime; //控制CurrentTime的累加时间，当前进程的服务时间小于时间片q的时候，起到重要作用int i=1;int a=0; int processNumber = 0; //执行RR算法后，进程的个数 int Time[100] ;//判断第一个进程的服务时间是否大于时间片，如果大于CurrentTime=q，如果小于CurrentTime=服务时间if (PROarray[0].ServiceTime>=q)CurrentTime = q;elseCurrentTime = PROarray[0].ServiceTime;while(!PROqueue.empty()){for (int j=i;j<n;j++){ //使得满足进程的到达时间小于当前时间的进程都进入队列if (PROarray[j].name!=NULL && CurrentTime >= PROarray[j].ArrivalTime){PROqueue.push(PROarray[j]);i++;}}//队列首进程进行执行，进程每执行一次，就将其服务时间 -qif (PROqueue.front().ServiceTime>=q)tempTime = q;elsetempTime = PROqueue.front().ServiceTime;PROqueue.front().ServiceTime -= q; //将队首进程的名称放入数组中processName[a]= PROqueue.front().name;a++;Time[processNumber] = tempTime;processNumber++;if (PROqueue.front().ServiceTime <= 0)//把执行完的进程退出队列PROqueue.pop(); //如果进程的服务时间小于等于，即该进程已经服务完了，将其退栈else{//将队首移到队尾PROqueue.push(PROqueue.front());PROqueue.pop();} CurrentTime += tempTime;} //进程输出处理 每个时间段对应的执行的进程 int time = Time[0];int count = 0;//计算完成时间for (int i=0;i<processNumber;i++){count = 0;while(PROarray[count].name!=processName[i] &&count<n){count++ ;} PROarray[count].FinishTime=time ;if (i<processNumber-1){time += Time[i+1];}} //周转时间、带权周转时间、平均周转时间、带权平均周转时间的计算for (int i=0;i<n;i++){PROarray[i].WholeTime = PROarray[i].FinishTime - PROarray[i].ArrivalTime;PROarray[i].WeightWholeTime = (double)PROarray[i].WholeTime/PROarray[i].ServiceTime;} for (int i=0;i<n;i++){SumWT += PROarray[i].WholeTime;SumWWT += PROarray[i].WeightWholeTime;}AverageWT = SumWT/n;AverageWWT = SumWWT/n;for(int i=0;i<processNumber;i++){//输出for(int j=0;j<Time[i];j++){cout<<setw(3)<<count-2<<"--"<<setw(3)<<count-1<<setw(6)<<"时刻"<<"进程"<<processName[i]<<"开始执行";for(int k=0;k<n;k++){if(PROarray[k].ArrivalTime==count){cout<<" 进程"<<PROarray[k].name<<"到达";}else if(PROarray[k].FinishTime==count+1&&count!=0){cout<<" 进程"<<PROarray[k].name<<"完成";}}count+=1;cout<<endl;}}} //显示各时间执行情况，以及各个时间值void output(){int i;//输出各个时间cout<<"ID"<<"\t";cout<<"到达时间"<<"\t";cout<<"服务时间"<<"\t";cout<<"完成时间"<<"\t";cout<<"周转时间"<<"\t";cout<<"带权周转时间"<<endl;for (i=0;i<n;i++){cout<<PROarray[i].name<<"\t\t";cout<<PROarray[i].ArrivalTime<<"\t\t";cout<<PROarray[i].ServiceTime<<"\t\t";cout<<PROarray[i].FinishTime<<"\t\t";cout<<PROarray[i].WholeTime<<"\t\t";cout<<setprecision(3)<<PROarray[i].WeightWholeTime<<"\t\t"<<endl;;}cout<<"平均周转时间 = "<<setprecision(3)<<AverageWT<<endl;cout<<"平均带权周转时间 = "<<setprecision(3)<<AverageWWT<<endl;}