操作系统 - 看完这篇还读不懂《银行家算法》那我也没办法了

故事背景

为什么想到总结一篇从 0-1 学习银行家算法，读这篇至少要有死锁的概念，网上很多文章根本没讲解当中的一些小概念，连概念和算法过程都不了解，直接上题目怎么看得懂？

原理讲解

非剥夺资源的竞争和进程的不恰当推进顺序会导致死锁，而银行家算法就是为了解决死锁问题——避免死锁。

银行家算法：当一个进程申请使用资源的时候，银行家算法通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

那么此时会有一个问题，如何判断系统是否处于安全状态？算法流程将用下面一张图来表示。

首先是银行家算法中的进程

1. 包含进程Pi的需求资源数量（也是最大需求资源数量，MAX）
2. 已分配给该进程的资源A（Allocation）
3. 还需要的资源数量N（Need=M-A）

Available为空闲资源数量，即资源池（注意：资源池的剩余资源数量+已分配给所有进程的资源数量=系统中的资源总量）

假设资源P1申请资源，银行家算法先试探的分配给它（当然先要看看当前资源池中的资源数量够不够），若申请的资源数量小于等于Available，然后接着判断分配给P1后剩余的资源，能不能使进程队列的某个进程执行完毕，若没有进程可执行完毕，则系统处于不安全状态（即此时没有一个进程能够完成并释放资源，随时间推移，系统终将处于死锁状态）。

若有进程可执行完毕，则假设回收已分配给它的资源（剩余资源数量增加），把这个进程标记为可完成，并继续判断队列中的其它进程，若所有进程都可执行完毕，则系统处于安全状态，并根据可完成进程的分配顺序生成安全序列（如{P0，P3，P2，P1}表示将申请后的剩余资源Work先分配给P0–>回收（Work+已分配给P0的A0=Work）–>分配给P3–>回收（Work+A3=Work）–>分配给P2–>······满足所有进程），如此就可避免系统存在潜在死锁的风险。

数据结构与算法

• 数据结构

可用资源向量：Available，是一个数组，表示现在系统中总共还有多少可用的资源。

例如：A B C 的 Available 是 [1，2，3]

表示现在系统中还有 A 类资源 1 个，B 类资源 2 个，C 类资源 3 个。

最大需求：Max，是一个矩阵，表示某进程最多需要多少某资源，一行代表一个进程，一列代表一个资源。例如

	A B C
 P1 1 2 3
 P2 4 5 6
 P3 7 8 9
 
// P3 进程最多需要 C 类资源 9 个
// P2 进程最多需要 B 类资源 5 个

分配矩阵：Allocation 表示系统中现在某类资源分配给某进程的数量

	A B C
 P1 1 2 3
 P2 4 5 6
 P3 7 8 9
 
// P3 进程现在已经分配了 C 类资源 9 个
// P1 进程现在已经分配了 A 类资源 1 个

需求矩阵：Need，表示现在进程中尚需的各类资源数

	A B C
 P1 1 2 3
 P2 4 5 6
 P3 7 8 9
 
// P1 进程现在还需要 C 类资源 3 个
// P2 进程现在还需要 B 类资源 5 个

Need 矩阵 = Max 矩阵 - Allocation 矩阵；（请一定要理解这条很好理解的原则）

Need 矩阵 = Max 矩阵 - Allocation 矩阵；（请一定要理解这条很好理解的原则）

Need 矩阵 = Max 矩阵 - Allocation 矩阵；（请一定要理解这条很好理解的原则）

也很好理解，最多需要的数量减去现在已经给的数量就是还需要的数量。矩阵的减法直接 对应位置 相减即可。

一般情况下，Max 矩阵和 Alocation 矩阵都是已知条件，求出 Need 矩阵是解题的第一步。

• 算法（银行家——整个过程）

设 request 是进程 P 的请求向量，request[A] = K 表示进程 P 需要 A 类资源 K 个。

当 P 发出资源请求后，系统按照以下步骤进行检查。

1. 如果 request[A] 的值小于 need[P，A]，也就是说如果现在请求的数量小于 need 矩阵中规定的他所需要的数量，那么就转到步骤 2 ；否则认为出错，因为他所请求的数量已经超过了他所宣布的最大值。

2. 如果 request[A] 的值小于 available[A]，也就是说请求的值小于现在系统中有的值，则转向步骤 3 ；否则表示尚足够资源，进程 P 需要等待。

3. 系统 试探 着把资源分配给进程 P，并修改下面数据结构中的值：

   • 更新可用：Available = Available - request；
   • 更新已分配：Allocation[P,A] = Allocation[P,A] + request[A]；
   • 更新所需：Need[P,A] = Need[P,A] - request[A];

4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全才将资源分配给进程 P；否则此次的试探分配作废，恢复原来的资源分配状态，让进程 P 等待。

接下来看一下安全性算法是什么？

• 算法（银行家——安全性）

1. 初始时 安全序列 为空
2. 从 Need 矩阵中找到符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于等于 Available 向量，找到后，把对应的进程加入 安全序列；若找不到，则执行步骤 4
3. 进程 P 进入 安全序列 后，可顺利执行，直至完成，并释放分配给它的资源，故应执行 Available = Available + Allocation[P]，其中 Allocation[P] 表示进程 P 在 Allocation 矩阵中对应的行，返回步骤 2
4. 若此时安全序列中已有所有进程，则系统处于安全状态，否则处于不安全状态

下面以一个例子来看一下

假定系统中有 5 个进程 {P0,P1,P2,P3,P4} 和 3 类资源 {A,B,C}，各类资源的数量分别是 10，5，7，在 T0 时刻的资源分配表如下

• Tips：起始 Available[A,B,C] = [10,5,7] - Sum(Allocation[A,B,C]) = [3,3,2]（[2,3,0]）
• 这个提示我不得不在这里说明下，之前很多人一开始看对这里会有疑问，这个 [3,3,2] 是怎么得到的？这个起始资源 [10,5,7] 又有什么用？

强化练习

• 题1

•  题2

• 题3

Tips：这题不瞒你说，网上很多一开始就放这题，我敢说，没上面概念的铺垫，你让谁在这里加加减减找规律，非常痛苦~现在的你看到这还会觉得“银行家算法”难吗？！