一、死鎖的概念

操作系統(tǒng)中的死鎖是指：

如果在一個進程集合中的每個進程都在等待只能有該集合中的其它進程才能引起的事件，而無限期陷入僵持的局面稱為死鎖。

二、死鎖的產(chǎn)生因素

1、系統(tǒng)擁有的資源數(shù)量

2、資源分配策略

3、進程對資源的使用要求

4、并發(fā)進程的推薦順序

三、死鎖的必要條件

1、互斥條件

進程互斥使用資源，一旦某個資源被占用，欲使用該資源的進程必須等待。

2、占有和等待條件（部分分配條件）

進程申請新資源得不到滿足而等待時，不釋放已占有資源。

3、不剝奪條件

一個進程不能搶奪其它進程占有的資源。

4、循環(huán)等待條件（環(huán)路條件）

存在一組進程循環(huán)等待資源的現(xiàn)象。

前三個條件是死鎖產(chǎn)生的必要條件，不是充分條件。第四個條件是前三個條件同時存在時產(chǎn)生的結(jié)果。只要破壞這四個條件之一，死鎖就可防止。

四、死鎖防止

死鎖防止通過破壞產(chǎn)生死鎖的四個條件之一來實現(xiàn)。

1、破壞互斥條件

使資源可同時訪問而不是互斥使用。

該辦法對于磁盤適用，對于磁帶機、打印機等多數(shù)資源不僅不能破壞互斥使用條件，還要加以保證。

2、破壞占有和等待條件

靜態(tài)分配可以破壞占有和等待條件。

靜態(tài)分配是指一個進程必須在執(zhí)行前就申請它所需要的全部資源，并且直到它所需要的資源都得到滿足后才開始執(zhí)行。資源利用率低。

3、破壞不剝奪條件

采用剝奪式調(diào)度方法。

當(dāng)進程申請資源未獲準(zhǔn)許時，在等待前主動釋放資源。剝奪調(diào)度方法目前只適用于內(nèi)存資源和處理器資源。

4、破壞循環(huán)等待條件

采用層次分配策略可以破壞循環(huán)等待條件。

層次分配策略將資源被分成多個層次，進程按照由低到高的層次順序申請和得到資源，按照由高到低的層次順序釋放資源。當(dāng)進程得到某一層的一個資源后，如果需要申請該層的另一個資源，則必須先釋放該層中的已占資源。

五、死鎖避免

1、避免死鎖的策略

死鎖避免方法允許系統(tǒng)中同時存在死鎖的三個必要條件，即互斥、占有且等待和非搶占；

每當(dāng)進程提出資源申請時，系統(tǒng)分析滿足該資源請求時系統(tǒng)是否會發(fā)生死鎖，若不會發(fā)生則實施分配，否則拒絕分配。

銀行家算法就是避免死鎖的一種方法。

2、銀行家算法思想

一個銀行家擁有資金M，被N個客戶共享，銀行家對客戶提出下列約束條件：

① 每個客戶必須預(yù)先說明自己所要求的最大資金量；

② 每個客戶每次提出部分資金量申請和獲得分配；

③ 如果銀行滿足了客戶對資金的最大需求量，則客戶在資金運作后一定可以很快歸還資金。

3、銀行家算法在死鎖問題上的應(yīng)用

步驟：

① 系統(tǒng)中的所有進程進入進程集合；

② 在安全狀態(tài)下對進程請求的資源進行試探性分配；

③ 系統(tǒng)用剩余的可用資源和進程集合中其它進程還要的資源數(shù)作比較，找到剩余資源能滿足最大需求量的進程A，保證A運行完畢并歸還全部資源；

④ 把進程A從集合中去掉，相當(dāng)于回收其資源。如果進程集合非空，則返回②；

⑤ 若進程集合為空，則系統(tǒng)處于安全狀態(tài)，可實施本次分配；否則，系統(tǒng)處于不安全狀態(tài)，本次資源分配暫不實施，申請進程等待。

安全狀態(tài)與不安全狀態(tài)：

如果系統(tǒng)能夠按某種進程順序（P1，P2，… … ，Pn）（稱< P1，P2，… … ，Pn >序列為安全序列），為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都能順利完成，則稱系統(tǒng)處于安全狀態(tài)。

如果找不到這樣的安全序列，則稱系統(tǒng)處于不安全狀態(tài)。

例：

4、銀行家算法的缺點

① 使用銀行家算法時，很難在進程運行前知道其所需的資源最大量；② 算法要求系統(tǒng)中的進程必須是無關(guān)的，相互間沒有同步要求；③ 進程的個數(shù)和分配的資源數(shù)目應(yīng)該是固定的；這些要求事先難以滿足，因而銀行家算法缺乏實用價值。

