死锁避免

2.4.2 的预防太粗暴——为了杜绝死锁，把大量本来完全安全的分配也一并禁止了。

死锁避免的思路更聪明：不预设规则，而是在每次分配之前算一算——这一笔分出去，系统会不会陷入危险？ 安全就分，不安全就先不分。

机制

安全状态与安全序列

安全状态：系统能找出一个进程执行序列 P₁, P₂, …, Pₙ，使得按这个顺序，每个进程所需的剩余资源都能被满足，从而所有进程都能顺利跑完。这样的序列称为安全序列。

只要能找出至少一个安全序列，系统就处于安全状态。 找不出任何一个，就是不安全状态。

关键在于理解”按这个顺序”：安全序列不要求所有进程同时都能拿到资源，只要求能一个接一个地推进——P₁ 先跑完并释放它的全部资源，这些资源加上原有的空闲量足够 P₂ 跑完，P₂ 释放后又足够 P₃……如此接力到底。

银行家算法：最直白的说法

疑问点：用最直白的语言表述银行家算法

该算法的核心思想需要一个不绕弯子的表述，同时需要确认这种表述在考试中是否稳妥。

最直白的一句话：

有人来借资源，银行先在账本上假装借给他，然后检查一遍：按这本新账，能不能找出一个顺序，让所有客户一个接一个地把资源借够、干完活、全部还回来？ 找得出来就真借；找不出来，就把账本改回原样，让他先等着。

这个表述是准确的，可以直接用。它抓住了算法的三个动作：试探 → 检查 → 决定。

但用于答题时，有三个词不能省，否则会被判表述不完整：

必须出现	原因
试探性分配（或”假定分配”）	强调这是一次假设，不是真分配。漏掉它，就说不清”找不出来时把账本改回去”这一步
安全序列	”让所有客户一个接一个还回来”的规范名称。这是评分的关键词
安全状态 / 不安全状态	判断的结论必须落在这对术语上

规范表述：当进程提出资源请求时，系统先进行试探性分配，然后执行安全性算法检查此时是否存在安全序列。若存在，则系统处于安全状态，正式分配；若不存在，则处于不安全状态，撤销本次试探性分配，让该进程等待。

四个数据结构

银行家算法维护四张表（设 n 个进程、m 类资源）：

名称	规模	含义
Max	n×m	每个进程对每类资源的最大需求
Allocation	n×m	每个进程已分配到的数量
Need	n×m	每个进程还需要的数量
Available	m	系统当前空闲的各类资源数

三者之间有一个恒等式，做题时可用于校验：

算法的两个部分

第一部分：请求检查与试探分配

进程 Pᵢ 提出请求向量 Request_i：

1. 若 Request_i > Need_i，报错——请求量超过了它当初声明的最大需求。
2. 若 Request_i > Available，让 Pᵢ 等待——系统现在没这么多空闲资源。
3. 两项都通过，则试探性分配：

Available    = Available    - Request_i
Allocation_i = Allocation_i + Request_i
Need_i       = Need_i       - Request_i

4. 执行安全性算法。安全则正式分配；不安全则把上面三行全部回滚，让 Pᵢ 等待。

第二部分：安全性算法（找安全序列）

设工作向量 Work = Available，标记数组 Finish[i] = false。

1. 从所有 Finish[i] == false 的进程中，找一个满足 Need_i ≤ Work 的。
2. 找到了：假设它能跑完并归还全部资源，于是

Work = Work + Allocation_i
Finish[i] = true

回到第 1 步继续找。

3. 找不到任何满足条件的进程了，就停下来判断：
   • 若所有 Finish[i] 都为 true → 安全，刚才的记录顺序就是一个安全序列
   • 否则 → 不安全

手算要诀：每轮扫描时，把 Need 逐行与当前 Work 比较，找到第一个”每一类都不超过 Work”的进程就选它，把它的 Allocation 加进 Work，划掉该行，再从头扫一遍。注意归还的是 Allocation（它实际占着的），不是 Need。 这是手算最常见的错处。

一道公式题

疑问点：同类资源下保证不死锁的最大需求量之和

28. 某系统有 m 个同类资源供 n 个进程共享，若每个进程最多申请 k 个资源（k>1）， 采用银行家算法分配资源，为保证系统不发生死锁，则各进程的最大需求量之和应（ ）。 A. 等于 m　B. 等于 m+n　C. 小于 m+n　D. 大于 m+n

答案 C：小于 m+n。

这道题不用套公式，想清楚”最坏情况长什么样”就出来了。

最坏的局面是：每个进程都拿到了 k−1 个资源，每个都只差最后 1 个就能完成，而系统里一个空闲的都不剩。这时谁也动不了，死锁。

此时被占用的资源总数是 。

要避免这个局面，只需保证系统里还剩至少 1 个资源。 因为只要还剩 1 个，就可以给其中任意一个进程，它便能凑够 个、跑完、把手里的全部资源归还——接力就此启动，后面的进程依次都能完成。

于是安全的条件是：整理一下（注意各进程最大需求量之和就是 ）：

代入一组数验证：设 、，则最大需求之和 。

• 若 ： ✓ 满足条件。验证一下最坏情况——3 个进程各持 2 个共占 6 个，还剩 1 个，给谁谁就能跑完。安全。
• 若 ： ✗ 不满足。验证——3 个进程各持 2 个正好占满 6 个，一个不剩，三方都只差 1 个，死锁。

公式与直觉完全对上。

这类题的通用模板：只要问”n 个进程、每个最多需要 k 个、共享 m 个同类资源，不死锁的条件”，一律回到那句话——让最坏情况下（人人差一个）还能剩下至少一个。

