Featured image of post 当所有人都在等待对方时，为什么一切都会停止：死锁（Deadlock）的数学理论、银行家算法与活锁防治
计算机科学

当所有人都在等待对方时，为什么一切都会停止：死锁（Deadlock）的数学理论、银行家算法与活锁防治

全面剖析并发计算中的死锁理论：迪杰斯特拉哲学家就餐问题、科夫曼四条件（1971）、霍尔特资源分配图（RAG）的单实例与多实例环路定理、全序加锁预防定理的反证法证明、迪杰斯特拉银行家算法 5×3 矩阵完整推演、数据库等待图（WFG）与分布式 Wait-Die / Wound-Wait 协议、鸵鸟算法，以及死锁、活锁与饥饿的本质对比。

1. 引言：哲学家就餐问题与科夫曼（Coffman）死锁四条件

1965年，荷兰计算机科学家艾兹赫尔·迪杰斯特拉（Edsger W. Dijkstra）提出了著名的“哲学家就餐问题（Dining Philosophers Problem）”：五位哲学家 \(P_0 \dots P_4\) 围坐圆桌，每人左右两侧各有一把叉子 \(F_i\) 与 \(F_{(i+1)\bmod 5}\)（共5把叉子），必须同时拿起左右两把叉子才能进餐。如果五位哲学家在同一瞬间感到饥饿，并各自拿起左手的叉子 \(F_i\)，那么每个人都会握着左叉永远等待邻居释放右叉——没有任何硬件故障，整个系统却陷入了永久停滞，这便是死锁（Deadlock）。

形式化地说，进程集合 \(D \subseteq \mathcal{P}\)（\(D \neq \emptyset\)）处于死锁状态，当且仅当 \(D\) 中的每一个进程 \(P_i \in D\) 都在等待某个只能由同一集合 \(D\) 中的其他进程 \(P_j \in D\) 触发的事件（如释放锁资源）。

1971年，Edward G. Coffman Jr. 等人证明了资源死锁发生必须同时满足四个必要条件（科夫曼条件）：

  1. 互斥（Mutual Exclusion）：至少有一种资源以排他（非共享）模式被单个进程独占。
  2. 占有并等待（Hold and Wait）：进程在已经持有至少一个资源的同时，阻塞等待获取其他进程持有的额外资源。
  3. 不可抢占（No Preemption）：已分配给进程的资源不能被操作系统或他者强行剥夺，只能由持有者主动释放。
  4. 循环等待（Circular Wait）：存在闭合的等待链 \(\{P_0, P_1, \dots, P_{k-1}\}\)，使得 \(P_i\) 等待 \(P_{(i+1)\bmod k}\) 持有的资源。

由于这四个条件均为必要条件，只要在系统设计中逻辑否定其中任意一个条件，死锁在数学上就 \(100\%\) 不可能发生。

2. 资源分配图（RAG）与环路定理（Holt, 1972）

1972年，Richard C. Holt 引入了有向二分图——资源分配图（Resource Allocation Graph, RAG） \(G = (V, E)\)，其中顶点集 \(V = \mathcal{P} \cup \mathcal{R}\)（进程顶点 \(P_i\) 与资源类型顶点 \(R_j\)，每个 \(R_j\) 含 \(W_j \ge 1\) 个实例），有向边分为请求边 \(P_i \to R_j\)（等待分配）与分配边 \(R_j \to P_i\)（已持有实例）。

关于 RAG 中的有向环（Directed Cycle）与死锁的关系，存在三大核心定理：

  • 定理 1（无环必无死锁）：若 RAG 中不存在有向环（即为 DAG），则系统中绝无死锁。
  • 定理 2（单实例充要定理）：若所有资源类型均只有一个实例（\(\forall j, W_j = 1\)），则存在有向环 \(\iff\) 发生死锁（充分必要条件）。
  • 定理 3（多实例非充分定理）：若某资源类型具有多个实例（\(\exists j, W_j > 1\)），则有向环只是死锁的必要条件而非充分条件！
  flowchart TD
    subgraph RAG_Single["情况 A：单实例资源系 (有向环 <==> 必然死锁)"]
        PA1(("P1 (阻塞)")) -->|"请求"| RA1["R1 (1 个实例: ●)"]
        RA1 -->|"已分配"| PA2(("P2 (阻塞)"))
        PA2 -->|"请求"| RA2["R2 (1 个实例: ●)"]
        RA2 -->|"已分配"| PA1
    end

    subgraph RAG_Multi["情况 B：多实例资源系 (存在环 P1->R1->P3->R2->P1，但并未死锁！)"]
        PB1(("P1 (阻塞)")) -->|"请求"| RB1["R1 (2 个实例: ●●)"]
        RB1 -->|"分配实例 #1"| PB3(("P3 (阻塞)"))
        PB3 -->|"请求"| RB2["R2 (2 个实例: ●●)"]
        RB2 -->|"分配实例 #1"| PB1
        RB1 -->|"分配实例 #2"| PB2(("P2 (运行中: 无请求边！)"))
        RB2 -->|"分配实例 #2"| PB4(("P4 (运行中: 无请求边！)"))
    end

