Appearance
银行家算法
2026 大纲 二（四）3 死锁避免。
不改规则，只在每次分配前算一算
上一节的死锁预防很有效，但代价也明摆着：它从条件上就把路堵死了。 比如资源有序分配法要求所有进程按固定序号申请资源—— 可实际程序未必是那个顺序，硬改就得改代码，而且资源利用率会掉下来。
避免换了个思路：四个必要条件一个都不破坏， 只是在每次分配之前先试算一下——如果批准这次请求之后， 系统仍然能找到一条路让所有进程都跑完，就批；否则就让它等。
这里的关键是"仍然能找到一条路"，它有个名字叫安全状态： 存在一个安全序列，使得按这个顺序执行，每个进程都能拿到它还需要的全部资源并跑完。
⚠️ 要立住一处口径：不安全状态不等于死锁。 不安全只是说"可能走到死锁"，系统仍然可以侥幸不死； 但银行家算法宁可保守——它的目标是使系统永远不进入不安全状态。
算法本身就是把上面那句话翻译成四步： 假设手上的可用资源是 Work、所有进程都还没完成 → 找一个"还需要的量 ≤ Work"的进程 → 让它跑完并归还全部已占资源（Work += Allocation）→ 重复，全部完成即安全。
⚠️ 两处最容易错的地方要先钉住： 第 2 步比的是 Need（还需要多少）不是 Request（这次要多少）； 第 3 步加的是 Allocation（它手上已有的全部）不是 Need。
交互可视化
一、安全状态：死锁避免的全部理论基础
教材原话是"虽然并非所有不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，就有可能进入死锁状态"。"不安全 ≠ 死锁"决定了银行家算法是保守的：它会拒掉一些其实不会死锁的请求，代价是资源利用率不如"检测+解除"路线，收益是永远不会真的死锁。
二、四张表
| 数据结构 | 维度 | 含义 |
|---|---|---|
| Available | 1×m | 各类资源当前的可用数量，随分配与回收动态改变 |
| Max | n×m | 每个进程对各类资源的最大需求，进程进入系统时必须申明，且不应超过系统资源总量 |
| Allocation | n×m | 每个进程当前已分配到的各类资源数 |
| Need | n×m | 每个进程尚需的各类资源数，由 Max − Allocation 推出 |
三、安全性算法
1. 初始化：
Work = Available // 工作向量：系统当前可提供的资源
Finish[i] = false // 所有进程标记为未完成
2. 找一个同时满足两条的进程 P_i：
Finish[i] == false 且 Need[i] <= Work
3. 找到就：
Work = Work + Allocation[i] // 模拟它跑完，归还全部已占资源
Finish[i] = true
回到步骤 2
4. 若最终所有 Finish[i] == true → 安全，记录下来的顺序就是安全序列
否则 → 不安全步骤 2 里"随便挑一个
四、资源请求处理：三道关
| 关 | 检查 | 不通过怎么办 | 为什么要有这一关 |
|---|---|---|---|
| ① | 认为出错——它所需要的资源数已超过它宣布的最大值 | Max 是进程自己申明的承诺，超了说明进程行为不合法 | |
| ② | 尚无足够资源， | 物理可行性：系统当下拿不出这么多，无从试探分配 | |
| ③ | 试探分配后安全性检查通过 | 作废本次试探分配，恢复原状态，让 | 物理够了，但分完之后可能失去"所有进程都能跑完"的保证 |
试探分配（第 ③ 关之前）要同时改三处：
Available = Available - Request_i
Allocation_i = Allocation_i + Request_i
Need_i = Need_i - Request_i关的顺序不能乱：②不过就不必做③——系统连资源都拿不出来，谈不上试探分配。判据一句话：先看拿不拿得出来，再看敢不敢给。
一套完整手算：算 Need 与 Available、跑一轮安全性检查、再处理两个走向不同的请求（想看清每一轮 Work 怎么变、什么时候能立即判不安全时展开）
系统有 A、B、C 三类资源，总量 (12, 8, 9)，4 个进程当前状态：
| 进程 | Max (A,B,C) | Allocation (A,B,C) | Need = Max − Allocation |
|---|---|---|---|
| P0 | 6, 2, 4 | 3, 1, 2 | 3, 1, 2 |
| P1 | 4, 5, 3 | 2, 3, 1 | 2, 2, 2 |
| P2 | 8, 1, 5 | 4, 0, 3 | 4, 1, 2 |
| P3 | 3, 4, 2 | 1, 2, 1 | 2, 2, 1 |
第 1 步：算 Need。 逐格做减法，结果见上表第三列。Need 是安全性算法唯一要比较的量，而题目通常只给 Max 与 Allocation。
第 2 步：算 Available。 Work 的初值就是 Available，算错了后面全错。
第 3 步：跑安全性算法。
| 轮次 | Work (A,B,C) | 逐个试 | 选中 | Work += Allocation |
|---|---|---|---|---|
| 1 | 2, 2, 2 | P0 Need(3,1,2)：A 需 3 > 2 ✗ P1 Need(2,2,2) ≤ (2,2,2) ✓ | P1 | (2,2,2)+(2,3,1) = 4, 5, 3 |
| 2 | 4, 5, 3 | P0 Need(3,1,2) ≤ (4,5,3) ✓ | P0 | (4,5,3)+(3,1,2) = 7, 6, 5 |
| 3 | 7, 6, 5 | P2 Need(4,1,2) ≤ (7,6,5) ✓ | P2 | (7,6,5)+(4,0,3) = 11, 6, 8 |
| 4 | 11, 6, 8 | P3 Need(2,2,1) ≤ (11,6,8) ✓ | P3 | (11,6,8)+(1,2,1) = 12, 8, 9 |
第 4 步：判定并自检。 四个进程 Finish 全为 true → 系统处于安全状态，安全序列为
第 5 步：安全序列不唯一。 把 4 个进程的全部
| 进程 | Need | 与 | 能不能起步 |
|---|---|---|---|
| P0 | (3,1,2) | A：3 > 2 | ✗ |
| P1 | (2,2,2) | 三项均 ≤ | ✓ |
| P2 | (4,1,2) | A：4 > 2 | ✗ |
| P3 | (2,2,1) | 三项均 ≤ | ✓ |
10 条里 6 条以
贪心与全排列穷举等价这一条，另用 200 000 组随机实例（进程数 2~5、资源类型 1~3、各项取值 0~3）逐组比对过，不一致 0 组（其中被判为安全的 114 412 组）。
第 6 步：处理一次请求——P2 请求 (2, 1, 1)，过了②、倒在③。
- 第①关：
， ✓ - 第②关：
， ✓ - 试探分配：
| 原值 | 变化 | 新值 | |
|---|---|---|---|
| Available | (2,2,2) | −(2,1,1) | (0, 1, 1) |
| Allocation[P2] | (4,0,3) | +(2,1,1) | (6, 1, 4) |
| Need[P2] | (4,1,2) | −(2,1,1) | (2, 0, 1) |
- 对新状态跑安全性算法，
：
| 进程 | Need | 与 Work=(0,1,1) 比较 | 能推进吗 |
|---|---|---|---|
| P0 | (3,1,2) | A：3 > 0 | ✗ |
| P1 | (2,2,2) | A：2 > 0 | ✗ |
| P2 | (2,0,1) | A：2 > 0 | ✗ |
| P3 | (2,2,1) | A：2 > 0 | ✗ |
第一轮就找不到可推进的进程，即可立即判定不安全，不必再循环。根因很清楚：A 类资源被 P2 一次拿走 2 个后只剩 0，而四个进程的 Need 在 A 上都 ≥ 2。于是撤销试探分配，三处数值恢复为 Available=(2,2,2)、Allocation[P2]=(4,0,3)、Need[P2]=(4,1,2)，让 P2 等待。
第 7 步：对照——P0 请求 (3, 0, 0)，在第②关就被挡下。 第①关
五、算法的局限性
| 局限 | 说明 | 根因 |
|---|---|---|
| 需要预知 Max | 每个新进程进入系统时必须申明各类资源的最大需求 | 没有 Max 就算不出 Need，安全性算法失去比较对象 |
| 效率低 | 每次分配都要执行一遍安全性检查 | 复杂度约 |
| 进程数固定 | 不适合进程数动态变化的系统 | 进程动态增减会让 Max/Allocation 矩阵不断重建 |
| 偏保守 | 会拒掉一些其实不会死锁的请求 | 它按最坏情况（Need）判定，而进程未必真的会要到 Max |
考点速记
- 银行家算法属于死锁避免：不破坏任何必要条件，而在每次分配前试算，只批准仍处于安全状态的请求。实质是使系统不进入不安全状态。
- ⚠️不安全状态
死锁：不安全只表示可能发展成死锁，并非一定死锁；而安全状态则一定不会死锁。 - 安全性算法四步：
Work = Available、Finish全false→ 找Need ≤ Work且未完成的进程 →Work += Allocation并置Finish = true→ 全部完成即安全。 - ⚠️两处必错点：第 2 步用
Need不用Request；第 3 步加Allocation不加Need。末态的Work应当等于系统资源总量——这是自检的好办法。 - 处理一次请求要过三道关：
→ → 试探性分配后跑安全性检查。②不过立即阻塞、③不过回滚再阻塞。 - ⚠️贪心找与全排列穷举等价：只要贪心地"随便找一个能满足的就让它跑"跑不下去，系统就一定不安全——不必担心是不是换个顺序就行了。
Need = Max − Allocation。题目给的表格通常只给其中两列，第三列要自己算。
这一节在真题里被考过的形式：
银行家算法是 process 章计算题最密的一节——deadlock 那 13 道题里有 6 道是它， 而且六道题走的是完全相同的四步，只是数据不同。
- 给某时刻的资源分配表，判断系统是否安全 / 求安全序列（2011-27、2012-27、2018-26、2020-27、2022-26）。⚠️ 做题时按顺序做三件事就不会错：① 先补出
Need = Max − Allocation这一列；② 算出Available（总量减去已分配之和，题目常常不直接给）；③ 按速记第三条走四步，每让一个进程跑完就把它的Allocation全部加回Work。做完用速记第四条自检——末态Work应等于资源总量。 - 判断关于银行家算法的叙述（2013-32）。⚠️ 落点是速记第一、二条：它是避免不是预防（不破坏必要条件）、目标是使系统不进入不安全状态、不安全状态不等于死锁。
- 比较死锁避免与死锁检测（2015-26，在死锁的概念与预防讲）。关键差别是避免需要
Need（资源总需求），检测不需要。
复习优先级：必须拿满，这是全章最稳的送分题。 四步流程练熟即可， 但每一步都要照速记第四条那两个"用哪一列"的提醒来做—— 用错列是这类题唯一的失分方式。做完务必用"末态 Work 等于资源总量"自检一遍。
易错：安全性检查第 2 步拿
Request去比Work。要用Need——那是它还需要多少才能跑完。
易错：第 3 步把
Need加进Work。要加Allocation——进程跑完归还的是它手上已有的全部。
易错：忘了先算
Need = Max − Allocation。表格常常只给两列。
易错：认为不安全状态就是死锁。不安全只是可能死锁；反过来安全状态则一定不死锁。
易错：贪心找不到安全序列时怀疑是顺序选错了。贪心与穷举等价，跑不下去就是不安全。
易错：把银行家算法归到死锁预防。它是避免——一个必要条件都没破坏。
教材出处
- 安全状态与安全序列的定义：汤小丹《计算机操作系统》3.7.1 节，印刷 p110—p111——"所谓安全状态，是指系统能按某种进程推进顺序
为每个进程 分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成"；"虽然并非所有不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，就有可能进入死锁状态。反之，只要系统处于安全状态，系统便不会进入死锁状态"；"避免死锁的实质在于，系统在进行资源分配时，应使系统不进入不安全状态"。 - 四个数据结构与 Need = Max − Allocation：同书 3.7.2 节，印刷 p112。
- 资源请求的四个步骤：同书印刷 p112——(1)
Request[i] ≤ Need[i,j]否则"认为出错，因为它所需要的资源数已超过它所宣布的最大值"；(2)Request[i] ≤ Available[j]否则"表示尚无足够资源，Pi 须等待"；(3) 试探分配并修改三处数值；(4) 执行安全性算法，"否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 Pi 等待"。 - 安全性算法的 Work 与 Finish：同书印刷 p112——"在执行安全算法开始时，Work := Available"；"Finish……开始时先做 Finish[i] := false"。
- 进程进入系统须申明最大需求：同书印刷 p111——"每一个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量"。
本节算例的数据为自行构造，与教材的磁带机算例（12 台磁带机、3 进程）无关，可对照阅读。