4、死锁的避免算法：银行家算法详解与实例分析

死锁的避免，说白了就是系统在分配资源之前，先“算一卦”——看看这次分配会不会导致将来大家互相掐架、谁也动不了。如果会，那就先不分配，让进程等着。这个“算卦”的算法，最经典的就是银行家算法。

我第一次接触这个算法时，觉得名字挺有意思。后来在做一个嵌入式实时系统项目时，真遇到了资源分配的死锁问题，才体会到这算法的价值。嗯，咱们今天就把这个“算卦”的过程掰开揉碎了讲清楚。

4.1 银行家算法的核心思想

银行家算法，名字来源于银行放贷的逻辑。银行不会把所有钱都贷出去，得留一部分准备金，防止客户突然来取钱。操作系统也一样，分配资源时不能“倾囊而出”，得留点家底，确保系统始终处于安全状态。

什么叫安全状态？说白了就是：系统能找到一个安全序列，按照这个顺序给进程分配资源，每个进程都能在有限时间内拿到所需资源，最终完成任务并释放资源。如果找不到这样的序列，系统就处于不安全状态，可能发生死锁。

4.2 算法需要的数据结构

银行家算法需要维护几张表，我习惯把它们想象成“账本”。假设系统有 n 个进程，m 类资源。

数据结构	含义	维度
Available[m]	每类资源的可用数量	一维数组
Max[n][m]	每个进程对每类资源的最大需求	二维矩阵
Allocation[n][m]	每个进程当前已分配的资源数	二维矩阵
Need[n][m]	每个进程还需要的资源数（Need = Max - Allocation）	二维矩阵

4.3 安全性算法——判断系统是否安全

这是银行家算法的核心步骤。我把它总结成三步走：

1. 初始化： 设置两个临时向量 Work = Available（当前可用资源），Finish[i] = false（所有进程未完成）。
2. 找进程： 找一个 Finish[i] == false 且 Need[i] <= Work 的进程。找到了就继续，找不到就跳到第4步。
3. 模拟释放： 假设该进程完成任务，释放它占用的所有资源：Work = Work + Allocation[i]，设置 Finish[i] = true。然后回到第2步。
4. 判断结果： 如果所有 Finish[i] 都是 true，系统安全；否则不安全。

你想想看，这个过程像不像在玩“消消乐”？每次找一个能“吃饱”的进程，让它吃完释放资源，再去喂下一个。

4.4 实例分析——手把手算一遍

咱们来看一个具体例子。假设系统有5个进程（P0~P4），3类资源（A、B、C）。当前状态如下：

进程	Max (A B C)	Allocation (A B C)	Need (A B C)	Available (A B C)
P0	7 5 3	0 1 0	7 4 3	3 3 2
P1	3 2 2	2 0 0	1 2 2
P2	9 0 2	3 0 2	6 0 0
P3	2 2 2	2 1 1	0 1 1
P4	4 3 3	0 0 2	4 3 1

第一步： 初始化 Work = (3, 3, 2)，所有 Finish = false。

第二步： 找满足条件的进程。检查 P0：Need(7,4,3) > Work(3,3,2)，不行。P1：Need(1,2,2) <= Work(3,3,2)，找到了！

第三步： 模拟P1完成。Work = Work + Allocation[P1] = (3,3,2) + (2,0,0) = (5,3,2)。Finish[P1] = true。

第四步： 继续找。P0：Need(7,4,3) > Work(5,3,2)，不行。P2：Need(6,0,0) > Work(5,3,2)，不行。P3：Need(0,1,1) <= Work(5,3,2)，找到了！

第五步： 模拟P3完成。Work = (5,3,2) + (2,1,1) = (7,4,3)。Finish[P3] = true。

第六步： 继续找。P0：Need(7,4,3) <= Work(7,4,3)，找到了！模拟P0完成。Work = (7,4,3) + (0,1,0) = (7,5,3)。Finish[P0] = true。

第七步： 继续找。P2：Need(6,0,0) <= Work(7,5,3)，找到了！模拟P2完成。Work = (7,5,3) + (3,0,2) = (10,5,5)。Finish[P2] = true。

第八步： 最后P4：Need(4,3,1) <= Work(10,5,5)，模拟完成。Work = (10,5,5) + (0,0,2) = (10,5,7)。Finish[P4] = true。

所有进程都 Finish = true，安全序列为：P1 → P3 → P0 → P2 → P4。系统当前处于安全状态。

4.5 资源请求算法——实际分配时的决策

当进程 Pi 请求资源 Request[i] 时，算法按以下步骤判断：

1. 检查请求是否合法： 如果 Request[i] > Need[i]，说明进程要的资源超过了它声明的最大需求，直接报错。
2. 检查资源是否足够： 如果 Request[i] > Available，资源不够，进程必须等待。
3. 试分配： 假装分配了资源，更新数据结构：

   Available = Available - Request[i]
   Allocation[i] = Allocation[i] + Request[i]
   Need[i] = Need[i] - Request[i]

4. 执行安全性算法： 如果试分配后系统仍安全，正式分配；否则回滚，让进程等待。

举个例子，接上面的状态。假设P1请求资源 Request = (1, 0, 2)。

检查： Request(1,0,2) <= Need[P1](1,2,2)，合法。Request(1,0,2) <= Available(3,3,2)，资源够。

试分配后：

• Available = (3,3,2) - (1,0,2) = (2,3,0)
• Allocation[P1] = (2,0,0) + (1,0,2) = (3,0,2)
• Need[P1] = (1,2,2) - (1,0,2) = (0,2,0)

执行安全性算法： 用新的Available(2,3,0)重新找安全序列。你会发现仍然能找到（比如P1→P3→P0→P2→P4），所以这次分配是安全的，可以正式分配。

4.6 银行家算法的优缺点

优点	缺点
能有效避免死锁	进程必须预先声明最大需求，实际中很难做到
资源利用率比死锁预防高	进程数量固定，不支持动态创建进程
算法逻辑清晰，容易实现	每次分配都要执行O(n²·m)的安全性检查，开销大

4.7 知识体系流程图

下面我用一张SVG图把银行家算法的核心逻辑串起来，方便你理解整体脉络。

这张图把银行家算法的流程串了一遍：从输入数据开始，计算Need矩阵，收到请求后先做合法性检查，再试分配，最后用安全性算法判断。每一步都环环相扣，缺一不可。

4.8 实际应用中的思考

说实话，银行家算法在实际操作系统中用得并不多。为什么？因为让每个进程预先声明最大资源需求，这个要求太苛刻了。很多程序自己都不知道将来会用到多少资源。

不过，在一些嵌入式实时系统和数据库管理系统中，银行家算法还是有它的用武之地。我记得在一个车载系统的项目中，我们就用银行家算法来管理内存资源，因为每个任务的最大内存需求是确定的，而且系统对可靠性要求极高——死锁是绝对不能发生的。

另外，银行家算法的思想也启发了很多其他领域的资源管理策略。比如在云计算中，给虚拟机分配物理资源时，也会做类似的“超额分配”检查，防止资源争抢导致系统崩溃。

---

公众号:蓝海资料掘金营，微信deep3321