在情况 B 中，虽然存在环 \(P_1 \to R_1 \to P_3 \to R_2 \to P_1\)，但持有第二个实例的 \(P_2\) 与 \(P_4\) 出度为 \(0\)（汇点，正在运行），它们执行完毕释放 \(R_1, R_2\) 后即可立即解开环路！

3. 策略1（死锁预防）：全序加锁规则的反证法证明

在操作系统内核（如 Linux lockdep）与多线程工程中，打破第4条件（循环等待）的黄金法则是全局锁排序（Total Lock Ordering）：为所有锁赋予唯一序号 \(\phi: \mathcal{L} \to \mathbb{N}\)，强制要求任何线程在持有锁集 \(\mathcal{H}\) 时，只能请求序号严格更大的新锁：

\[\forall L_{\text{held}} \in \mathcal{H}: \quad \phi(L_{\text{held}}) < \phi(L_{\text{new}})\]

【反证法证明】：假设系统发生了长度为 \(k \ge 2\) 的循环等待环 \(\{P_0, P_1, \dots, P_{k-1}\}\)，其中 \(P_i\) 持有锁 \(L_i\) 并等待 \(P_{(i+1)\bmod k}\) 持有的锁 \(L_{(i+1)\bmod k}\)。由于每个线程均遵守全序加锁规则，必有：

\[\phi(L_0) < \phi(L_1) < \phi(L_2) < \cdots < \phi(L_{k-1}) < \phi(L_0) \implies \phi(L_0) < \phi(L_0)\]

自然数不可能严格小于自身，矛盾（\(\bot\)）！因此在全序加锁规则下（如银行转账始终先锁 ID 较小的账户，或让哲学家 \(P_4\) 先拿右叉 \(F_0\) 再拿左叉 \(F_4\)），循环等待在数学上绝不可能存在。\(\blacksquare\)

4. 策略2（死锁避免）：迪杰斯特拉银行家算法与 5×3 矩阵推演

当无法静态固定加锁顺序时，迪杰斯特拉银行家算法（Banker’s Algorithm, 1965 / Habermann, 1969）要求进程预先申报最大需求矩阵 \(\mathbf{Max}\)，并在每次分配前通过复杂度为 \(O(m \cdot n^2)\) 的安全性算法检验系统是否仍存在至少一条安全序列（Safe Sequence）（注意：\(\text{死锁状态} \subsetneq \text{不安全状态}\)，不安全状态并非已死锁，而是存在未来可能死锁的风险）。

设系统有 \(n=5\) 个进程 \(\{P_0 \dots P_4\}\)，3 类资源 \(\mathbf{Total} = (A=10, B=5, C=7)\)，时刻 \(t_0\) 状态如下表所示，当前剩余可用资源为 \(\mathbf{Available} = (10,5,7) - (7,2,5) = \mathbf{(3, 3, 2)}\)：

进程已分配 \(\mathbf{Allocation}\) \((A,B,C)\)最大需求 \(\mathbf{Max}\) \((A,B,C)\)剩余需求 \(\mathbf{Need} = \mathbf{Max} - \mathbf{Allocation}\)安全序列推演（初始 \(\mathbf{Work} = (3,3,2)\)）
\(P_0\)\((0, 1, 0)\)\((7, 5, 3)\)\((7, 4, 3)\)第 4 步满足：\((7,4,3) \le (7,4,5) \to \mathbf{Work}=(7,5,5)\)
\(P_1\)\((2, 0, 0)\)\((3, 2, 2)\)\((1, 2, 2)\)第 1 步满足：\((1,2,2) \le (3,3,2) \to \mathbf{Work}=(5,3,2)\)
\(P_2\)\((3, 0, 2)\)\((9, 0, 2)\)\((6, 0, 0)\)第 5 步满足：\((6,0,0) \le (7,5,5) \to \mathbf{Work}=(10,5,7)\)
\(P_3\)\((2, 1, 1)\)\((2, 2, 2)\)\((0, 1, 1)\)第 2 步满足：\((0,1,1) \le (5,3,2) \to \mathbf{Work}=(7,4,3)\)
\(P_4\)\((0, 0, 2)\)\((4, 3, 3)\)\((4, 3, 1)\)第 3 步满足：\((4,3,1) \le (7,4,3) \to \mathbf{Work}=(7,4,5)\)

