//
//程序名稱：進(jìn)程調(diào)度模擬程序
//程序作者：張煥人
//作者郵箱: renwairen369@yahoo.com.cn
//          renwairen369@hotmail.com
//作者QQ：27949278
//
//
//


#include <iostream.h>
#include <stdio.h>
typedef struct pcb 
{ 
 char name[10];  //進(jìn)程名
 char state;   //狀態(tài)w(就緒)r(運(yùn)行)f(結(jié)束)
 int super;   //優(yōu)先級
 int atime;   //到達(dá)時(shí)間
 int ntime;   //需運(yùn)行的時(shí)間
 int rtime;   //已運(yùn)行的時(shí)間
 struct pcb *next;
}*pcb1; 

int time=0;
int alg=1;
pcb1 s,w;//s,w分別是就緒隊(duì)列、阻塞隊(duì)列的節(jié)點(diǎn)


void print(pcb1 p)
//輸出就緒隊(duì)列信息
{
 pcb1 p0; //c語言當(dāng)中指針傳遞直接傳地址!!!
 if(p==NULL) cout<<"  當(dāng)前隊(duì)列為空"<<endl;
 else
 {
       p0=p;
	   cout<<"  "<< p0->name;
	   p0=p0->next;
       while(p0!=NULL)
	   {
	       cout<<" -> ";
		   cout<<p0->name;
		   p0=p0->next;
	   }
       cout<<endl;
 }
 
}

void printpcb()
//輸出pcb信息
{
 pcb1 p0;
 if(s==NULL&&w==NULL) cout<<"  當(dāng)前沒有進(jìn)程處于調(diào)度中"<<endl;
 else
 {
       cout<<"當(dāng)前處于調(diào)度中進(jìn)程的PCB信息:"<<endl;
       cout<<"\t進(jìn)程名 "<<"\t優(yōu)先級 "<<"\t狀態(tài)"<<"\t到達(dá)時(shí)間 "<<"\t已運(yùn)行時(shí)間 "<<"\t需運(yùn)行時(shí)間"<<endl;
       p0=s;
	   while(p0!=NULL)
	   {
	       cout<<"\t"<<p0->name<<"\t "<<p0->super<<"\t "<<p0->state<<"\t "<<p0->atime<<"\t\t "<<p0->rtime<<"\t\t "<<p0->ntime<<endl;
	       p0=p0->next;
	   }
	   p0=w;
	   while(w!=NULL)
	   {
	       cout<<"\t"<<p0->name<<"\t "<<p0->super<<"\t "<<p0->state<<"\t "<<p0->atime<<"\t\t "<<p0->rtime<<"\t\t "<<p0->ntime<<endl;
	       p0=p0->next;
	   }
 }
 
 
}

//check the queue if empty
bool empty(pcb1 r)
//隊(duì)列為空返回true,否則返回false
{
 if(r==NULL)
  return true;
 else
  return false;
}


void sort0(pcb1 &r,pcb1 p)
{  
	pcb1 p0=r;
    bool in=false;
    if(r==NULL)//隊(duì)列為空
	{
       r=p;
	}
	else 
	{
		while(p0->next!=NULL)  p0=p0->next;
		p0->next=p;
	}
}

void sort(pcb1 &r,pcb1 p)
//根據(jù)優(yōu)先級將進(jìn)程排序，插入到就緒隊(duì)列或阻塞隊(duì)列當(dāng)中
{
 pcb1 p1,p2;
 bool in=false;
 if(r==NULL)//隊(duì)列為空
 {
  r=p;
 }
 else  
 {
  if(p->super>=r->super)//待插入的進(jìn)程優(yōu)先級比隊(duì)列第一個(gè)進(jìn)程優(yōu)先級要高
  {         
   p->next=r;
   r=p;
  }
  else
  {
   p1=r;
   p2=r->next;
   if(p2==NULL)//only one process in the queue
   {
    r->next=p;
   }
   else
   {
    while(in==false&&p2!=NULL)//insert to the middle of the queue
    {
     if(p->super>=p2->super)
     {
      p->next=p2;
      p1->next=p;
      in=true;
     }
     else
     {
      p1=p1->next;
      p2=p2->next;
     }
    }
   }
   
   if(!in)//如果進(jìn)程沒有插入到隊(duì)列之中(優(yōu)先級最小)將進(jìn)程插入到就緒隊(duì)列最后
    p1->next=p;
  }
 }
}


void block()
//將進(jìn)程阻塞并插入到阻塞隊(duì)列當(dāng)中block one process and insert to block queue
{
 if(!empty(s))  //就緒隊(duì)列不空  
 {
  if(s->next==NULL)
  {
   if(alg) sort(w,s);
   else   sort0(w,s);
   s=s->next;
  }
  else
  {
   pcb1 p1;
   p1=s;  
   s=s->next;
   p1->next=NULL;
   if(alg) sort(w,p1);
   else   sort0(w,p1);
   
  }
 }
 else
 {
  cout<<endl<<endl;
  cout<<"  現(xiàn)在就緒隊(duì)列已經(jīng)為空，再?zèng)]有進(jìn)程需要阻塞"<<endl;
 }
}


