Appearance
死锁检测与解除
考情分析
死锁检测在 408 真题中偶有考查，常以资源分配图化简的形式出现。属于 🔥🔥 中频考点。
预防和避免都是在死锁发生前做文章，但代价不小。另一种思路是：先不管，允许死锁发生，但定期"体检"，发现死锁了再治——这就是检测与解除。
死锁检测的思路
与死锁预防和避免不同，死锁检测允许死锁发生，但通过周期性检测来发现死锁，然后采取措施解除。
资源分配图
资源分配图是死锁检测的核心工具，它把进程和资源之间的"谁持有谁、谁在等谁"画成一张有向图，如果图中能消去所有边就没有死锁，消不干净就说明有进程被卡住了。具体来看：
- 进程节点：圆圈 ○
- 资源节点：方框 □（内部的点表示资源实例数）
- 请求边：进程 → 资源（进程请求资源）
- 分配边：资源 → 进程（资源已分配给进程）
上图中：P1 持有 R1、请求 R2，P2 持有 R2、请求 R1 → 形成环路 → 死锁。
资源分配图化简
化简规则：
- 找到一个既不阻塞又非孤立的进程 P_i（即 P_i 的所有请求都能被满足）
- 删除 P_i 的所有请求边和分配边（模拟 P_i 运行完毕释放资源）
- 重复步骤 1-2
- 如果能消去所有边 → 不存在死锁；否则 → 存在死锁
化简与安全性算法的关系
资源分配图化简的过程本质上和银行家算法的安全性检查类似——都是尝试找到一个可以完成的进程序列。
化简示例
初始状态:
P1: 持有 R1(1个), 请求 R2(1个)
P2: 持有 R2(1个), 请求 R1(1个)
P3: 持有 R1(1个)
R1 总量: 2, R2 总量: 1
化简过程:
P3 不请求任何资源 → 可以完成 → 释放 R1(1个)
现在 Available: R1=1, R2=0
P1 请求 R2(1个)，但 R2 可用=0 → 不能满足
P2 请求 R1(1个)，R1 可用=1 → 可以满足！
P2 完成 → 释放 R1(1个), R2(1个)
现在 Available: R1=2, R2=1
P1 请求 R2(1个)，R2 可用=1 → 可以满足！
P1 完成 → 所有边消除 → 不存在死锁化简失败 = 死锁
把上面的例子改一个数字看反例：
初始状态:
P1: 持有 R1(1个), 请求 R2(1个)
P2: 持有 R2(1个), 请求 R1(1个)
P3: 持有 R1(1个), 请求 R2(1个) ← P3 也开始请求 R2
R1 总量: 2, R2 总量: 1
化简过程:
P3 有请求边（请求 R2），且 R2 当前可用=0 → 阻塞
P1 阻塞（请求 R2，R2 可用=0）
P2 阻塞（请求 R1，R1 已全部分给 P1/P3）
→ 没有任何进程能完成 → 化简卡住 → 存在死锁
被锁住的进程集合: {P1, P2, P3}
── 这就是「死锁进程集」，是死锁解除时要处理的对象化简的两个判定要点
- 化简能消去所有边 → 不存在死锁；只要还有边没消去 → 死锁
- 资源分配图中存在环路是死锁的必要不充分条件——只有当环路上每种资源都只有 1 个实例时才必死；多实例时要靠化简
死锁检测算法
与银行家算法的安全性检查类似，但有一个重要区别：
| 对比 | 银行家算法 | 死锁检测算法 |
|---|---|---|
| 使用的需求量 | Need（最大需求-已分配） | 当前请求（Request） |
| 时机 | 分配前检查 | 分配后检查 |
| 乐观程度 | 保守（考虑最大需求） | 乐观（只看当前请求） |
交互可视化
死锁解除
检测到死锁后，需要采取措施解除：
1. 终止进程
| 方式 | 说明 | 代价 |
|---|---|---|
| 终止所有死锁进程 | 简单粗暴 | 代价最大，可能白费大量工作 |
| 逐个终止 | 每次终止一个进程后重新检测 | 开销大（每次都要重新检测） |
逐个终止时，选择哪个进程终止的考虑因素：
- 进程优先级
- 已执行的时间和还需要的时间
- 已使用的资源数量
- 进程类型（交互式 vs 批处理）
2. 资源剥夺
从死锁进程中强制剥夺资源给其他进程使用。
需要考虑：
- 从哪个进程剥夺（代价最小原则）
- 回滚：被剥夺资源的进程需要回退到某个安全状态
- 防止饥饿：不能总是剥夺同一个进程的资源
死锁检测的时机
| 策略 | 说明 |
|---|---|
| 每次资源请求时 | 实时性好，但开销大 |
| 定时检测 | 折中方案 |
| 资源利用率下降时 | 按需检测 |
考研高频考点
- 🔥🔥🔥 资源分配图的化简过程
- 🔥🔥 死锁检测算法与银行家算法的区别（用 Request 而非 Need）
- 🔥🔥 死锁解除的两种方式（终止进程/资源剥夺）
- 🔥 选择终止进程时的考虑因素
到这里，进程管理的全部内容就结束了。下一章进入内存管理，看操作系统如何为进程分配和保护内存空间。