银行家算法
银行家算法(Banker's Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹赫尔·戴克斯特拉在1965年为T.H.E系统设计的一种避免死結產生的演算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。
背景
在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量,在满足所有贷款要求时,客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在这样的描述中,银行家就好比操作系统,资金就是资源,客户就相当于要申请资源的进程。
處理程序
Allocation Max Available ABCD ABCD ABCD P1 0014 0656 1520 P2 1432 1942 P3 1354 1356 P4 1000 1750
我們會看到一個資源分配表,要判斷是否為安全狀態,首先先找出它的Need,Need即Max(最多需要多少資源)減去Allocation(原本已經分配出去的資源),計算結果如下:
NEED ABCD 0642 0510 0002 0750
然後加一個全都為false的欄位
FINISH false false false false
接下來找出need比available小的(千萬不能把它當成4位數 他是4個不同的數)
NEED Available ABCD ABCD 0642 1520 0510<- 0002 0750
P2的需求小於能用的,所以配置給他再回收
NEED Available ABCD ABCD 0642 1520 0000 +1432 0002------- 0750 2952
此時P2 FINISH的false要改成true(己完成)
FINISH false true false false
接下來繼續往下找,發現P3的需求為0002,小於能用的2952,所以資源配置給他再回收
NEED Available ABCD A B C D 0642 2 9 5 2 0000 +1 3 5 4 0000---------- 0750 3 12 10 6
依此類推,做完P4→P1,當全部的FINISH都變成true時,就是安全狀態。
安全和不安全的状态
如果所有过程有可能完成执行(终止),则一个状态(如上述范例)被认为是安全的。由于系统无法知道什么时候一个过程将终止,或者之后它需要多少资源,系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。在大多数情况下,这是一个合理的假设,因为系统不是特别关注每个进程运行了多久(至少不是从避免死锁的角度)。此外,如果一个进程终止前没有获取其它能获取的最多的资源,它只是让系统更容易处理。
基于这一假设,该算法通过尝试寻找允许每个进程获得的最大资源并结束(把资源返还给系统)的进程请求的一个理想集合,来决定一个状态是否是安全的。不存在这个集合的状态都是不安全的。
虛擬碼(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;
参考文献
引用
- (PDF). [2009-01-13]. (原始内容存档 (PDF)于2014-01-06).
书籍
- 《操作系统概念(Operating System Concepts)》第六版 页面存档备份,存于