一、死鎖的處理策略——預(yù)防死鎖

（一）破壞互斥條件

互斥條件：只有對必須互斥使用的資源的爭搶才會導(dǎo)致死鎖。

如果把只能互斥使用的資源改造為允許共享使用，則系統(tǒng)不會進(jìn)入死鎖狀態(tài)。比如： SPOOLing技術(shù)。操作系統(tǒng)可以采用 SPOOLing 技術(shù)把獨(dú)占設(shè)備在邏輯上改造成共享設(shè)備。比如，用SPOOLing技術(shù)將打印機(jī)改造為共享設(shè)備…

該策略的缺點(diǎn)：并不是所有的資源都可以改造成可共享使用的資源。并且為了系統(tǒng)安全，很多地方還必須保護(hù)這種互斥性。因此，很多時候都無法破壞互斥條件。

（二）破壞不剝奪條件

不剝奪條件：進(jìn)程所獲得的資源在未使用完之前，不能由其他進(jìn)程強(qiáng)行奪走，只能主動釋放。

破壞不剝奪條件：

①、方案一：當(dāng)某個進(jìn)程請求新的資源得不到滿足時，它必須立即釋放保持的所有資源，待以后需要時再重新申請。也就是說，即使某些資源尚未使用完，也需要主動釋放，從而破壞了不可剝奪條件。

②、方案二：當(dāng)某個進(jìn)程需要的資源被其他進(jìn)程所占有的時候，可以由操作系統(tǒng)協(xié)助，將想要的資源強(qiáng)行剝奪。這種方式一般需要考慮各進(jìn)程的優(yōu)先級（比如：剝奪調(diào)度方式，就是將處理機(jī)資源強(qiáng)行剝奪給優(yōu)先級更高的進(jìn)程使用）

該策略的缺點(diǎn)：

①、實(shí)現(xiàn)起來比較復(fù)雜。

②、釋放已獲得的資源可能造成前一階段工作的失效。因此這種方法一般只適用于易保存和恢復(fù)狀態(tài)的資源，如CPU。

③、反復(fù)地申請和釋放資源會增加系統(tǒng)開銷，降低系統(tǒng)吞吐量。

④、若采用方案一，意味著只要暫時得不到某個資源，之前獲得的那些資源就都需要放棄，以后再重新申請。如果一直發(fā)生這樣的情況，就會導(dǎo)致進(jìn)程饑餓。

（三）破壞請求和保持條件

請求和保持條件：進(jìn)程已經(jīng)保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他進(jìn)程占有，此時請求進(jìn)程被阻塞，但又對自己已有的資源保持不放。

可以采用靜態(tài)分配方法，即進(jìn)程在運(yùn)行前一次申請完它所需要的全部資源，在它的資源未滿足前，不讓它投入運(yùn)行。一旦投入運(yùn)行后，這些資源就一直歸它所有，該進(jìn)程就不會再請求別的任何資源了。

該策略實(shí)現(xiàn)起來簡單，但也有明顯的缺點(diǎn)：

有些資源可能只需要用很短的時間，因此如果進(jìn)程的整個運(yùn)行期間都一直保持著所有資源，就會造成嚴(yán)重的資源浪費(fèi)，資源利用率極低。另外，該策略也有可能導(dǎo)致某些進(jìn)程饑餓。

（四）破壞循環(huán)等待條件

循環(huán)等待條件：存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中的每一個進(jìn)程已獲得的資源同時被下一個進(jìn)程所請求。

可采用順序資源分配法。首先給系統(tǒng)中的資源編號，規(guī)定每個進(jìn)程必須按編號遞增的順序請求資源，同類資源（即編號相同的資源）一次申請完。

原理分析：一個進(jìn)程只有已占有小編號的資源時，才有資格申請更大編號的資源。按此規(guī)則，已持有大編號資源的進(jìn)程不可能逆向地回來申請小編號的資源，從而就不會產(chǎn)生循環(huán)等待的現(xiàn)象。

該策略的缺點(diǎn)：

①、不方便增加新的設(shè)備，因?yàn)榭赡苄枰匦路峙渌械木幪枺?/p>

②、進(jìn)程實(shí)際使用資源的順序可能和編號遞增順序不一致，會導(dǎo)致資源浪費(fèi)；

