#include<iostream.h>

#define N 4       //定義進程數   

#define M 3       //定義資源數  

#define False 0

#define True 1

//————————————  初始化資源分配表  ——————————————

 

int Max[N][M]={{3,2,2},{6,1,3},{3,1,4},{4,2,2}};    //各進程所需最大資源數

int Allocation[N][M]={{1,0,0},{5,1,1},{2,1,1},{0,0,2}};   //系統已分配資源

int Need[N][M]={{2,2,2},{1,0,2},{1,0,3},{4,2,0}};  //還需資源

int Available[M]={1,1,2};  //系統可用資源

int Request[M];   //請求分配的資源序列

 

//—————————————   所 用 函 數  ———————————————

void showdata();//顯示資源狀況

int request(int i);//資源分配算法

int safe();//安全性算法

int free(int i);//資源釋放

 

//+++++++++++++++   輸出資源狀況  +++++++++++++++

void showdata() 

{

   int i,j;

   cout<<"+++++++++++++++++++++++++++++++"<<endl;

   cout<<"+++++    資源分配情況     +++++"<<endl;

   cout<<"+++++++++++++++++++++++++++++++"<<endl;

   //cout<<endl;

//輸出可用資源

   cout<<"系統可用資源(Available):\n";

 

   //按 <R1,R2,R3>羅列各類資源

   cout<<"  <";

   for(j=0;j<M;j++) 

   {

       cout<<"R"<<j+1;

       if(j<M-1)cout<<",";

   }

   cout<<">：";

   for (j=0;j<M;j++) //輸出可用資源

   {

       cout<<Available[j]<<" ";

   }

   cout<<endl<<endl;

//輸出所需資源

   cout<<"各進程資源最大需求(Max):\n";

   cout<<"      <R1 R2 R3>\n";

   for (i=0;i<N;i++) //掃描各進程

   {

       cout<<"  pr"<<i<<"：";

       for (j=0;j<M;j++) //各類資源最大需求  

       {

           cout<<Max[i][j]<<"  ";

       }

       cout<<endl;

   } 

   cout<<endl;

   

//輸出所獲得的資源情況

   cout<<"各進程當前獲得資源(Allocation):\n";

   cout<<"      <R1 R2 R3>\n";

   for (i=0;i<N;i++)

   {

      cout<<"  pr"<<i<<"：";

      for(j=0;j<M;j++)//輸出當前已分配資源數

      {

          cout<<Allocation[i][j]<<"  ";

      }

      cout<<endl;

   }

   cout<<endl;

//輸出仍需資源情況

   cout<<"各進程仍需資源(Need):\n";

   cout<<"      <R1 R2 R3>\n";

   for (i=0;i<N;i++)

   {

       cout<<"  pr"<<i<<"：";

       for(j=0;j<M;j++)//輸出還需要資源數

       {

          cout<<Need[i][j]<<"  ";

       }

       cout<<endl;

   }

   cout<<"================================="<<endl;

   cout<<"================================="<<endl;

}

//+++++++++++++++++++   資 源 分 配 算 法  +++++++++++++++++++++++

int request(int i)//為進程pr[i]進行資源分配

{

    int j,flag;

    for (j=0;j<M;j++)

    {

      if(Request[j]>Need[i][j])

      {

          cout<<"對不起，申請的資源大于它需要的資源數，請重試！";

          return -1;  break;

      }

      if(Request[j]>Available[j]) 

      {

          cout<<"對不起，當前系統可用資源不夠，請等待！";

          return -1;  break;

      }

    }

    for (j=0;j<M;j++)

    {

      Available[j]=Available[j]-Request[j];   //可用資源減少

      Allocation[i][j]=Allocation[i][j]+Request[j];//所得資源增加

      Need[i][j]=Need[i][j]-Request[j];       //仍需資源減少

    }

    flag=safe();

    if(flag<0) 

    {

        cout<<"分配不成功，請等待！";

        for (j=0;j<M;j++)//把資源恢復成分配之前的狀態

        { 

            Available[j]=Available[j]+Request[j];  

            Allocation[i][j]=Allocation[i][j]-Request[j]; 

            Need[i][j]=Need[i][j]+Request[j]; 

        }

    }

    return 0;

}

//+++++++++++++++++++++++   安 全 性 算 法  +++++++++++++++++++++++++

int safe()

{

    int Finish[N]={False};

    int Work[M],temp[N];

    int i,j,k,z=0,flag;

    for(j=0;j<M;j++) 

        Work[j]=Available[j]; //工作分配初始化為系統可用資源 

    for(i=0;i<N;i++) //掃描所有進程

    {

        flag=0; //標記 

        for(j=0;j<M;j++)//掃描各類資源

        {

          if(Finish[i]==False && Need[i][j]<=Work[j])//R[j]類資源滿足

          {   

              flag++; //統計得到滿足的資源類總數

              if(flag==M) //進程Pr[i]各類全部得到滿足

              {

                for(k=0;k<M;k++)

                    Work[k]+=Allocation[i][k];//工作分配加上可用資源

                Finish[i]=True; //將進程pr[i]寫入安全序列中

                temp[z]=i; z++; //序列生成

                i=-1; //為下一次進程全掃描作準備               

              }

          }

          else break;

        }

        if(Finish[i]==False && i==N-1)//全掃描至最后一個進程仍未分配 

        {

            cout<<"系統不安全!!!\n";//如果不成功，輸出系統不安全

            return -1;

            break;

        }

        else if(Finish[i]==True && i==N-1) break;//進程全部分配成功

    }

    cout<<"系統資源分配成功!"<<endl; //如果安全，輸出成功

    cout<<"安全序列：";

    for(z=0;z<N;z++)  //輸出安全序列

        cout<<"pr"<<temp[z]<<" ";

    cout<<endl;

    return 0;

}

//+++++++++++++++++++   資 源 釋 放  +++++++++++++++++++++

int free(int i)

{

    int j;

    for(j=0;j<M;j++)

    {

        Available[j]+=Allocation[i][j]; //系統可用資源增加

        Allocation[i][j]=0;  //進程所獲資源置0

    }

    return 1;

}

//++++++++++++++++++++   主 函 數  +++++++++++++++++++++++

void main()

{

    int choice;  //用戶選擇

    showdata();  //顯示資源狀況

    safe();  //進行安全性檢查

    while(1)

    {

       cout<<endl;

       cout<<"************************************"<<endl;

       cout<<"**   1:分配資源     2:釋放資源    **"<<endl;

       cout<<"**   3:顯示資源     4:離    開    **"<<endl;

       cout<<"************************************"<<endl;

       cout<<"輸入要進行的操作:";

       cin>>choice;

       if(choice==1)//分配資源

       {

           int i;

           cout<<"請輸入您要分配的進程號(0,1,2,3):";

           cin>>i;

           cout<<"請輸入您要為該進程分配的資源<R1,R2,R3>:";

           for(int j=0;j<M;j++) cin>>Request[j];

           request(i);

       }

       else if(choice==2)//釋放資源

       {

           int i;

           cout<<"請輸入您要釋放資源的進程號(0,1,2,3):";

           cin>>i;

           free(i);

       }

       else if(choice==3)//顯示資源

       {

           showdata();

       }

       else if(choice==4)  break; //離 開

       else cout<<"請輸入合法數字!";

    }

}