//
//程序名稱：進程調度模擬程序
//程序作者：張煥人
//作者郵箱: renwairen369@yahoo.com.cn
//          renwairen369@hotmail.com
//作者QQ：27949278
//
//
//


#include <iostream.h>
#include <stdio.h>
typedef struct pcb 
{ 
 char name[10];  //進程名
 char state;   //狀態w(就緒)r(運行)f(結束)
 int super;   //優先級
 int atime;   //到達時間
 int ntime;   //需運行的時間
 int rtime;   //已運行的時間
 struct pcb *next;
}*pcb1; 

int time=0;
int alg=1;
pcb1 s,w;//s,w分別是就緒隊列、阻塞隊列的節點


void print(pcb1 p)
//輸出就緒隊列信息
{
 pcb1 p0; //c語言當中指針傳遞直接傳地址!!!
 if(p==NULL) cout<<"  當前隊列為空"<<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<<"  當前沒有進程處于調度中"<<endl;
 else
 {
       cout<<"當前處于調度中進程的PCB信息:"<<endl;
       cout<<"\t進程名 "<<"\t優先級 "<<"\t狀態"<<"\t到達時間 "<<"\t已運行時間 "<<"\t需運行時間"<<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)
//隊列為空返回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)//隊列為空
	{
       r=p;
	}
	else 
	{
		while(p0->next!=NULL)  p0=p0->next;
		p0->next=p;
	}
}

void sort(pcb1 &r,pcb1 p)
//根據優先級將進程排序，插入到就緒隊列或阻塞隊列當中
{
 pcb1 p1,p2;
 bool in=false;
 if(r==NULL)//隊列為空
 {
  r=p;
 }
 else  
 {
  if(p->super>=r->super)//待插入的進程優先級比隊列第一個進程優先級要高
  {         
   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)//如果進程沒有插入到隊列之中(優先級最小)將進程插入到就緒隊列最后
    p1->next=p;
  }
 }
}


void block()
//將進程阻塞并插入到阻塞隊列當中block one process and insert to block queue
{
 if(!empty(s))  //就緒隊列不空  
 {
  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<<"  現在就緒隊列已經為空，再沒有進程需要阻塞"<<endl;
 }
}


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


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

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


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

void menu()
{
	 cout<<endl<<"                               進程調度程序"<<endl<<endl;
     cout<<"               1.  創建進程                  2.  運行進程      "<<endl;    
	 cout<<"               3.  阻塞進程                  4.  喚醒進程      "<<endl;
     cout<<"               5. 查看就緒隊列               6. 查看阻塞隊列   " <<endl;
	 cout<<"               7. 查看進程 PCB               8.  退出程序      "<<endl<<endl;
}

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