银行家算法（避免死锁的算法）

银行家算法[编辑]

 

 

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

 

目录

  [隐藏] 

• 1 背景
• 2 进程^[1]
• 3 安全和不安全的状态
• 4 伪代码(pseudo-code)^[2]
• 5 参考文献
  • 5.1 引用
  • 5.2 书籍

 

背景[编辑]

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

进程^[1][编辑]

 Allocation　　　Max　　　Available
 　　ＡＢＣＤ　　ＡＢＣＤ　　ＡＢＣＤ
 P1　００１４　　０６５６　　１５２０　
 P2　１４３２　　１９４２　
 P3　１３５４　　１３５６
 P4　１０００　　１７５０

我们会看到一个资源分配表，要判断是否为安全状态，首先先找出它的Need，Need即Max(最多需要多少资源)减去Allocation(原本已经分配出去的资源)，计算结果如下：

 NEED
 ＡＢＣＤ
 ０６４２　
 ０５１０
 ０００２
 ０７５０

然后加一个全都为false的字段

 FINISH
 false
 false
 false
 false

接下来找出need比available小的(千万不能把它当成4位数 他是4个不同的数)

   NEED　　Available
 ＡＢＣＤ　　ＡＢＣＤ
 ０６４２　　１５２０
 ０５１０<-
 ０００２
 ０７５０

P2的需求小于能用的，所以配置给他再回收

  NEED　　Available
 ＡＢＣＤ　　ＡＢＣＤ
 ０６４２　　１５２０
 ００００　＋１４３２
 ０００２－－－－－－－
 ０７５０　　２９５２

此时P2 FINISH的false要改成true(己完成)

 FINISH
 false
 true
 false
 false

接下来继续往下找，发现P3的需求为0002，小于能用的2952，所以资源配置给他再回收

 　NEED　　Available
 ＡＢＣＤ　　Ａ　Ｂ　Ｃ　Ｄ
 ０６４２　　２　９　５　２
 ００００　＋１　３　５　４
 ０００２－－－－－－－－－－
 ０７５０　　３　12　10　6

同样的将P3的false改成true

 FINISH
 false
 true
 true
 false

依此类推，做完P4→P1，当全部的FINISH都变成true时，就是安全状态。

安全和不安全的状态[编辑]

如果所有过程有可能完成执行（终止），则一个状态（如上述范例）被认为是安全的。由于系统无法知道什么时候一个过程将终止，或者之后它需要多少资源，系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。在大多数情况下，这是一个合理的假设，因为系统不是特别关注每个进程运行了多久（至少不是从避免死锁的角度）。此外，如果一个进程终止前没有获取其它能获取的最多的资源，它只是让系统更容易处理。

基于这一假设，该算法通过尝试寻找允许每个进程获得的最大资源并结束（把资源返还给系统）的进程请求的一个理想集合，来决定一个状态是否是安全的。不存在这个集合的状态都是不安全的。

伪代码(pseudo-code)^[2][编辑]

P - 进程的集合

Mp - 进程p的最大的请求数目

Cp - 进程p当前被分配的资源

A - 当前可用的资源

while (P != ∅) {
    found = FALSE;
    foreach (p ∈ P) {
        if (Mp − Cp ≤ A) {
             /* p可以獲得他所需的資源。假設他得到資源後執行；執行終止，並釋放所擁有的資源。*/
             A = A + Cp ;
             P = P − {p};
             found = TRUE;
        }
    }
    if (! found) return FAIL;
}
return OK;