/*
===银行家算法的模拟实现===
一、实验题目
　　银行家算法的模拟实现
二、目的：
1、了解进程产生死锁的原因，了解为什么要进行死锁的避免。
2、掌握银行家算法的数据结构，了解算法的执行过程，加深对银行家算法的理解。
三、内容：
　  设计一个n 个并发进程共享m 个系统资源的系统。进程可动态申请资源和释放资源，系统按各进程的
申请动态的分配资源。要求采用银行家算法实现。
四、实验提示：
1、整个银行家算法的思路。
  先对用户提出的请求进行合法性检查，再进行预分配，利用安全性检查算法进行安全性检查。
2、算法用到的主要数据结构和C语言说明。
 （1）、可利用资源向量  INT  AVAILABLE[M]  M为资源的类型。
 （2）、最大需求矩阵    INT  MAX[N][M]  N为进程的数量。
 （3）、已分配矩阵      INT  ALLOCATION[N][M]
 （4）、还需求矩阵      INT  NEED[N][N]
    （5）、申请各类资源数量int Request[x]; //
    （6）、工作向量        int Work[x];
    （7）、int Finish[y]; //表示系统是否有足够的资源分配给进程，0为否，非0为是
3、银行家算法 （主程序）
 （1）、系统初始化。输入进程数量，资源种类，各进程已分配、还需求各资源数量，各资源可用数
 量等
 （2）、输入用户的请求三元组（I，J，K），为进程I申请K个J类资源。
 （3）、检查用户的请求是否小于还需求的数量，条件是 K<=NEED[I,J]。如果条件不符则提示重新输
    入，即不允许索取大于需求量
 （4）、检查用户的请求是否小于系统中的可利用资源数量，条件是K<=AVALIABLE[I,J]。如果条件不
 符则申请失败，阻塞该进程，重新进行进程动态资源申请（使用goto语句）
 （5）、进行资源的预分配，语句如下：
 AVALIBLE[I][J]= AVALIBLE[I][J]-K；
 ALLOCATION[I][J]= ALLOCATION[I][J]+K；
 NEED[I][J]=NEED[I][J]-K；
    （6）、系统调用安全性检查算法（safe()函数）进行检查，如果检查通过，则不用回收，否则进行
 回收，进程资源申请失败进入等待。
4、安全性检查算法（safe()子函数）
    （1）、设置两个临时变量。
     FINISH[N]记录进程模拟执行的结束状态，初值为0，如果可以模拟执行结束，则可设为1，也可设为
  其它非零值以表示执行的先后次序。
     WORK[M]记录模拟执行中资源的回收情况，初值为AVAILABLE[M]的值。
 （2）、在进程中查找符合以下条件的进程。
           条件1：FINISH[I]=0
     条件2：NEED[I][J]〈=WORK[J]
    （3）、如果查找成功则进行资源的模拟回收，语句如下：
           WORK[J]=WORK[J]+ALLOCATION[I][J]；
     FINISH[I]=1 或查找到的顺序号
    （4）、如果查找不成功，则检查所有进程的FINISH[]，如果有一个为0，则系统不为0，返回不成功
 标志。否则返回成功标志。

*/

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h> 
#include <conio.h>
#include <string.h>

//===定义全局变量===
const int x=50,y=100;  //定义常量，便于修改
int Available[x];      //各种资源可利用的数量
int Allocation[y][y];  //各进程当前已分配的资源数量
int Max[y][y];  //各进程对各类资源的最大需求数
int Need[y][y]; //还需求矩阵
int Request[x]; //申请各类资源的数量
int Work[x]; //工作向量，表示系统可提供给进程继续运行所需的各类资源数量
int Finish[y]; //表示系统是否有足够的资源分配给进程，0为否，非0为是
int p[y];  //存储安全序列
int i,j;
int n,m;  //n为进程的数量,m为资源种类数
int l=0,counter=0;
//函数声明
int shuzi(int sz);  //数字判断函数  或者使用 void shuzi(int& sz); 方式
void chushihua();  //系统初始化函数
void safe();       //安全性算法函数
void bank();       //银行家算法函数
void showdata();   //函数showdata,输出当前资源分配情况
void sign();       //签名函数

