深圳幻海软件技术有限公司 欢迎您！
更多

银行家算法（C++实现）

2023-04-28

int cout need
目录一、银行家算法概述二、银行家算法需要的数组结构三、算法概述1.安全性算法2.银行家算法四、代码实现五、实验结果验证一、银行家算法概述银行家算法（Banker'sAlgorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产

目录

一、银行家算法概述

二、银行家算法需要的数组结构

三、算法概述

1.安全性算法

2.银行家算法

四、代码实现

五、实验结果验证

一、银行家算法概述

银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

二、银行家算法需要的数组结构

1）可利用资源向量Available：这是一个含有m个元素的数组，其中的每一个元素代表一类可用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j] = K，则表示系统中现有Rj类资源K个。

2）最大需求矩阵Max：这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j] = K，则表示进程i需要Rj类资源的最大数目为K。

3）分配矩阵Allocation：这也是一个n*m的矩阵，它定义了系统中的每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j] = K，则表示进程i当前已分得Rj类资源的数目为K。

4）需求矩阵Need：这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K，则表示进程i还需要Rj类资源K个方能完成其任务。

其中三个矩阵间存在下述关系：

Need[i,j] = Max[i,j] - allocation[i,j]

三、算法概述

1.安全性算法

系统所执行的安全性算法可描述如下：

（1）设置两个向量：
        ① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false; 当有足够资源分配给进程时， 再令Finish[i]=true。

（2）从进程集合中找到一个能满足下述条件的进程：
        ① Finish［i］=false;
        ② Need［i，j］≤Work［j］； 若找到， 执行步骤3)；否则，执行步骤4)。

（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
        Work［j］=Work［i］+Allocation［i,j］;
        Finish［i］=true;
        go to step 2;

（4）如果所有进程的Finish[i]=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

2.银行家算法

设Requesti是进程Pi的请求向量，如果表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1) 如果 ≤ Need[i,j]，转向步骤(2)，否则认为出错，因为它所需的资源数目已超过它所宣布的最大值。

(2) 若  ≤ Available[j]，转向步骤(3)，否则表示尚无足够资源，Pi必须等待。

(3) 系统尝试把资源分配给进程Pi，并修改下面数据结构中的数值：
Available[j] = Available[j] – 
Allocation[i,j] = Allocation[i,j] + 
Need[i,j] = Need[i,j] – 

(4) 系统执行安全性算法，检查此次分配后系统是否处于安全状态。若安全，才正式分配给Pi，完成此次分配；否则，此次试分配作废，恢复原来资源的分配状态，进程Pi等待。

