在多道程序環(huán)境中，多個進程可以競爭有限數(shù)量的資源。當進程申請資源時，如果沒有可用資源，那么這個進程進入等待狀態(tài)。有時，如果所申請的資源被其它等待進程占有，那么該進程可能再也無法改變狀態(tài)。這種情況稱為死鎖。

一、系統(tǒng)模型

資源分為多種類型，每種類型有一定數(shù)量的實例。

• 資源類型R1, R2, . . ., Rm, 如CPU, 內(nèi)存空間, I/O 設(shè)備，文件
• 每個資源類型Ri有Wi個實例

正常操作模式下，進程只按如下順序使用資源:

1. 申請：進程請求資源
2. 使用：進程對資源進行操作
3. 釋放：進程釋放資源

當一組進程中的每個進程都在等待一個事件的發(fā)生，而這一事件只能由這一組進程的另一進程引起，那么這組進程就處于死鎖狀態(tài)

二、死鎖特征

1.必要條件

如果在一個系統(tǒng)如下四個條件同時成立，就會引起死鎖：

• 互斥(mutual excusive)：至少有一個資源只能由一個進程占用（非共享）
• 占用并等待：一個進程應占用至少一個資源，并請求/等待另一個資源
• 非搶占：資源不能被搶占
• 循環(huán)等待：有一組等待進程{P0, P1, …, Pn}，P0等待的資源被P1所占用，P1等待的資源被P2 所占用，…，Pn–1等待的資源被Pn所占用，Pn等待的資源被P0所占用

2.資源分配圖

通過系統(tǒng)資源分配圖的有向圖可以更精確的描述死鎖。

資源分配圖由一個節(jié)點集合V和一個邊集合E組成。

1.節(jié)點集合V分為進程集合P和資源集合R

• 進程節(jié)點集合：P = {P1, P2, …, Pn}
• 資源節(jié)點集合：R = {R1, R2, …, Rm}

2 邊集合E

• Pi → Rj，表示進程Pi 已經(jīng)申請使用資源類型Rj的一個實例，并等待這個資源
• Rj → Pi，表示資源類型Rj的一個實例已經(jīng)分配給進程Pi

上圖一個成環(huán)是死鎖，一個成環(huán)不是死鎖

根據(jù)資源分配圖的定義，可以證明：

1. 如果分配圖沒有環(huán)，就沒有死鎖
2. 如果分配圖有環(huán)，就有可能發(fā)生死鎖如果每個資源類型只有一個實例，就肯定會發(fā)生死鎖
   如果每個資源類型有多個實例，就有可能處于死鎖

三、死鎖處理方法

一般來說，處理死鎖問題有三種方法：

預防或避免（prevention or avoidance）

• 預防死鎖：確保?少?個必要條件不成?
• 避免死鎖：利?事先得到進程申請資源和使?資源的額外信息，判斷每當發(fā)?資源請求時是否會發(fā)?死鎖

發(fā)生死鎖，檢測并恢復。確定死鎖是否確實發(fā)?， 并提供算法從死鎖中恢復

忽視死鎖問題，認為死鎖不會發(fā)生

四、死鎖預防

發(fā)生死鎖有4個必要條件，所以只要確保至少一個必要條件不成立，就能預防死鎖發(fā)生

1.互斥

通常不能通過否定互斥條件來預防死鎖

可共享的資源不要求互斥訪問，如只讀?件；但不可共享的資源本身就是非共享的，必須要確保互斥，如打印機，一個互斥鎖

2.占用并等待

為否定這一條件，應保證：當一個進程請求一個資源時，它不能占有其他資源。

實現(xiàn)的方法如下：

1. 每個進程在執(zhí)?前申請并獲得所有資源
2. 另一種是進程只有在不占?資源時, 才允許申請資源

注意：讓互斥和占?并等待不成?、兩種?法的缺點是資源利?率低和可能發(fā)?饑餓問題

3.非搶占

為了確保這一條件不成立，可以是使用如下協(xié)議：

如果一個進程占有資源并申請另一個不能分配的資源（也就是說，這個進程應該等待），那么其現(xiàn)已分配的資源可被搶占。

如果一個進程申請一些資源，那么首先檢查它們是否可用。

1. 如果可?，就分配。
2. 如果不可?，檢查這些資源是否已分配給其他等待額外資源的進程，如果是，那么就搶占。
3. 如果不可?，且也沒有被其他等待額外資源的進程占有，那么就等待

4.循環(huán)等待

確保其不成立地一個方法：對所有資源類型進行完全排序，且要求每個進程按遞增順序來申請資源。

假設(shè)資源類型集合R={R1,R2…Rn}，為每個資源類型分配一個唯一的整數(shù)，形式地，定義一個函數(shù)F：R → N（N為自然數(shù)集合）

可采用如下協(xié)議預防死鎖：

