lei.txt

操作系统课程设计程序,能实现时间片法跟最高响应比法来进行进程调度.用结构体的链表来实现

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int processnum= 0;//进程数
int Round=0;      //时间片大小
float R;
int W[200];
int totalTimeSum=0;//总的周转时间
int WeightTotalTimeSum=0;//总的带权周转时间
struct PCBNode
{        
    int  processID;              //进程ID
    int  reqTime;                //总的需要运行时间
    int  needTime;               //剩下需要运行时间
    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, int Round,int& currentTime,PCBNode * ProcessTable);//分配时间片给q所指进程,p为刚退出的进程
void RoundRobin(LinkQueue& Q,int Round, int& totalTimeSum, int& WeightTotalTimeSum,PCBNode * ProcessTable);//时间片轮转调度,调用RR_Run(),时间片大小设为Round
void InitialQueue(LinkQueue& Q,PCBNode * ProcessTable, int processnum);//初始化就绪队列
void Input(PCBNode * ProcessTable, int processnum);//从input.txt文件输入数据
void HRN(LinkQueue &Q,PCBNode *ProcessTable);//最高响应比
void printHRN(LinkQueue &Q,int &totalTimeSum,int &WeightTotalTimeSum,PCBNode *ProcessTable);//最高响应比
int main()
{
    LinkQueue Q;              //就绪队列
    Q.head = NULL;
    char flag; 
	cout<<"请输入进程个数:"<<endl;
	cin>>processnum;
	PCBNode * ProcessTable=new PCBNode[processnum];   //进程表
	Input(ProcessTable, processnum);
    InitialQueue(Q, ProcessTable, processnum);
	cout<<"请选择进程调度算法，R为RR算法，H为HRN算法"<<endl;
	cin>>flag;
	if(flag=='r'||flag=='R')
	{
	cout<<"请输入时间片大小:"<<endl;
	cin>>Round;
    RoundRobin(Q, Round, totalTimeSum,WeightTotalTimeSum,ProcessTable);    
    cout<<"时间片轮调度的平均周转时间为:"<<float(totalTimeSum)/processnum<<endl;
    cout<<"时间片轮调度的平均带权周转时间为:"<<float(WeightTotalTimeSum)/processnum<<endl;
	}
	else if (flag=='h'||flag=='H')
	{
		HRN(Q,ProcessTable);
		cout<<"最高响应比优先调度算法的平均周转时间为:"<<float(totalTimeSum)/processnum<<endl;
		cout<<"最高响应比优先调度算法的平均带权周转时间为:"<<float(WeightTotalTimeSum)/processnum<<endl;
	}
	else 
	{
		cout<<"输入错误！";
	}
  return 0;
}
void RoundRobin(LinkQueue& Q,int Round, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable)//轮转法
{
    int currentTime = 0;   //当前时间
    QueueNode* p;
    QueueNode* q;
    QueueNode* r;
    bool finish = false;   //调用RR_Run()后,该进程是否已经做完退出   
    p = Q.head;
    q = p->next;
    currentTime=currentTime+ProcessTable[q->ID].arriveTime;
    while (q != NULL)      //从队首开始依次分配时间片
    {     
	
        do
        {    
            cout<<"在时间段"<<currentTime<<'~';
			if(ProcessTable[q->ID].needTime < Round){
          cout<<currentTime+ProcessTable[q->ID].needTime<<"内,活动进程为:  "<<"进程"<<ProcessTable[q->ID].processID<<endl;

			}
				else{
				cout<<currentTime+Round<<"内,活动进程为:  "<<"进程"<<ProcessTable[q->ID].processID<<endl;
				}			
			cout<<"现在还需要的时间片为:";
			if(ProcessTable[q->ID].needTime % Round==0)
			{
				cout<<ProcessTable[q->ID].needTime/Round-1<<endl;
			}
			else 
				cout<<ProcessTable[q->ID].needTime/Round<<endl;
            finish = RR_Run(Q, q, p, Round, currentTime, ProcessTable);//分配时间片给q进程
            cout<<endl; 
            if (!finish)                                               //若是进程在本时间片内没有做完
            {            
                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, int Round,int& currentTime,PCBNode * ProcessTable)
{   
    if (ProcessTable[q->ID].needTime<=Round)  //在此时间片内能够做完,之后退出进程调度
    {
        ProcessTable[q->ID].finishTime = currentTime + ProcessTable[q->ID].needTime;
        ProcessTable[q->ID].totalTime = ProcessTable[q->ID].finishTime-ProcessTable[q->ID].arriveTime;
        ProcessTable[q->ID].weightTotalTime =float(ProcessTable[q->ID].finishTime-ProcessTable[q->ID].arriveTime)/ProcessTable[q->ID].reqTime ;       
        currentTime = ProcessTable[q->ID].finishTime;       
        p->next = q->next;
        cout<<endl;
        cout<<"进程"<<q->ID<<"完成!"<<endl;
        cout<<"进程"<<q->ID<<"的周转时间为:"<<ProcessTable[q->ID].finishTime-ProcessTable[q->ID].arriveTime<<endl;
		cout<<"进程"<<q->ID<<"的带权周转时间为:"<<float(ProcessTable[q->ID].finishTime-ProcessTable[q->ID].arriveTime)/ProcessTable[q->ID].reqTime<<endl;
        return true;
    }
    else                                       //此时间片内做不完
    {

        ProcessTable[q->ID].needTime = ProcessTable[q->ID].needTime - Round;
        currentTime += Round;
        return false;
    }
}
void HRN(LinkQueue &Q,PCBNode *ProcessTable)
{
	QueueNode* p;
	float m;
    p=Q.head->next; //p指向第1号进程
	if (p!=NULL) 
    {
        ProcessTable[p->ID].startTime=ProcessTable[p->ID].arriveTime;//0号进程最先执行
        ProcessTable[p->ID].finishTime=ProcessTable[p->ID].startTime + ProcessTable[p->ID].needTime;
    }
	int j=0;
	R=0.0;
	W[0]=0;
	for(int n=1;n<processnum;n++)
	{
		int l;
		for(int i=1;i<processnum;i++)
		{
			if(ProcessTable[i].startTime==0)
			{
				if(ProcessTable[i].arriveTime<=ProcessTable[j].finishTime)
				m=float(ProcessTable[j].finishTime-ProcessTable[i].arriveTime)/ProcessTable[i].needTime;
				if(R<m && ProcessTable[i].startTime==0)
				{
					R=m;l=i;W[n]=i;
				}
			}
		}
		
		if(R==0)
		{
			j=j+1;W[n]=j;
			ProcessTable[j].startTime=ProcessTable[j].arriveTime;
			ProcessTable[j].finishTime=ProcessTable[j].startTime+ProcessTable[j].needTime;
		}
		else
		{
			ProcessTable[l].startTime=ProcessTable[j].finishTime;
			ProcessTable[l].finishTime=ProcessTable[l].startTime+ProcessTable[l].needTime;
			j=l;
		}
		R=0.0;
	}
	printHRN(Q,totalTimeSum,WeightTotalTimeSum,ProcessTable);
}
void printHRN(LinkQueue &Q,int &totalTimeSum,int &weightTotalTimeSum,PCBNode *ProcessTable)
{
	int i,j;
    QueueNode* p;
    QueueNode* 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 =float(ProcessTable[q->ID].totalTime)/ProcessTable[q->ID].needTime;//先将周转时间转换成float型才能得到float型的带权周转时间
        totalTimeSum+=ProcessTable[q->ID].totalTime;
        WeightTotalTimeSum+=ProcessTable[q->ID].weightTotalTime;
    }    
    for(i=0;i<processnum;i++)
    {
		while(ProcessTable[0].arriveTime<=ProcessTable[W[i]].finishTime)
		{
			cout<<"时刻"<<ProcessTable[0].arriveTime<<":"<<endl;
			for(j=i;j<processnum;j++)//判断该时刻当前进程以及后续是否到达
			{
				if(ProcessTable[0].arriveTime==ProcessTable[W[j]].arriveTime)
					cout<<"进程"<<W[j]<<"到达"<<endl;
			}
			if(ProcessTable[0].arriveTime==ProcessTable[W[i]].startTime)
			{
				cout<<"进程"<<W[i]<<"开始运行"<<endl;
			}
			else if(ProcessTable[0].arriveTime<ProcessTable[W[i]].finishTime && ProcessTable[0].arriveTime>ProcessTable[W[i]].startTime)
			{
				cout<<"进程"<<W[i]<<"活动"<<endl;
			}
			else if(ProcessTable[0].arriveTime==ProcessTable[W[i]].finishTime)
			{
				if(W[i+1]!=NULL)
				{
					cout<<"进程"<<W[i]<<"结束活动,";
					if(ProcessTable[0].arriveTime>=ProcessTable[W[i+1]].arriveTime)
						cout<<"进程"<<W[i+1]<<"开始运行"<<endl;
					else 
					cout<<endl;
					cout<<"进程"<<W[i]<<"的周转时间为: "<<ProcessTable[W[i]].totalTime<<endl;
					cout<<"进程"<<W[i]<<"的带权周转时间为: "<<ProcessTable[W[i]].weightTotalTime<<endl;
				}
				else
				{
					cout<<"进程"<<W[i]<<"结束活动."<<endl<<endl;
					cout<<"进程"<<W[i]<<"的周转时间为: "<<ProcessTable[W[i]].totalTime<<endl;
					cout<<"进程"<<W[i]<<"的带权周转时间为: "<<ProcessTable[W[i]].weightTotalTime<<endl<<endl; 
				}
			}
			else cout<<"无进程进入。"<<endl;
			ProcessTable[0].arriveTime=ProcessTable[0].arriveTime+1;
			cout<<endl;
		}
	}
	delete Q.head;
    Q.head = NULL;
}
void InitialQueue(LinkQueue& Q, PCBNode * ProcessTable,int processnum)    //初始化
{
     for (int i=0;i<processnum;i++)
    {
        ProcessTable[i].processID=i;
        ProcessTable[i].reqTime=ProcessTable[i].needTime;
        ProcessTable[i].finishTime=0;
        ProcessTable[i].startTime=0;    
        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, 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].processID,&ProcessTable[i].arriveTime,&ProcessTable[i].needTime);
		}

    fclose(fp);
}