sy.cpp

操作系统实验 实现先进先出算法 基于优先级算法 最短执行时间算法

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <iostream.h>
#include <time.h>
#define NUM 4

typedef struct pcb{
	char name[10];		//进程名
	int state;			//进程状态
	int prior;			//优先级
    int exetime;		//执行时间
	int exe;              //是否执行过
	struct pcb *next;	//指向下一个PCB
}pcb,*PCB;

typedef struct {
	PCB front;			//对头指针 
	PCB rear;			//队尾指针

}team;					//队列

void Initteam(team &Q){
	  //初始化队列
	  Q.front=Q.rear=(PCB)malloc(sizeof(pcb));
	  if(!Q.front) exit(0);  //存储分配失败
	  Q.front->next=NULL;


}


void Enteam(team &Q,PCB e){
   //入队函数
	 Q.rear->next=e;
     e->next=NULL;
	 Q.rear=e;
 }

 void Deteam(team &Q,PCB &e){
	 //出队函数

	 e=Q.front->next;
	 Q.front->next=e->next;
	 if(Q.rear==e) Q.rear=Q.front;
	
}


void Inti(team &Q1, team &Q2){
	int i;
	PCB s;
	PCB h1;
	PCB h2;
	int Q1num,Q2num;
	cout<<"请输入PCB的信息："<<endl<<endl;
	
    for(i=1;i<=NUM;i++){
		 s=(PCB)malloc(sizeof(pcb));
		 s->exe=0;
		 cout<<"第"<<i<<"个PCB:"<<endl<<endl;
		 cout<<"请输入此PCB的名称:  ";
		 cin>>s->name;
	   	 cout<<endl;
		 cout<<"请输入此PCB的优先级:  "; 
		 cin>>s->prior;
		 cout<<endl;
	     cout<<"请输入此PCB的执行时间:  ";
		 cin>>s->exetime;
		 cout<<endl;
		 
		 s->state=rand()%2;
		 if(s->state==1)
			Enteam(Q1,s); //1表示在等待态中
	   	 if(s->state==0)
			Enteam(Q2,s); //0表示在就绪态中
		 
	}
	h1=Q1.front;
	h2=Q2.front;
	
	cout<<"当前在等待队列中的PCB是："<<endl;
	if(Q1.front==Q1.rear)
		cout<<"就绪队列为空"<<endl;
	for(Q1num=0;h1!=Q1.rear; Q1num++)
			{h1=h1->next;
			 cout<<Q1num+1<<".  "<<h1->name<<endl;}
	cout<<endl;
	//记下等待态中PCB数目
	cout<<"当前在就绪队列中的PCB是："<<endl;
    if(Q2.front==Q2.rear)
	{	cout<<"抱歉，当前就绪队列为空"<<endl;
		cout<<endl;}
	for(Q2num=0;h2!=Q2.rear; Q2num++)
			{h2=h2->next;
			cout<<Q2num+1<<".   "<<h2->name<<endl;}
	cout<<endl;
	//记下就绪态中PCB数目
	
 }
 

void FIFO(team Q1,team Q2){
     //先来先出调度算法,Q1为等待态队列，Q2为就绪态队列
     PCB s;
	 int i;
	 int Q1num,Q2num;
	 cout<<"先进先出算法："<<endl;
	 for(int n=1;n<=NUM;n++){
		 PCB e=(PCB)malloc(sizeof(pcb));//e用于接受Q1的第一个PCB
         PCB d=(PCB)malloc(sizeof(pcb));//d用于接受Q2的第一个PCB
		 PCB h1=Q1.front;
		 PCB h2=Q2.front;
		
		cout<<"第"<<n<<"轮执行"<<endl;
		for(Q1num=0;h1!=Q1.rear; Q1num++)
			{h1=h1->next;}//记下等待态中PCB数目
		for(Q2num=0;h2!=Q2.rear; Q2num++)
			{h2=h2->next;}//记下就绪态中PCB数目
	 
		 if(Q2num==0)//就绪态队列为空
		   {Deteam(Q1,e);//让Q1的第一PCB出队，保存在e中
			Enteam(Q2,e);
			Deteam(Q2,d);//让Q2的第一PCB出队，保存在d中
			Enteam(Q1,d);
			cout<<"当前就绪态为空，所以执行等待队列的PCB!"<<endl;
			cout<<endl;
			cout<<"当前在执行的PCB是： "<<d->name<<endl;
			cout<<"其执行时间是："<<d->exetime<<endl;
            cout<<"其优先级是："<<d->prior<<endl;          
			cout<<endl;
			cout<<"经过执行，现在的等待队列中的PCB是："<<endl;
			s=Q1.front->next;
			for(i=1;i<=Q1num;i++)
			{	cout<<i<<"."<<s->name<<endl;
				s=s->next;
			}
			cout<<endl;
			cout<<"执行完成，当前就绪队列依然为空!"<<endl;
	 }
	       
	 else if(Q1num==0)//等待队列为空	  
     {		Deteam(Q2,d);//让Q2的第一PCB出队，保存在d中
			Enteam(Q1,d);//让d进入Q1的队尾
			
		    
			cout<<"当前在执行的PCB是： "<<d->name<<endl;
			cout<<"其执行时间是："<<d->exetime<<endl;
            cout<<"其优先级是："<<d->prior<<endl<<endl;     
			cout<<"经过执行，现在的等待队列中的PCB是："<<endl;
			s=Q1.front->next;
			for(i=1;i<=Q1num;i++)
			{	cout<<i<<"."<<s->name<<endl;
				s=s->next;
			}
			if(Q2.front==Q2.rear)
				cout<<"经过执行，现在的就绪队列为空"<<endl;
			else{
				cout<<"经过执行，现在的就绪队列中的PCB是："<<endl;
				s=Q2.front->next;
				for(i=1;i<=Q2num;i++)
				{	cout<<i<<"."<<s->name<<endl;
					s=s->next;
				}
				cout<<endl;
			}
	 
	 }
	 else{  
		    Deteam(Q2,d);//让Q2的第一PCB出队，保存在d中
			Enteam(Q1,d);//让d进入Q1的队尾
		    Deteam(Q1,e);//让Q1的第一PCB出队，保存在e中
			Enteam(Q2,e);//让e进入Q2的队尾
			cout<<"当前在执行的PCB是： "<<d->name<<endl;
			cout<<"其执行时间是："<<d->exetime<<endl;
            cout<<"其优先级是："<<d->prior<<endl;     
			cout<<endl;
			cout<<"经过执行，现在的等待队列中的PCB是："<<endl;
			s=Q1.front->next;
			for(i=1;i<=Q1num;i++)
			{	cout<<i<<"."<<s->name<<endl;
				s=s->next;
			}
			cout<<endl;
			cout<<"经过执行，现在的就绪队列中的PCB是："<<endl;
			s=Q2.front->next;
			for(i=1;i<=Q2num;i++)
			{	cout<<i<<"."<<s->name<<endl;
                s=s->next;
			}
			cout<<endl;
	 }
	 }//for
     }

