死結與如何避免它

客氣的僵局

在這個章節裡你已經攢起一整箱工具：保護臨界區的互斥鎖、等待述詞成立的條件變數、用來計數資源的號誌，還在生產者消費者裡把它們組了起來。每一樣工具都讓某個執行緒等待，好讓另一個能往前走。死結就是當這種等待繞成一個封閉迴圈時發生的事：每個執行緒都在等，沒有人能前進，程式就這麼停住了——不當機、沒有錯誤訊息，只有一片寂靜。

想像兩個執行緒和兩把互斥鎖，叫它們 A 和 B。執行緒 1 先鎖住 A，然後伸手去拿 B。執行緒 2 在同一瞬間先鎖住 B，然後伸手去拿 A。現在執行緒 1 握著 A 等 B；執行緒 2 握著 B 等 A。誰也不會放掉手上那把，因為它們都在完成之前就被擋住了。它們會一直互相等待，直到你把行程砍掉。這就是最小、最純粹的死結了，而它不需要什麼花俏的東西——只要兩把鎖以相反的順序被取得就夠了。

四個條件

1971 年，Edward Coffman 和同事們寫下了四個條件：要讓死結有可能發生，這四個必須「同時」全部成立。把它們記熟就掌握了全局，因為要防住死結，你只要打破其中任何一個就好。它們值得背下來，因為它們把一個神祕的卡死，變成一張你真的能推理的檢查清單。

互斥——一項資源在任一時刻最多被一個執行緒持有。這正是鎖的全部目的，所以你很少放棄它；它只是讓其餘三個變得要緊的前提。
持有並等待——一個執行緒在阻塞著去取得另一把鎖的同時，仍緊抓著它已經拿到的鎖。執行緒 1 握著 A 等 B，講的就是這個。
不可搶占——一把鎖無法被強行奪走；持有者必須自願釋放它。系統不能伸手進去，從卡住的執行緒手裡沒收 B。
循環等待——存在一個執行緒的環，每一個都在等環裡下一個所持有的資源。兩個執行緒時，這個環就是「A 等 B、B 等 A」。

第四個條件，循環等待，是你在日常程式碼裡最能乾淨俐落攻擊的一個。把環打斷，無論執行緒怎麼交錯執行，死結都不可能發生。「替你的鎖訂一個全域順序」這單一概念，是多數程式設計師一輩子最常用得上的實用防禦，下一節整節都在講它。

鎖的排序：打斷那個環

規矩在這裡，而且簡單得漂亮：替你所有的鎖挑一個固定的全域順序，並讓每個執行緒「永遠」照那個順序去取得它們。如果 A 永遠排在 B 前面，那就沒有人會在握著 B 的時候去拿 A——於是那個既要「A 在 B 前」又要「B 在 A 前」的環，永遠閉合不起來。順序可以是任何一致的東西：鎖的位址、你指派的編號、字母名稱。重點是每一條程式路徑都同意這個順序。

/* deadlock-prone: order depends on which way you call it */
void transfer(Account *from, Account *to, long amt) {
    pthread_mutex_lock(&from->lock);
    pthread_mutex_lock(&to->lock);     /* <- can invert vs another thread */
    from->balance -= amt;
    to->balance   += amt;
    pthread_mutex_unlock(&to->lock);
    pthread_mutex_unlock(&from->lock);
}

/* fixed: always lock the lower address first */
void transfer(Account *from, Account *to, long amt) {
    Account *first  = from < to ? from : to;
    Account *second = from < to ? to   : from;
    pthread_mutex_lock(&first->lock);
    pthread_mutex_lock(&second->lock);
    from->balance -= amt;
    to->balance   += amt;
    pthread_mutex_unlock(&second->lock);
    pthread_mutex_unlock(&first->lock);
}

transfer(x, y) 和 transfer(y, x) 同時跑就是經典的死結；用位址排序把它消掉。

注意修好的版本保護了什麼：它沒有改變「哪些」鎖被持有，只改變了取得它們的順序。鎖不變式——也就是每把鎖守護什麼的那條規則——完全沒動。這就是為什麼鎖排序這麼受喜愛：它是純粹的紀律，執行時不花成本，而且你讀程式碼就能檢查它。困難之處在於隨著程式碼庫成長，要把順序維持一致，所以人們會把這個階層寫成文件，而有些除錯器和執行緒消毒器能標出順序不對的上鎖。

其他的出路，和幾個近親

鎖排序攻擊的是循環等待；trylock 加退避攻擊的是持有並等待。你也可以正面攻擊持有並等待：在一開始就以一個不可分割的步驟取得你會用到的「所有」鎖，拿不齊就不動手——不部分持有、不中途等待。對於簡單的共用計數器，你還能用不可分割操作例如比較並交換，徹底繞開互斥：一個不可分割的加法不取任何鎖，所以根本沒有鎖能死結。這些無鎖技巧很強大但很微妙，是留給後面章節的主題，不是免費的午餐。

有兩個近親值得點名，免得你把它們誤認成死結。飢餓是指一個執行緒技術上能跑，卻一直輸掉搶鎖的競賽、永遠進不去；整個系統有在前進，但那一個執行緒卡住了。優先權反轉更討厭：一個低優先權的執行緒握著高優先權執行緒需要的鎖，而一個中優先權執行緒（兩把鎖都不需要）霸佔著 CPU，讓那個低優先權的持有者一直沒機會釋放——於是高優先權的執行緒等在一個低優先權的身上。解法叫優先權繼承，暫時把持有者的優先權拉高。你會在真實的排程器裡再遇到優先權反轉和飢餓。

找出並承認死結

對死結在實務上怎麼現身要誠實：它通常是一張寫著「它就卡死了」的臭蟲回報。因為沒有東西當機，所以沒有核心傾印、也沒有錯誤碼可以用 grep 去找。最有用的單一動作，是把除錯器接上卡住的行程，印出每一個執行緒的回溯。你通常會看到兩個執行緒都停在 pthread_mutex_lock() 裡頭，各自只差一行就完成，各自等著對方握著的鎖——那個環就這樣現形了。這幅景象，你一旦看過，就再也認不錯。

兩個提醒讓你保持謙卑。第一，死結可能是個海森堡蟲：它依賴一個精確的交錯，所以它可能在正式環境一週才出現一次，在你的除錯器底下卻一次都不現身。那不是死結很聰明——是那個時序很罕見。第二，別把死結和「某個操作很慢」或「某個執行緒合法地阻塞在輸入上」搞混；下任何結論前先看回溯。整個章節誠實的總結是：鎖是必要的，而且它們很鋒利。四個條件確切告訴你鋒利的邊在哪，而鎖排序就是讓你不會割到自己的那個習慣。