死锁的检测与解除 · 融合风（象牙 + Obsidian 入口）

速查

检测与解除是事后策略：允许死锁发生，但提供检测与恢复机制。核心判据是死锁定理——资源分配图不可完全化简 $\iff$ 死锁。单实例资源有环 $\iff$ 死锁。

核心概念 ▾

死锁检测与解除是一种事后策略：不预防也不避免，允许死锁发生，但提供检测和恢复机制。

1. 资源分配图（RAG）化简

节点：进程（圆圈）、资源（方框，圆点表示实例）。
边：请求边（$P \to R$）、分配边（$R \to P$）。
化简步骤：找一个请求都能满足的进程，移除其所有边，重复。
所有边都能移除 → 图可完全化简 → 无死锁；不能完全化简 → 有死锁。

死锁定理资源分配图不可完全化简 $\iff$ 系统处于死锁状态。

2. 单 / 多实例

每类资源单实例时：有环 $\iff$ 死锁（充要条件）。
每类资源多实例时：有环是死锁的必要非充分条件。

3. 检测时机

每次资源请求时检测（开销大但及时）、周期性检测（开销较小但延迟）、CPU 利用率低于阈值时检测（启发式）。

4. 解除方法

终止进程：终止所有死锁进程（简单但代价大）或逐个终止直到死锁解除。
资源抢占：从死锁进程抢占资源分配给其他进程。
回滚：将进程回滚到某个安全状态重新执行。

关键性质 ▾

检测方法	适用场景	时间复杂度
资源分配图化简	单实例资源	$O(n^2)$
等待图检测	单实例资源	$O(n^2)$
类银行家算法	多实例资源	$O(m \times n^2)$

解除方法	优点	缺点
终止所有死锁进程	彻底	代价最大
逐个终止	代价较小	可能需要多次检测
资源抢占	保持进程运行	可能导致饥饿或回滚

常见考法 ▾

考法	解题套路
资源分配图化简	找请求可满足的进程 → 移除边 → 重复 → 判断是否完全化简
单实例有环	有环 $\iff$ 死锁（充要条件）
多实例有环	有环是必要非充分条件（有环可能没死锁）
死锁定理	不可完全化简 $\iff$ 死锁
解除方法选择	考虑优先级、执行时间、资源占用量

易错点 ▾

必记

⚠️ 每类资源单实例时：有环 $\iff$ 死锁；多实例时：有环只是必要条件。
⚠️ 资源分配图可完全化简 → 无死锁；不可完全化简 → 有死锁。
⚠️ 化简时找的是「请求都能满足」的进程（$Need \leq Available$），不是任意进程。
⚠️ 资源抢占需要保存和恢复进程状态，否则无法正确继续执行。

记忆卡片 ▾

死锁定理是什么？

资源分配图不可完全化简 $\iff$ 系统处于死锁状态。

单实例资源有环？

有环 $\iff$ 死锁（充要条件）。

多实例资源有环？

有环是死锁的必要非充分条件。

死锁解除两种主要方法？

终止进程（全部或逐个）、资源抢占（需保存/恢复状态）。

交互动画 · 资源分配图化简 ▾

P3 已持有一个 R 实例，剩余请求可满足 —— 可先化简 P3。

点击「化简一步」移除可满足进程的边。

示意图：P3 请求可满足 → 移除其边；随后 P1、P2 相继可化简 → 图可完全化简 → 无死锁。

相关知识点

deadlock deadlock-prevention deadlock-avoidance

↑ 以上为站内 HTML 相对链接（纯网页可浏览）；本页右上「在 Obsidian 中打开」跳回源笔记。