//===数字判断函数===
int shuzi(int sz){  //输入数据并判断是否为数字
    char *temp;
    temp=new char;   //临时指针，存放输入字符
    int len; //存储取字符的长度
    sz=0 ; //清零
    char s; //
    do{                                        //输入赌注，只能输入数字                                            
       // gets(temp);   //getline(cin,temp)
  cin>>temp;
        len=strlen(temp);     //取字符长度
        for(int i=0;i<len;i++){       
           s= *(temp+i);
           if(s<'0' || s>'9'){          
               cout<<" 笨蛋，输错了! 你输入的是数字吗?! nn";
      cout<<"请重新输入：";
      break;
           }         
        }
    }while(s<'0' || s>'9');  
    for(int i=0;i<len;i++){       //输入字符串转化为整形数字  
        int t=1; 
        for(int j=1;j<len-i;j++) t*=10;
        sz+=(*(temp+i)-48)*t;  
    }
 return sz;
}
//===系统初始化函数===
void chushihua(){ 
 //===系统初始化输入===
 cout<<"%% 程序开始，系统初始化输入 %%"<<endl;  //<<endl
    cout<<"==============================================================="<<endl<<endl;
    cout<<"请输入进程的数量: ";//从此开始输入有关数据
    n=shuzi(n);
    cout<<"请输入资源种类数: ";
 m=shuzi(m);

    cout<<endl<<endl<<"请输入各种资源可利用的数量( "<<m<<" 种): "<<endl;
  cout<<endl; 
 for (j=0; j<m; j++){
  cout<<"   输入资源 "<<j<<" 可利用的数量Available["<<j<<"]: ";
  Available[j]=shuzi(Available[j]);
        Work[j]=Available[j];          //初始化Work[j]
 // cout<<endl;
 }

 //system("cls");  //清屏
 cout<<endl;

 cout<<"请输入各进程当前已分配的资源数量Allocation["<<n<<"]["<<m<<"]: "<<endl<<endl;
 for (i=0; i<n; i++){
  for (j=0; j<m; j++){
   cout<<"   请输入进程 "<<i<<" 当前已分配的资源 "<<j<<" 数量: ";
   Allocation[j]=shuzi(Allocation[j]);
  // cout<<endl;
  }
  cout<<endl;
  Finish=0;//初始化Finish
  //break;
 }
 cout<<endl<<endl;

 cout<<"请输入各进程对各类资源的最大需求数Max["<<n<<"]["<<m<<"]: "<<endl<<endl;
 for (i=0; i<n; i++){
  for (j=0; j<m; j++) {
   cout<<"   请输入进程 "<<i<<" 对资源 "<<j<<" 的最大需求数: ";
   Max[j]=shuzi(Max[j]);
   if(Max[j]>=Allocation[j])  //
    Need[j] = Max[j]-Allocation[j];  //计算还需求量
   else
    Need[j]=0;//最大需求量小于已分配量时还需求量为0,即此类资源已足够不需再申请
  }
  cout<<endl;
 }

    cout<<endl<<"%% 初始化完成! %%"<<endl;
}

