一、死鎖的處理策略——預防死鎖

（一）破壞互斥條件

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

如果把只能互斥使用的資源改造為允許共享使用，則系統不會進入死鎖狀態。比如： SPOOLing技術。操作系統可以采用 SPOOLing 技術把獨占設備在邏輯上改造成共享設備。比如，用SPOOLing技術將打印機改造為共享設備…

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

（二）破壞不剝奪條件

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

破壞不剝奪條件：

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

②、方案二：當某個進程需要的資源被其他進程所占有的時候，可以由操作系統協助，將想要的資源強行剝奪。這種方式一般需要考慮各進程的優先級（比如：剝奪調度方式，就是將處理機資源強行剝奪給優先級更高的進程使用）

該策略的缺點：

①、實現起來比較復雜。

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

③、反復地申請和釋放資源會增加系統開銷，降低系統吞吐量。

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

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

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

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

該策略實現起來簡單，但也有明顯的缺點：

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

（四）破壞循環等待條件

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

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

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

該策略的缺點：

①、不方便增加新的設備，因為可能需要重新分配所有的編號；

②、進程實際使用資源的順序可能和編號遞增順序不一致，會導致資源浪費；

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

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

（一）什么是安全序列

（二）安全序列、不安全狀態、死鎖的聯系

所謂安全序列，就是指如果系統按照這種序列分配資源，則每個進程都能順利完成。只要能找出一個安全序列，系統就是安全狀態。當然，安全序列可能有多個。

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

如果系統處于安全狀態，就一定不會發生死鎖。如果系統進入不安全狀態，就可能發生死鎖（處于不安全狀態未必就是發生了死鎖，但發生死鎖時一定是在不安全狀態）

因此可以在資源分配之前預先判斷這次分配是否會導致系統進入不安全狀態，以此決定是否答應資源分配請求。這也是“銀行家算法”的核心思想。

（三）銀行家算法

銀行家算法是荷蘭學者 Dijkstra 為銀行系統設計的，以確保銀行在發放現金貸款時，不會發生不能滿足所有客戶需要的情況。后來該算法被用在操作系統中，用于避免死鎖。

核心思想：在進程提出資源申請時，先預判此次分配是否會導致系統進入不安全狀態。如果會進入不安全狀態，就暫時不答應這次請求，讓該進程先阻塞等待。

1. 實現步驟

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

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

手算（找到安全系列）

手算（找不到安全系列）

3. 代碼實現

假設系統中有 n 個進程，m 種資源

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

另外，還要用一個長度為m的一維數組 Available 表示當前系統中還有多少可用資源。

某進程Pi向系統申請資源，可用一個長度為m的一維數組 Requesti表示本次申請的各種資源量。

數據結構：

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

②、n*m 矩陣 Max 表示各進程對資源的最大需求數

③、n*m 矩陣 Allocation 表示已經給各進程分配了多少資源

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

⑤、用長度為 m 的一位數組 Request 表示進程此次申請的各種資源數

銀行家算法步驟：

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

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

③、試探著分配，更改各數據結構

④、用安全性算法檢查此次分配是否會導致系統進入不安全狀態

安全性算法步驟：

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

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

系統處于不安全狀態未必死鎖，但死鎖時一定處于不安全狀態。系統處于安全狀態一定不會死鎖。

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

如果系統中既不采取預防死鎖的措施，也不采取避免死鎖的措施，系統就很可能發生死鎖。在這種情況下，系統應當提供兩個算法：

①死鎖檢測算法：用于檢測系統狀態，以確定系統中是否發生了死鎖。

②死鎖解除算法：當認定系統中已經發生了死鎖，利用該算法可將系統從死鎖狀態中解脫出來。

（一）死鎖的檢測

為了能對系統是否已發生了死鎖進行檢測，必須：

①用某種數據結構來保存資源的請求和分配信息；

②提供一種算法，利用上述信息來檢測系統是否已進入死鎖狀態。

如果系統中剩余的可用資源數足夠滿足進程的需求，那么這個進程暫時是不會阻塞的，可以順利地執行下去。

如果這個進程執行結束了把資源歸還系統，就可能使某些正在等待資源的進程被激活，并順利地執行下去。相應的，這些被激活的進程執行完了之后又會歸還一些資源，這樣可能又會激活另外一些阻塞的進程…

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

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

最終還連著邊的那些進程就是處于死鎖狀態的進程。

（二）死鎖的解除

一旦檢測出死鎖的發生，就應該立即解除死鎖。

補充：并不是系統中所有的進程都是死鎖狀態，用死鎖檢測算法化簡資源分配圖后，還連著邊的那些進程就是死鎖進程

解除死鎖的主要方法有：

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

②、 撤銷進程法（或稱終止進程法） 。強制撤銷部分、甚至全部死鎖進程，并剝奪這些進程的資源。這種方式的優點是實現簡單，但所付出的代價可能會很大。因為有些進程可能已經運行了很長時間，已經接近結束了，一旦被終止可謂功虧一簣，以后還得從頭再來。

③、 進程回退法 。讓一個或多個死鎖進程回退到足以避免死鎖的地步。這就要求系統要記錄進程的歷史信息，設置還原點。

原文標題：死鎖的處理策略—預防死鎖、避免死鎖、檢測和解除死鎖

文章出處：【微信公眾號：一口Linux】歡迎添加關注！文章轉載請注明出處。