银行家算法详解

拼搏现实的明天。 2022-05-24 06:25 341阅读 0赞

银行家算法（ banker's algorithm ）由 Dijkstra(1065)提出。他将死锁的问题演示为一个银行家贷款的模型。  
一个银行家向一群客户发放信用卡，每个客户有不同的信用额度。每个客户可以提出信用额度内的任意额度的请求，直到额度用完后再一次性还款。银行家承诺每个客户最终都能获得自己需要的额度。  
所谓“最终”，是说银行家可以先挂起某个额度请求较大的客户的请求，优先满足小额度的请求，等小额度的请求还款后，再处理挂起的请求。这样，资金能够永远流通。  
银行家算法可以用以下图表表示：  
![银行家算法图表][bankersAlgorithm.jpg]  
每个客户和银行家都有交易限额。银行家只能和限额小于自己限额的客户进行交易。一旦银行家的限额小于所有客户的限额，便发生了死锁。  
如上图所示。银行家分别和客户1，客户2,客户3进行了交易。第一次交易时，所有客户的限额都小于银行家的限额，任何客户都可以实现借款；第二次交易时，客户3的限额大小银行家的限额，这时银行家会挂起客户3 的请求；第三次交易时，只有客户3可以进行交易，其它的交易都会被挂起。直到客户3还款后，银行家才会考虑处理其它客户的交易。  
  
**银行家算法其核心是：保证自己的限额至少不小于一个客户的限额。**  
我们可以用填表法来快速解决银行家算法。  
  
  
建立一个二维表格：每列数据表示每次交易各个参与者的限额。这个表格第一列数据是银行家是客户的交易限额，每发生一次交易，增加一列，同时将银行家和发生交易的客户的限额减小。直到银行家的限额小于某个客户的限额时，交易不能继续进行。否则便发生死锁。  
![banksAlgorithmTable0.jpg][]  
  
例题：  
1、操作系统分配资源时的一个重要考虑是避免死锁的发生．若系统中有同类资源 16 个，由四个进程 P1、P2、P3 和 P4 共享该资源。已知 P1、P2、P3、P4 所需的资源总数分别为 8、5、9、6。各进程请求资源的次序如下表，若系统采用银行家算法为它们分配资源，那么\_(1)\_\_依次申请分配会使系统进入不安全状态。   
进程申请资源的情况

序号 进程 申请量   
1 P1 6   
2 P2 4   
3 P3 5   
4 P4 1   
5 P1 1   
6 P2 1   
A．3、4 B．3、5 C．4、5 D．5、6

答案是c  
我们初始化一个二维表格  
![banksAlgorithmTable.jpg][]  
  
到完成第三个请求到达的时候，资源只有一个了。此时只能满足p2的请求。所以，第四个和第五个请求会被系统挂起。第六个请求p2到达后会被处理。等p2事务结束释放资源后，系统会再处理挂起的请求，这样就不会发生死锁。一旦在第三步后将剩下的唯一的一个资源分配给其它的进程，（如请求4或请求5），则请求4和5可能会因需要不止一个资源而继续等待，则发生了死锁。**(通过表格可以看出，依次申请到C组时，银行家的剩余额度已经不能满足所有的客户的需求了)**

[bankersAlgorithm.jpg]: /images/20220524/90a4eb014f864ba0ab3e9388cf208245.png
[banksAlgorithmTable0.jpg]: /images/20220524/7edf9acffc344949b83c83d761aa3453.png
[banksAlgorithmTable.jpg]: /images/20220524/de29fe3ee30a4ee0b7332f7dc55bd904.png