//===安全性算法函数===
void safe(){
 l=0; 
 for (i=0; i<n;){  //i++ 
  if (Finish==0){  //寻找Finish==0的进程    条件一
   counter=0;   //记数器
 /* 算法一： 
   for (j=0; j<m; j++){
    if (Work[j]>=Need[j])  //可用大于等于需求
                counter=counter+1;//记数
   }
   if(counter==m){…
*/  //算法二：
   for (j=0; j<m; j++)
    if (Work[j]>=Need[j]);  //可用大于等于需求
                else{
     counter=1;
     break;
    }

   if(counter!=1){ //进程的每类资源量都符合条件Work[j]>=Need[j]   条件二
    p[l]=i;  //存储安全序列
                Finish=1;  //标志为可分配
    for (j=0; j<m;j++){
     Work[j]=Work[j]+Allocation[j];  //释放资源
    }
    l=l+1; //记数,当L=N时说明满足安全序列,即都符合条件Work[j]>=Need[j]
    i= -1; //从第一个进程开始继续寻找满足条件一二的进程
   }
  }
  i++; //for循环继续寻找
 }
}
//===显示分配情况函数 ===
void showdata() //函数showdata,输出当前资源分配情况
{
    int i,j; //局部变量
 int All[y]; //各种资源的总数量
 int l2; //局部变量      l1,
 
   cout<<"==============================================================="<<endl<<endl;
 cout<<"%% 系统当前状态如下：%%"<<endl<<endl;

    cout<<"%% 各种资源的总数量(all):"<<endl; 
    for (j=0;j<m;j++) {
  cout<<" 资源"<<j<<": ";
  All[j]=Available[j]; //初始化 先赋值加上可利用量
  for (i=0;i<n;i++){
   All[j]+=Allocation[j]; //再加上每个进程已分配量计算J类资源总量
  }
  cout<<All[j]<<"  ";
  if ((j+1)%5==0 ) cout<<endl;  //每行显示五个     && j!=0
 }
    cout<<endl<<endl;

    cout<<"%% 系统目前各种资源可用的数为(available):"<<endl;

    for (j=0;j<m;j++){
  cout<<" 资源"<<j<<": "<<Available[j]<<"  ";
  if((j+1)%5==0) cout<<endl; //每行最多显示五个     && j!=0
 }
    cout<<endl<<endl;

    cout<<"%% 各进程已经得到的资源量(allocation): "<<endl;
// l1=0;  //归零
 for(i=0;i<=m/5;i++){  //设计每行最多显示五种资源
  for (j=i*5;j<i*5+5 && j<m;j++)cout<<"      资源"<<j;
  cout<<endl;
  for(l2=0;l2<n;l2++){
   cout<<"进程"<<l2<<":";
   for (j=i*5;j<i*5+5 && j<m;j++)cout<<Allocation[l2][j]<<"          ";
      cout<<endl;
  }
 }
 cout<<endl;

    cout<<"%% 各进程还需要的资源量(need):"<<endl;     //<<endl
 //l1=0;
 for(i=0;i<=m/5;i++){  //设计每行显示五种资源
  for (j=i*5;j<i*5+5 && j<m;j++)cout<<"      资源"<<j;
  cout<<endl;
  for(l2=0;l2<n;l2++){
   cout<<"进程"<<l2<<":";
   for (j=i*5;j<i*5+5 && j<m;j++)cout<<Need[l2][j]<<"          ";
      cout<<endl;
  }
 }
 
    cout<<endl;
    cout<<"==============================================================="<<endl;
 cout<<endl;
    system("pause");  // 暂停

}
//===签名函数 ===
void sign()
{
   system("cls");     //   清屏
   cout<<endl<<endl<<endl<<endl<<endl<<endl;
   cout<<"tt  ========================================="<<endl;
   cout<<"tt  =@                                     @="<<endl;
   cout<<"tt  =@          本程序由李志文制作         @="<<endl;
   cout<<"tt  =@             谢谢你的使用            @="<<endl;
   cout<<"tt  =@          版权没有，随便复制         @="<<endl;
   cout<<"tt  =@                                     @="<<endl;
   cout<<"tt  =@            洛阳师院 08.5            @="<<endl;
   cout<<"tt  =@                                     @="<<endl;
   cout<<"tt  ========================================="<<endl;
   cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl;
 
  
    // getch();            //等待键盘输入，不返回任何值，用于设置程序运行界面     
    system("pause");//暂停  比较两种方式

/*     经过在不同的编辑器中调试发现,不同的调试器对函数执行的顺序有差别
    如在此处使用 getch() 和 system("pause") 函数时,在visual c++6.0中先执行此函数再显示,
    而在dev-c++ 中则按顺序执行
    对此问题我在很多地方搜索查找均未找到满意的答案,本次换用调试器才发现理解–4.29

       本次调试格式时，将换行命令 "n" 改为 endl 时，发现 system("pause") 函数执行变为顺序
    执行，由此领悟到  "n" 命令和system("pause")调用了一样系统函数，在调用的顺序上system("pause")
    优先所以它就先执行了
查找了一下相关帮助：
      在OSTREAM.H中有这样的一个inline函数：
      inline _CRTIMP ostream& __cdecl endl(ostream& _outs) { return _outs << 'n' << flush; }
      也就是说
      endl= return _outs << 'n' << flush;
      endl除了写'n'进外，还调用flush函数，刷新缓冲区，把缓冲区里的数据写入文件或屏幕，
      如果考虑效率就用'n'
 */

 //  cout<<"tttt输入任意字符结束";  //处理最后生成EXE程序执行问题
 //  cin>>l; 
   cout<<"ttt   ";
}

