死鎖檢測與解除主要內(nèi)容一、死鎖檢測策略二、進(jìn)程-資源分配圖的結(jié)構(gòu)三、進(jìn)程-資源分配圖與死鎖判斷的關(guān)系四、死鎖檢測方法五、死鎖檢測算法與死鎖避免算法比較六、死鎖解除方法一、死鎖檢測策略死鎖檢測和解除對資源分配不加任何限制，也不采取死鎖避免措施，但系統(tǒng)定時運(yùn)行一個“死鎖檢測”程序，如果檢測到系統(tǒng)發(fā)生了死鎖，再采取措施解除它。進(jìn)程-資源分配圖是描述進(jìn)程和資源間申請與分配關(guān)系的一種有向圖，可用以檢測系統(tǒng)是否處于死鎖狀態(tài)。死鎖檢測依據(jù)的數(shù)據(jù)結(jié)構(gòu)進(jìn)程-資源分配圖二、進(jìn)程-資源分配圖的結(jié)構(gòu)由進(jìn)程結(jié)點(diǎn)P、資源結(jié)點(diǎn)R和有向邊組成。從資源指向進(jìn)程的有向邊Rj→Pi為分配邊，表示Rj類中的一個資源已分配給進(jìn)程Pi。進(jìn)程-資源分配圖從進(jìn)程指向資源的有向邊Pi→Rj為請求邊，表示進(jìn)程Pi申請資源類Rj中的一個資源。請求邊分配邊有向邊進(jìn)程-資源分配圖實(shí)例R1R2P1P2P3R3請求邊分配邊資源結(jié)點(diǎn)進(jìn)程結(jié)點(diǎn)R1R2P1P2P3P4進(jìn)程-資源分配圖1進(jìn)程-資源分配圖2三、進(jìn)程-資源分配圖與死鎖判斷的關(guān)系則此時系統(tǒng)沒有發(fā)生死鎖則環(huán)的存在只是產(chǎn)生死鎖的必要條件而不是充分條件（1）如果進(jìn)程-資源分配圖中無環(huán)路則系統(tǒng)中發(fā)生了死鎖，此時，環(huán)路是系統(tǒng)發(fā)生死鎖的充要條件，環(huán)路中的進(jìn)程便為死鎖進(jìn)程（2）如果進(jìn)程-資源分配圖中有環(huán)路，且每個資源類中僅有一個資源（3）如果進(jìn)程-資源分配圖中有環(huán)路，且涉及的資源類中有多個資源死鎖判斷實(shí)例1R1R2P1P2P3R3進(jìn)程-資源分配圖1R1R2P1P2P3R3進(jìn)程-資源分配圖2進(jìn)程-資源分配圖中有環(huán)路，且資源類R3中資源數(shù)超過1個，無法判定是否發(fā)生死鎖。死鎖判斷實(shí)例2R1R2P1P2P3P4進(jìn)程-資源分配圖2進(jìn)程-資源分配圖中有環(huán)路，且每類資源數(shù)超過1個，無法判定是否發(fā)生死鎖。四、死鎖檢測方法從進(jìn)程-資源分配圖中找到一個不阻塞（或者雖阻塞但其資源需求可滿足）且非孤立的進(jìn)程，消去所有與該進(jìn)程相連的有向邊，相當(dāng)于該進(jìn)程能夠執(zhí)行完成而釋放資源，回收資源使之成為孤立結(jié)點(diǎn)。然后將所回收的資源分配給其它進(jìn)程，再從進(jìn)程-資源分配圖中找到下一個不阻塞（或者雖阻塞但其資源需求可滿足）且非孤立的進(jìn)程，消去所有與該進(jìn)程相連的有向邊，使之成為孤立結(jié)點(diǎn)……。不斷重復(fù)該過程，直到所有進(jìn)程成為孤立結(jié)點(diǎn)，則稱該圖是可完全化簡的；否則稱該圖是不可完全化簡的。系統(tǒng)為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)該狀態(tài)的進(jìn)程-資源分配圖是不可完全簡化的。該充分條件稱為死鎖定理。死鎖定理死鎖檢測實(shí)例1R1R2P1P2P3R3解決思路：無法應(yīng)用死鎖判定原則，需要化簡。按照P1、P2和P3的順序逐一考察每個進(jìn)程，判斷其是否孤立和阻塞。分析如下進(jìn)程-資源分配圖，判斷該進(jìn)程集合是否發(fā)生死鎖？問題求解：P1、P2和P3三個進(jìn)程均不孤立，接下來需要判斷它們是否阻塞。R1R2P1P2P3R3P1該進(jìn)程請求資源R1，而R1僅有的一個資源已經(jīng)分配給P2，所以P1阻塞。P2該進(jìn)程請求資源R2，而R2僅有的一個資源已經(jīng)分配給P3，所以P2阻塞。P3該進(jìn)程請求資源R3，而R3的兩個資源已經(jīng)分別分配給P1和P2，所以P3阻塞。進(jìn)程-資源分配圖無法完全化簡，因此進(jìn)程集合發(fā)生死鎖。死鎖檢測實(shí)例2請自行分析如下進(jìn)程-資源分配圖，判斷該進(jìn)程集合是否發(fā)生死鎖？R1R2P1P2P3P4請自行計算五、死鎖檢測算法與死鎖避免算法比較死鎖檢測算法考慮了檢查每個進(jìn)程還需要的所有資源能否滿足要求；死鎖避免算法則僅根據(jù)進(jìn)程的當(dāng)前申請資源量來判斷系統(tǒng)是否進(jìn)入了不安全狀態(tài)。在銀行家算法中，一次僅允許一個進(jìn)程提出資源請求，做安全分析并分配資源后，才允許下一個進(jìn)程提出資源請求。死鎖檢測算法處理的進(jìn)程-資源圖中可以同時存在多個進(jìn)程的請求邊。六、死鎖解除方法（1）立即結(jié)束所有進(jìn)程的執(zhí)行，并重新啟動操作系統(tǒng)。以前工作全部作廢，損失可能很大。（2）剝奪陷于死鎖的進(jìn)程占用的資源，但并不撤銷它，直至死鎖解除。（3）撤銷陷于死鎖的所有進(jìn)程，解除死鎖繼續(xù)運(yùn)行。（4）逐個撤銷陷于死鎖的進(jìn)程，回收其資源，直至死鎖解除。（5）根據(jù)系統(tǒng)保存的檢