與死鎖的有關知識簡述

我們先來舉例認識一下死鎖：

例如，系統中隻有一台掃描器R1和一台刻錄機R2。有兩個程序P1和P2,他們都準備将掃描的檔案刻錄到CDCD光牒上，程序P1先請求掃描器R1并獲得成功，程序P2先請求刻錄機也獲得成功。後來P1又請求CD刻錄機，因它已被配置設定給了P2而阻塞。P2又請求掃描器，也因被配置設定給了P1而阻塞。

此時兩個程序都被阻塞，雙方都希望對方能釋放出自己所需要的資源，但它們都因不能獲得自己所需要的資源去繼續運作，進而無法釋放自己占有的資源，并且一直處于這樣的僵持狀态而形成死鎖。

一、資源問題

了解死鎖之前我們應先了解一下資源的各種不同類型。

1、可重用性資源

顧名思義，是一種可供使用者重複使用多次的資源，有如下性質：

（1）每一個可重用資源中的單元隻能配置設定給一個程序使用，不允許多個程序共享。

（2）程序在使用時，須按照順序：

請求資源，如果失敗，程序将會被阻塞或循環等待。

使用資源；

釋放資源。

（3）系統中每一類可重用性資源中的單元數目是相對固定的，程序在運作期間既不能建立也不能删除它。

2、可消耗資源

又稱為臨時性資源，是在程序運作期間，由程序動态的建立和消耗的，具有如下性質：

（1）每一類可消耗性資源的單元數目在程序運作期間是可以不斷變化的，甚至有時可能為0

（2）程序在運作過程中，可以不斷的創造可消耗性資源的單元，将它們放入該資源類的緩沖區中，增加該資源類的單元數目。

（3）程序在運作過程中，可以請求若幹個可消耗性資源單元，用于自己的消耗，不再将它們傳回給該資源類中。

3、可搶占性資源

指某程序在獲得這類資源後，該資源可以再被其他程序或系統搶占。

對于這類資源是不會引起死鎖的。

4、不可搶占性資源

即一旦系統把某資源配置設定給該程序後，就不能将它強行收回，隻能在程序用完後自行釋放。

二、死鎖的起因

死鎖的起因，通常是源于多個程序對資源的争奪，不僅對不可搶占資源進行搶奪時會引起死鎖，而且對可消耗資源進行争奪時，也會引起死鎖。

1、競争不可搶占性資源引起死鎖

通常系統中所擁有的不可搶占性資源其數量不足以滿足多個程序運作的需要，使得程序在運作過程中，會因争奪資源而陷于僵局。

2、競争可消耗性資源引起死鎖

若在程序通信時，程序先執行讀資料的操作，就會在等待一條沒發出的消息，就可能産生死鎖。

3、程序推進順序不當引起死鎖

程序在運作過程中，對資源進行申請和釋放的順序是否合法，也是在系統中是否會産生死鎖的一個重要因素。

三、死鎖的概念

1、定義

如果一組程序中的每一個程序都在等待僅由該組程序中的其他程序才能引發的事件，那麼該程序是死鎖的。

2、産生死鎖的必要條件

（1）互斥條件：程序對所配置設定資源進行排它性使用。

（2）請求和保持條件：程序已經保持了一個資源，但又提出了新的資源請求，而該資源已經被其他程序占有，此時請求程序被阻塞。

（3）不可搶占條件：程序已獲得的資源在未使用完之前不能被搶占，隻能在程序使用完時自己釋放。 

（4）循環等待條件：在發生死鎖時，必然存在資源的循環鍊，即程序集合依次循環等待。

四、處理死鎖的方法

1、預防死鎖

預防死鎖的方法，即是通過設定某些限制條件，去破壞産生死鎖的四個必要條件中的一個或者幾個，以此預防死鎖。

主要有以下幾種方法：

（1）破壞“請求和保持”條件

破壞該條件，有一個條件：當一個程序在請求資源時，它不能持有不可搶占資源。

該保證可通過以下兩個協定實作：

第一種協定：

該協定規定，所有程序在開始運作之前，必須一次性的申請其在整個運作過程中所需的全部資源，進而破壞上面講過的“請求”條件。

若有一種資源不能滿足程序的要求，那麼其他資源也不會配置設定給該程序，該程序就會等待，破壞了“保持”條件。

該協定的優點是簡單、易行且安全，缺點是資源被嚴重浪費，惡化了資源的使用率，使程序會經常發生饑餓現象。

第二種協定：