//===银行家算法函数===
void bank(){
 cout<<"==============================================================="<<endl<<endl;
 cout<<"%% 以下开始为进程进行资源分配申请 %%"<<endl<<endl;
 //===申请资源===
 int k=0;//用于输入进程编号
 bool r=false;  // 初值为假，输入Y继续申请则置为真

 do{
        //输入请求
  cout<<"请输入申请资源的进程编号(输入0–"<<n-1<<"之间): ";
  k=shuzi(k);
  cout<<endl;
  while(k>n-1) { //输入异常处理
   cout<<endl<<"您输入了错误的进程号，请重新输入!"<<endl;
   cout<<endl<<"请输入申请资源的进程编号(输入0–"<<n-1<<"之间): ";
      k=shuzi(k);
   cout<<endl;
  }

  cout<<endl<<"请输入该进程申请各类资源的数量: "<<endl;
  for (j=0; j<m; j++){

   do{  //do……while 循环判断申请输入的情况
    cout<<"进程 "<<k<<" 申请资源["<<j<<"]的数量:";
       Request[j]=shuzi(Request[j]);
    cout<<endl;
    if(Request[j]>Need[k][j]){  //申请大于需求量时出错，提示重新输入（贷款数目不允许超过需求数目）
        cout<<"申请大于需要量!!!"<<endl;
        cout<<"您申请资源"<<j<<"的数量为"<<Request[j]<<",大于进程"<<k<<"对该资源需求量"<<Need[k][j]<<"。"<<endl;
        cout<<"请重新输入!!!"<<endl;
    }
    else   //先判断是否申请大于需求量，再判断是否申请大于可利用量
     if(Request[j]>Available[j]){  //申请大于可利用量， 应该阻塞等待？……    ？？？
      cout<<"n没有那么多资源，目前可利用资源"<<j<<"数量为"<<Available[j]<<",本次申请不成功，进程等待!!!"<<endl;
      Finish[k]=0;  //该进程等待
      goto ppp;  //goto语句 跳转，结束本次申请
     }

   }while(Request[j]>Need[k][j]);  //Request[j]>Available[j]||
  }

  //改变Avilable、Allocation、Need的值
  for (j=0; j<m; j++) {
   Available[j] = Available[j]-Request[j];
   Allocation[k][j] = Allocation[k][j]+Request[j];
   Need[k][j] = Need[k][j]-Request[j];
   Work[j] = Available[j];
  }

       //判断当前状态的安全性
  safe();  //调用安全性算法函数
  if (l<n) {
   l=0; 
   cout<<"n当前状态不安全,不予分配!!!!!!"<<endl;
   //恢复数据
   for (j=0; j<m; j++) {
    Available[j] = Available[j]+Request[j];
    Allocation[k][j] = Allocation[k][j]-Request[j];
    Need[k][j] = Need[k][j]+Request[j];
    Work[j] = Available[j];
   }
   for (i=0; i<n; i++)
    Finish=0;  //进程置为未分配状态
  }
  else{
  // system("cls");
   l=0; 
            cout<<"n申请资源成功!!!"<<endl;

//===========================================
/* 
  //如果该进程所有需要的资源都已申请到，即NEED[k][j]均为零，则进程可以执行，执行完后需释放其所有拥有的资源
          
    //算法一：
   for(j=0;j<m;j++) if(Need[k][j]==0) l=l+1;
   if(l==m){                                 //此处借用 l 做下计数器
    for (j=0;j<m;j++){   //释放该进程的所有资源
     Available[j]=Available[j]+Max[k][j];
     Allocation[k][j]=0; 
    }
   }
   l=0;  //归零
*/
           //算法二：  （相对第一种算法节省时间）
   for(j=0;j<m;j++){
    if(Need[k][j]==0);
    else {     //有一种资源还没全部申请到，则该进程不可执行，不能释放拥有的资源
     l=1;   //置l为1，作为判断标志
     break; 
    }
   }
   if(l!=1){ //进程可以执行，则释放该进程的所有资源
    for (j=0;j<m;j++){
     Available[j]=Available[j]+Allocation[k][j];
     Allocation[k][j]=0;
    }
    cout<<"该进程已得到所有需求资源，执行后将释放其所有拥有资源！"<<endl;
            }
   l=0;  //归零
//===========================================

            cout<<"n安全的状态!!!"<<endl;
            cout<<"安全序列为:   ";
      cout<<endl<<"进程"<<"("<<p[0]<<")";  //输出安全序列，考虑显示格式，先输出第一个
      Finish[0]=0;
      for (i=1; i<n; i++){
       cout<<"==>>"<<"进程"<<"("<<p<<")";
                Finish=0; //所有进程置为未分配状态
   }
   cout<<endl<<endl;
  }

  showdata();  //显示当前状态

ppp:   //申请大于可利用量， 应该阻塞等待,结束本次资源申请，GOTO 语句跳转至此
  cout<<endl<<"是否继续申请资源(y/n) ?";
  char* b=new char;  //输入y/n，判断是否继续申请    <<endl
  cin>>b;
  cout<<endl;
     cout<<"==============================================================="<<endl<<endl;
        cout<<endl;

  if(*b=='y'||*b=='Y')
   r=true;
  else{
   r=false;  //输入非 Y 则令 R =false
  // system("cls");  //在sign() 里调用
   sign();  //调用签名函数
  }
    } while (r==true);
}

 

