408

操作系统

死锁的检测与解除

---

一、定位信息

• 所属圈层：核心层
• 前置知识：理解死锁的概念和四个必要条件（OS-02-14），了解死锁预防与避免（OS-02-15）
• 知识网络位置：本单元是死锁处理三部曲的最后一部分——当预防和避免都无法完全消除死锁时，需要检测并解除
• 考点热度等级：M级（中频常考）——近5年选择题出现约2–3次，资源分配图和死锁检测是主要考点

---

二、知识点讲解

2.1 死锁检测的思路

不预防、不避免，允许死锁发生，但及时发现并处理。

检测工具：资源分配图（Resource Allocation Graph, RAG）

2.2 资源分配图

资源分配图由两类节点和两类边组成：

元素	符号	含义
进程节点	圆圈P	表示进程
资源节点	方框R（内含圆点表示实例数）	表示资源类型
请求边	P→R	进程请求资源
分配边	R→P	资源已分配给进程

死锁检测规则：

• 如果资源分配图中无环路→一定没有死锁
• 如果资源分配图中有环路：
  • 每种资源只有一个实例→一定死锁
  • 每种资源有多个实例→可能死锁（需要进一步检查）

2.3 死锁检测算法

基于银行家算法的简化版：

1. 初始化：$Work = Available$，$Finish[i] = false$（对所有拥有资源的进程）
2. 找一个进程i：$Finish[i] = false$ 且 $Request_i \leq Work$
3. 如果找到：$Work = Work + Allocation_i$，$Finish[i] = true$，回到第2步
4. 如果找不到：所有 $Finish[i] = false$ 的进程都处于死锁状态

与安全性算法的区别：安全性算法检查"系统是否安全"，检测算法检查"哪些进程已经死锁"。

2.4 死锁的解除方法

方法	做法	优缺点
资源剥夺法	从死锁进程中剥夺资源给其他进程	简单，但被剥夺进程可能需要回滚
撤销进程法	终止一个或多个死锁进程	直接有效，但可能丢失已完成的工作
进程回退法	让进程回退到某个安全状态重新执行	保留部分工作，但实现复杂

选择撤销进程的策略：

• 优先级最低的进程
• 已执行时间最短的进程
• 已完成工作量最少的进程
• 需要资源最多的进程

2.5 死锁处理策略对比表

策略	时机	开销	资源利用率	实现复杂度
死锁预防	事前（运行前）	低	低（限制多）	低
死锁避免	事中（分配时）	中	中	中（需预知Max）
死锁检测+解除	事后（发生后）	高（检测+解除）	高	高
鸵鸟策略	不处理	无	最高	无

鸵鸟策略：忽略死锁问题，假设死锁不会发生或发生概率极低。许多实际系统（如Linux、Windows）采用此策略。

---

三、记忆与理解辅助

1. 死锁处理三部曲口诀："预防→避免→检测解除，越往后越灵活但开销越大"
2. 资源分配图判断口诀："无环一定不死锁，有环单实例必死锁，有环多实例可能死锁"
3. 检测算法vs安全性算法：安全性算法是"能不能都完成"，检测算法是"找出哪些完成不了"
4. 解除死锁的代价：终止进程>资源剥夺>进程回退（代价由大到小）

---

四、例题与精解

例题1（基础巩固）

题目：在资源分配图中，如果存在环路且每种资源只有一个实例，则（ ）

A. 一定没有死锁 B. 一定有死锁 C. 可能有死锁 D. 需要进一步检测

命题意图：考查资源分配图与死锁的关系。

精解：

1. 审题分析：有环路 + 每种资源只有一个实例
2. 解题思路：单实例资源有环路则必然死锁
3. 完整步骤：
   • 资源分配图中存在环路，表示存在循环等待
   • 每种资源只有一个实例，意味着环路中的每个进程都在等待一个已被占用的资源
   • 没有额外的资源实例可以打破环路
   • 因此一定有死锁
   • 多实例时有环路只是可能死锁（因为可能有其他资源实例可以打破环路）
4. 方法反思：单实例+有环=必然死锁，多实例+有环=可能死锁

答案：B

例题2（中等提升）

题目：系统检测到死锁后，以下解除方法中，对系统影响最小的是（ ）

A. 终止所有死锁进程 B. 从一个死锁进程中剥夺资源 C. 终止优先级最低的一个死锁进程 D. 让死锁进程回退到死锁前的状态重新执行

命题意图：考查死锁解除方法的影响程度。

精解：

1. 审题分析：需要比较各种解除方法对系统的影响
2. 解题思路：影响最小意味着丢失的工作量最少
3. 完整步骤：
   • A选项：终止所有死锁进程，影响最大（所有工作丢失）
   • B选项：从一个进程剥夺资源，该进程可能需要回滚，影响中等
   • C选项：终止一个进程，影响较大（该进程工作全部丢失）
   • D选项：回退到死锁前的状态重新执行，保留了死锁前已完成的工作，影响最小
   • 但D选项实现复杂度最高，需要保存进程的历史状态
4. 方法反思：影响大小排序：回退（最小）→ 剥夺一个 → 终止一个 → 终止全部（最大）

答案：D

---

五、考情分析

• 考查频次：近5年约2–3次
• 常见题型：选择题
• 分值占比：2分/题
• 命题趋势：资源分配图的环路判断和死锁检测算法是主要考点，可能与银行家算法对比出题

---

六、易错点提醒

1. 错误表现：认为有环路就一定有死锁 错误原因：忽略了多实例资源的情况 正确理解：只有单实例资源有环路才必然死锁，多实例有环路只是可能死锁

2. 错误表现：混淆死锁检测算法和安全性算法 错误原因：两者结构相似 正确理解：安全性算法判断系统是否安全（能否全部完成），检测算法找出已经死锁的进程（哪些完成不了）

3. 错误表现：认为死锁解除后系统恢复正常，不需要额外处理 错误原因：忽略了被终止/回退进程的影响 正确理解：被终止的进程可能需要重新执行，被剥夺资源的进程可能需要回滚，这些都有代价

4. 错误表现：认为鸵鸟策略不是合理的死锁处理方法 错误原因：认为"不处理"是不负责任的 正确理解：鸵鸟策略在死锁发生概率极低、检测/预防代价过高的情况下是合理的工程权衡，许多实际系统采用此策略

---

七、来源标注

• 依据2026考研统考408大纲
• 依据《计算机操作系统》（汤小丹/汤子瀛版）第2章
• 依据《操作系统概念》（Silberschatz版）第7章