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