//===主函数===
 int main(){  // void main()
 system("color 06f"); //设置当前窗口的背景色和前景色 0 = 黑色 8 = 灰色

 cout<<endl<<endl;
 cout<<"tt================================================"<<endl;
    cout<<"tt||                                            ||"<<endl;
    cout<<"tt||              模拟银行家算法                ||"<<endl;
    cout<<"tt||                                            ||"<<endl;
    cout<<"tt||                             作者：lzw      ||"<<endl;
    cout<<"tt||                                            ||"<<endl;
    cout<<"tt================================================"<<endl<<endl<<endl<<endl;

    chushihua(); //初始化函数调用
    cout<<endl<<endl;
 showdata();  //输出初始化后的状态

    //===判断当前状态的安全性===
 safe();  //安全性算法函数调用

 if (l<n){
  cout<<"n当前状态不安全，无法申请,程序退出!!!!!"<<endl;
  cout<<endl;
  system("pause");
 // cin>>l;

  sign(); //调用签名函数
  return 0;  // break;
 }
 else{
  int i;  //局部变量
  l=0;
        cout<<"n安全的状态!!!"<<endl;
        cout<<"安全序列为:   ";
 
  cout<<endl<<"进程"<<"("<<p[0]<<")";  //输出安全序列，考虑显示格式，先输出第一个
  for (i=1; i<n; i++){
   cout<<"==>>"<<"进程"<<"("<<p<<")";
  }
  for (i=0; i<n; i++) Finish=0;  //所有进程置为未分配状态
  cout<<endl<<endl;
 }
 
 bank();    //银行家算法函数调用
    return 0; // break;
}