考研笔记

死锁检测和解除

前两节都是不让死锁发生：预防在设计时立规矩，避免在分配时算风险。这一节换一条路——允许死锁发生，事后再收拾。

代价是要有一套”看出死锁”的手段，以及一套”把它拆开”的手段。前者靠资源分配图，后者靠剥夺或撤销。

机制

资源分配图

用一张有向图描述”谁占着什么、谁在要什么”。

两类结点：

  • 进程结点（画成圆圈 P₁、P₂）
  • 资源结点（画成方框 R₁、R₂），方框内的圆点数量表示该类资源有几个实例

两类边（方向是关键）：

  • 请求边 Pᵢ → Rⱼ：进程 Pᵢ 正在申请一个 Rⱼ 类资源，尚未拿到
  • 分配边 Rⱼ → Pᵢ：一个 Rⱼ 类资源实例已经分配给了 Pᵢ

记忆抓手：箭头从谁指出来，谁就是”主动的一方”——进程主动申请（P 指向 R），资源被动地分配出去（R 指向 P）。

flowchart LR
    P1(("P₁")):::proc -->|"请求边"| R2["R₂<br/>● ●"]:::res
    R2 -->|"分配边"| P2(("P₂")):::proc
    P2 -->|"请求边"| R1["R₁<br/>●"]:::res
    R1 -->|"分配边"| P1

    classDef proc fill:#dbeafe,stroke:#2563eb,color:#1e3a5f
    classDef res fill:#fef3c7,stroke:#d97706,color:#78350f

资源分配图的化简

化简的思想是模拟”让能跑的进程先跑完”：

  1. 在图中找一个既不阻塞又非孤立的进程结点 Pᵢ——即它申请的每一类资源都还有足够的空闲实例可以满足。
  2. 既然它能被满足，就假设它顺利运行完毕，释放全部资源。于是把它的所有边（请求边和分配边）都消去，使 Pᵢ 变成孤立结点。
  3. 释放出来的资源可能让别的进程变得可满足，回到第 1 步继续找。
  4. 重复直到再也找不到可消去的进程。

若最终所有进程结点的边都被消去（图中只剩孤立结点），称该图可完全简化；否则称不可完全简化。

手算要点：判断某进程能否被消去时，比较的是它的请求边数量与当前空闲实例数（总实例数减去已分配出去的），而不是与总数比较。这与 银行家算法中”归还 Allocation”是同一类易错点。

死锁定理

疑问点：死锁定理属于哪一类死锁处理方法

  1. 死锁定理是用于处理死锁的（ ）方法。 A. 预防死锁　B. 避免死锁　C. 检测死锁　D. 解除死锁

该定理此前未曾接触，需明确其内容与用途。

答案 C：检测死锁。

“死锁定理”这个名字听起来很正式，但它说的其实就是上面化简过程的结论：

死锁定理：系统状态 S 为死锁状态的充分必要条件是——S 状态的资源分配图不可完全简化。

也就是说，它是一条判定准则：给你一张资源分配图，化简一遍，简化不完就是死锁，能简化完就没死锁。

判定准则用来”看有没有”，因此属于检测。 逐项排除也很清楚：

  • 预防是在设计时破坏四个必要条件之一，用不着判定
  • 避免用的是银行家算法，判断的是”安全 / 不安全”，不是”死锁 / 未死锁”
  • 解除是发现死锁之后的处理动作（剥夺、撤销），死锁定理不负责处理

之所以对这个名字感到陌生，是因为教材通常把重点放在”资源分配图化简”这个操作上，而”死锁定理”是给这个操作的结论起的名字。两者说的是同一件事：会化简，就等于掌握了死锁定理。

死锁解除的三种方法

检测出死锁之后，必须打破僵局。三种手段：

① 资源剥夺法——挂起某些死锁进程，抢占它们的资源分配给其他死锁进程。

注意被挂起的进程要防止长期得不到资源而饥饿。

