银行家算法¶

约 1084 个字预计阅读时间 5 分钟

银行家算法简介¶

银行家算法 (Banker's Algorithm)

银行家算法是操作系统中最经典的死锁避免算法之一。它的核心思想是：把操作系统比作银行家，系统中的资源就像银行的资金，进程向系统申请资源就像客户向银行贷款。

在进程运行前，必须声明对各种资源的最大需求量，这个最大值不能超过系统资源的总量。当进程运行过程中申请资源时，系统会先判断当前资源是否足够分配。如果资源充足，系统还会进一步“试探”分配后系统是否依然安全。如果安全，才真正分配资源；否则，进程需要等待。

假设系统中有 \(n\) 个进程和 \(m\) 类资源，银行家算法需要用到以下 4 个数据结构：

可利用资源向量 (Available)：长度为 \(m\) 的数组，表示每类资源当前可用的数量。Available[j] = K 表示第 \(j\) 类资源还有 \(K\) 个可用。
最大需求矩阵 (Max)：\(n \times m\) 的矩阵，表示每个进程对每类资源的最大需求。Max[i, j] = K 表示进程 \(P_i\) 最多需要 \(K\) 个 \(R_j\) 资源。
分配矩阵 (Allocation)：\(n \times m\) 的矩阵，表示每个进程当前已分配到的各类资源数量。Allocation[i, j] = K 表示 \(P_i\) 已分配到 \(K\) 个 \(R_j\) 资源。
需求矩阵 (Need)：\(n \times m\) 的矩阵，表示每个进程还需要的各类资源数量。Need[i, j] = K 表示 \(P_i\) 还需要 \(K\) 个 \(R_j\) 资源。

三者之间有如下关系：

\[ Need = Max - Allocation \]

假设进程 \(P_i\) 发出资源请求 \(Request_i\)，其中 \(Request_i[j]=K\) 表示 \(P_i\) 需要 \(K\) 个 \(R_j\) 资源。系统处理流程如下：

如果 \(Request_i[j] \leq Need[i, j]\)，进入下一步；否则说明进程请求超出最大需求，属于错误请求。
如果 \(Request_i[j] \leq Available[j]\)，进入下一步；否则资源不足，进程需要等待。
系统“试探性”地分配资源，临时修改如下数据结构：
- \(Available = Available - Request_i\)
- \(Allocation[i, j] = Allocation[i, j] + Request_i[j]\)
- \(Need[i, j] = Need[i, j] - Request_i[j]\)
执行安全性检查算法，判断分配后系统是否安全。如果安全，则正式分配资源；否则，撤销试探分配，让进程等待。

安全性算法用于判断当前资源分配状态是否安全。步骤如下：

初始化工作向量 Work = Available，安全序列为空。
在所有未进入安全序列的进程中，查找一个 \(Need[i] \leq Work\) 的进程 \(P_i\)。如果找到，将 \(P_i\) 加入安全序列，并执行 \(Work = Work + Allocation[i]\)，然后重复本步骤。
如果找不到满足条件的进程，算法结束。
若所有进程都能进入安全序列，则系统安全；否则系统不安全。

安全性算法示例

假设系统有 5 个进程 \(\{P_0, P_1, P_2, P_3, P_4\}\) 和三类资源 \(\{A, B, C\}\)，总资源分别为 10、5、7。\(T_0\) 时刻的资源分配如下：

计算 Need 矩阵和 Available 向量

\[ Need = Max - Allocation \]

进程名 Need (仍需)

\(P_0\) 7 4 3

\(P_1\) 1 2 2

\(P_2\) 6 0 0

\(P_3\) 0 1 1

\(P_4\) 4 3 1

\[ Available = (10, 5, 7) - (7, 2, 5) = (3, 3, 2) \]

安全性检查过程

步骤	Work 向量	可满足的 Need	分配进程	Work 更新	安全序列
0	(3, 3, 2)	\(P_1\)	\(P_1\)	(5,3,2)	\(P_1\)
1	(5, 3, 2)	\(P_3\)	\(P_3\)	(7,4,3)	\(P_1, P_3\)
2	(7, 4, 3)	\(P_4\)	\(P_4\)	(7,4,5)	\(P_1, P_3, P_4\)
3	(7, 4, 5)	\(P_0\)	\(P_0\)	(7,5,5)	\(P_1, P_3, P_4, P_0\)
4	(7, 5, 5)	\(P_2\)	\(P_2\)	(10,5,7)	\(P_1, P_3, P_4, P_0, P_2\)

所有进程都能进入安全序列，因此系统当前是安全的。一个可能的安全序列为 \(\{P_1, P_3, P_4, P_0, P_2\}\)。