rr.cpp

链接指针：指出下一个到达进程的进程控制块首地址。按照进程到达的顺序排队。系统设置一个队头和队尾指针分别指向第一个和最后一个进程。新生成的进程放队尾。 估计运行时间、到达时间以及进程状态一第一题中相同

// 时间片轮转调度算法
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;
enum STATUS {RUN,READY,WAIT,FINISH};

struct PCBNode
{		
	int  processID;	          //进程ID
	STATUS  status;	          //进程状态
	int  priorityNum;	      //优先数
	int  reqTime;             //总的需要运行时间
	int  remainTime;          //剩下需要运行时间
	int  arriveTime;          //进入就绪队列时间
	int  startTime;           //开始运行时间
	int  finishTime;          //结束运行时间
	int  totalTime;           //周转时间
    float  weightTotalTime;	  //带权周转时间	
};

struct QueueNode 
{
	int ID;          //进程ID
	struct QueueNode * next;   //队列中下一个进程指针
};

struct LinkQueue
{
	QueueNode *head;//队首
};

bool RR_Run(LinkQueue& Q,QueueNode* q, QueueNode* p, const int Round,int& currentTime,PCBNode * ProcessTable);
//分配时间片给q所指进程,p为刚退出的进程
void RoundRobin(LinkQueue& Q,const int Round, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable);
//时间片轮转调度,调用RR_Run(),时间片大小设为Round
void InitialQueue(LinkQueue& Q,PCBNode * ProcessTable,const int processnum);
//初始化就绪队列
void Input(PCBNode * ProcessTable, const int processnum);
//从input.txt文件输入数据

int main()
{
	LinkQueue Q;//就绪队列
	Q.head = NULL;
    const int processnum = 16;//进程数
	const int Round = 1;      //时间片大小
	int totalTimeSum = 0;     //周转时间
	int	WeightTotalTimeSum = 0;//带权周转时间
	PCBNode * ProcessTable=new PCBNode[processnum];   //进程表

	Input(ProcessTable, processnum);
	InitialQueue(Q, ProcessTable, processnum);
	RoundRobin(Q, Round, totalTimeSum,WeightTotalTimeSum,ProcessTable);	
	cout<<"时间片轮调度的平均周转时间为:"<<totalTimeSum/processnum<<endl;
	cout<<"时间片轮调度的平均带权周转时间为:"<<WeightTotalTimeSum/processnum<<endl;

	delete [] ProcessTable;
	return 0;
}

void RoundRobin(LinkQueue& Q,const int Round, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable)
{
	totalTimeSum = 0;   //总的周转时间
	weightTotalTimeSum = 0;//平均周转时间
	int currentTime = 0;   //当前时间
	QueueNode* p;
	QueueNode* q;
	QueueNode* r;
	bool finish = false;//调用RR_Run()后,该进程是否已经做完退出
	
	p = Q.head;
	q = p->next;
	while (q != NULL)//从队首开始依次分配时间片
	{
		do
		{		
			cout<<"**********************"<<endl;
			cout<<"在时间片"<<(currentTime+1)/Round<<"内,活动进程为:  "<<q->ID<<endl;
			cout<<"进程"<<q->ID<<" 现在需要的时间片为:  "<<ProcessTable[q->ID].remainTime<<endl;
			finish = RR_Run(Q, q, p, Round, currentTime, ProcessTable);//分配时间片给q进程
			cout<<endl;
			
			if (!finish)//若是进程在本时间片内做完,则跳出do…while循环
			{			
				if (q->next == NULL) 
				{
					r = Q.head->next;
				}
				else
				{
					r = q->next;
				}
			}
			else //否则计算周转时间和带权周转时间
			{
				totalTimeSum += ProcessTable[q->ID].totalTime;
				weightTotalTimeSum += ProcessTable[q->ID].weightTotalTime;

		        delete q; //从队列中删除q进程
				q = p;
			}
		}while (!finish &&  (ProcessTable[r->ID].arriveTime > currentTime + Round));
		//下一个进程很晚才来,则继续给当前进程分配时间片
		
		p = q;
		q = q->next;

		if (q == NULL && Q.head->next!=NULL)
		{
			p = Q.head;
			q = p->next;
		} 
	} 
	delete Q.head;
	Q.head = NULL;
}

bool RR_Run(LinkQueue& Q,QueueNode* q, QueueNode* p, const int Round,int& currentTime,PCBNode * ProcessTable)
{
	if (ProcessTable[q->ID].remainTime <= Round)//在此时间片内能够做完,之后退出进程调度
	{
		ProcessTable[q->ID].finishTime = currentTime + ProcessTable[q->ID].remainTime;
		ProcessTable[q->ID].totalTime += ProcessTable[q->ID].remainTime;
		ProcessTable[q->ID].weightTotalTime = ProcessTable[q->ID].totalTime/ProcessTable[q->ID].reqTime;		

		currentTime = ProcessTable[q->ID].finishTime;
		
		p->next = q->next;
		cout<<endl;
		cout<<"进程"<<q->ID<<"完成!"<<endl;

		return true;
	}
	else//此时间片内做不完
	{
		ProcessTable[q->ID].remainTime = ProcessTable[q->ID].remainTime - Round;
		ProcessTable[q->ID].totalTime += Round;
		currentTime += Round;
		
		return false;
	}
}


void InitialQueue(LinkQueue& Q, PCBNode * ProcessTable,const int processnum)
{
	//初始化
	
	for (int i=0;i<processnum;i++)
	{
		ProcessTable[i].processID=i;
		ProcessTable[i].reqTime=ProcessTable[i].remainTime;
		ProcessTable[i].finishTime=0;
		ProcessTable[i].startTime=0;	
		ProcessTable[i].status=WAIT;
		ProcessTable[i].totalTime=0;
		ProcessTable[i].weightTotalTime=0;		
	}
	
	Q.head = new QueueNode;
	Q.head->next = NULL;
	QueueNode * p;
	QueueNode * q;
	for (i=0;i<processnum;i++)
	{	
		p = new QueueNode;
		p->ID = i;
		p->next = NULL;
		if (i == 0)
		{
			Q.head->next = p;			
		}
		else
			q->next = p;
		
		q = p;
	}
}


void Input(PCBNode * ProcessTable, const int processnum)
{
	FILE *fp;		//读入线程的相关内容
	if((fp=fopen("input.txt","r"))==NULL)
	{
		cout<<"can not open file!"<<endl;
		exit(0);
	}		
	for(int i=0;i<processnum;i++)
	{
		fscanf(fp,"%d %d %d",&ProcessTable[i].arriveTime,&ProcessTable[i].remainTime,&ProcessTable[i].priorityNum);
	}
	fclose(fp);
}