② 撤销进程法——强制撤销部分甚至全部死锁进程，剥夺其全部资源。

最简单粗暴，代价也最大——被撤销进程之前所做的工作全部作废。

③ 进程回退法——让进程回退到足以避开死锁的某个检查点，从那里重新执行。

代价最小，但要求系统记录进程的历史信息、设置还原点，实现复杂。

选择牺牲品的原则：应挑选代价最小的进程，通常综合考虑——进程优先级高低、已运行时间长短、还需运行多久、已占用资源多少、是交互式还是批处理。

检测的时机

死锁检测本身有开销，跑得越勤发现越及时、但越费 CPU。常见策略：

  • 每次资源请求得不到满足时立即检测——发现最及时，开销最大
  • 定时检测（如每小时一次）
  • 系统资源利用率下降到某个阈值时检测——利用率骤降往往意味着大量进程被卡住

边界

有环 ≠ 死锁

这是本节最重要、也最容易错的一条，与 2.4.1 的”循环等待是必要不充分条件”是同一件事在图上的体现。

分两种情况：

每类资源只有一个实例时：图中有环 ⟺ 死锁。此时只要看出环，就能判定死锁。

每类资源有多个实例时：有环只是必要条件，不充分。图里画得出环，系统却未必死锁——因为环上某个资源可能还有空闲实例，或者环外有进程用完后会释放。

所以不能只靠”找环”来判断，必须老老实实化简。 这正是死锁定理用”不可完全简化”而不用”存在环路”来表述的原因。

一句话：环是嫌疑，化简才是定罪。

死锁定理 vs 银行家算法

两者都要”模拟进程逐个跑完”，极易混淆。判据是看的数据不同：

银行家算法资源分配图化简（死锁定理）
属于避免（事前）检测（事后）
依据的数据Need——按最大需求预判当前实际的请求边
回答这笔分配能不能批现在是否已经死锁
结论用词安全 / 不安全死锁 / 未死锁
需要预知未来吗需要（必须声明最大需求）不需要

最实用的区分：银行家算法是预言家，看的是”你将来还要多少”；化简是验尸官，看的是”你现在正在要什么”。

也正因为化简不需要预知最大需求，检测策略在工程上比避免策略实用得多——这就是数据库采用检测 + 回滚的原因。

三种解除方法的代价排序

方法代价实现复杂度
进程回退法最小最高（需检查点和历史信息）
资源剥夺法中（注意防饥饿）中
撤销进程法最大（工作全部作废）最低

注意代价与实现复杂度恰好相反：越省事的方法损失越大。这个反向关系常被用来出选择题。

检测与解除 vs 鸵鸟策略

两者都”允许死锁发生”，区别在于事后管不管：

  • 鸵鸟策略：发生了也不管，装作没看见。通用操作系统（Linux、Windows）的实际选择，理由是死锁概率极低而处理代价高。
  • 检测与解除：发生了要检测出来并主动拆开。数据库系统的标准做法，因为事务天然可回滚，牺牲代价小。

对照速查

资源分配图含义
圆圈进程结点
方框资源结点，框内圆点数 = 实例数
P → R请求边（进程在申请）
R → P分配边（已分给该进程）
死锁定理内容
表述S 为死锁状态 ⟺ S 的资源分配图不可完全简化
属于检测死锁
资源实例数有环意味着
每类只有 1 个有环 ⟺ 死锁
每类有多个有环是必要不充分条件
解除方法代价复杂度
资源剥夺法中中
撤销进程法最大最低
进程回退法最小最高

考点

  • 请求边 P→R、分配边 R→P 的方向
  • 资源分配图化简的步骤，以及”消去的是能被满足的进程”
  • 死锁定理属于检测方法；内容是”不可完全简化 ⟺ 死锁”
  • 有环 ≠ 死锁（多实例资源时），必须化简才能定论
  • 银行家算法看 Need，化简看当前请求边
  • 三种解除方法及其代价与复杂度反向的关系

链接

反向链接