昨天實驗室老闆在群組張貼出了新的實驗室守則，裡面呢，就像是「進行研究是研究生的基本義務，不應僅在會議前才被動準備呀」、「請養成 Think before you ask 的習慣」、「成員間應互相鼓勵、良性競爭呀」、「主動分享各自的研究經驗與成果呀」....。感覺這一年應該也是兇多吉少瞜。

資源配置圖（Resource-Allocation Graph，RAG）與死結的關係

在資源配置圖 (Resource-Allocation Graph, RAG) 中，循環 (cycle) 是判斷潛在死結的重要依據。然而，有循環並不代表一定會發生死結。這兩者之間的關係取決於資源的實例數量。

如果每種資源類型只有一個實例 (instance)：
如果 RAG 中存在循環，則必然會發生死結 (deadlock)。這是因為每個執行緒都在等待另一個執行緒所持有的唯一資源，形成無法打破的循環等待。

如果某些資源類型擁有多個實例：
如果 RAG 中存在循環，則可能會發生死結。這種情況下，一個執行緒即使位於循環中，仍可能獲得所需的資源並完成執行。例如，如果循環中的執行緒等待的資源還有多餘的實例，或者另一個不在循環中的執行緒釋放了它所需的資源，那麼這個循環就可以被打破。因此，循環只是必要條件 (necessary condition)，但不是充分條件 (sufficient condition)。

資源配置圖的基本構成

• 執行緒 Ti(圓形節點)：代表一個 thread 或 process
• 資源類型 Rj(矩形節點)：代表一種資源（如 CPU、印表機）
• 請求邊 Ti → Rj(➡️從圓形指向矩形)：表示執行緒 Ti 正在「等待」資源 Rj
• 分配邊 Rj → Ti(➡️從矩形指向圓形)：表示資源 Rj 的某個實例已「分配給」Ti

假設：T1 等待資源 R1，R1 的某個實例被分配給 T2。則圖示為：
T1  →  R1  →  T2

執行緒集合：T = {T1, T2, T3}
資源集合：R = {R1, R2, R3, R4}
資源實例數量：
    R1 和 R3 各有 1 個
    R2 有 2 個
    R4 有 3 個

有循環但不一定死結？

讓我們再仔細看這個範例：

在這個圖中，T1 → R1 → T3 → R2 → T1 形成了一個循環。

• T1 正在等待 R1，而 R1 被 T3 持有。
• T3 正在等待 R2，而 R2 被 T1 持有。
• T4 持有 R2，並且不在循環中。

儘管有一個循環，但死結不一定會發生。原因在於 R2 資源有多個實例，其中一個實例被 T4 所持有。當 T4 完成工作並釋放 R2 時，T3 或 T1 就有可能獲得這個資源。一旦資源被釋放，循環就可以被打破，等待中的執行緒就能繼續執行，從而避免死結。簡而言之，資源配置圖中的循環只是死結的必要條件。只有當圖中存在循環，且所有資源類型都只有一個實例，才能確定發生死結。

死結預防（Deadlock Prevention）

死結預防是一種在系統設計階段就主動避免死結的策略，其核心思想是破壞死結的四個必要條件之一或多個。只要能確保這四個條件不同時成立，系統就永遠不會陷入死結。

互斥（Mutual Exclusion）

這個條件是指資源在任何時候只能被一個執行緒使用。如果資源可以被多個執行緒同時共享，那麼互斥條件就不成立。然而，破壞此條件通常不切實際。大多數系統資源，如印表機、檔案鎖或 Mutex 鎖，其本質就是不可共享的。強行讓它們共享會導致資料混亂或系統邏輯錯誤。因此，互斥通常被視為不可避免的條件。

保有並等待（Hold and Wait）

這個條件是指一個執行緒在持有部分資源的同時，還在等待其他資源。有兩種預防策略：

第一種是一次性請求所有資源（All-or-Nothing）： 執行緒在開始執行前，必須一次性請求它所需要的所有資源。如果任何一個資源無法取得，它就必須放棄所有已取得的資源，然後重新嘗試。其優點是簡單有效，能徹底避免保有並等待。但缺點是資源利用率低。許多資源可能在很長一段時間內被「佔著不用」，導致其他執行緒無法使用。此外，當一個執行緒需要大量資源時，可能會導致飢餓（starvation），因為它很難一次性滿足所有請求。

第二種是在請求新資源前先釋放所有資源： 執行緒如果需要請求新的資源，必須先釋放所有目前持有的資源。相較於第一種方式，這種方法更能適應動態的資源需求。但缺點是頻繁的資源釋放與重新申請會增加系統開銷，且可能導致飢餓，因為執行緒可能總是在釋放資源後，又無法立即取得所有所需的新資源。

不可搶佔（No Preemption）

這個條件是指已分配給執行緒的資源不能被強制收回，只能由持有者主動釋放。允許資源被搶佔。如果一個執行緒在等待某個資源時，無法立即取得，系統可以強制收回它已持有的資源。 這種方法主要適用於那些可以暫時儲存狀態的資源。

以可搶佔資源而言： 像是 CPU、記憶體頁面（可以交換到磁碟）、資料庫交易（可以回溯 rollback）。
以不可搶佔資源而言： 像是互斥鎖（Mutex）、號誌（Semaphore）、印表機等。強行搶佔這些資源可能會導致邏輯錯誤或資料損壞。

循環等待（Circular Wait）

這個條件是指存在一個等待鏈，形成一個環，使得每個執行緒都在等待鏈中下一個執行緒所持有的資源。
實施方式：

• 為每種資源類型分配一個唯一的整數編號。
• 要求執行緒只能以遞增的順序請求資源。
  範例：
• 假設資源 R1 編號為 1，R2 編號為 2，R3 編號為 3。
• 合法請求： 執行緒先請求 R1，再請求 R2。這符合遞增順序。
• 不合法請求： 執行緒先請求 R3，然後再請求 R1。由於 1 < 3，這個請求是無效的，無法獲得 R1。

這種嚴格的遞增順序確保了資源請求鏈永遠無法形成一個閉合的環。如果所有執行緒都遵循此規則，則循環等待條件永遠無法成立，從而從根本上杜絕了死結的發生。