③、必須按規(guī)定次序申請資源，用戶編程麻煩。

二、死鎖的處理策略——避免死鎖

（一）什么是安全序列

（二）安全序列、不安全狀態(tài)、死鎖的聯(lián)系

所謂安全序列，就是指如果系統(tǒng)按照這種序列分配資源，則每個進(jìn)程都能順利完成。只要能找出一個安全序列，系統(tǒng)就是安全狀態(tài)。當(dāng)然，安全序列可能有多個。

如果分配了資源之后，系統(tǒng)中找不出任何一個安全序列，系統(tǒng)就進(jìn)入了不安全狀態(tài)。這就意味著之后可能所有進(jìn)程都無法順利的執(zhí)行下去。當(dāng)然，如果有進(jìn)程提前歸還了一些資源，那系統(tǒng)也有可能重新回到安全狀態(tài)，不過我們在分配資源之前總是要考慮到最壞的情況。【比如A 先歸還了10億，那么就有安全序列T→B → A】

如果系統(tǒng)處于安全狀態(tài)，就一定不會發(fā)生死鎖。如果系統(tǒng)進(jìn)入不安全狀態(tài)，就可能發(fā)生死鎖（處于不安全狀態(tài)未必就是發(fā)生了死鎖，但發(fā)生死鎖時一定是在不安全狀態(tài)）

因此可以在資源分配之前預(yù)先判斷這次分配是否會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，以此決定是否答應(yīng)資源分配請求。這也是“銀行家算法”的核心思想。

（三）銀行家算法

銀行家算法是荷蘭學(xué)者 Dijkstra 為銀行系統(tǒng)設(shè)計(jì)的，以確保銀行在發(fā)放現(xiàn)金貸款時，不會發(fā)生不能滿足所有客戶需要的情況。后來該算法被用在操作系統(tǒng)中，用于避免死鎖。

核心思想：在進(jìn)程提出資源申請時，先預(yù)判此次分配是否會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)。如果會進(jìn)入不安全狀態(tài)，就暫時不答應(yīng)這次請求，讓該進(jìn)程先阻塞等待。

1. 實(shí)現(xiàn)步驟

以此類推，共五次循環(huán)檢查即可將5個進(jìn)程都加入安全序列中，最終可得一個安全序列。該算法稱為安全性算法。可以很方便地用代碼實(shí)現(xiàn)以上流程，每一輪檢查都從編號較小的進(jìn)程開始檢查。實(shí)際做題時可以更快速的得到安全序列。

2. 銀行家算法示例（手算）

手算（找到安全系列）

手算（找不到安全系列）

3. 代碼實(shí)現(xiàn)

假設(shè)系統(tǒng)中有 n 個進(jìn)程，m 種資源

每個進(jìn)程在運(yùn)行前先聲明對各種資源的最大需求數(shù)，則可用一個 n*m 的矩陣（可用二維數(shù)組實(shí)現(xiàn)）表示所有進(jìn)程對各種資源的最大需求數(shù)。不妨稱為最大需求矩陣 Max，Max［i， j］=K 表示進(jìn)程 Pi 最多需要 K 個資源Rj。同理，系統(tǒng)可以用一個 n*m 的分配矩陣 Allocation表示對所有進(jìn)程的資源分配情況。Max – Allocation =Need 矩陣，表示各進(jìn)程最多還需要多少各類資源。

另外，還要用一個長度為m的一維數(shù)組 Available 表示當(dāng)前系統(tǒng)中還有多少可用資源。

某進(jìn)程Pi向系統(tǒng)申請資源，可用一個長度為m的一維數(shù)組 Requesti表示本次申請的各種資源量。

數(shù)據(jù)結(jié)構(gòu)：

①、長度為 m 的一維數(shù)組 Available 表示還有多少可用資源

②、n*m 矩陣 Max 表示各進(jìn)程對資源的最大需求數(shù)

③、n*m 矩陣 Allocation 表示已經(jīng)給各進(jìn)程分配了多少資源

④、Max – Allocation = Need 矩陣表示各進(jìn)程最多還需要多少資源

⑤、用長度為 m 的一位數(shù)組 Request 表示進(jìn)程此次申請的各種資源數(shù)

銀行家算法步驟：

①、檢查此次申請是否超過了之前聲明的最大需求數(shù)

