Learning Objectives
- 手動排出兩把鎖的死結，說出誰在等誰
- 說明死結的四個必要條件，以及每種對策打破的是哪一個
- 在資源配置圖上判斷循環與死結，說明為什麼資源有多份時有循環不一定是死結
- 用固定的鎖順序修好死結，並用隨機執行驗證
- 用銀行家演算法判斷請求是否安全，並寫出安全性檢查
- 分辨死結、活結與飢餓
大家都拿著一半，等對方放手
銀行系統轉帳要同時鎖住兩個帳戶。A 轉給 B 的程式先鎖 A 再鎖 B，B 轉給 A 的程式先鎖 B 再鎖 A。寫起來都很合理，上線也跑得好好的，直到某一天兩筆轉帳剛好同時發生：
轉帳一：拿到 A，等 B
轉帳二：拿到 B，等 A
兩邊都不會放手，因為放手的程式碼在拿到第二把鎖之後。這就是死結（deadlock）。放到真正的 Linux 上，兩個執行緒各拿一把鎖，第一輪順序相同、第二輪順序相反，主執行緒等 1 秒後看結果：
same order : after 1 second, 2 of 2 threads finished
opposite order: after 1 second, 0 of 2 threads finished
在真正的 Linux 上實際執行的結果（Compiler Explorer 的 Linux x86-64 環境，gcc 13.3，2026-11-04）。
第二輪的兩個執行緒永遠不會結束，程式只能由主執行緒呼叫 exit 把整個行程收掉。這個行程沒有使用 CPU，也沒有錯誤訊息，就是不動了。實際系統上看到的症狀常常就是：服務還活著，但不再回應。
死結的四個必要條件
Coffman、Elphick 與 Shoshani 在 1971 年的論文 System Deadlocks 裡整理了死結發生的必要條件。四個同時成立才可能死結，所以只要打破一個就不會發生：
| 條件 | 意思 | 在剛才的程式裡 | 打破它的方法 |
|---|---|---|---|
| 互斥 | 資源一次只能給一個人 | mutex 本來就是 | 用不需要獨佔的設計，例如原子操作、不可變資料 |
| 持有並等待 | 拿著一個，還在等另一個 | 拿著 a 等 b | 一次把需要的全部拿到，拿不到就都不拿 |
| 不可搶佔 | 不能硬把資源從別人手上拿走 | 沒有人能拿走別人的鎖 | 拿不到就放掉手上的（pthread_mutex_trylock），等一下重來 |
| 循環等待 | 等待關係繞成一圈 | left 等 right，right 等 left | 固定上鎖順序，實務上最常用 |
剛才的修法打破的是第四個。如果所有人都先拿 a 再拿 b，就不可能有人拿著 b 等 a，圈繞不起來。
要注意這是必要條件：四個都成立也可能沒有卡住，你剛才隨機跑就看到了，要看時機。
有循環一定是死結嗎
每種資源只有一份時（例如 mutex）：有循環就是死結，反過來也對。
資源有好幾份時：有循環不一定是死結。剛才的 R1 有兩份，T1 和 T2 繞成一圈，但 R1 有另一份在 T3 手上，T3 沒有在等任何東西，它做完就會放手，T2 就等到了。所以偵測要用化簡法，不能只看圖上有沒有圈。
沒有循環一定沒有死結，這個方向永遠成立。
偵測與復原是實務上真的在用的策略，而不是只存在課本裡。MySQL 的 InnoDB 預設會偵測交易之間的死結，自動復原其中一筆（通常挑改動列數少的交易），應用程式收到錯誤後再重試。這對資料庫行得通，因為交易本來就設計成可以整筆撤銷。作業系統的一般鎖就不一樣了，硬把一個執行緒砍掉，它改到一半的資料沒有人收拾。
實務上最常用的是鎖順序
大部分真實系統就是靠約定上鎖順序來避免死結，把順序寫進文件和註解。Linux 核心的 mm/rmap.c 開頭就有一段「Lock ordering in mm」註解，列出哪把鎖要在哪把之前拿。
轉帳這種「兩把鎖是動態決定的」情況，可以依帳戶編號或位址排序，一律先鎖小的：
void transfer(int from, int to, long amount) {
int first = from < to ? from : to; // ?: 是條件運算子：條件成立取前者，否則取後者
int second = from < to ? to : from;
pthread_mutex_lock(&account_lock[first]);
pthread_mutex_lock(&account_lock[second]);
// …
}
光靠人守約定還是會出錯，所以也有工具檢查。Linux 核心的 lockdep 會在執行時記錄鎖之間的先後關係，發現循環就警告，即使死結這次沒有真的發生。使用者程式可以用 ThreadSanitizer，它也能回報鎖順序不一致。
其他常見的原則：
- 持有鎖的時候，不要呼叫不知道裡面在做什麼的函數，例如別人傳進來的回呼函數，它可能會去拿另一把鎖。
- 鎖越少、持有越短，順序問題就越少。 能用一把鎖解決的，就不要用兩把。
避免：銀行家演算法
預防是從設計上排除死結。避免（avoidance）的想法不同：系統每次分配資源之前先算一下，如果給了可能走向死結，就先不給。
代表作是 Dijkstra 的銀行家演算法（手稿 EWD 123），比喻是銀行放款：資金有限，每位客戶事先說好最多要借多少，保證拿到上限就會還。銀行每筆放款前先想，給了之後，還有沒有辦法讓所有人都完成？
- Allocation：現在手上有多少。
- Max：事先宣告最多要多少。
- Need = Max − Allocation：還可能再要多少。
- Available：系統還剩多少。
安全狀態：存在一個順序，讓所有行程依序拿到需要的、做完、放手。這個順序叫安全序列。
檢查的方法：找一個 Need 不超過目前可用量的行程，假設它做完，把它手上的全部加回可用量，重複到全部做完（安全）或找不到人（不安全）。
不安全不等於死結：不安全只代表最壞情況下可能卡住，大家實際上不一定會要到上限。銀行家是保守的，所以它有時候會拒絕一個其實沒事的請求。
逐步看安全性檢查
同樣的資料，用 Python 寫出來。每找到一個做得完的行程就 break，while 再從第 0 個開始找。答案會和小工具「自動尋找」的結果一樣。
實作：寫出安全性檢查
把 safe_order 補完。規則和小工具一樣：每一輪從編號最小的開始找，找到做得完的就做完，再從頭找。
all(need[p][r] <= work[r] for r in range(len(work))) 可以檢查一個行程需要的每一項是否都不超過 work。
四種策略，還有兩個長得很像的問題
面對死結的策略：
| 策略 | 做法 | 代價 | 用在哪 |
|---|---|---|---|
| 預防 | 設計上打破一個條件（通常是鎖順序） | 寫程式要守規矩 | 一般程式、作業系統核心 |
| 避免 | 銀行家：每次分配前算安全性 | 要事先知道上限，每次都要算，還可能拒絕其實沒事的請求 | 一般作業系統幾乎不用，適合需求可預知的專用系統 |
| 偵測與復原 | 讓它發生，定期找循環，砍掉或撤銷一個 | 要能撤銷 | 資料庫 |
| 不處理 | 當作不會發生，發生了就重開 | 使用者要忍受 | 作業系統對使用者程式的鎖，大多就是這樣 |
Linux 不會替你檢查 pthread_mutex 有沒有死結，預設型別的 mutex 就是這樣卡著。為什麼避免用得少？因為一般程式說不出自己「最多要幾把鎖、幾 MB 記憶體」，而且資源一直在變。
死結、活結、飢餓長得很像，判斷方法不同：
| 有沒有在跑 | 有沒有進展 | 例子 | |
|---|---|---|---|
| 死結（deadlock） | 都在睡 | 沒有 | 拿著一把等另一把 |
| 活結（livelock） | 都在跑，CPU 很忙 | 沒有 | 拿不到就放手、馬上重試，兩個人一直同步地互相禮讓 |
| 飢餓（starvation） | 有人在跑 | 系統有，只是某個人一直輪不到 | 上一課的寫者 |
活結最有趣的地方是它常常是修死結修出來的：用 pthread_mutex_trylock 打破「不可搶佔」後，兩個人可能拿了又放、放了又拿。常見的解法是加入隨機的等待時間，讓兩邊錯開（網路的 CSMA/CD 碰撞退避也是這個想法）。
確認一下
下面兩個函數同時在不同執行緒跑，會怎樣？
f: lock(a); lock(b); … unlock(b); unlock(a); g: lock(a); lock(b); … unlock(a); unlock(b);
程式約定：每個執行緒開始工作之前，一次要齊所有需要的資源，要不到就什麼都不拿、等一下再試。這打破的是哪個條件？
一張資源配置圖上有循環，每種資源都只有一份。可以判定什麼？
可用量 [1, 0]。P0 的 Allocation [1, 1]、Need [1, 1]；P1 的 Allocation [0, 1]、Need [1, 0]。現在安全嗎？
銀行家演算法判定一個狀態「不安全」。這代表什麼？
兩個執行緒的 CPU 使用率都接近 100%，但工作一直沒有完成，程式裡有 trylock 失敗就放手重試的迴圈。最可能是什麼？
重點整理
- 死結：一群人都拿著東西等別人放手。一旦形成就不會自己恢復；沒形成時看起來完全正常，所以跑過幾次都對不算數。
- 四個必要條件：互斥、持有並等待、不可搶佔、循環等待。打破一個就不會死結。
- 資源配置圖上，每種資源只有一份時有循環就是死結；有多份時要用化簡法判斷。
- 實務上最常用的是固定上鎖順序，打破循環等待。
- 銀行家演算法在分配前檢查是否還有安全序列。它要事先知道上限，一般作業系統幾乎不用，但「安全狀態」是很好的思考工具。
- 資料庫走偵測與復原；一般作業系統對 mutex 不處理，靠你寫對。
- 死結是都睡著、活結是都在跑但沒進展、飢餓是別人有進展只有你輪不到。
想再深入，可以讀免費公開的教科書 OSTEP 第 32 章 Concurrency Bugs。
並行的主題到這裡告一段落。下一課換到記憶體：程式看到的位址空間到底長什麼樣。