void wake()
//喚醒阻塞隊(duì)列當(dāng)中的一個(gè)進(jìn)程并插入到就緒隊(duì)列當(dāng)中
{
 if(!empty(w))  //就緒隊(duì)列不空
 {
  pcb1 p1;
  p1=w;  
  w=w->next;
  p1->next=NULL;
  if(alg) sort(s,p1);
   else   sort0(s,p1);
   
 }
 else 
 {
  cout<<endl<<endl;
  cout<<"  阻塞隊(duì)列已經(jīng)為空，沒有進(jìn)程再需要喚醒"<<endl;
 }
}


bool finished()
//檢查就緒隊(duì)列的第一個(gè)進(jìn)程是否完成
{
 pcb1 p;
 p=s;
 if(p->rtime==p->ntime)
 {
  p->state='F';//進(jìn)程運(yùn)行結(jié)束
  cout<<endl<<"  進(jìn)程"<<p->name<<" 已經(jīng)結(jié)束"<<endl<<endl;
  return true;
 }
 else
  return false;
}

void run()
{
  time++;
  if(!empty(s)) //就緒隊(duì)列不空
 {
  pcb1 p;
  p=s;
  if(!finished()) //就緒隊(duì)列隊(duì)首進(jìn)程是否運(yùn)行結(jié)束
  {//沒有運(yùn)行結(jié)束
   s=s->next;
   p->rtime++;
   p->super--; 
   p->next=NULL;
   if(alg) sort(s,p);
   else   sort0(s,p);
   
  }
  else
  {//已經(jīng)運(yùn)行結(jié)束
   s=s->next;
   delete p;
  }
 }
 else  //就緒隊(duì)列為空
 {
    cout<<endl<<"  就緒隊(duì)列已經(jīng)為空"<<endl<<endl;
 }
 cout<<"就緒隊(duì)列的信息:"<<endl;
 print(s);
 printpcb();
 printf("%s","按任意鍵繼續(xù)...");
 getchar();
 
}


void creat()
//創(chuàng)建進(jìn)程
{
  pcb1 p;
  p=new pcb;
  cout<<"請輸入進(jìn)程的相應(yīng)信息"<<endl;
  cout<<"  進(jìn)程名: ";
  cin>>p->name;
  cout<<"  進(jìn)程優(yōu)先級: ";
  cin>>p->super;
//  cout<<"程序到達(dá)時(shí)間時(shí)間: ";
//  cin>>p->atime;
  p->atime=time;
  cout<<"  需要運(yùn)行時(shí)間: ";
  cin>>p->ntime;
 
  p->atime=time;
  p->rtime=0;
  p->state='W'; //就緒狀態(tài)
  p->next=NULL;
  if(alg) sort(s,p);//按優(yōu)先級將進(jìn)程p插入到就緒隊(duì)列當(dāng)中
   else   sort0(s,p); 
}

void menu()
{
	 cout<<endl<<"                               進(jìn)程調(diào)度程序"<<endl<<endl;
     cout<<"               1.  創(chuàng)建進(jìn)程                  2.  運(yùn)行進(jìn)程      "<<endl;    
	 cout<<"               3.  阻塞進(jìn)程                  4.  喚醒進(jìn)程      "<<endl;
     cout<<"               5. 查看就緒隊(duì)列               6. 查看阻塞隊(duì)列   " <<endl;
	 cout<<"               7. 查看進(jìn)程 PCB               8.  退出程序      "<<endl<<endl;
}

//main function
void main()
{
 char ch;
 s=NULL;
 w=NULL;
 cout<<"請選擇用于調(diào)度的算法 0.先來先服務(wù) 1.優(yōu)先權(quán)算法:  ";
 cin>>alg;
 menu();
 cout<<"請選擇相應(yīng)功能: ";
 cin>>ch;
 while(ch!='8')
 {
  
  switch(ch)
  {
   case '1': creat();   break;
   case '2': run();     break;
   case '5': cout<<"就緒隊(duì)列進(jìn)程信息:"<<endl;
	         print(s);  
			 printf("%s","按任意鍵繼續(xù)...");
             getchar();
			 break;
   case '6': cout<<"阻塞隊(duì)列進(jìn)程信息:"<<endl;
	         print(w);  
			 printf("%s","按任意鍵繼續(xù)...");
             getchar();
			 break;
   case '7': printpcb();
	         printf("%s","按任意鍵繼續(xù)...");
             getchar();
	         break; 
   case '4': wake();    break;
   case '3': block();   break;
  }
  menu();
  cout<<"請選擇相應(yīng)功能: ";
  cin>>ch;
 }
}