②、檢查此時系統(tǒng)剩余的可用資源是否還能滿足這次請求

③、試探著分配，更改各數(shù)據(jù)結(jié)構(gòu)

④、用安全性算法檢查此次分配是否會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)

安全性算法步驟：

①、檢查當(dāng)前的剩余可用資源是否能滿足某個進(jìn)程的最大需求，如果可以，就把該進(jìn)程加入安全序列，并把該進(jìn)程持有的資源全部回收。

②、不斷重復(fù)上述過程，看最終是否能讓所有進(jìn)程都加入安全序列。

系統(tǒng)處于不安全狀態(tài)未必死鎖，但死鎖時一定處于不安全狀態(tài)。系統(tǒng)處于安全狀態(tài)一定不會死鎖。

三、死鎖的處理策略——檢測和解除

如果系統(tǒng)中既不采取預(yù)防死鎖的措施，也不采取避免死鎖的措施，系統(tǒng)就很可能發(fā)生死鎖。在這種情況下，系統(tǒng)應(yīng)當(dāng)提供兩個算法：

①死鎖檢測算法：用于檢測系統(tǒng)狀態(tài)，以確定系統(tǒng)中是否發(fā)生了死鎖。

②死鎖解除算法：當(dāng)認(rèn)定系統(tǒng)中已經(jīng)發(fā)生了死鎖，利用該算法可將系統(tǒng)從死鎖狀態(tài)中解脫出來。

（一）死鎖的檢測

為了能對系統(tǒng)是否已發(fā)生了死鎖進(jìn)行檢測，必須：

①用某種數(shù)據(jù)結(jié)構(gòu)來保存資源的請求和分配信息；

②提供一種算法，利用上述信息來檢測系統(tǒng)是否已進(jìn)入死鎖狀態(tài)。

如果系統(tǒng)中剩余的可用資源數(shù)足夠滿足進(jìn)程的需求，那么這個進(jìn)程暫時是不會阻塞的，可以順利地執(zhí)行下去。

如果這個進(jìn)程執(zhí)行結(jié)束了把資源歸還系統(tǒng)，就可能使某些正在等待資源的進(jìn)程被激活，并順利地執(zhí)行下去。相應(yīng)的，這些被激活的進(jìn)程執(zhí)行完了之后又會歸還一些資源，這樣可能又會激活另外一些阻塞的進(jìn)程…

如果按上述過程分析，最終能消除所有邊，就稱這個圖是可完全簡化的。此時一定沒有發(fā)生死鎖（相當(dāng)于能找到一個安全序列）

如果最終不能消除所有邊，那么此時就是發(fā)生了死鎖

最終還連著邊的那些進(jìn)程就是處于死鎖狀態(tài)的進(jìn)程。

（二）死鎖的解除

一旦檢測出死鎖的發(fā)生，就應(yīng)該立即解除死鎖。

補(bǔ)充：并不是系統(tǒng)中所有的進(jìn)程都是死鎖狀態(tài)，用死鎖檢測算法化簡資源分配圖后，還連著邊的那些進(jìn)程就是死鎖進(jìn)程

解除死鎖的主要方法有：

①、 資源剝奪法 。掛起（暫時放到外存上）某些死鎖進(jìn)程，并搶占它的資源，將這些資源分配給其他的死鎖進(jìn)程。但是應(yīng)防止被掛起的進(jìn)程長時間得不到資源而饑餓。

②、 撤銷進(jìn)程法（或稱終止進(jìn)程法） 。強(qiáng)制撤銷部分、甚至全部死鎖進(jìn)程，并剝奪這些進(jìn)程的資源。這種方式的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，但所付出的代價(jià)可能會很大。因?yàn)橛行┻M(jìn)程可能已經(jīng)運(yùn)行了很長時間，已經(jīng)接近結(jié)束了，一旦被終止可謂功虧一簣，以后還得從頭再來。

③、 進(jìn)程回退法 。讓一個或多個死鎖進(jìn)程回退到足以避免死鎖的地步。這就要求系統(tǒng)要記錄進(jìn)程的歷史信息，設(shè)置還原點(diǎn)。

原文標(biāo)題：死鎖的處理策略—預(yù)防死鎖、避免死鎖、檢測和解除死鎖

文章出處：【微信公眾號：一口Linux】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。