前言

死鎖避免算法大部分小伙伴應(yīng)該都能說(shuō)出來(lái) “銀行家算法”，死鎖檢測(cè)算法確實(shí)不常問(wèn)也不常見(jiàn)，最近在一篇 Bilibili 的三面面經(jīng)中看見(jiàn)了死鎖檢測(cè)算法，遂寫(xiě)出此文。

圖片

死鎖檢測(cè)模型

在并發(fā)系統(tǒng)中，多個(gè)進(jìn)程可能會(huì)因?yàn)橘Y源競(jìng)爭(zhēng)而陷入死鎖。死鎖檢測(cè)模型提供了一種機(jī)制，通過(guò)將系統(tǒng)狀態(tài)抽象為資源分配圖，來(lái)識(shí)別死鎖的存在。在這個(gè)圖中，每個(gè)進(jìn)程和資源都被表示為節(jié)點(diǎn)，資源和進(jìn)程之間的有向邊表示資源的分配和請(qǐng)求。

可證明結(jié)論：

• 無(wú)環(huán)安全狀態(tài)：如果資源分配圖是一個(gè)無(wú)環(huán)圖，系統(tǒng)處于安全狀態(tài)，因?yàn)榇嬖谝环N資源分配序列可以使得所有進(jìn)程順利完成。

圖片

• 環(huán)存在不確定性：如果圖中存在環(huán)，系統(tǒng)處于不安全狀態(tài)，但不一定處于死鎖狀態(tài)

圖片

當(dāng)每種資源類(lèi)型只有一個(gè)實(shí)例時(shí)，死鎖一定發(fā)生

如果資源類(lèi)型有多個(gè)實(shí)例，系統(tǒng)也可能通過(guò)資源的動(dòng)態(tài)分配來(lái)避免死鎖

每種資源類(lèi)型一個(gè)實(shí)例

圖片

上圖為資源分配圖，其中方框表示資源，圓圈表示進(jìn)程。資源指向進(jìn)程表示該資源已經(jīng)分配給該進(jìn)程，進(jìn)程指向資源表示進(jìn)程請(qǐng)求獲取該資源。

圖 a 可以抽取出環(huán)，如圖 b，它滿足了環(huán)路等待條件，因此一定會(huì)發(fā)生死鎖。

每種類(lèi)型一個(gè)資源的死鎖檢測(cè)算法是通過(guò)檢測(cè)有向圖是否存在環(huán)來(lái)實(shí)現(xiàn)，從一個(gè)節(jié)點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索，對(duì)訪問(wèn)過(guò)的節(jié)點(diǎn)進(jìn)行標(biāo)記，如果訪問(wèn)了已經(jīng)標(biāo)記的節(jié)點(diǎn)，就表示有向圖存在環(huán)，也就是檢測(cè)到死鎖的發(fā)生。具體算法描述如下：

1. 初始化：創(chuàng)建一個(gè)資源分配圖，用有向邊表示資源和進(jìn)程之間的關(guān)系。
2. 深度優(yōu)先搜索（DFS）：從任意一個(gè)進(jìn)程開(kāi)始，進(jìn)行深度優(yōu)先搜索。
3. 標(biāo)記訪問(wèn)：在搜索過(guò)程中，對(duì)訪問(wèn)過(guò)的節(jié)點(diǎn)（進(jìn)程）進(jìn)行標(biāo)記。
4. 檢測(cè)環(huán)：如果在搜索中遇到了已經(jīng)被標(biāo)記的節(jié)點(diǎn)，說(shuō)明存在環(huán)，即檢測(cè)到死鎖。

詳細(xì)算法步驟：

1. 選擇一個(gè)未訪問(wèn)的進(jìn)程作為起點(diǎn)。
2. 進(jìn)行DFS，訪問(wèn)其相鄰的資源節(jié)點(diǎn)。
3. 標(biāo)記該進(jìn)程為已訪問(wèn)。
4. 如果從該進(jìn)程出發(fā)可以回到任何已標(biāo)記的進(jìn)程，則存在死鎖。
5. 如果所有進(jìn)程都被訪問(wèn)且沒(méi)有形成環(huán)，則沒(méi)有死鎖。

每種資源類(lèi)型多個(gè)實(shí)例

圖片

上圖中，有三個(gè)進(jìn)程四個(gè)資源，每個(gè)數(shù)據(jù)代表的含義如下：

• E 向量：資源總量
• A 向量：資源剩余量
• C 矩陣：每個(gè)進(jìn)程所擁有的資源數(shù)量，每一行都代表一個(gè)進(jìn)程擁有資源的數(shù)量（P1、P2、P3 三個(gè)進(jìn)程）
• R 矩陣：每個(gè)進(jìn)程請(qǐng)求的資源數(shù)量

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

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

詳細(xì)算法步驟：

1. 標(biāo)記所有進(jìn)程為未標(biāo)記。
2. 從所有未標(biāo)記的進(jìn)程中選擇一個(gè)，其請(qǐng)求的資源向量Ri小于等于A。
3. 將該進(jìn)程的資源需求從A中減去，并更新C矩陣，標(biāo)記該進(jìn)程為已執(zhí)行。
4. 如果沒(méi)有這樣的進(jìn)程，檢查是否有任何進(jìn)程可以執(zhí)行。如果沒(méi)有，則檢測(cè)到死鎖
5. 重復(fù)步驟2和3，直到所有進(jìn)程都被標(biāo)記為已執(zhí)行或檢測(cè)到死鎖

總結(jié)

總結(jié)下：

• 對(duì)于每種資源類(lèi)型一個(gè)實(shí)例的場(chǎng)景，若有環(huán)則必死鎖；其死鎖檢測(cè)算法基于圖論中的環(huán)檢測(cè)技術(shù)，將死鎖檢測(cè)問(wèn)題轉(zhuǎn)化為有向圖中的環(huán)判斷問(wèn)題
• 對(duì)于沒(méi)中資源類(lèi)型多個(gè)實(shí)例的場(chǎng)景，有環(huán)不一定死鎖；其死鎖檢測(cè)算法通過(guò)模擬資源分配和回收過(guò)程，檢測(cè)是否存在一系列進(jìn)程可以順利獲取資源完成執(zhí)行，從而判斷系統(tǒng)是否處于死鎖狀態(tài)