允許一個程序隻獲得初期運作所需要的資源後，便開始運作。程序運作過程中再逐漸釋放已配置設定給自己的、且已用畢的全部資源，然後再請求新的所需資源。

（2）破壞“不可搶占”條件

該協定中規定，當一個已經保持了某些不可搶占資源的程序，提出了新的資源請求而不能得到滿足時，它必須釋放已經保持的所有資源，待以後需要時再重新申請，進而破壞了“不可搶占”條件。

該方法實作複雜，延長了程序的周轉時間，而且也增加了系統開銷，降低了系統的吞吐量。

（3）破壞“循環等待”條件

對系統所有資源類型進行線性排序，并賦予不同的序号，并規定每個程序必須按序列号遞增的順序請求資源。

存在問題：各類資源所規定的序号必須相對穩定；作業使用各資源機關順序可能會和系統規定的不同，造成資源的浪費；限制使用者簡單、自主的程式設計。

2、避免死鎖

除了事先采取某種限制措施，破壞産生死鎖的條件，我們也可以，在資源配置設定過程中，防止系統進入不安全狀态，以避免發生死鎖。

（1）系統安全狀态

所謂安全狀态是指系統能按照某種程序推進順序為每個程序配置設定其所需資源，直至滿足每個程序對資源的最大需求，使每個程序都可順利的完成。

需要注意的是：并非所有的不安全狀态都必然會轉為死鎖狀态，但系統進入不安全狀态後就有可能進入死鎖狀态。

（2）利用銀行家算法避免死鎖

最有代表性的避免死鎖的算法是Dijkstra的銀行家算法。

為了實作銀行家算法，每一個新程序在進入系統時，必須申明在運作過程中，可能需要每種資源類型的最大單元數目。其數目不應超過系統所擁有的資源總量。若有，保證配置設定後，不會使系統處于不安全狀态，否則，讓程序等待。

銀行家算法的資料結構：

在系統中必須設定這樣四個資料結構，分别用來描述系統中可利用資源、所有程序對資源的最大請求、系統中的資源配置設定，以及所有程序還需要多少資源的情況。

1、可利用資源向量Available

2、最大需求矩陣Max

3、配置設定矩陣Allocation

4、需求矩陣Need

上述三個矩陣間存在下述關系：Need[i,j]=Max[i,j]-Allocation[i,j]

銀行家算法:

1．如果Request<=Need,則轉向2;否則,出錯

2．如果Request<=Available,則轉向3,否則等待

3．系統試探把資源配置設定給程序Pi，并修改資料結構中的值：

Available[j]=Available[j]-Requesti[j];

Allocation[i,j]=Allocation[i,j]+Requesti[j];

Need[i.j]=Need[i,j]-Requesti[j];

4．系統執行安全性算法，檢查是否會使系統處于不安全狀态

安全性算法：

1. 設定兩個向量

①　工作向量:Work=Available(表示系統可提供給程序繼續運作所需要的各類資源數目)

②　Finish:表示系統是否有足夠資源配置設定給程序(True:有;False:沒有).初始化為False

2. 若Finish[i]=False&&Need[i,j]<=Work[j]，則執行3;否則執行4(i為資源類别)

3. 程序P獲得第i類資源,則順利執行，直至完成，并釋放資源: Work[j]=Work[j]+Allocation[i,j]; Finish[i]=true;轉第2步。

4. 若所有程序的Finish[i]=true,則表示系統安全;否則,不安全

3、死鎖的檢測

（1）允許死鎖的發生，但是作業系統會不斷監視系統的進展情況，判斷死鎖是否真的發生

（2）一旦死鎖真的發生則采取專門的措施，解除死鎖并以最小的代價恢複作業系統的運作

死鎖檢測的時機：

（1）當程序由于資源請求不滿足而等待時檢測死鎖——系統開銷太大

（2）定時檢測

（3）系統資源使用率下降時檢測死鎖

4、死鎖的解除

當檢測到系統發生死鎖時，就采取相應的措施，将程序從死鎖狀态中解脫出來。

常用的死鎖解除方法是：

（1）搶占資源

從一個或多個程序中搶占足夠數量的資源，配置設定給死鎖程序，以解除死鎖狀态。

（2）終止或撤銷程序

終止或撤銷系統中的一個或多個程序，直至打破循環環路，使系統從死鎖狀态中解脫出來。 終止程序的兩個方法：

   終止所有死鎖程序：

   即是終止所有的死鎖程序，死鎖就自然解除了；

   缺點是有些程序可能已經運作了很長時間，以後還會從頭再來。

逐個終止程序：