什麼是 Deadlock

Deadlock 應該是軟體工程師在開發過程中，常見的問題之一。有多個執行緒或是多個程序，等待某個執行緒或是程序釋放資源，導致所有的執行緒或程序都無法繼續執行下去，這種情況就是 deadlock。

對使用者來說，使用體驗會很差，頻繁遇到系統卡住沒有回應，或是等待的時間異常久，有可能是 deadlock 的問題。

Deadlock 四個必要條件 (Coffman Conditions)

• Mutual Exclusion: 資源只能被一個執行緒或程序使用。
• Hold and Wait: 一個執行緒或程序持有一個資源，並且等待另一個資源。
• No Preemption: 其他執行緒或程序無法強制取得資源，只能等待它自己釋放資源。
• Circular Wait: 一個執行緒或程序等待另一個執行緒或程序持有的資源，而另一個執行緒或程序又等待第一個執行緒或程序持有的資源。造成大家都在等待資源。

Deadlock 的處理方式

• Deadlock Prevention: 預防 Deadlock 發生，讓四個必要條件其中一個不成立就可以。最常做的方式就是去掉 Circular Wait 的情況，透過固定順序取得資源來避免 Circular Wait 的情況。
• Deadlock Avoidance: 避免 Deadlock 發生，則是透過演算法的方式，例如 Banker’s Algorithm，但就是會造成效能上的負擔。
  • Banker’s Algorithm: 預先知道每個執行緒或程序需要的資源數量，並且預先知道每個執行緒或程序可以釋放的資源數量，透過這些資訊來判斷是否可以取得資源，避免 Deadlock 的發生。
• Deadlock Recovery: 恢復 Deadlock 的狀態，如果沒有做預防與避免，那麼就要透過偵測 Deadlock，接著透過以下幾個方式恢復 Deadlock。
  • Manual Intervention: 手動介入，讓使用者或是系統重新啟動。
  • Automatic Recovery: 自動恢復，透過系統自動重新啟動。
    • Process Termination: 終止一個或多個執行緒或程序，讓其他執行緒或程序可以繼續執行。
    • Resource Preemption: 強制取得資源，讓其他執行緒或程序可以繼續執行。
• Deadlock Ignorance: 忽略 Deadlock 的問題，讓 Deadlock 發生，並且等待使用者或是系統重新啟動。

Deadlock 如何檢測

最常見的方式就是透過 資源分配圖 (Resource Allocation Graph, RAG) 來檢測 Deadlock 的問題。

• 資源分配圖 (Resource Allocation Graph, RAG): 透過圖形的方式來表示執行緒或程序與資源之間的關係，並且透過圖形的方式來檢測是否有 Deadlock 的問題。
  • Node: 代表執行緒或程序。
  • Edge: 代表資源。
  • Directed Edge: 代表執行緒或程序持有資源。
  • Undirected Edge: 代表執行緒或程序等待資源。

以下圖片，代表這是有 Deadlock 情況的資源分配圖。

以下圖片，則是沒有 Deadlock 情況的資源分配圖。

Deadlock 在分散式系統中

在分散式系統中，Deadlock 的問題會更加複雜，因為不同的節點之間會有不同的資源，而且不同的節點之間會有不同的通訊方式，這樣就會造成 Deadlock 的問題更加複雜。所以可以區分成有兩類 Deadlock 的問題：

• Resource Deadlock: 直接附上資源分配圖。

• Communication Deadlock: 可以理解為執行緒或程序呼叫其他 Server 的 API，等待回應，但是其他 Server 也在等待這個執行緒或程序的回應，這樣就會造成 Communication Deadlock 的問題。 用以下圖片來表示 Communication Deadlock 的問題。

參考

• Introduction of Deadlock in Operating System
• Conditions for Deadlock in Distributed System
• Deadlock Handling Strategies in Distributed System
• Resource Allocation Graph (RAG) in Operating System