前言

死鎖避免算法大部分小伙伴應該都能說出來 “銀行家算法”，死鎖檢測算法確實不常問也不常見，最近在一篇 Bilibili 的三面面經中看見了死鎖檢測算法，遂寫出此文。

圖片

死鎖檢測模型

在并發系統中，多個進程可能會因為資源競爭而陷入死鎖。死鎖檢測模型提供了一種機制，通過將系統狀態抽象為資源分配圖，來識別死鎖的存在。在這個圖中，每個進程和資源都被表示為節點，資源和進程之間的有向邊表示資源的分配和請求。

可證明結論：

• 無環安全狀態：如果資源分配圖是一個無環圖，系統處于安全狀態，因為存在一種資源分配序列可以使得所有進程順利完成。

圖片

• 環存在不確定性：如果圖中存在環，系統處于不安全狀態，但不一定處于死鎖狀態

圖片

當每種資源類型只有一個實例時，死鎖一定發生

如果資源類型有多個實例，系統也可能通過資源的動態分配來避免死鎖

每種資源類型一個實例

圖片

上圖為資源分配圖，其中方框表示資源，圓圈表示進程。資源指向進程表示該資源已經分配給該進程，進程指向資源表示進程請求獲取該資源。

圖 a 可以抽取出環，如圖 b，它滿足了環路等待條件，因此一定會發生死鎖。

每種類型一個資源的死鎖檢測算法是通過檢測有向圖是否存在環來實現，從一個節點出發進行深度優先搜索，對訪問過的節點進行標記，如果訪問了已經標記的節點，就表示有向圖存在環，也就是檢測到死鎖的發生。具體算法描述如下：

1. 初始化：創建一個資源分配圖，用有向邊表示資源和進程之間的關系。
2. 深度優先搜索（DFS）：從任意一個進程開始，進行深度優先搜索。
3. 標記訪問：在搜索過程中，對訪問過的節點（進程）進行標記。
4. 檢測環：如果在搜索中遇到了已經被標記的節點，說明存在環，即檢測到死鎖。

詳細算法步驟：

1. 選擇一個未訪問的進程作為起點。
2. 進行DFS，訪問其相鄰的資源節點。
3. 標記該進程為已訪問。
4. 如果從該進程出發可以回到任何已標記的進程，則存在死鎖。
5. 如果所有進程都被訪問且沒有形成環，則沒有死鎖。

每種資源類型多個實例

圖片

上圖中，有三個進程四個資源，每個數據代表的含義如下：

• E 向量：資源總量
• A 向量：資源剩余量
• C 矩陣：每個進程所擁有的資源數量，每一行都代表一個進程擁有資源的數量（P1、P2、P3 三個進程）
• R 矩陣：每個進程請求的資源數量

進程 P1 和 P2 所請求的資源都得不到滿足，只有進程 P3 可以，因此我們讓 P3 先執行，之后釋放 P3 擁有的資源，此時 A = (2 2 2 0)。這樣的話 P2 就可以執行了，執行后釋放 P2 擁有的資源，A = (4 2 2 1) 。P1 也可以執行了。所有的進程都可以順利執行，所以沒有死鎖。具體算法描述如下：

1. 初始化：定義E（資源總量）、A（資源剩余量）、C（進程擁有的資源矩陣）和R（進程請求的資源矩陣）。
2. 尋找可執行進程：選擇一個請求資源不超過A的進程執行。
3. 資源分配：將該進程請求的資源分配給它，并更新A和C。
4. 進程完成：當進程執行完畢后，將其擁有的資源釋放回A，并更新C。如果所有線程都可以順利執行完畢，則沒有死鎖

詳細算法步驟：

1. 標記所有進程為未標記。
2. 從所有未標記的進程中選擇一個，其請求的資源向量Ri小于等于A。
3. 將該進程的資源需求從A中減去，并更新C矩陣，標記該進程為已執行。
4. 如果沒有這樣的進程，檢查是否有任何進程可以執行。如果沒有，則檢測到死鎖
5. 重復步驟2和3，直到所有進程都被標記為已執行或檢測到死鎖

總結

總結下：

• 對于每種資源類型一個實例的場景，若有環則必死鎖；其死鎖檢測算法基于圖論中的環檢測技術，將死鎖檢測問題轉化為有向圖中的環判斷問題
• 對于沒中資源類型多個實例的場景，有環不一定死鎖；其死鎖檢測算法通過模擬資源分配和回收過程，檢測是否存在一系列進程可以順利獲取資源完成執行，從而判斷系統是否處于死鎖狀態