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

一、系統(tǒng)模型

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

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

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

1. 申請(qǐng)：進(jìn)程請(qǐng)求資源
2. 使用：進(jìn)程對(duì)資源進(jìn)行操作
3. 釋放：進(jìn)程釋放資源

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

二、死鎖特征

1.必要條件

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

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

2.資源分配圖

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

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

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

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

2 邊集合E

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

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

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

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

三、死鎖處理方法

一般來(lái)說(shuō)，處理死鎖問(wèn)題有三種方法：

預(yù)防或避免（prevention or avoidance）

• 預(yù)防死鎖：確保?少?個(gè)必要條件不成?
• 避免死鎖：利?事先得到進(jìn)程申請(qǐng)資源和使?資源的額外信息，判斷每當(dāng)發(fā)?資源請(qǐng)求時(shí)是否會(huì)發(fā)?死鎖

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

忽視死鎖問(wèn)題，認(rèn)為死鎖不會(huì)發(fā)生

四、死鎖預(yù)防

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

1.互斥

通常不能通過(guò)否定互斥條件來(lái)預(yù)防死鎖

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

2.占用并等待

為否定這一條件，應(yīng)保證：當(dāng)一個(gè)進(jìn)程請(qǐng)求一個(gè)資源時(shí)，它不能占有其他資源。

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

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

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

3.非搶占

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

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

如果一個(gè)進(jìn)程申請(qǐng)一些資源，那么首先檢查它們是否可用。

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

4.循環(huán)等待

確保其不成立地一個(gè)方法：對(duì)所有資源類型進(jìn)行完全排序，且要求每個(gè)進(jìn)程按遞增順序來(lái)申請(qǐng)資源。

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

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

每個(gè)進(jìn)程只能按遞增順序來(lái)申請(qǐng)資源，即一個(gè)進(jìn)程開始可以申請(qǐng)任何數(shù)量的資源類型Ri的實(shí)例，之后，僅當(dāng)F(Rj)>F(Ri)時(shí)，進(jìn)程才能申請(qǐng)資源類型Rj的實(shí)例

五、死鎖避免

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

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

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

1. 當(dāng)前可用資源
2. 已分配給每個(gè)進(jìn)程的資源
3. 每個(gè)進(jìn)程將來(lái)要申請(qǐng)或釋放的資源
4. 每個(gè)進(jìn)程可能申請(qǐng)的每種資源類型實(shí)例的需求

針對(duì)每次申請(qǐng)，系統(tǒng)在做決定時(shí)考慮現(xiàn)有可用資源、現(xiàn)已分配給每個(gè)進(jìn)程的資源、每個(gè)進(jìn)程將來(lái)申請(qǐng)和釋放的資源來(lái)申請(qǐng)與釋放資源

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

1.安全狀態(tài)

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

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

2.資源分配圖法

適用于每個(gè)資源具有單個(gè)實(shí)例。

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

除原來(lái)的申請(qǐng)邊和分配邊，引入了新的類型邊叫需求邊。需求邊用虛線Pi - - > Rj，表示進(jìn)程Pi可能在將來(lái)某個(gè)時(shí)刻申請(qǐng)資源Rj；當(dāng)進(jìn)程Pi申請(qǐng)資源Rj時(shí)，需求邊變成申請(qǐng)邊（虛線變成實(shí)線）；當(dāng)進(jìn)程Pi釋放資源Rj時(shí)，分配變成需求邊

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

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

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

3.銀行家算法

適用于每個(gè)資源具有多個(gè)實(shí)例

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

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

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

STEP 1:

Work 和Finish 分別為長(zhǎng)度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:

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

資源請(qǐng)求算法：判斷是否可安全允許請(qǐng)求的算法。

每次進(jìn)程請(qǐng)求資源的時(shí)候，運(yùn)行資源請(qǐng)求檢測(cè)算法，確認(rèn)是否允許請(qǐng)求

設(shè)Request i 為進(jìn)程P i 的請(qǐng)求向量，當(dāng)進(jìn)程Pi作出資源請(qǐng)求時(shí)，采取如下操作:

STEP 1:

如果Requesti <= Need i , 那么轉(zhuǎn)到STEP 2. 否則，產(chǎn)生出錯(cuò)條件，這是因?yàn)檫M(jìn)程Pi 已超過(guò)了其最大請(qǐng)求

STEP 2:

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

STEP 3:

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

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

4.銀行家算法實(shí)例

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

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

執(zhí)行算法過(guò)程：

查找滿足如下條件的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】；

此時(shí)Finish都為true，說(shuō)明分配資源后，系統(tǒng)仍出于安全狀態(tài)，安全順序?yàn)椤綪1,P3,P4,P0,P2】

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

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

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

六、死鎖檢測(cè)

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

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

需要從如下兩個(gè)方面分別考慮這個(gè)問(wèn)題：

1. 第一個(gè)方面，每個(gè)資源類型有單個(gè)實(shí)例
2. 另一個(gè)方面，每個(gè)資源類型有多個(gè)實(shí)例

1.每種資源類型只有單個(gè)實(shí)例

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

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

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

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

2.每種資源類型可有多個(gè)實(shí)例

類似于銀行家算法

3.應(yīng)用檢測(cè)算法

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

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

每次資源請(qǐng)求調(diào)用檢測(cè)算法

每次資源請(qǐng)求不被允許時(shí)調(diào)用檢測(cè)算法

七、死鎖恢復(fù)

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

1.終止進(jìn)程

兩種方法：

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

如果采用部分終止，我們應(yīng)該終止造成最小代價(jià)的進(jìn)程，許多因素影響了選擇哪個(gè)進(jìn)程：

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

2.資源搶占

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

需要處理三個(gè)問(wèn)題

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