由于存在安全序列 \(\langle P_1, P_3, P_4, P_0, P_2 \rangle\)，状态 \(t_0\) 是安全状态。若此时 \(P_1\) 请求 \((1,0,2)\)，试分配后 \(\mathbf{Available}=(2,3,0)\) 仍满足 \(\mathbf{Need}_1=(0,2,0)\)，立即批准；但若紧接着 \(P_0\) 请求 \((0,2,0)\)，试分配后 \(\mathbf{Available}=(2,1,0)\) 将导致所有进程的 \(\mathbf{Need}\) 均无法满足（进入不安全状态），银行家算法会立即回滚并阻塞 \(P_0\)！

5. 策略3 & 4（检测恢复与鸵鸟算法）以及死锁 vs. 活锁 vs. 饥饿

在关系型数据库（RDBMS）中，由于 SQL 语句动态到达，系统采用等待图（Wait-For Graph, WFG）通过 \(O(|V|+|E|)\) 的 DFS 寻找环路（MySQL InnoDB 阻塞时立即检测并回滚 Undo 量最小的牺牲者；PostgreSQL 则睡眠等待 deadlock_timeout = 1s 后再检测）。而在分布式数据库（如 Google Spanner）中，则采用基于启动时间戳 \(\text{TS}(T_i)\)（越小越年长）的 Wait-Die（非抢占）与 Wound-Wait（抢占，年长者直接击伤回滚年轻者，重启次数更少）协议，且被中止事务重试时必须保留原时间戳以彻底防止饥饿。至于罕见的操作系统用户态表项耗尽，UNIX/Windows 则采用鸵鸟算法（Ostrich Algorithm）直接忽略，以免日常系统调用背负沉重的检测开销。

  flowchart TD
    Req["分布式事务 Ti 请求被 Tj 持有的锁"] --> Cmp{"比较启动时间戳: TS(Ti) < TS(Tj) ？<br/>(请求方 Ti 是否比持有方 Tj 更年长？)"}
    Cmp -->|"是: Ti 更年长 (Older)"| WD1["【Wait-Die (非抢占)】: 年长的 Ti 等待年轻的 Tj (老 -> 少)<br/>【Wound-Wait (抢占)】: 年长的 Ti 击伤回滚 Tj 并夺锁！"]
    Cmp -->|"否: Ti 更年轻 (Younger)"| WD2["【Wait-Die (非抢占)】: 年轻的 Ti 自杀中止 (保留原 TS 重试)<br/>【Wound-Wait (抢占)】: 年轻的 Ti 安静等待年长的 Tj (少 -> 老)"]

最后，在并发系统的活性故障（Liveness Failures）诊断中，必须严格区分死锁、活锁（Livelock）与饥饿（Starvation）：

诊断维度死锁 (Deadlock)活锁 (Livelock)饥饿 (Starvation)
核心机制與定义阻塞线程形成循环等待链，彼此等待对方释放资源线程为避开死锁而对称地不断执行 trylock 失败、释放并立即重试（走廊礼让死循环）系统整体正常推进，但特定低优先级线程永远抢不到资源
OS 线程状态与 CPU 占用SLEEPING / BLOCKED（CPU 占用 \(0\%\)）RUNNING（CPU 飙升至 \(100\%\) 空转，有效推进为 0）等待队列中长期停滞（受害者 CPU 为 \(0\%\)）
根本工程解药全序加锁（\(\phi(L_1)<\phi(L_2)\)）、银行家算法、WFG 回滚引入随机指数退避（Randomized Exponential Backoff with Jitter）打破时间对称性优先级老化（Aging）、保留原时间戳、公平 FIFO 队列锁（MCS 锁）
comments powered by Disqus