武林網訊

1、為什么會出現死鎖

   1.1、一個簡單的例子

   有兩個進程準備掃描文檔并記錄到CD上。進程A請求掃描儀并獲取，而進程B先請求CD刻錄機并獲取。然后進程A請求CD刻錄機，失敗了，因為進程B已經擁有了CD刻錄機并不愿釋放，而且還要請求掃描儀以完成工作。結果是，兩個進程誰也無法完成工作，死鎖出現了。

   1.2、關于資源

   掃描儀就是一種資源，從上面可以看出，對資源的請求是發生死鎖的根本。其實資源可以是硬件設備（如CD刻錄機）或是一組信息（如數據庫中一個加鎖的記錄），簡單來說資源就是能夠獲得、使用以及使用完之后釋放的任何東西。

資源分為兩類：可搶占的和不可搶占的。可搶占是指資源從擁有它的進程中搶占而不會產生副作用，從這可以看出，對可搶占資源的使用發生死鎖時通過重新分配資源就可以解決。

其實有較少部分的死鎖不是因為資源而導致的，這里不做討論。

2、死鎖建模

   2.1、死鎖的規范定義

   如果一個進程集合中的每個進程都在等待只能由該進程集合中的其他進程才能引發的事件，那么，該進程集合就是死鎖的。

   既然是每個進程都在等待，結果就是每個進程都無法引發能夠滿足其他進程的事件，所有進程都會一直等待。用資源使用的話來說就是，每個進程都還需要另外的資源才能繼續，而擁有這些資源的進程不會釋放它們，因為這些進程都由于沒有足夠的資源而繼續。

   2.2、資源死鎖的條件及應對策略

   2.2.1、資源死鎖的發生有4個必要條件：①互斥條件。也就是說一個資源不能被多個進程同時使用。②占有和等待條件。已經得到某個資源的進程還可以繼續請求另外的資源。③不可搶占條件。如上所述，資源被搶占時會引發副作用，只能由擁有它的進程顯式釋放。④環路等待條件。存在一種進程循環鏈，鏈中每一個進程已獲得的資源同時被下一個進程所請求。

   2.2.2、有四種處理死鎖的策略：①忽略該問題。②檢測死鎖并恢復。③小心分配資源，避免死鎖的發生。④通過破壞引起死鎖的4個必要條件之一，防止死鎖發生。下面分別討論這幾種策略。

3、鴕鳥算法

   該算法對應上面的第一種策略：忽略。被叫做鴕鳥算法是緣于這樣的一個民間傳說：鴕鳥在遇到問題時就會把頭埋在沙子里，什么也不管，假裝沒有問題發生。也許你會感到很糾結：怎么會有這樣一個扯淡的算法的？對于數學家，他們的想法跟你一樣，絕不能容忍什么也不做的策略。但對于工程師來說，他們卻會認真地考慮鴕鳥算法。當死鎖發生的概率很低很低，而有一大堆其他問題等著解決時，他們就會對死鎖問題采取鴕鳥算法。

4、死鎖檢測與死鎖恢復

   死鎖檢測基于前面提到的環路，也就是檢測進程對資源的擁有和請求是否形成了環路，若是，側說明死鎖存在。本文是“簡述”，不對檢測算法作具體描述。

死鎖恢復的方法有3種：①利用搶占恢復。②利用回滾恢復。恢復到更早的狀態。③通過殺死進程恢復。實際上，這些方法都不是好方法，有很多缺陷。

5、死鎖避免

   避免死鎖的主要算法基于安全狀態的概念。而安全狀態是指，如果沒有死鎖發生，并且即使所有進程突然請求對資源的最大需求，也仍然存在某種調度次序能夠使得每一個進程運行完畢，則稱該狀態是安全的。

死鎖避免最著名的算法是銀行家算法，就是對每一個請求進行檢查，如果滿足這一請求后還是安全狀態，則滿足之，否則推遲對這一請求的滿足。

6、死鎖預防

   死鎖預防就是要破壞引起死鎖的4個必要條件之一。①破壞互斥條件。使用假脫機技術，模擬多個進程同時占用一個資源。②破壞占用和等待條件。規定所有進程在開始執行之前先請求并獲得所需的所有資源。③破壞不可搶占條件。也是使用假脫機技術。④破壞環路等待條件。將所有資源統一編號，進程在請求多個資源時按順序請求。

7、總結

   沒有完美應對死鎖的辦法，也沒有普遍適用的方法。只能在不同的情況下，綜合考慮各種策略，制定一定程度上滿足要求的算法。