每個進程只能按遞增順序來申請資源，即一個進程開始可以申請任何數(shù)量的資源類型Ri的實例，之后，僅當F(Rj)>F(Ri)時，進程才能申請資源類型Rj的實例

五、死鎖避免

采用上述死鎖預防中的的方法來預防死鎖有副作用：設(shè)備使用率低和系統(tǒng)吞吐率低。

避免死鎖的另一種方法，需要額外信息，即如何申請資源。在獲悉每個進程的請求和釋放的完整順序后，系統(tǒng)可以決定，在每次請求時是否應該等待以避免未來可能的死鎖。

需要掌握的額外信息包括：

1. 當前可用資源
2. 已分配給每個進程的資源
3. 每個進程將來要申請或釋放的資源
4. 每個進程可能申請的每種資源類型實例的需求

針對每次申請，系統(tǒng)在做決定時考慮現(xiàn)有可用資源、現(xiàn)已分配給每個進程的資源、每個進程將來申請和釋放的資源來申請與釋放資源

鑒于這些先驗信息，可構(gòu)造算法確保系統(tǒng)不會進入死鎖狀態(tài)。避免死鎖是動態(tài)的方法，它根據(jù)進程申請資源的附加信息決定是否申請資源

1.安全狀態(tài)

如果系統(tǒng)按一定順序（存在一個順序）為每個進程分配資源（不超過它的最大需求），且能避免死鎖，那么系統(tǒng)狀態(tài)就是安全的，如果沒有，系統(tǒng)狀態(tài)就是非安全的

避免死鎖指的是確保系統(tǒng)不進入不安全狀態(tài)

2.資源分配圖法

適用于每個資源具有單個實例。

由上一節(jié)的資源分配圖的變形可以避免死鎖

除原來的申請邊和分配邊，引入了新的類型邊叫需求邊。需求邊用虛線Pi - - > Rj，表示進程Pi可能在將來某個時刻申請資源Rj；當進程Pi申請資源Rj時，需求邊變成申請邊（虛線變成實線）；當進程Pi釋放資源Rj時，分配變成需求邊

算法規(guī)則：只有在將申請邊變成分配邊而不會導致資源分配圖形成環(huán)時，才允許申請資源。

假設(shè)進程Pi申請資源Rj，對資源的申請，把申請邊變成分配邊后，如果沒有環(huán)就允許申請，如有環(huán)就不允許申請

下圖中如果將R2分配給P2，就會創(chuàng)建一個環(huán)，表示系統(tǒng)處于非安全狀態(tài)。

3.銀行家算法

適用于每個資源具有多個實例

當一個新進程進入系統(tǒng)時，它應聲明可能需要的每種類型資源實例的最大數(shù)量，當然這不能超過系統(tǒng)資源總和。當用戶申請一組資源時，系統(tǒng)應確定這些資源的分配是否會使系統(tǒng)處于安全狀態(tài)，如果會，就可以分配；否則進程應等待，直到某個進程釋放了做夠多的資源為止。

為實現(xiàn)這一算法，引入一些數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)都資源分配系統(tǒng)的狀態(tài)進行了記錄

安全性算法：確定計算機系統(tǒng)是否處于安全狀態(tài)的算法。

STEP 1:

Work 和Finish 分別為長度m 和n的向量, 分別初始化為:

Work = Available //可分配的資源數(shù)

Finish [ i ] = false for i = 0, 1, …, n- 1

STEP 2:

查找i使其滿足：Finish [ i ] = false && Need i <= Work

如果沒有滿足以上條件的i, 那么就跳轉(zhuǎn)到STEP 4

STEP 3:

Work = Work + Allocation i

Finish[ i ] = true

返回到STEP 2

STEP 4:

如果對所有i, Finish[i] == true 那么系統(tǒng)處于安全狀態(tài)，如果不是就處于不安全狀態(tài)

資源請求算法：判斷是否可安全允許請求的算法。

每次進程請求資源的時候，運行資源請求檢測算法，確認是否允許請求

設(shè)Request i 為進程P i 的請求向量，當進程Pi作出資源請求時，采取如下操作:

STEP 1:

如果Requesti <= Need i , 那么轉(zhuǎn)到STEP 2. 否則，產(chǎn)生出錯條件，這是因為進程Pi 已超過了其最大請求

STEP 2:

如果Requesti <= Available, 那么轉(zhuǎn)到STEP 3. 否則Pi必須等待，這是因為沒有可用資源

STEP 3:

假定系統(tǒng)可以分配給進程Pi所請求的資源，則修改資源分配狀態(tài)，進入安全性檢查

1. 如果所產(chǎn)生的資源分配狀態(tài)是安全的，那么Pi 可分配到其所需要資源.
2. 如果所產(chǎn)生的資源分配狀態(tài)是不安全的，那么Pi 必須等待并恢復到原來資源分配狀態(tài)

4.銀行家算法實例

假設(shè)一個系統(tǒng)，有5個進程：P0、P1、P2、P3、P4。3 種資源類型: A (10個實例), B (5個實例),C (7個實例)。