边界

安全状态、不安全状态与死锁的关系

这三者的包含关系是本节最高频的辨析点，千万不要画等号：

flowchart LR
    subgraph ALL[" 系统的全部状态 "]
        direction LR
        S["<b>安全状态</b><br/>存在安全序列<br/><b>一定不会死锁</b>"]:::safe
        subgraph U[" 不安全状态 "]
            D["<b>死锁状态</b>"]:::dead
            N["尚未死锁<br/>但可能演变成死锁"]:::warn
        end
    end
    classDef safe fill:#dbeafe,stroke:#2563eb,color:#1e3a5f
    classDef warn fill:#fef3c7,stroke:#d97706,color:#78350f
    classDef dead fill:#fee2e2,stroke:#dc2626,color:#7f1d1d

三条结论：

• 安全状态 ⟹ 一定不会死锁。（因为安全序列已经给出了一条全员跑完的路径）
• 不安全状态 ⟹ 可能死锁，但不一定死锁。 只要进程们没有真的把最大需求全部提出来，系统仍可能侥幸通过。
• 死锁状态 ⊂ 不安全状态。 死锁一定不安全，但不安全不一定死锁。

因此银行家算法是”宁可错杀”的保守策略——它拒绝一切会导致不安全状态的分配，哪怕那次分配实际上不会引发死锁。这正是下一条要讲的代价。

为什么进程会”长时间阻塞”

2.4.2 提到过表 2.5 里这条缺点，在这里才能真正讲清。

被拒绝的进程等待的不是资源，而是算法的放行。

系统里明明有空闲资源，进程的请求也没超过它声明的最大需求，但因为分配后找不出安全序列，请求就被驳回。进程只能干等，直到别的进程释放资源、局面变得安全为止。

由于银行家算法按最大需求（而非当前实际需要）来评估风险，它会系统性地高估危险，于是拒绝相当一部分实际上无害的分配。进程因此可能等待很久——这不是资源不足造成的，是保守策略的代价。

现实中真的有系统使用银行家算法吗

疑问点：银行家算法的实际运行开销与工程可用性

该算法每次分配都要执行一遍安全性检查，开销似乎很大。现实中是否有系统采用？

几乎没有通用操作系统使用它。 有四个原因，前两个是致命的：

① 必须预先知道每个进程的最大需求——这在现实中做不到。 一个普通程序在启动时根本无法说清它接下来要用多少内存、开多少文件。要求用户程序预先声明最大需求，既不现实也不可靠。

② 进程和资源的数量是动态变化的。 银行家算法假设 n 个进程、m 类资源是相对固定的，而真实系统里进程随时创建和终止。

③ 开销大。 一次安全性检查的复杂度约为 。若每次资源请求都跑一遍，在请求频繁的系统里代价难以承受。

④ 过于保守。 如上一条所述，它会拒绝大量实际安全的分配，资源利用率偏低。

现实中的真实做法主要有两种：

鸵鸟策略——绝大多数通用操作系统（Linux、Windows）的选择。假装死锁不存在。理由是通用系统中死锁发生概率极低，而预防和避免的代价远高于偶尔重启的代价。

检测 + 解除——数据库系统的标准做法。以 MySQL InnoDB 为例：它允许事务自由加锁，同时维护一张等待图，周期性地（或在等待超时时）检测其中是否存在环；一旦发现死锁，就选一个”代价最小”的事务作为牺牲品回滚，让其余事务继续。

数据库之所以能这么做，是因为它天然具备银行家算法所缺的条件：事务有明确的回滚机制，被牺牲的事务可以干净地撤销并重试。而操作系统杀死一个进程的代价要大得多。这正是 2.4.4 的内容。

考试层面：银行家算法仍是必考的手算题，因为它是”避免”策略的唯一代表算法。理解它工程上不实用，反而有助于记住它的缺点栏。

银行家算法 vs 资源分配图化简

两者都要”试着让进程跑完”，但目的与时机完全不同：

	银行家算法	资源分配图化简
属于	避免（事前）	检测（事后）
用什么判断	Need（还需要多少，基于最大需求）	当前实际请求边
回答的问题	这次分配能不能批	系统现在是否已经死锁
结论	安全 / 不安全	死锁 / 未死锁

最容易混的一点：银行家算法看的是 Need（按最大需求预判未来），化简看的是当前实际提出的请求。 前者是预言家，后者是验尸官。

对照速查

数据结构	含义
Max	最大需求
Allocation	已分配
Need	还需要，= Max − Allocation
Available	当前空闲

算法步骤	内容
①	Request > Need？→ 出错
②	Request > Available？→ 等待
③	试探性分配（改三张表）
④	安全性算法找安全序列
⑤	安全→正式分配；不安全→回滚并等待

关系	结论
安全状态	一定不死锁
不安全状态	可能死锁，不一定死锁
死锁状态	⊂ 不安全状态

考点

• 安全序列的定义：能一个接一个跑完的顺序，不要求同时满足
• Need = Max − Allocation（校验用）
• 安全性算法中归还的是 Allocation 而非 Need（手算最易错处）
• 安全 ⟹ 不死锁；不安全 ⇏ 死锁（三者包含关系）
• 银行家算法看 Need，资源分配图化简看当前请求边
• 进程、每个最多 、共 个同类资源时，不死锁需
• 缺点：须预知最大需求、开销大、过于保守、进程可能长期阻塞

链接

• 🏠 返回总览：操作系统第 2 章：进程与线程总览
• ⬅️ 上一节：2.4.2 死锁预防
• ➡️ 下一节：2.4.4 死锁检测和解除
• 📖 名词库：第 2 章名词库