fcfs.cpp

链接指针：按照进程到达系统的时间将处于就绪状态的进程连接成衣个就绪队列。指针指出下一个到达进程的进程控制块首地址。最后一个进程的链接指针为NULL。 估计运行时间：可由设计者任意指定一个时间值。

// 时间片轮转调度算法
#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;//队首
};

void Fcfs(LinkQueue& Q,int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable);
//先来先服务算法
void InitialQueue(LinkQueue& Q,PCBNode * ProcessTable,const int processnum);

void Input(PCBNode * ProcessTable, const int processnum);

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);
	Fcfs(Q, totalTimeSum,WeightTotalTimeSum,ProcessTable);
	cout<<"先来先服务的平均周转时间为:"<<totalTimeSum/processnum<<endl;
	cout<<"先来先服务的平均带权周转时间为:"<<WeightTotalTimeSum/processnum<<endl;

	delete [] ProcessTable;

	system("Pause");
	if(getchar()=='y')
		getchar();
	return 0;
}



void Fcfs(LinkQueue& Q, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable)
{
	totalTimeSum = 0;
	weightTotalTimeSum = 0;//平均周转时间
	QueueNode* p;
	QueueNode* q;
	
	p = Q.head->next;
	if (p !=NULL ) 
	{
		ProcessTable[p->ID].startTime = ProcessTable[p->ID].arriveTime;
		ProcessTable[p->ID].finishTime = ProcessTable[p->ID].arriveTime + ProcessTable[p->ID].reqTime;
	}
	
	for(q=p->next; q!=NULL; q=q->next)
	{
		
		if (ProcessTable[q->ID].arriveTime < ProcessTable[p->ID].finishTime)
		{
			ProcessTable[q->ID].startTime = ProcessTable[p->ID].finishTime;
			ProcessTable[q->ID].finishTime = ProcessTable[p->ID].finishTime + ProcessTable[q->ID].reqTime;
		}
		else//下个进程到达时间较晚
		{
			ProcessTable[q->ID].startTime = ProcessTable[q->ID].arriveTime;
			ProcessTable[q->ID].finishTime = ProcessTable[q->ID].arriveTime + ProcessTable[q->ID].reqTime;
		}
		p = q;
	}
	
	for(q=Q.head->next; q!=NULL; q=q->next)
	{
		ProcessTable[q->ID].totalTime = ProcessTable[q->ID].finishTime - ProcessTable[q->ID].arriveTime;
		ProcessTable[q->ID].weightTotalTime = ProcessTable[q->ID].totalTime/ProcessTable[q->ID].reqTime;		
		totalTimeSum += ProcessTable[q->ID].totalTime;
		weightTotalTimeSum += ProcessTable[q->ID].weightTotalTime;
	}	
	
	int t = 0;
	for(q=Q.head->next; q!=NULL; q=q->next)
	{
		cout<<"*********************"<<endl;
		while ( t<ProcessTable[q->ID].finishTime )
		{
			cout<<"时刻"<<t<<":  进程"<<q->ID<<"活动"<<endl;
			t++;
		}
		if (q->next != NULL)
		{	
			cout<<"时刻"<<t<<":  进程"<<q->ID<<"结束活动,开始下一个进程."<<endl;
			cout<<"进程"<<q->ID<<"的周转时间为: "<<ProcessTable[q->ID].totalTime<<endl;
			cout<<"进程"<<q->ID<<"的带权周转时间为: "<<ProcessTable[q->ID].weightTotalTime<<endl<<endl;
		}
		else
		{
			cout<<"时刻"<<t<<":  进程"<<q->ID<<"结束活动."<<endl<<endl;
			cout<<"进程"<<q->ID<<"的周转时间为: "<<ProcessTable[q->ID].totalTime<<endl;
			cout<<"进程"<<q->ID<<"的带权周转时间为: "<<ProcessTable[q->ID].weightTotalTime<<endl<<endl;			
		}
	}
	cout<<"所有进程结束活动."<<endl<<endl;

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

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);
}