假定在時間T0，系統(tǒng)資源分配狀態(tài)如下：

執(zhí)行算法過程：

查找滿足如下條件的i :Finish [ i ] = false && Needi <= Work

發(fā)現(xiàn)P1滿足以上條件，則Finish[1] 設(shè)置為1，

Work = Work + Allocationi；

Work = 【3,3,2】+ 【2,0,0】

繼續(xù)往下查找，

發(fā)現(xiàn)P3 滿足條件，則Finish[3]設(shè)置為1，

Work = 【5,3,2】+ 【2,1,1】= 【7,4,3】；

繼續(xù)往下查找，

發(fā)現(xiàn)P4 滿足條件，則Finish[4]設(shè)置為1，

Work = 【7,4,3】+ 【0,0,2】= 【7,4,5】；

繼續(xù)往下查找，

發(fā)現(xiàn)P0滿足條件，則Finish[0]設(shè)置為1，

Work = 【7,4,5】+ 【0,1,0】= 【7,5,5】；

繼續(xù)往下查找，

發(fā)現(xiàn)P2滿足條件，則Finish[2]設(shè)置為1，

Work = 【7,5,5】+ 【3,0,2】= 【10,5,7】；

此時Finish都為true，說明分配資源后，系統(tǒng)仍出于安全狀態(tài)，安全順序為【P1,P3,P4,P0,P2】

對上述例子及銀行家算法和安全狀態(tài)的理解：

銀行家算法算的是是否可以分配給某個進程某些資源，所以假設(shè)系統(tǒng)把資源分配后，去判斷系統(tǒng)是否仍處于安全狀態(tài)。上面例子T0時刻的資源狀態(tài)，其實就是某個進程請求了某些資源后的一個狀態(tài)，算法需要去判斷這個狀態(tài)是否安全，如果安全便可以分配。

上文提到了什么是安全狀態(tài)，即在當前資源分配下，存在一個序列使所有進程運行不死鎖。關(guān)鍵在于如何知道存在，銀行家算法模擬了最壞情況，即進程每次都請求最大數(shù)量的Need（顯然實際環(huán)境中進程可能只請求一個實例），如果這樣分配資源仍然能使所有進程都完成，那顯然這個序列就是存在的，系統(tǒng)就是安全的

六、死鎖檢測

如果一個系統(tǒng)既不采用死鎖預防算法也不采用死鎖避免算法，那死鎖可能出現(xiàn)，這種環(huán)境下系統(tǒng)可以提供：

1. 檢測算法：確定系統(tǒng)是否進入死鎖
2. 恢復算法：從死鎖狀態(tài)中恢復

需要從如下兩個方面分別考慮這個問題：

1. 第一個方面，每個資源類型有單個實例
2. 另一個方面，每個資源類型有多個實例

1.每種資源類型只有單個實例

檢測算法：用等待圖，它是資源分配圖的一個變形，從資源分配圖中刪除所有資源類型節(jié)點，合并適當邊，就能得到等待圖。

• 每個節(jié)點是進程
• Pi → Pj 意味著進程Pi等待進程Pj釋放一個Pi所需的資源

如等待圖中有環(huán)，系統(tǒng)中存在死鎖。

為檢測死鎖，系統(tǒng)需要維護等待圖，并周期性的調(diào)用在圖中進行搜索環(huán)的算法

2.每種資源類型可有多個實例

類似于銀行家算法

3.應用檢測算法

何時調(diào)用算法取決于:

1. 死鎖發(fā)生的頻率
2. 死鎖發(fā)生時，有多少進程會受影響

每次資源請求調(diào)用檢測算法

每次資源請求不被允許時調(diào)用檢測算法

七、死鎖恢復

當檢測算法確定已有死鎖是，需要打破。打破死鎖有兩個選擇，一個是簡單的終止一個或多個進程來打破循環(huán)等待；另一個是從一個或多個進程那里搶占一個或多個資源

1.終止進程

兩種方法：

1. 終止所有死鎖進程
2. 一次只終止一個進程直到取消死鎖循環(huán)為止

如果采用部分終止，我們應該終止造成最小代價的進程，許多因素影響了選擇哪個進程：

• 進程的優(yōu)先級
• 進程已計算了多久，進程在完成指定任務之前還需要多久
• 進程使用了多少數(shù)量的何種類型的資源
• 進程需要多少資源以完成
• 多少資源需要被終止
• 進程是交互的還是批處理的

2.資源搶占

通過搶占資源以取消死鎖，逐步從進程中搶占資源給其他進程使用，直到死鎖被打破為止。

需要處理三個問題

1. 選擇犧牲品：搶占哪些資源和哪個進程
2. 需要考慮饑餓：避免同一個進程總成為犧牲品
3. 回滾(Rollback)：必須把不能正常運行的進程，回滾到某個安全狀態(tài)，以便重啟進程