四、代码实现

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. const int p=5;//进程数
  5. const int r=4;//资源种类
  6.  
  7. int num = 1;//需要分配资源的进程序号
  8.  
  9. void init_request(int request[r])
  10. {
  11.     //初始化request矩阵
  12.     cout<<"Input the number of request:"<<endl;
  13.     cin>>num;
  14.     num-=1;//下标减1
  15.     cout<<"Input the request vector:"<<endl;
  16.     for(int i=0;i<r;i++)
  17.         cin>>request[i];
  18. }
  19.  
  20. void init_matrix(int maximum[p][r],int allocation[p][r],int need[p][r],int available[r],int request[r])
  21. {
  22.     //初始化函数
  23.     cout<<"Input the Allocation matrix:"<<endl;
  24.     for(int i=0;i<p;i++)
  25.         for(int j=0;j<r;j++)
  26.             cin>>allocation[i][j];
  27.     cout<<"Input the Need matrix:"<<endl;
  28.     for(int i=0;i<p;i++)
  29.         for(int j=0;j<r;j++)
  30.             cin>>need[i][j];
  31.     //cout<<"Input the Max matrix:"<<endl;
  32.     //Max矩阵可以由Need和Allocation矩阵推导得出
  33.     //Max[i,j]= Need[i,j]+Allocation[i,j]
  34.     for(int i=0;i<p;i++)
  35.         for(int j=0;j<r;j++)
  36.             maximum[i][j]=need[i][j]+allocation[i][j];
  37.     cout<<"Input the available vector:"<<endl;
  38.     for(int i=0;i<r;i++)
  39.         cin>>available[i];
  40. }
  41.  
  42. void output_func(int allocation[p][r],int need[p][r],int available[r])
  43. {
  44.     //输出函数
  45.     cout<<endl<<"     "<<"Allocation"<<"     Need"<<"        Available"<<endl;
  46.     for(int i=0;i<p;i++)
  47.     {
  48.         cout<<"P"<<i+1<<"   :";
  49.         for(int j=0;j<r;j++)
  50.         {
  51.             cout<<allocation[i][j]<<' ';
  52.  
  53.         }
  54.         cout<<"     ";
  55.         for(int j=0;j<r;j++)
  56.             cout<<need[i][j]<<' ';
  57.         if(i==0)
  58.         {
  59.             cout<<"     ";
  60.             for(int k=0;k<r;k++)
  61.                 cout<<available[k]<<' ';
  62.         }
  63.         cout<<endl;
  64.     }
  65.     cout<<endl;
  66.  
  67. }
  68.  
  69. bool compare(int need[],int work[])
  70. {
  71.     bool flg = 1;
  72.     for(int i=0;i<r;i++)
  73.     {
  74.         //检查是否有大于的情况存在
  75.         if(need[i]>work[i])
  76.         {
  77.             flg=0;
  78.             break;
  79.         }
  80.     }
  81.     return flg;
  82. }
  83.  
  84. int check_security(int allocation[p][r],int need[p][r],int available[r])
  85. {
  86.     //安全性检查函数
  87.     int finish[p] = {0};//初始化finish向量
  88.     int work[r];  //拷贝available
  89.     int lis[p];//用来记录安全时的队列
  90.     int cnt=0;
  91.     for(int i=0;i<r;i++)
  92.         work[i] = available[i];//初始化work向量
  93.     //序列分配
  94.     //循环p次
  95.     for(int m=0;m<p;m++)
  96.     {
  97.         for(int i=0;i<p;i++)
  98.         {
  99.             //如果当前进程执行完成，跳过
  100.             if(finish[i] == 1)
  101.                 continue;
  102.             //找到finish[i] = false
  103.             else{
  104.                 //如果Need[i,j]<=Work[j]
  105.                 if(compare(need[i],work))
  106.                 {
  107.                     for(int j=0;j<r;j++)
  108.                         work[j]+=allocation[i][j];
  109.                     finish[i] = 1;
  110.                     lis[cnt++] = i+1;//将该状态放入安全状态队列中
  111.                     break;
  112.                 }
  113.             }
  114.         }
  115.     }
  116.     int flag=1;
  117.     for(int i=0;i<r;i++)
  118.     {
  119.         if(finish[i]==0)
  120.         {
  121.             flag = 0;
  122.             break; //如果存在F的进程，表明系统处于不安全状态
  123.         }
  124.         else
  125.             continue;
  126.     }
  127.     if(flag)
  128.     {
  129.          cout<<"系统处于安全状态！"<<endl;
  130.          cout<<"安全序列为:";
  131.          for(int i=0;i<p;i++)
  132.             cout<<lis[i]<<' ';
  133.          cout<<endl;
  134.     }
  135.     else cout<<"系统处于不安全状态！"<<endl;
  136.     return flag;
  137.  
  138. }
  139.  
  140. void banker(int allocation[p][r],int need[p][r],int available[r],int request[r],int n)
  141. {
  142.     if(!compare(request,need[n]))
  143.     {
  144.         //如果存在Requesti[j]>Need[i][j],认为出错
  145.         cout<<"出错！所需资源已超过所宣布的最大值！"<<endl;
  146.         return ;
  147.     }
  148.     else{
  149.         //银行家算法(1)没有出错
  150.         if(!compare(request,available))
  151.         {
  152.             //如果存在Requesti[j]>Available[j]，认为出错
  153.             cout<<"尚无足够资源，必须等待！"<<endl;
  154.             return ;
  155.         }
  156.         else{
  157.             for(int j=0;j<r;j++)
  158.             {
  159.                 available[j]-=request[j];
  160.                 allocation[n][j]+=request[j];
  161.                 need[n][j]-=request[j];
  162.             }
  163.             if(check_security(allocation,need,available))
  164.             {
  165.                 cout<<"安全！将资源正式分配"<<endl;
  166.             }
  167.             else
  168.             {
  169.                 cout<<"不安全！资源分配作废！恢复以前状态"<<endl;
  170.                 for(int j=0;j<r;j++)
  171.                 {
  172.                     need[n][j]+=request[j];
  173.                     allocation[n][j]-=request[j];
  174.                     available[j]+=request[j];
  175.                 }
  176.             }
  177.         }
  178.     }
  179.     output_func(allocation,need,available);
  180.  
  181. }
  182.  
  183. int main()
  184. {
  185.     int maximum[p][r],allocation[p][r],need[p][r];
  186.     int available[r],request[r];
  187.     init_matrix(maximum,allocation,need,available,request);
  188.     cout<<endl<<"检查T0时刻系统是否处于安全状态..."<<endl;
  189.     check_security(allocation,need,available);
  190.     int flag = 1;
  191.     while(flag)
  192.     {
  193.         cout<<endl<<"对请求资源进行银行家算法检查..."<<endl;
  194.         init_request(request);//初始化request矩阵
  195.         banker(allocation,need,available,request,num);
  196.         cout<<"是否继续输入？(输入0退出):";
  197.         cin>>flag;
  198.     }
  199.  
  200.     return 0;
  201. }
  202. /*测试数据
  203. 0 0 3 2
  204. 1 0 0 0
  205. 1 3 5 4
  206. 0 3 3 2
  207. 0 0 1 4
  208. 0 0 1 2
  209. 1 7 5 0
  210. 2 3 5 6
  211. 0 6 5 2
  212. 1 6 5 6
  213. 1 6 2 2
  214. */

五、实验结果验证

1.能安全分配的情况


 

 

2.分配不安全情况（注意一定要恢复原来的状态）

 3.需要的资源超过自己需要的最大值

 4.尚无足够资源，需等待分配

 

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览45247 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