时间片轮转法

《操作系统》实验二内容要求

【实验题目】：时间片轮转RR进程调度算法

【实验学时】：4学时

【实验目的】

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

【实验内容】

问题描述：

设计程序模拟进程的时间片轮转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）进程调度的实现过程如下：

 变量初始化；

 接收用户输入n，T1, … ,Tn，S1, … ,Sn；时间片大小q；

 按照时间片轮转RR算法进行进程调度，计算进程的完成时间、周转时间和带权周转时间；

 计算所有进程的平均周转时间和平均带权周转时间；

 按格式输出调度结果。

代码

#include

#include

#include

using namespace std;

const int MaxNum = 100;

struct Node{

int index;

int arriveTime;

int rest;

};

bool NodeCmp(const Node& a,const Node& b)

{

return a.arriveTime < b.arriveTime;

}

int n; //进程数

int ArrivalTime[MaxNum];

int ServiceTime[MaxNum];

int PServiceTime[MaxNum];

int FinishTime[MaxNum];

int WholeTime[MaxNum];

double WeightWholeTime[MaxNum];

bool Finished[MaxNum];

double AverageWT,AverageWWT;

bool isEnterQue[MaxNum];

int cntTimes[MaxNum];

void init()

{

memset(PServiceTime,0,sizeof(PServiceTime));

memset(Finished,0,sizeof(Finished));

memset(FinishTime,0,sizeof(FinishTime));

memset(WholeTime,0,sizeof(WholeTime));

memset(WeightWholeTime,0,sizeof(WeightWholeTime));

}

int sum(int array[],int n)

{

int sum=0;

int i;

for(i=0;i

{

sum += array[i];

}

return sum;

}

double sum(double array[],int n)

{

double sum=0;

int i;

for(i=0;i

{

sum += array[i];

}

return sum;

}

void print()

{

int i=0;

cout<<"进程完成时间:";

for(i=0;i

{

cout<

}

cout<

cout<<"周转时间:";

for(i=0;i

{

cout<

}

cout<

cout<<"带权周转时间:";

for(i=0;i

{

printf("%.2f ",WeightWholeTime[i]);

}

cout<

}

void SearchToEnterQue(queue& que,Node* pArr,int maxArrivalTime)

{

int i;

for(i=0;i

{

if(pArr[i].arriveTime>maxArrivalTime)

break;

if(isEnterQue[pArr[i].index]==false)

{

que.push(pArr[i]);

isEnterQue[pArr[i].index] = true;

}

}

}

void Work(int q)

{

init();

memset(isEnterQue,0,sizeof(isEnterQue));

memset(cntTimes,0,sizeof(cntTimes));

Node* pNodeArr = new Node[n];

int i;

for(i=0;i

{

pNodeArr[i].index = i;

pNodeArr[i].arriveTime = ArrivalTime[i];

pNodeArr[i].rest = ServiceTime[i];

}

sort(pNodeArr,pNodeArr+n,NodeCmp);

int totalTime = sum(ServiceTime,n);

int time=pNodeArr[0].arriveTime;

queue que;

que.push(pNodeArr[0]);

isEnterQue[pNodeArr[0].index]=true;

Node cur;

cout<<"================================================="<

while(!que.empty()) {

cur = que.front();

que.pop();

cntTimes[cur.index]++;

if(cntTimes[cur.index]==1)

printf("在%d时刻，进程%d开始执行。。。\n",time,cur.index);

if(cur.rest > q)

{

time += q;

cur.rest -= q;

}

else

{

time += cur.rest;

Finished[cur.index]=true;

FinishTime[cur.index] = time;

cur.rest = 0;

printf("在%d时刻，进程%d执行结束。\n",time,cur.index);

}

SearchToEnterQue(que,pNodeArr,time);

if(cur.rest!=0)

que.push(cur);

if(que.empty())//若队列为空，则在time之后才达到的进程找最早到达的进程入队列

{

for(i=0;i

{

if(isEnterQue[i]==false)//找到了

{

que.push(pNodeArr[i]);//入队列

time = pNodeArr[i].arriveTime;

break;

}

}

}

}

for(i=0;i

{

WholeTime[i] = FinishTime[i] - ArrivalTime[i];

WeightWholeTime[i] = (double)WholeTime[i] / (double)ServiceTime[i];

}

AverageWT = (double)sum(WholeTime,n)/(double)n;

AverageWWT=(double)sum(WeightWholeTime,n)/(double)n; cout<<"================================================="<

print();

cout< cout<<"================================================="<

printf("平均周转时间:%.2f,平均带权周转时间:%.2f\n",AverageWT,AverageWWT);

delete[] pNodeArr;

}

int main()

{

// freopen("test.txt","rw",stdin);

int q;//时间片大小

int i;

cout<<"输入进程数:";

cin>>n;;

cout<<"输入每个进程的到达时间:"<

for(i=0;i

cin>>ArrivalTime[i];

cout<<"输入每个进程的服务时间:"<

for(i=0;i

cin>>ServiceTime[i];

cout<<"输入时间片大小"<

cin>>q;

Work(q);

return 0;

}

运行截图

本文来源：https://www.2haoxitong.net/k/doc/450905ef6294dd88d0d26bdb.html