银行家算法

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

背景

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

處理程序

 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 ＡＢＣＤ　　ＡＢＣＤ ０６４２　　１５２０ ００００　[phone]－－－－－－－ ０７５０　　２９５２ 

此時P2 FINISH的false要改成true（己完成）

 FINISH false true false false 

接下來繼續往下找，發現P3的需求為0002，小於能用的2952，所以資源配置給他再回收

 　NEED　　 Available ＡＢＣＤ　　Ａ　Ｂ　Ｃ　Ｄ ０６４２　　２　９　５　２ ００００　[phone]－－－－－－－－－－ ０７５０　　３　12　10　6 

依此類推，做完P4→P1，當全部的FINISH都變成true時，就是安全狀態。

安全和不安全的状态

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

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

虛擬碼（pseudo-code）^[1]

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; 

参考文献

引用

1. Concurrency (PDF). [2009-01-13]. （原始内容 (PDF)于2014-01-06）. 

书籍

• 《操作系统概念（Operating System Concepts）》第六版[1] （页面存档备份，存于互联网档案馆）