大话银行家算法
2019年9月25日银行家算法是最著名的死锁避免算法。
一、算法思想
操作系统相当于银行家，操作系统管理的资源就是银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 操作系统按照银行家制定的规则为进程分配资源 。
当进程首次申请资源时，要查看该进程对资源的最大需求量，若系统现存的资源可以满足它的最大需求量，则按当前的申请量分配资源，否则就推迟分配。
当进程在执行中继续申请资源时，先查看该进程已占用资源数与本次申请资源数之和是否超过该进程对资源的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
二、算法描述
实现分为三个部分：描述算法的数据结构、银行家算法的描述和安全性算法的描述。
1. 数据结构
假设系统中有 $m$ 个资源，$n$ 个进程。
- $Available[n]$，一个数组，表示系统中每种资源可利用数量。其中每个元素表示一类可用的资源数目，如 $Available[i] = s$ 表示系统中有 $R_i$ 类的资源 $s$ 个。
- $Max[n][m]$，一个 $n \times m$ 的矩阵，定义系统中这 $n$ 个进程中的每个进程对这 $m$ 类资源的最大需求。
- $Allocation[n][m]$，一个 $n \times m$ 的矩阵，定义系统中这 $n$ 个进程已经得到资源的数目。
- $Need[n][m]$，一个 $n \times m$ 的矩阵，表示每个进程尚需的各类资源数。
显然有 $Need = Max – Allocation$，即各个进程尚需的资源量等于各个进程总需求量减去系统已经分配给各个进程的资源量。在 $Need, Max, Allocation$ 这三个矩阵中，只要知道其中两个就可以根据它们之间的关系得到第三个。
2. 银行家算法的描述
设 $Request_i$ 是进程 $P_i$ 的资源请求向量。当 $P_i$ 发出资源请求后，系统按照以下步骤进行检查：
(1). 若 $Request_i[j] \leq Need[i][j]$，则进入 (2)。否则出错，因为它所需资源数已超过它所宣布的最大值。
(2). 若 $Request_i[j] \leq Available[j]$，则进入 (3)。否则，表示尚无足够资源，$P_i$ 须等待。
(3). 系统试探把资源分配给 $P_i$。分配操作如下：
$$Available=Available – Request_i \
Allocation[i][j] = Allocation[i][j] + Request_i[j]\
Need[i][j] = Need[i][j] – Request_i[j]$$
(4). 系统执行安全性算法，检查此次分配后，系统是否处于安全状态。若安全，才正式将资源分配给 $P_i$，以完成本次分配；否则，将本次试探分配作废，恢复原来的资源分配状态，让进程 $P_i$ 等待。
3. 安全性算法
(1). 初始时安全序列为空。
(2). 从 $Need$ 矩阵中找出符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于等于 $Available$ 向量，找到后，把对应进程加入安全序列；若找不到，则执行步骤(4)。
(3). 进程 $P_i$ 进程安全序列后，可顺利执行，直至完成，并释放分配给他的资源，故应执行 $Available=Available+Allocation[i]$ 来对该进程已分配的资源进行回收，其中 $Allocation[i]$表示进程 $P_i$ 代表的在 $Allocation$ 矩阵中对应的行，返回步骤(2).
三、安全性算法举例
假设系统有 5 个进程，分别为 ${P_0, P_1,P_2,P_3,P_4}$ 和 3 类资源 ${A,B,C}$，这三类资源的总数量分别为10、5、7，在某一个 $T_0$ 时刻，系统的资源分配情况如下表：
| 进程\资源情况 | Max | Allocation | Available | ||||||
|---|---|---|---|---|---|---|---|---|---|
| A | B | C | A | B | C | A | B | C | |
| $P_0$ | 7 | 5 | 3 | 0 | 1 | 0 | 7 | 5 | 3 |
| $P_1$ | 3 | 2 | 2 | 2 | 0 | 0 | |||
| $P_2$ | 9 | 0 | 2 | 3 | 0 | 2 | |||
| $P_3$ | 2 | 2 | 2 | 2 | 1 | 1 | |||
| $P_4$ | 4 | 3 | 3 | 0 | 0 | 2 | |||
- 在题目中可以得到 $Max$ 矩阵和 $Allocation$ 矩阵，这两个矩阵相减得到 $Need$ 矩阵：
$$\begin{bmatrix}
7 & 5 & 3 \
3 & 2 & 2 \
9 & 0 & 2 \
2 & 2 & 2 \
4 & 3 & 3
\end{bmatrix}{Max} –
\begin{bmatrix}
0 & 1 & 0 \
2 & 0 & 0 \
3 & 0 & 2 \
2 & 1 & 1 \
0 & 0 & 2
\end{bmatrix}{Allocation} =
\begin{bmatrix}
7 & 4 & 3 \
1 & 2 & 2 \
6 & 0 & 0 \
0 & 1 & 1 \
4 & 3 & 1
\end{bmatrix}_{Need}
$$ 然后将 $Avaiable$ 与 $Need$ 矩阵的每一行相比较，找出比 $Avaiable$ 矩阵中小的行。例如，在初始时，有：
$$(3,3,2) > (1,2,2),对应 P_1 \
(3,3,2) > (0,1,1),对应 P_3$$
这样一来，就可以选择将$P_1$（也可以选择$P_3$）暂时加入安全序列。
- 由于 $P_1$ 的资源都得到了满足，因此可以将其释放（即 $P_1$ 可以结束了），将 $P_1$ 的资源都回收，即把 $P_1$ 进程对应的$Allocation$ 矩阵中的那一行与$Available$向量相加。回收的操作为：
$$(3\ 3\ 2) + (2\ 0\ 0) = (5\ 3\ 2) = Avaliable$$
此时需求矩阵更新为：
$$
\begin{matrix}
P_0 \ P_2 \ P_3 \ P_4
\end{matrix}
\begin{bmatrix}
7 & 4 & 3 \
6 & 0 & 0 \
0 & 1 & 1 \
4 & 3 & 1
\end{bmatrix}_{Need}
$$
去掉 $P_1$ 对应的一行（因为该进程所有资源都得到满足了，可以结束了，进程资源也已经回收了，也就没有必要留着了）。再用更新的 $Available$ 向量和 $Need$ 矩阵重复步骤 2。
最后得到一个安全序列 ${P_1, P_3, P_4, P_2, P_0}$（此序列不唯一）。
$Need$ 矩阵和 $Available$ 数组在此期间会不断更新。假如 $Need$ 矩阵的每一行都比 $Available$ 数组大，则认为是不安全的。
四、总结
银行家算法的关键是理解安全性算法。系统先尝试对资源进行分配，然后利用安全性算法进行检测，若监测安全才进行分配。对于安全性算法，将系统可用资源与每一个进程所要求的资源数量进行对比，从中找到某个进程，使系统可用资源能够完全满足该进程所需资源。找到后即可认为该进程可顺利进行，就释放该进程并对该进程进行回收。系统资源会因为回收进程资源而增加，进而继续对比剩下的每一个进程资源所需资源。随着不断回收进程的资源，进程越来越少，如能完全回收每一个进程，则认为安全的；否则就是不安全。
