死鎖檢測算法｜Bilibili 三面，資源分配圖中存在環(huán)路則一定出現(xiàn)死鎖么？
前言
死鎖避免算法大部分小伙伴應(yīng)該都能說出來 “銀行家算法”，死鎖檢測算法確實不常問也不常見，最近在一篇 Bilibili 的三面面經(jīng)中看見了死鎖檢測算法，遂寫出此文。
圖片
死鎖檢測模型
在并發(fā)系統(tǒng)中，多個進程可能會因為資源競爭而陷入死鎖。死鎖檢測模型提供了一種機制，通過將系統(tǒng)狀態(tài)抽象為資源分配圖，來識別死鎖的存在。在這個圖中，每個進程和資源都被表示為節(jié)點，資源和進程之間的有向邊表示資源的分配和請求。
可證明結(jié)論：
- 無環(huán)安全狀態(tài)：如果資源分配圖是一個無環(huán)圖，系統(tǒng)處于安全狀態(tài)，因為存在一種資源分配序列可以使得所有進程順利完成。
圖片
- 環(huán)存在不確定性：如果圖中存在環(huán)，系統(tǒng)處于不安全狀態(tài)，但不一定處于死鎖狀態(tài)
圖片
當每種資源類型只有一個實例時，死鎖一定發(fā)生
如果資源類型有多個實例，系統(tǒng)也可能通過資源的動態(tài)分配來避免死鎖
每種資源類型一個實例
圖片
上圖為資源分配圖，其中方框表示資源，圓圈表示進程。資源指向進程表示該資源已經(jīng)分配給該進程，進程指向資源表示進程請求獲取該資源。
圖 a 可以抽取出環(huán)，如圖 b，它滿足了環(huán)路等待條件，因此一定會發(fā)生死鎖。
每種類型一個資源的死鎖檢測算法是通過檢測有向圖是否存在環(huán)來實現(xiàn)，從一個節(jié)點出發(fā)進行深度優(yōu)先搜索，對訪問過的節(jié)點進行標記，如果訪問了已經(jīng)標記的節(jié)點，就表示有向圖存在環(huán)，也就是檢測到死鎖的發(fā)生。具體算法描述如下：
- 初始化：創(chuàng)建一個資源分配圖，用有向邊表示資源和進程之間的關(guān)系。
- 深度優(yōu)先搜索（DFS）：從任意一個進程開始，進行深度優(yōu)先搜索。
- 標記訪問：在搜索過程中，對訪問過的節(jié)點（進程）進行標記。
- 檢測環(huán)：如果在搜索中遇到了已經(jīng)被標記的節(jié)點，說明存在環(huán)，即檢測到死鎖。
詳細算法步驟：
- 選擇一個未訪問的進程作為起點。
- 進行DFS，訪問其相鄰的資源節(jié)點。
- 標記該進程為已訪問。
- 如果從該進程出發(fā)可以回到任何已標記的進程，則存在死鎖。
- 如果所有進程都被訪問且沒有形成環(huán)，則沒有死鎖。
每種資源類型多個實例
圖片
上圖中，有三個進程四個資源，每個數(shù)據(jù)代表的含義如下：
- E 向量：資源總量
- A 向量：資源剩余量
- C 矩陣：每個進程所擁有的資源數(shù)量，每一行都代表一個進程擁有資源的數(shù)量（P1、P2、P3 三個進程）
- R 矩陣：每個進程請求的資源數(shù)量
進程 P1 和 P2 所請求的資源都得不到滿足，只有進程 P3 可以，因此我們讓 P3 先執(zhí)行，之后釋放 P3 擁有的資源，此時 A = (2 2 2 0)。這樣的話 P2 就可以執(zhí)行了，執(zhí)行后釋放 P2 擁有的資源，A = (4 2 2 1) 。P1 也可以執(zhí)行了。所有的進程都可以順利執(zhí)行，所以沒有死鎖。具體算法描述如下：
- 初始化：定義E（資源總量）、A（資源剩余量）、C（進程擁有的資源矩陣）和R（進程請求的資源矩陣）。
- 尋找可執(zhí)行進程：選擇一個請求資源不超過A的進程執(zhí)行。
- 資源分配：將該進程請求的資源分配給它，并更新A和C。
- 進程完成：當進程執(zhí)行完畢后，將其擁有的資源釋放回A，并更新C。如果所有線程都可以順利執(zhí)行完畢，則沒有死鎖
詳細算法步驟：
- 標記所有進程為未標記。
- 從所有未標記的進程中選擇一個，其請求的資源向量Ri小于等于A。
- 將該進程的資源需求從A中減去，并更新C矩陣，標記該進程為已執(zhí)行。
- 如果沒有這樣的進程，檢查是否有任何進程可以執(zhí)行。如果沒有，則檢測到死鎖
- 重復(fù)步驟2和3，直到所有進程都被標記為已執(zhí)行或檢測到死鎖
總結(jié)
總結(jié)下：
- 對于每種資源類型一個實例的場景，若有環(huán)則必死鎖；其死鎖檢測算法基于圖論中的環(huán)檢測技術(shù)，將死鎖檢測問題轉(zhuǎn)化為有向圖中的環(huán)判斷問題
- 對于沒中資源類型多個實例的場景，有環(huán)不一定死鎖；其死鎖檢測算法通過模擬資源分配和回收過程，檢測是否存在一系列進程可以順利獲取資源完成執(zhí)行，從而判斷系統(tǒng)是否處于死鎖狀態(tài)
