// 时间片轮转调度算法.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
#include
#include
using namespace std;
int ArrivalTime[100]; //进程到达时间
int ServiceTime[100]; //进程服务时间
int PServiceTime[100]; //剩余服务时间
int FinishTime[100]; //进程完成时间
int WholeTime[100]; //周转时间
double WeightWholeTime[100]; //带权周转时间
double AverageWT; //平均周转时间
double AverageWWT; //平均带权周转时间
bool Finished[100]; //标记进程是否完成
int n,i,j; //n为进程数量,i和j为循环变量
int q; //q为时间片大小
int NowTime=0; //当前时刻
//定义一个"进程"结构体,包含进程Id,进程所需内容可根据Id号得到
typedef struct Process{
int ProcessID; //进程ID
struct Process *next;
}Process,*ProcessPtr;
//定义一个队列CpuQueue,模仿CPU
typedef struct CpuQueue{
int count;
ProcessPtr beginzz; //队头指针
ProcessPtr endzz; //队尾指针
}CpuQueue;
//初始化队列函数
void InitQueue(CpuQueue &c){
c.count=0;
c.beginzz=c.endzz=(ProcessPtr)malloc(sizeof(Process));
c.beginzz->next=NULL;
}
//判断队列是否为空,如果为空返回true
bool IsEmpty(CpuQueue c){
/* if(Q.count==0){
return true;
}
return false;*/
return c.beginzz==c.endzz?true:false;
}
//进队函数,将进程号为id的进程进队
void EnQueue (CpuQueue &c,int id){
ProcessPtr p;
p=(ProcessPtr)malloc(sizeof(Process));
p->ProcessID=id;
p->next = NULL;
c.endzz->next=p;;
c.endzz = p;
c.count++;
cout<<"进队1次使用:"<<" 个数:"<<c.count<<endl;
}
//出队函数,返回队首指针的进程ID号
int DeQueue (CpuQueue &c)
{
int id;
ProcessPtr p;
if(c.beginzz->next==NULL){cout<<"yes!"<
p=c.beginzz->next;
id=p->ProcessID;
c.beginzz->next = p->next;
c.count--;
free(p);
cout<<"出队1次使用:"<<" 个数:"<<c.count<<endl;
return id;
}
//将进程号在num数组中按规定顺序排列好
//返回num[]为按时间到达先后顺序排列的进程号
int* order(int ArrivalTime[]){
int *num=new int[100];
for(i=0;i<n;i++){
num[i]=i; //初始化num数组
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(ArrivalTime[num[i]]<ArrivalTime[num[j]]){
int temp=num[i];
num[i]=num[j];
num[j]=temp;
}
}
}
return num;
}
//时间片轮转调度算法
void RR(){
CpuQueue c;
InitQueue(c);
int *num=new int[100];
num=order(ArrivalTime); //返回按到达时间先后顺序排列好的数组num
if(ArrivalTime[0]>NowTime)
{
NowTime=ArrivalTime[0];
}
EnQueue(c,0); //先把第一个进程进队
bool isFirst=true;
i=1;
while(!IsEmpty(c)||isFirst){
isFirst=false;
int proId=DeQueue(c);
if(PServiceTime[proId]<=q){ //当剩余服务时间比时间片q小的情况
NowTime+=PServiceTime[proId];
PServiceTime[proId]=0; //对该进程剩余时间归0
//如果进程在上一个进程完成之前到达,则进队
while(i<n&&ArrivalTime[i]<=NowTime)
{
EnQueue(c,i);
i++;
}
//对进程数据进行赋值操作
FinishTime[proId]=NowTime;
WholeTime[proId]=FinishTime[proId]-ArrivalTime[proId]; //周转时间=完成时间-到达时间
WeightWholeTime[proId]=WholeTime[proId]/ServiceTime[proId]; //带权周转时间=周转时间/服务时间
}
else{ //当剩余服务时间比时间片大的情况
PServiceTime[proId]=PServiceTime[proId]-q; //剩余服务时间处理
NowTime=NowTime+q;
//如果进程在上一个进程时间片用完之前到达,则进队
while(i<n&&ArrivalTime[i]<=NowTime)
{
EnQueue(c,i);
i++;
}
EnQueue(c,proId);
}
}
}
//输入函数,用于接收数据
void input(){
cout<<"请输入进程数量n: ";
cin>>n;
while(n100){
cout<<"n为1~100之间的整数,请重新输入。n=";
cin>>n;
}
cout<<"-------------------------------------------"<
for(i=0;i
cout
cin>>ArrivalTime[i];
}
cout<<"-------------------------------------------"<<endl;
for(i=0;i<n;i++){
cout<<"请输入第"<<i+1<<"进程的服务时间:";
cin>>ServiceTime[i];
}
//初始化PServiceTime[]
for(i=0;i<n;i++){
PServiceTime[i]=ServiceTime[i];
}
cout<<"-------------------------------------------"<<endl;
cout<<"请输入时间片大小q: ";
cin>>q;
}
//打印输出函数
//将进程进展情况以表格的形式打印
void print()
{
cout<<"-------------------------------------------"<<endl;
cout<<"进程名\t\t";
for(i=0;i<n;i++)
{
char c=i+65;
cout<<c<<"\t";
}
cout<<"\n到达时间\t";
for(i=0;i<n;i++)
{
cout<<ArrivalTime[i]<<"\t";
}
cout<<"\n服务时间\t";
for(i=0;i<n;i++)
{
cout<<ServiceTime[i]<<"\t";
}
cout<<"\n完成时间\t";
for(i=0;i<n;i++)
{
cout<<FinishTime[i]<<"\t";
}
cout<<"\n周转时间\t";
for(i=0;i<n;i++)
{
cout<<setprecision(3)<<WholeTime[i]<<"\t";
}
cout<<"\n带权周转时间\t";
for(i=0;i<n;i++)
{
cout<<setprecision(3)<<WeightWholeTime[i]<<"\t";
}
cout<<"\n剩余服务时间\t";
for(i=0;i<n;i++)
{
cout<<setprecision(3)<<PServiceTime[i]<<"\t";
}
cout<<endl;
for(int i=0;i<n;i++) //计算平均周转时间和平均带权周转时间
{
AverageWT+=(double)WholeTime[i]/n;
AverageWWT+=(double)WeightWholeTime[i]/n;
}
cout<<endl;
cout<<setprecision(3)<<"平均周转时间: "<<AverageWT<<endl;
cout<<setprecision(3)<<"平均带权周转时间: "<<AverageWWT<<endl;
}
int main(int argc, char* argv[])
{
input();
RR();
print();
return 0;
}
在进队函数中 c.beginzz->next 轮转几次就变为空
我用的输入 进程数:1
到达时间:2
服务时间:3
q=1 测试的