深入淺出：作業系統死結（Deadlock）成因、模型與四大應對策略

電腦店訊　死結是多執行緒/多程序環境中最棘手的並發問題之一。本文從生活化範例切入，系統梳理死結的四個必要條件、建模定義、四大經典應對策略（鴕鳥演算法、偵測與恢復、避免、預防），並說明銀行家演算法等核心機制，最後總結：無完美方案，唯有因地制宜。

1. 為何會出現死結？

1.1 生活化範例：掃描儀與燒錄機的僵持

程序 A 佔用掃描儀、請求燒錄機；程序 B 佔用燒錄機、請求掃描儀。雙方各執一資源、互求對方資源，形成循環等待，誰也無法繼續——這就是死結。

1.2 資源分類

• 可搶佔資源：可從擁有者強制奪取不產生副作用（如 CPU 時間片），死結可透過重新分配解決。
• 不可搶佔資源：強制奪取會導致錯誤（如燒錄機、資料庫鎖定記錄），只能由擁有者主動釋放，這是死結的主要溫床。

2. 死結建模與規範定義

若一組程序中，每個程序都在等待只能由該組內其他程序觸發的事件，則該組程序處於死結。換句話說：每個程序都需要額外資源才能繼續，但持有那些資源的程序因資源不足而無法釋放，形成閉環。

3. 資源死結的四個必要條件（Coffman 條件）

1. 互斥條件：資源同一時間只能由一程序使用。
2. 佔有並等待：程序持有資源的同時可請求新資源。
3. 不可搶佔：資源只能由持有者主動釋放。
4. 循環等待：存在程序鏈，每個程序持有的資源被下一個程序請求。

四條件同時成立才會死結；破壞任一條件即可預防。

4. 四大應對策略

4.1 鴕鳥演算法—— 忽略問題

源於鴕鳥遇危險埋頭沙中假裝沒事。工程觀點：若死結機率極低、處理成本極高，不處理反而划算。許多商業作業系統（早期 UNIX、Windows）對一般使用者採此策略。

4.2 死結偵測與恢復

• 偵測：定期檢查資源分配圖是否存在環路。
• 恢復手段：① 搶佔資源 ② 回滾到安全狀態 ③ 殺死死結程序。缺點：可能導致資料遺失、作業中斷。

4.3 死結避免—— 銀行家演算法

核心概念：安全狀態——即使所有程序突然請求最大資源需求，仍存在某種調度順序讓所有程序跑完。每次資源請求前模擬分配，若分配後仍處於安全狀態則允許，否則拒絕/延遲。缺點：需預知最大需求、計算開銷大。

4.4 死結預防—— 破壞四條件之一

5. 總結

沒有銀彈。實務上常混合策略：關鍵系統用避免/預防，一般系統用鴕鳥演算法+偵測恢復。工程師需根據系統關鍵性、資源類型、負載特性，量身打造死結管理方案。