void FIFOtime(team Q1,team Q2){
	//计算先进先出算法周转时间函数，Q1为等待态队列，Q2为就绪态队列
	float t[NUM+1],tave,tsum,w[NUM+1],wave,wsum;
	//定义周转时间，平均周转时间带权周转时间，平均带权周转时间
	PCB s;
	PCB h1=Q1.front;
	PCB h2=Q2.front;
	int i;
	int Q1num,Q2num;
	for(Q1num=0;h1!=NULL; Q1num++)
			{h1=h1->next;}//记下等待态中PCB数目
	for(Q2num=0;h2!=NULL; Q2num++)
			{h2=h2->next;}//记下就绪态中PCB数目
     s=Q1.front->next;
	 t[0]=0;  
     w[0]=0;//0单元不用
	 for(i=1;i<=(Q1num-1);i++)
	 {	 t[i]=t[i-1]+s->exetime;
		 w[i]=t[i]/(s->exetime); 
		 s=s->next;
	 }
	 
	 s=Q2.front->next;
	 for(;i<=NUM;i++)
	 {	
		 t[i]=t[i-1]+s->exetime;
    	 w[i]=t[i]/(s->exetime);
         s=s->next;
	 }
	  tsum=0;
      wsum=0;
      for(i=1;i<=NUM;i++)
	  {	 tsum=tsum+t[i];
         wsum=wsum+w[i];}
      tave=tsum/NUM;
      wave=wsum/NUM;
      cout<<"FIFO算法的平均周转时间是：" <<tave;
	  cout<<endl;
      cout<<"FIFO算法的平均带权周转时间是："<<wave;
	  cout<<endl<<endl;
}

void  Prior(team Q1,team Q2){
	//基于优先级的算法 每次执行就绪队列里优先级高的PCB
	//Q1为等待态队列，Q2为就绪态队列
	PCB h1=Q1.front->next;
	PCB h2=Q2.front->next;
	PCB e=(PCB)malloc(sizeof(pcb)); //接收Q1中出队的PCB
	PCB min;//=(PCB)malloc(sizeof(pcb));            //记下优先级最高的PCB
    int minprior;      //记下最高的那个优先级数
	int i,n;
	for(int Q1num=0;h1!=NULL; Q1num++)
			{h1=h1->next;}//记下等待态中PCB数目 
	for(int Q2num=0;h2!=NULL; Q2num++)
			{h2=h2->next;}//记下就绪态中PCB数目
	cout<<"基于优先级算法："<<endl;
	for(n=1;n<=NUM;n++){
		if((Q2num!=0)&&(Q1num!=0)){
        h2=Q2.front->next;
		minprior=h2->prior;
		min=Q2.front->next;//h2;
		for(i=1;i<=Q2num;i++){
			if((minprior>=(h2->prior))&&((h2->exe)!=1))
			{
				minprior=h2->prior;
				min=h2;
			}//if
			h2=h2->next;
		}//for
		h2=Q2.front;
		while((h2->next)!=min){
			h2=h2->next;
		}//while
		min->exe=1;
		cout<<"第"<<n<<"轮执行"<<endl;
		cout<<"正在执行的是："<<min->name<<endl;
		cout<<"其执行时间是："<<min->exetime<<endl;
		cout<<"其优先级是："<<min->prior<<endl<<endl;
		
		if(min!=Q2.rear)//->next)!=NULL)
			h2->next=min->next;
		else if((min->next)==NULL)
		{	Q2.rear=h2;
			Q2.rear->next=NULL;}
		Enteam(Q1,min);    //min执行完毕后进入等待队列
		Deteam(Q1,e);      //等待队列第一个PCB出队
		Enteam(Q2,e);
		cout<<"经过执行，当前等待队列里的PCB是："<<endl;
		PCB a,b;