操作系统（一）银行家算法
描述
银行家算法是为了避免产生死锁的算法，设计者是Dijkstra。
在银行的日常借贷过程中，每个客户借贷的数额是有限的，在客户申请贷款之前需要声明自己需要借贷的最大资金数额，在申请贷款时，只要不超过最大值，银行应该尽量满足客户的需要，客户在使用完后应该及时归还。在这个描述中，银行家就像操作系统，资金就是资源，客户就是申请资源的进程。
伪代码
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;
数据结构
Max——最大需求矩阵
Allocation——分配矩阵
Need——需求矩阵
Available——可用资源向量
Work——工作向量
Resource——全部资源向量
Request——请求向量
Finish——完成标记向量
看起来挺多，但是理解了它们之间的关系就很好理解了。
举个例子
俺爹每月最多给我打生活费1000，第一次给了600了，第二次只能要400了。
Max = 1000； Allocation = 600； Need = 400；
在俺爹的计划中可不能只给我啊，每月的支出至少是衣食住行，假设总共每月是3000吧，给我打了600块钱后，还有2400的计划数。
Resource = 3000； Allocation = 600； Available = 2400；
总结一波，以上数据有如下关系：
Need = Max – Allocation；
Available = Resource – Allocation；
Work = Work + Allocation；（这个式子是在安全性算法中用）
安全和不安全的状态
维基百科上对于此状态的描述为：
如果所有过程有可能完成执行（终止），则一个状态（如上述范例）被认为是安全的。由于系统无法知道什么时候一个过程将终止，或者之后它需要多少资源，系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。在大多数情况下，这是一个合理的假设，因为系统不是特别关注每个进程运行了多久（至少不是从避免死锁的角度）。此外，如果一个进程终止前没有获取其它能获取的最多的资源，它只是让系统更容易处理。
基于这一假设，该算法通过尝试寻找允许每个进程获得的最大资源并结束（把资源返还给系统）的进程请求的一个理想集合，来决定一个状态是否是安全的。不存在这个集合的状态都是不安全的。
举例：
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
依此类推，做完P4→P1，当全部的FINISH都变成true时，就是安全状态。
版权声明：本文为gaojinmanlookworld原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。