Appearance
408
操作系统
死锁的预防与避免（银行家算法）
一、定位信息
- 所属圈层：核心层
- 前置知识：理解死锁的概念和四个必要条件（OS-02-14）
- 知识网络位置：银行家算法是408考试中OS部分最高频的综合题考点之一，必须掌握其执行过程和安全性判断
- 考点热度等级：H级（高频重点）——近5年综合题出现≥3次，是必考必练的核心算法
二、知识点讲解
2.1 死锁预防
通过破坏死锁四个必要条件中的至少一个来预防死锁：
| 预防策略 | 破坏的条件 | 做法 | 缺点 |
|---|---|---|---|
| 一次性分配 | 请求与保持 | 进程开始前一次性申请所有资源 | 资源利用率低，可能饥饿 |
| 可剥夺式分配 | 不可剥夺 | OS可以强制回收进程的资源 | 实现复杂，可能需要回滚 |
| 资源有序分配 | 循环等待 | 按编号递增顺序申请资源 | 编号难以确定，限制灵活性 |
| 假脱机技术 | 互斥 | 将独占设备虚拟为共享设备 | 仅适用于特定设备（如打印机） |
2.2 死锁避免——安全状态
安全状态：系统能按某种顺序为所有进程分配资源，使每个进程都能顺利完成。该顺序称为安全序列。
- 安全状态→一定不会死锁
- 不安全状态→可能死锁（不一定死锁）
- 死锁状态→一定是不安全状态
2.3 银行家算法
核心思想：在分配资源前，先试探性分配，检查分配后系统是否仍处于安全状态。如果是，则分配；否则不分配，让进程等待。
数据结构：
Available[j]：系统中资源j的可用数量Max[i][j]：进程i对资源j的最大需求Allocation[i][j]：进程i已获得的资源j的数量Need[i][j]：进程i还需要的资源j的数量（）
银行家算法步骤（进程i请求资源Request）：
- 检查请求是否合法：，否则报错
- 检查资源是否足够：，否则等待
- 试探性分配：
- 安全性检查：执行安全算法，判断系统是否仍安全
- 如果安全，正式分配；如果不安全，撤销试探性分配，让进程等待
2.4 安全性算法
- 初始化：，（所有进程）
- 找一个进程i满足： 且
- 如果找到：，，回到第2步
- 如果找不到：检查是否所有
- 全部为true → 安全状态（找到安全序列）
- 有false → 不安全状态
三、记忆与理解辅助
- 银行家算法口诀："先试探→再检查→安全就分→不安全就等"
- 安全性算法口诀："找能完成的→归还资源→再找→全部完成就安全"
- 关键公式：
- 安全状态一句话：存在一种顺序让所有进程都能顺利完成
四、例题与精解
例题1（基础巩固）
题目：系统中有3类资源R1、R2、R3，可用资源向量Available=(3,3,2)。有5个进程，当前状态如下：
| 进程 | Allocation | Max | Need |
|---|---|---|---|
| P0 | (0,1,0) | (7,5,3) | (7,4,3) |
| P1 | (2,0,0) | (3,2,2) | (1,2,2) |
| P2 | (3,0,2) | (9,0,2) | (6,0,0) |
| P3 | (2,1,1) | (2,2,2) | (0,1,1) |
| P4 | (0,0,2) | (4,3,3) | (4,3,1) |
判断当前状态是否安全，若安全给出一个安全序列。
命题意图：考查安全性算法的执行过程。
精解：
审题分析：需要执行安全性算法，逐个找到能完成的进程
解题思路：Work初始=Available=(3,3,2)，找Need≤Work的进程
完整步骤：
第1轮：Work=(3,3,2)
- P0: Need=(7,4,3) > Work → 不行
- P1: Need=(1,2,2) ≤ Work=(3,3,2) → 可以！
- 执行P1: Work = (3,3,2)+(2,0,0) = (5,3,2), Finish[1]=true
第2轮：Work=(5,3,2)
- P0: Need=(7,4,3) > Work → 不行
- P2: Need=(6,0,0) > Work → 不行（6>5）
- P3: Need=(0,1,1) ≤ Work → 可以！
- 执行P3: Work = (5,3,2)+(2,1,1) = (7,4,3), Finish[3]=true
第3轮：Work=(7,4,3)
- P0: Need=(7,4,3) ≤ Work → 可以！
- 执行P0: Work = (7,4,3)+(0,1,0) = (7,5,3), Finish[0]=true
第4轮：Work=(7,5,3)
- P2: Need=(6,0,0) ≤ Work → 可以！
- 执行P2: Work = (7,5,3)+(3,0,2) = (10,5,5), Finish[2]=true
第5轮：Work=(10,5,5)
- P4: Need=(4,3,1) ≤ Work → 可以！
- 执行P4: Work = (10,5,5)+(0,0,2) = (10,5,7), Finish[4]=true
所有进程Finish=true → 安全状态，安全序列如：P1→P3→P0→P2→P4
方法反思：安全性算法的核心是"找能完成的→归还→再找"，注意Need≤Work的逐分量比较
例题2（中等提升）
题目：在上题的基础上，若P1请求资源Request=(1,0,2)，系统是否应该分配？
命题意图：考查银行家算法的完整执行过程。
精解：
审题分析：P1请求(1,0,2)，需要经过合法性检查→试探分配→安全性检查
解题思路：按银行家算法三步走
完整步骤：
步骤1：检查请求合法性
- P1的Need=(1,2,2), Request=(1,0,2) ≤ Need → 合法
步骤2：检查资源是否足够
- Available=(3,3,2), Request=(1,0,2) ≤ Available → 足够
步骤3：试探性分配
- Available = (3,3,2)-(1,0,2) = (2,3,0)
- Allocation[1] = (2,0,0)+(1,0,2) = (3,0,2)
- Need[1] = (1,2,2)-(1,0,2) = (0,2,0)
步骤4：安全性检查（Work初始=(2,3,0)）
- P1: Need=(0,2,0) ≤ Work → 可以！Work=(2,3,0)+(3,0,2)=(5,3,2)
- P3: Need=(0,1,1) ≤ Work → 可以！Work=(5,3,2)+(2,1,1)=(7,4,3)
- P0: Need=(7,4,3) ≤ Work → 可以！Work=(7,4,3)+(0,1,0)=(7,5,3)
- P2: Need=(6,0,0) ≤ Work → 可以！Work=(7,5,3)+(3,0,2)=(10,5,5)
- P4: Need=(4,3,1) ≤ Work → 可以！Work=(10,5,5)+(0,0,2)=(10,5,7)
- 所有进程完成 → 安全
结论：系统应同意分配，分配后系统仍处于安全状态。
方法反思：银行家算法的每一步都不能省略——先查合法性，再查资源够不够，再试探分配，最后安全检查
五、考情分析
- 考查频次：近5年综合题出现≥3次
- 常见题型：综合题（10–15分）
- 分值占比：综合题中10–15分
- 命题趋势：银行家算法的安全性判断和资源请求处理是必考内容。近年倾向于在安全性算法基础上增加资源请求的处理，考查完整流程
六、易错点提醒
错误表现：Need = Max + Allocation 错误原因：公式记反 正确理解：Need = Max - Allocation（还需要的 = 最大需求 - 已获得的）
错误表现：安全性检查中比较Need和Available时，使用向量加法而非逐分量比较 错误原因：对"≤"的理解错误 正确理解：Need ≤ Work是指每个分量都小于等于，如(1,2,2)≤(3,3,2)表示1≤3且2≤3且2≤2
错误表现：试探性分配后忘记在不安全时撤销 错误原因：遗漏回退步骤 正确理解：如果不安全，必须撤销试探性分配（恢复原值），让进程等待
错误表现：安全性检查时忘记更新Work 错误原因：忽略了"归还资源"的步骤 正确理解：进程完成后会释放所有资源，Work = Work + Allocation（不是 + Need）
七、来源标注
- 依据2026考研统考408大纲
- 依据《计算机操作系统》（汤小丹/汤子瀛版）第2章
- 依据《操作系统概念》（Silberschatz版）第7章
- 依据王道考研408操作系统辅导讲义