一、死鎖的概念

操作系統中的死鎖是指：

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

二、死鎖的產生因素

1、系統擁有的資源數量

2、資源分配策略

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

4、并發進程的推薦順序

三、死鎖的必要條件

1、互斥條件

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

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

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

3、不剝奪條件

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

4、循環等待條件（環路條件）

存在一組進程循環等待資源的現象。

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

四、死鎖防止

死鎖防止通過破壞產生死鎖的四個條件之一來實現。

1、破壞互斥條件

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

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

2、破壞占有和等待條件

靜態分配可以破壞占有和等待條件。

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

3、破壞不剝奪條件

采用剝奪式調度方法。

當進程申請資源未獲準許時，在等待前主動釋放資源。剝奪調度方法目前只適用于內存資源和處理器資源。

4、破壞循環等待條件

采用層次分配策略可以破壞循環等待條件。

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

五、死鎖避免

1、避免死鎖的策略

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

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

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

2、銀行家算法思想

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

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

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

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

3、銀行家算法在死鎖問題上的應用

步驟：

① 系統中的所有進程進入進程集合；

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

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

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

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

安全狀態與不安全狀態：

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

如果找不到這樣的安全序列，則稱系統處于不安全狀態。

例：

4、銀行家算法的缺點

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

六、死鎖檢測與解除

1、死鎖檢測策略

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

進程-資源分配圖是描述進程和資源間申請與分配關系的一種有向圖，可用以檢測系統是否處于死鎖狀態。

2、進程-資源分配圖的結構

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

有向邊：

① 請求邊：

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

② 分配邊：

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

3、進程-資源分配圖與死鎖判斷的關系

① 如果進程-資源分配圖中無環路

——>則此時系統沒有發生死鎖

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

——>則系統中發生了死鎖，此時，環路是系統發生死鎖的充要條件，環路中的進程便為死鎖進程

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

——>則環的存在只是產生死鎖的必要條件而不是充分條件

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

死鎖定理

系統為死鎖狀態的充分條件是：當且僅當該狀態的進程-資源分配圖是不可完全簡化的。該充分條件稱為死鎖定理。

簡化進程-資源分配圖

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

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

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

死鎖檢測實例：

問題求解：

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

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

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

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

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

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

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

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

死鎖避免算法則僅根據進程的當前申請資源量來判斷系統是否進入了不安全狀態。

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

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

6、死鎖的解除方法

① 立即結束所有進程的執行，并重新啟動操作系統。以前工作全部作廢，損失可能很大。

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

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

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

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

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