讓死結變得不可能的兩條路
在第 1 篇導覽裡，你認識了死結——一群行程各自永遠凍結，每一個都握著環上下一個正在等的資源。關鍵事實是：它需要四個必要條件同時成立——互斥、持有並等待、不可搶佔、循環等待。第 2 篇導覽接著教你畫出資源分配圖，並把圖中的環讀成警訊。這篇導覽要回答那個顯而易見的下一個問題：知道了這一切，我們究竟怎麼真正阻止死結發生？
這裡有兩種截然不同的態度，值得分清楚。預防是粗直、結構性的做法：把系統設計成四個條件中的某一個永遠無法成立，就這麼絕。只要桌子的一隻腳被鋸掉，桌子就立不起來——死結在結構上變得不可能，完全不需要執行期檢查。避免則溫和而聰明：原則上讓四個條件都可能成立，但讓核心在每一個請求一抵達的當下就審視它，唯有「准了它也不會把系統帶向日後的麻煩」時才核准。預防說：壓根別蓋這個陷阱；避免說：陷阱是存在的，所以每一步都繞著它走。
預防：鋸掉桌子的一隻腳
死結預防的做法，是保證四個條件中至少有一個永遠無法被滿足。誠實的難處在於，有些腳遠比其他腳容易鋸掉。互斥通常沒得商量：一臺印表機或一把鎖，真的就是同一時間只能被一個行程持有，你沒辦法把它願走。所以預防幾乎總是瞄準另外三個之一，而每一個選擇都要付出實實在在的代價。
攻擊「持有並等待」的辦法，是禁止一個行程在等另一個資源時還握著某個資源：要它把可能用到的一切一次全部、預先一口氣申請，等拿齊整套之後才開始跑。沒有部分持有，就沒有等待者的環能形成。代價是利用率很差——一個只在最尾端才需要磁帶機的行程，卻得從一開始就抓住它、整段時間死坐其上——再加上可能的飢餓：一個需要熱門組合的行程，也許永遠等不到那些資源剛好同時都空著。改成攻擊「不可搶佔」：若一個握著若干資源的行程，去要一個拿不到的資源，就強迫它把手上所有東西全交出來、稍後重試。這對「狀態易於存取與還原」的資源行得通，比如 CPU 暫存器或記憶體分頁，但對印到一半的印表機、或正在寫入的檔案，就毫無辦法。
最乾淨好鋸的一隻腳，通常是循環等待，而手法很漂亮：對每一種資源類型強加一個單一的全域順序——把它們編號 1、2、3 等等——並規定一個行程只能依遞增順序去申請資源。如果你握著資源 5，你可以去要 6 或 9，卻絕不能要 2。為什麼這能殺掉環？循環等待需要某個行程握著高編號資源、同時等著另一個行程握著的低編號資源，但這個順序規則恰恰禁止了那種往回的伸手——所以環永遠合不攏。這就是你在真實、重度用鎖的程式碼裡會真正看到的預防方案：一套寫進文件的「上鎖順序」慣例，每個開發者都得用手親自遵守。
避免：待在安全狀態裡
預防之所以霸道，是因為它永久地限制了行程「可以怎麼要」。死結避免則保持彈性，做法是在每一個請求的當下問一個更銳利的問題：如果我准了這個，我是否仍能保證每個人最終都跑得完？要回答它，避免需要一條預防不需要的額外資訊：每個行程必須事先宣告它在整個生命週期裡，對每種資源可能用到的最大數量。有了這個最大宣告值，核心就能往前看。
核心概念是安全狀態。一個狀態是安全的，若存在至少一種把所有行程排序的方式——稱之為安全序列——使得每個行程依序輪到時，都能僅憑「目前空閒的資源，加上序列中較早的行程跑完後會釋放的資源」，被滿足它可能還會提出的一切需求。想像在一臺咖啡機前排隊，咖啡師能證明：我用現在空著的東西就能服務完客人 A，A 一走、把杯子還回來，我手上的量就夠服務完 B，然後 C，一路到底。只要存在這樣一個「跑完的順序」，就沒有人會被永久卡住。所以一個安全狀態是一個承諾：從這裡開始，死結在可證明的意義上仍然是可避免的。
銀行家演算法，一步一步來
最有名的避免方案是銀行家演算法，由 Dijkstra 以一位銀行家命名——這位銀行家只在「即使最壞情況下，每位客戶仍能被付足他的全部信用額度、並還清貸款」時才肯借出現金。它追蹤四張表：每種資源類型的總可用量（Available）、每個行程宣告它可能需要的最大量（Max）、每個行程目前已分配到的量（Allocation），以及需求量（Need，就是 Max 減 Allocation）——每個行程還可能再要的上限。當一個請求抵達，銀行家先假裝准了它，再對結果的那些表跑一次安全檢查。若仍安全，這次核准就成真；若不安全，請求被駁回，提出者等待。
- 用一份草稿副本開始安全檢查：一個等於「此刻 Available」的工作向量 Work，並把每個行程都標記為「尚未完成」。
- 找出任何「尚未完成」、且整份剩餘 Need 都小於或等於 Work 的行程——意思是我們用現有空閒的量，就能把它完全滿足。
- 假裝那個行程跑到完成、把一切都交還回來：把它的 Allocation 加進 Work，再把它標記為「已完成」。可用量實質上變多了。
- 重複步驟 2 和 3，再次輪過所有行程，因為剛交還回來的資源，也許現在就能解開一個片刻前還塞不下的行程。
- 若每個行程最終都被標記為「已完成」，就存在一個安全序列，所以狀態是安全的。若卡住、有些行程永遠無法被滿足，狀態就是不安全的——於是原本那個請求必須被拒絕。
Resource type: 12 tape drives total. Need = Max - Allocation
Process Max Allocation Need
P0 10 5 5
P1 4 2 2
P2 9 2 7
-------
held = 9 -> Available = 12 - 9 = 3 free
Safety check (Work starts at 3):
Work=3 -> P1 Need 2 <= 3 : run P1, give back 2 -> Work = 5
Work=5 -> P0 Need 5 <= 5 : run P0, give back 5 -> Work = 10
Work=10 -> P2 Need 7 <= 10 : run P2, give back 2 -> Work = 12
All finished. Safe sequence found: <P1, P0, P2> -> SAFE.為什麼幾乎沒人真的去跑它
銀行家演算法很美，而且它是少數你能在數學上證明「系統永不死結」的情形之一。所以這裡有個讓每個學生都意外的誠實轉折：像 Linux、Windows、macOS 這類通用作業系統，並不使用它。理由既實際又致命。它要求每個行程事先宣告自己的最大資源需求——但真實程式在跑起來之前，幾乎從不知道自己會想要多少檔案、鎖、或記憶體分頁。隨著程式啟動與結束，行程和資源的數量一直在變，而這個演算法卻假設有一群固定、已知的成員。而且那個安全檢查並不免費：它在每一個請求上都要做「行程數乘以資源數」量級的工，對於一個繁忙核心上的每一次取鎖來說，這實在太慢了。
那真實系統到底怎麼做？大多是用手去預防那個容易的條件——循環等待——靠紀律嚴明的上鎖順序，其餘的就乾脆忽視死結、接受偶爾的當機（鴕鳥法，第 4 篇導覽會正面談它）。銀行家演算法只在狹窄、高風險、且資源集合確實固定又事先已知的地方才值回票價，例如某些嵌入式與即時控制器。學它的長久回報是觀念上的：最大宣告、安全狀態、安全序列這幾個概念，正是工程師——哪怕他們從不把演算法寫出來——用來推理資源安全的方式。接下來，第 4 篇導覽轉向相反的哲學——讓死結發生，再在等待圖上偵測它並復原，或者聳聳肩、乾脆完全忽視它。