/*
程序采用HRN算法模擬作業運行，程序運行時先輸入作業個數，并依次輸入作業信息，
輸入過程中作業信息順序構成一個全局鏈表。運行時，先將第一個作業投入運行，運行結束
后根據HRN算法在運行結束時刻已提交的作業隊列里選出最高響應比的作業投入運行
（注：在上個作業運行結束時刻還未到達的作業將不參與排序及競爭CPU） ，并將
余下的作業按最高優先比排序。作業運行結束調用釋放函數計算其周轉時間、帶權周轉時間
并顯示出來，更新總周轉時間、總帶權周轉時間 。所有作業運行完后將平均周轉時間、平
均帶權周轉時間計算出來并顯示。  
 
*/ 
#include<iostream>
#include<string>
using namespace std;
#define null 0
int Runtime=0;//CPU時刻跟蹤變量 
float T_time=0;//總周轉時間 
float W_time=0;//總帶權周轉時間
int marktime=0;//輸入排隊時運行標記時間 
int n;//作業個數 
typedef struct jcb{
string name;
int Ttime;
int Rtime;
int Sourse;
char State;
struct jcb *next;
}JCB;//作業信息塊 
JCB *head=null,*p,*q;
void sort0(JCB *r)//作業排序遞歸子函數 
{
if(r->next->next==null) return;
  JCB *s,*d=r,*m=r->next;
  s=r;
  float x,y;
  x=float(Runtime-r->next->Ttime+r->next->Rtime)/(r->next->Rtime);
  
while(1)
{ if(s->next->next==null) break;
   s=s->next;
  y=float(Runtime-s->next->Ttime+s->next->Rtime)/(s->next->Rtime);
  
   if(y>x) {d=s;m=s->next;}
  
}
  d->next=m->next;
  m->next=null;
  m->next=r->next;
  r->next=m;
 sort0(m);
}
void sort()//作業排序函數 
{
 if(head==null||head->next==null) return ;
q=head;
while(1)
{if(q->next==null) break;
if(q->next->Ttime<=Runtime) q=q->next;
else break;
}
JCB *z;

    z=q;q=q->next;z->next=null;
    z=new JCB;
    z->next=head;
sort0(z);

head=z->next;
delete z;
z=head;
while(z->next)
{
  z=z->next;
}
z->next=q;
}

int randtime(int T,int R)//根據前一個作業到達時間及總完成時間產生當前作業到來的隨機時間 
{
    return T+rand()%(R-T-1)+1;
}

void display(JCB *pr)//顯示pr指針所指作業信息 
{
     float x=float(Runtime-pr->Ttime+pr->Rtime)/pr->Rtime;
     cout<<pr->name<<'\t'<<pr->State<<'\t'<<pr->Sourse<<'\t'<<pr->Ttime<<'\t'<<pr->Rtime<<'\t'<<x<<'\n';
}

void input()//輸入函數 
{
     int T=0,R=0;
     cout<<"請輸入作業個數：";
     cin>>n;
     for(int i=1;i<=n;i++)
     {
       p=new JCB; 
      cout<<"輸入NO."<<i<<"作業名稱：";
      cin>> p->name;
      cout<<"輸入作業運行時間：";
      cin>>p->Rtime;
      cout<<"輸入作業所需資源：";
      cin>>p->Sourse;
      p->State='W';
      if(i==1) p->Ttime=0;
      else p->Ttime=randtime(T,R);
      R+=p->Rtime;
      T=p->Ttime;
     if(i==1) {p->next=head;head=p;q=p;}
     else {p->next=q->next;
          q->next=p;q=p;}
      
     } 
      cout<<"\n\n輸入完畢\n\n提出請求的作業隊列為：\n";
    JCB *pr=head;
  cout<<"name\tstate\tSourse\tTtime\tRtime\n";
  while(pr)
  {
cout<<pr->name<<'\t'<<pr->State<<'\t'<<pr->Sourse<<'\t'<<pr->Ttime<<'\t'<<pr->Rtime<<'\n';
           pr=pr->next;
  }
 system("pause");  
 cout<<"\n\n開始運行！\n\n";
}

int getlen()//返回鏈表長度 
{
    int l=0;
    JCB *pr=head;
    
    while(pr)
    {
     l++;
     pr=pr->next;
    }
    return (l);
} 

void show()//顯示當前CPU內作業運行狀態 
{    cout<<"Runtime="<<Runtime<<endl<<endl;
     cout<<"\t正在運行的作業\n";
     cout<<"name\tState\tSourse\tTtime\tRtime\n";
     cout<<p->name<<'\t'<<p->State<<'\t'<<p->Sourse<<'\t'<<p->Ttime<<'\t'<<p->Rtime<<'\n';
     cout<<"\t等待的作業\n";
     JCB *pr=head;
     if(!pr) {cout<<"\t無就緒進程！\n";return ;}
    cout<<"name\tState\tSourse\tTtime\tRtime\t響應比\n";
     while(pr!=q)
     {
       display(pr);
       pr=pr->next;
     }
}

void destroy()//作業運行完畢，撤銷并釋放內存 
{  p->State='F';
  cout<<"作業運行完成\n" ;  
  cout<<"Ttime\tBegin\tDone\tZ_time\tW_time\n";
 cout<<p->Ttime<<'\t'<<Runtime-p->Rtime<<'\t'<<Runtime<<'\t'<<Runtime-p->Ttime
 <<'\t'<<(float)(Runtime-p->Ttime)/p->Rtime<<endl; 
 T_time+=(float)Runtime-p->Ttime;
 W_time+=(float)(Runtime-p->Ttime)/p->Rtime;
 system("pause");
  delete p;
}

void run()//模擬運行函數
{
     system("cls");
     p=head;
     head=p->next; 
     Runtime+=p->Rtime;
     sort();
     p->State='R';
     show();
     system("pause");
     system("cls");
     destroy();  
     
}
int main()//主函數 
{
    input();
    while(1)
    {
            run();
            if(!getlen())
            break;
    }
    system("cls");
    cout<<"所有作業都已完成后\n\n";
    cout<<"AVG_T_time\tAVG_W_time\n";
    cout<<T_time/n<<'\t'<<'\t'<<W_time/n<<endl;
    system("pause");    
}