六、死鎖檢測與解除

1、死鎖檢測策略

死鎖檢測和解除對資源分配不加任何限制，也不采取死鎖避免措施，但系統(tǒng)定時運行一個“死鎖檢測”程序，如果檢測到系統(tǒng)發(fā)生了死鎖，再采取措施解除它。

進程-資源分配圖是描述進程和資源間申請與分配關(guān)系的一種有向圖，可用以檢測系統(tǒng)是否處于死鎖狀態(tài)。

2、進程-資源分配圖的結(jié)構(gòu)

進程-資源分配圖由進程結(jié)點P、資源結(jié)點R和有向邊組成。

有向邊：

① 請求邊：

從進程指向資源的有向邊Pi→Rj為請求邊，表示進程Pi申請資源類Rj中的一個資源。

② 分配邊：

從資源指向進程的有向邊Rj→Pi為分配邊，表示Rj類中的一個資源已分配給進程Pi。

3、進程-資源分配圖與死鎖判斷的關(guān)系

① 如果進程-資源分配圖中無環(huán)路

——>則此時系統(tǒng)沒有發(fā)生死鎖

② 如果進程-資源分配圖中有環(huán)路，且每個資源類中僅有一個資源

——>則系統(tǒng)中發(fā)生了死鎖，此時，環(huán)路是系統(tǒng)發(fā)生死鎖的充要條件，環(huán)路中的進程便為死鎖進程

③ 如果進程-資源分配圖中有環(huán)路，且涉及的資源類中有多個資源

——>則環(huán)的存在只是產(chǎn)生死鎖的必要條件而不是充分條件

4、死鎖的檢測和解除方法

死鎖定理

系統(tǒng)為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)該狀態(tài)的進程-資源分配圖是不可完全簡化的。該充分條件稱為死鎖定理。

簡化進程-資源分配圖

① 從進程-資源分配圖中找到一個既不阻塞又非獨立的進程，消去所有與該進程相連的有向邊，相當(dāng)于該進程能夠執(zhí)行完成而釋放資源，回收資源使之成為孤立結(jié)點。

② 然后將所回收的資源分配給其它進程，再從進程-資源分配圖中找到下一個既不阻塞又非獨立的進程，消去所有與該進程相連的有向邊，使之成為孤立結(jié)點。

③ 不斷重復(fù)該過程，直到所有進程成為孤立結(jié)點，則稱該圖是可完全化簡的；否則稱該圖是不可完全化簡的。

死鎖檢測實例：

問題求解：

解決思路：無法應(yīng)用死鎖判定原則，需要化簡。按照P1、P2和P3的順序逐一考察每個進程，判斷其是否孤立和阻塞。

① P1、P2和P3三個進程均不孤立，接下來需要判斷它們是否阻塞。

② P1：該進程請求資源R1，而R1僅有的一個資源已經(jīng)分配給P2，所以P1阻塞；

③ 該進程請求資源R2，而R2僅有的一個資源已經(jīng)分配給P3，所以P2阻塞。

④ 該進程請求資源R3，而R3的兩個資源已經(jīng)分別分配給P1和P2，所以P3阻塞。

結(jié)論：進程-資源分配圖無法完全化簡，因此進程集合發(fā)生死鎖。

5、死鎖檢測算法與死鎖避免算法比較

① 死鎖檢測算法考慮了檢查每個進程還需要的所有資源能否滿足要求；

死鎖避免算法則僅根據(jù)進程的當(dāng)前申請資源量來判斷系統(tǒng)是否進入了不安全狀態(tài)。

② 死鎖檢測算法處理的進程-資源圖中可以同時存在多個進程的請求邊。

在銀行家算法中，一次僅允許一個進程提出資源請求，做安全分析并分配資源后，才允許下一個進程提出資源請求。

6、死鎖的解除方法

① 立即結(jié)束所有進程的執(zhí)行，并重新啟動操作系統(tǒng)。以前工作全部作廢，損失可能很大。

② 剝奪陷于死鎖的進程占用的資源，但并不撤銷它，直至死鎖解除。

③ 撤銷陷于死鎖的所有進程，解除死鎖繼續(xù)運行。

④ 逐個撤銷陷于死鎖的進程，回收其資源，直至死鎖解除。

⑤ 根據(jù)系統(tǒng)保存的檢查點，使所有進程回退，直到足以解除死鎖。

⑥ 當(dāng)檢測到死鎖時，如果存在某些未卷入死鎖的進程，且它們會進一步建立一些新的抑制進程能執(zhí)行到結(jié)束，則它們可能釋放足夠的資源來解除死鎖。