窄橋上的對峙
在上一個階梯，你學會了讓執行緒輪流：一個號誌或一把鎖，會對某個臨界區間保證 互斥，於是它們之中沒有任何兩條會弄壞共用資料。那治好了一種病，卻悄悄替另一種病開了門。一旦一條執行緒能被迫去「等」某個資源，兩條執行緒就可能彼此互等——永遠等下去。想像一座單線道的橋，兩端各有一輛車開上來。它們在橋中央相遇，鼻子頂著鼻子。誰都過不去。誰也不肯倒車，因為各自都在等對方先退。沒有任何東西壞掉；兩位駕駛的行為都「正確」。車流只是凍結了，而且會一直凍結，直到某個規則之外的力量介入為止。
那座橋就是一個 死結（deadlock）：一組行程，其中「每一個」成員都被擋住，等著另一個同組成員正握著、且永遠不會釋放的某個資源。關鍵字是「每一個」。死結不是「有東西變慢了」，也不是「有東西卡了一下」；它是一個彼此互等的封閉圓圈，這群成員靠自己永遠出不來。因為每個行程都握著鄰居需要的東西、又需要鄰居握著的東西，沒有任何成員能往前進，於是沒有人會釋放它的資源，於是這場等待是永久的。系統並沒有當機——它甚至可說是異常地平靜——但它的一部分死了。記得前面階梯說過：一個行程是一個正在執行的程式，而不是程式檔案本身；這裡是好幾個這樣正在執行的程式，把彼此卡得死死的。
資源模型：請求、持有、釋放
要精確地推理死結，我們需要一套乾淨的方式來談論行程互相爭奪的那些東西。系統資源模型就是這套詞彙。一個「資源」是行程在能往前進之前必須取得、事後又必須歸還的任何東西：一台印表機、一把檔案鎖、固定大小緩衝區裡的一格、一塊記憶體、一筆資料庫列、一把互斥鎖。核心——也就是前面階梯說的那位大樓管理員——負責把這些發出去。每個行程對每個資源都玩同樣的三步驟遊戲：請求（request）它（若不可用就被擋住）、取得後使用（use）它、用完再釋放（release）它。死結這種病，完全活在這個「請求、使用、釋放」的循環裡面。
還有一個重要的區分：有些資源可重複使用，有些則用一次就消耗掉；而同一種資源類型可能有好幾個一模一樣的「實例（instance）」。一台印表機是「印表機」這個資源類型的一個實例；一池三台相同的印表機，是一種類型、三個實例，而一個只要求「一台印表機」的行程，拿到哪一台都開心。這個實例數量在後面會極其重要——有多個實例時，行程有時能靠等待繞出一個近乎死結的局面；而只有單一實例時，一個封閉的互等圓圈總是致命的。在這第一篇導覽裡，請想像單一實例的資源（一台印表機、一把特定的鎖），好讓危險呈現得最赤裸。
四個必要條件
整個階梯的核心，是一個漂亮而銳利的結論，通常歸功於 Coffman：唯有當四個必要條件「同時」全部成立時，死結才可能發生。它們是「必要」而非「充分」——四個全在，意思是死結「有可能」發生，而不是它已經發生了——但反過來說的那一面才是強大的地方。只要這四個之中少了任何一個，死結就不可能成立。光這一個事實，就是整個領域的萬能鑰匙：接下來幾篇導覽裡的每一種預防策略，骨子裡都是一套「確保這四個之中有一個永遠不可能為真」的辦法。
第一個條件是互斥：至少有一個資源以不可共享的方式被持有，所以同一時間只有一個行程能用它。如果一台印表機能被所有人同時使用，就沒什麼好等的了。第二個條件是持有並等待：一個行程在請求另一個資源的同時，正握著至少一個資源，伸手要拿更多時，卻不肯放掉手上已有的。第三個條件是不可搶占：資源無法從持有它的行程手中被強行奪走；它只會在那個行程自願選擇時，才被釋放。第四個條件是循環等待：存在一條封閉的行程鏈，P1 等著 P2 握著的某物、P2 等著 P3 握著的某物、依此類推，最後一個等著 P1 握著的某物——就是那場窄橋對峙，推廣到任意數量的車。
Two locks, A and B. Both threads run, interleaved.
Thread 1 Thread 2
-------- --------
lock(A) [holds A]
lock(B) [holds B]
lock(B) ... waits for B lock(A) ... waits for A
| |
+--- waits for T2 -------+
+------ waits for T1 ----+ <-- circular wait
Both block forever. All four conditions hold:
mutual exclusion (locks) hold-and-wait (each holds one)
no preemption (cannot steal) circular wait (the loop above)為什麼是「四個一起」
本階梯最重要的一個觀念是：這四個條件是「且（AND）」，不是「或（OR）」。一個死結需要互斥「且」持有並等待「且」不可搶占「且」循環等待，在同一瞬間全部成立。這是大好消息，因為它意味著我們不必把四個全部擊敗才能保持安全——打掉任何一個就夠了。用那座橋再走一遍：如果橋有兩線道（沒有互斥），就不會對峙。如果開上橋的駕駛必須先「預訂」整段過橋路、且在整條路淨空前都不會動（沒有持有並等待），就不會對峙。如果有拖吊車能把一輛車吊走（允許搶占），就不會對峙。如果規定車流一次只能往一個方向走（沒有循環等待），就不會對峙。每一種修法都是獨立的，而且任一種單獨就夠了。
這也解釋了為什麼死結在實務上感覺如此罕見、如此隨機。四個條件必須同時齊聚，「而且」執行緒還得恰好交錯到把那個圓圈關起來的那一步。把上面那個雙鎖例子跑一萬次，大多數次都會順利通過，因為執行緒一通常在執行緒二都還沒開始之前，就把兩把鎖都抓到手了。只有那種倒楣的交錯——各自在伸手拿第二把鎖之前，都先抓到了自己的第一把——才會把圓圈喀地關上。這種間歇性，正是我們在競爭條件那裡遇過的那種殘酷：臭蟲是真的、總在潛伏，但它只在特定時序下現身，於是它能躲過每一次測試，然後在正式環境裡發作。
與這份危險共處的四種辦法
有了這四個條件，作業系統面對死結就剛好有四種策略性的姿態，而本階梯接下來正是「一種姿態、一篇導覽」。第一種是 預防（prevention）：在結構上保證四個條件中有一個永遠不可能成立——例如，強制一套全域的上鎖順序，讓循環等待在數學上不可能發生。第二種是 避免（avoidance）：原則上允許這些條件存在，但在每一次請求時，拒絕任何「可能導向危險」的核准，永遠停留在一個可被證明的安全狀態裡——這正是銀行家演算法在做的事，像一位銀行家，他絕不會借出太多，以致某位客戶可能落到無法完成的地步。
第三種姿態是 偵測與復原（detection and recovery）：讓死結照樣發生，但定期掃描一張等待圖找環，一旦找到，就把它打破——靠中止某個行程，或強行收回某個資源。第四種，也是幾乎每一個真實的通用作業系統實際採取的，是 鴕鳥演算法（ostrich algorithm）：把頭埋進沙裡，徹底無視這個問題。這聽起來像玩笑，卻是一個清醒的工程決定。在每一次請求都跑銀行家演算法、或不停地掃描一張圖，都要花掉真實的時間，還要求行程預先宣告它們的最大需求——這些假設，根本不適合死結本就罕見的一般桌機。所以 Linux、Windows、macOS 多半什麼都不做，而在那難得一次的當機時，由你這個人去重開機或砍掉肇事者。那就是鴕鳥，而它是務實的預設選項。