關于死鎖你想知道的

先導知識

• 死鎖(Deadlock): 指程序之間無休止地互相等待!
• 饑餓(Starvation):指一個程序無休止地等待！
• 活鎖(livelock):指程序沒有被阻塞，但由于某些條件不滿足，導緻一直重複嘗試，失敗……
• 本文内容

  

• 死鎖概念
  • 指兩個或多個程序因競争共享資源而造成的一種僵局，若無外力作用，這些程序都将永遠不能再向前推進。
  • 涉及到程序就稱為死鎖程序。
• 關于死鎖的一些結論
  • 參與死鎖的程序最少是兩個 ；
  • 參與死鎖的程序至少有兩個已經占有資源；
  • 參與死鎖的所有程序都在等待資源；
  • 參與死鎖的程序是目前系統中所有程序的子集。
  • 如果死鎖發生，會浪費大量系統資源，甚至導緻系統崩潰。

3.5産生死鎖的原因和必要條件

3.5.1 産生死鎖的原因

• 産生死鎖的原因可歸結為如下兩點：

1、競争資源。

• 資源類型：

  • 可剝奪和不可剝奪性資源

    死鎖發生：雙方都擁有部分資源，同時在請求對方已占有的資源

    例：競争非剝奪性資源

    

  • 永久性資源和臨時性資源 (可重用資源和消耗性資源)

    (consumable resource)：可以動态生成和消耗，一般不限制數量。如信号、消息、緩沖區内的資料。

    死鎖發生：雙方都等待對方去生成資源，如次序：P1 P2

    

2、程序間推進順序非法。

• 例1

  

  但如果将程序P2改寫為這樣，則容易導緻死鎖

  将類似①→③→④→②、①→③→②→④、③→①→②→④、 ③→①→④→②這樣的序列稱為不安全序列。

• 程序通信中的推進順序及臨時資源引發的死鎖
  • 程序通信使用的信件是一種臨時性資源，如果對信件的發送和接收不加限制，可能引起死鎖。

    

• 如圖所示三個程序：
  • P1等待P3的信件S3來到後再向P2發送信件S1；
  • P2又要等待P1的信件S1來到後再向P3發送信件S2；
  • P3也要等待P2的信件S2來到後才能發出信件S3。
• 這種情況下形成了循環等待，産生死鎖。
• 正确的程序推進順序（先發送再索取）
  • P1: Release(S1); Request(S3); ……
  • P2: Release(S2); Request(S1); ……
  • P3: Release(S3); Request(S2); ……
• 死鎖的程序推進順序
  • P1: Request(S3); Release(S1);……
  • P2: Request(S1); Release(S2);……
  • P3: Request(S2); Release(S3);……

3.5.2 産生死鎖的必要條件

• 1.互斥條件
• 2.請求并保持條件
• 3.不剝奪條件
• 4.環路等待條件

3.5.3 處理死鎖的基本方法

• 一、預防死鎖——消除産生死鎖的必要條件（靜态+動态）
• 二、避免死鎖——配置設定資源時防止進入不安全狀态（動态）
• 三、檢測死鎖——不預防死鎖，随時檢測死鎖（動态）
• 四、解除死鎖——出現死鎖就解除（動态）

3.6預防與避免死鎖的方法

3.6.1預防死鎖

• 對于必要條件1（互斥條件），因為它是由裝置的固有條件所決定的，一般不能改變。
• 可以使用硬軟體結合的SPOOLing技術（資源轉換技術），将獨占裝置“改造”為共享裝置。
• 此處預防死鎖的方法，是使其餘三個條件之一不能成立，來預防死鎖。
• 下面分别對三種情況加以說明：

1、靜态資源配置設定法

所有程序在開始運作之前，都必須一次性 的申請其在整個運作過程所需的全部資源。

• 優點：算法簡單、易于實作且很安全。

• 缺點：資源浪費嚴重，程序延遲運作；

  可能造成“饑餓”。

2、摒棄“不剝奪”條件

程序申請不到新的資源則必須放棄已到手的所有資源。

• 特點：
  • 實作複雜，代價大，造成程序前、後工作不連貫甚至結果出現混亂；
  • 反複申請、釋放，導緻程序周轉時間加長，系統開銷加大，吞吐量下降。

3、摒棄“環路等待”條件

• 有序資源配置設定法：
  • 系統将所有資源按類型進行線性排隊，并賦予不同的序号。
  • 所有程序對資源的請求必須嚴格按照資源序号遞增的次序提出。

    

• 優點：資源使用率和系統吞吐量都有較明顯的改善。
• 缺點：為資源編号限制新裝置的增加；程序使用裝置順序與申請順序相反；限制使用者程式設計自由。

例一過河問題

• 題目描述
  • 每個石塊上最多容納一個過河者，兩個相臨石塊的間距恰好為一步。
  • 西岸人經過石塊1，2，5，6，4，3到東岸，
  • 東岸人經過石塊3，4，7，8，2，1到西岸。
  • 試分析可能發生的死鎖情況，給出一個無死鎖、無餓死且并行度高的算法，并用Wait/Signal操作實作！
• 分析
  • 當兩個方向各有1人、2人（同時走上87或56）或其中一方有3或4人（一方占上了2或4）時，可能發生死鎖！若雙方同時有3人以上踏上石塊（互相等待24），肯定發生死鎖！
• 解決方法
  • 方法1：規定東西兩岸人員不能同時過河！但可能導緻餓死，同時也影響并行度！
  • 方法2：根據資源的數量，限定同時過河的人數在5個以内； 且對兩岸競争的1，2和3，4兩對石塊，采用有序配置設定法。

//方法2
Semaphore  Smax=5;semaphore  S1,S2,S3,S4,S5,S6,S7,S8;(初值=1)
西過河程序
Wait(Smax);
Wait(S1);
//走到石塊1；
Wait(S2);
//走到石塊2；
Signal(S1);
Wait(S5);
//走到石塊5；
Signal(S2);
Wait(S6);
//走到石塊6；
Signal(S5);
Wait(S3); 
//有序申請3-4
Wait(S4);
//走到石塊4；
Signal(S6);
//走到石塊3；
Signal(S4);//
走到東岸；
Signal(S3);
Signal(Smax);

東過河程序
Wait(Smax);
Wait(S3);
//走到石塊3；
Wait(S4);
//走到石塊4；
Signal(S3);
Wait(S7);
//走到石塊7；
Signal(S4);
Wait(S8);
//走到石塊8；
Signal(S7);
Wait(S1); 
//有序申請
Wait(S2);
//走到石塊2；
Signal(S8);
//走到石塊1；
Signal(S2);//
走到西岸；
Signal(S1);
Signal(Smax);
           

例2：T型路口

• 問題描述
  • 設有一個T型路口，其中A、B、C、D處各可容納一輛車，車行方向如下圖所示，試找出死鎖并用有序資源配置設定法消除之。要求資源編号合理。

    

• 死鎖狀态：
  • (1)Ｅ方向兩輛車分别位于A和B；S方向一輛車位于C；W方向一輛車位于D。
  • (2)S方向兩輛車分别位于B和C；E方向一輛車位于A；W方向一輛車位于D。
• 設位置資源C、B、A、D的編号從低到高依次為1、2、3、4，管理四個位置的信号量分别為s1,s2,s3,s4，信号量的初值均為1。車輛活動如下
• 解答

  

3.6.2系統安全狀态

• 在預防死鎖的幾種方法中，都施加了較強的限制條件；在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統性能。
• 在該方法中把系統的狀态分為安全狀态和不安全狀态，隻要能使系統始終都處于安全狀态，便可避免發生死鎖。

1、安全狀态

系統處于安全狀态：存在安全程序式列<p1,p2,…,pn>，

按照這樣的序列，p1,p2,…,pn可依次進行完。

2、安全狀态例

• 假定系統中有三個程序A、B和C，共有12台錄音帶機。
• 程序A總共要求10台，B和C分别要求4台和9台。
• 假設在T0時刻，程序A、B和C已分别獲得5台、2台和2台，尚有3台未配置設定，如下表所示：

  

• 經分析發現，在T0時刻系統是安全的，因為此時存在一個安全序列<B,A,C>；
• 即隻要系統按此程序式列配置設定資源，就能使每個程序都順利完成。

3、由安全狀态向不安全狀态的轉換

• 如果不按照安全序列配置設定資源，則系統可能會由安全狀态進入不安全狀态。
• 例如，在T0時刻後，C又請求一台錄音帶機，若此時系統把剩餘3台中的1台配置設定給C，則系統便進入不安全狀态。
• 因為，此時再也無法找到一個安全序列，可能導緻死鎖！

3.6.3利用銀行家算法避免死鎖

1、銀行家算法所需的資料結構

(1)可利用資源向量Available

可利用資源向量Available。這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值随該類資源的配置設定和回收而動态地改變。如果Available［j］=K，則表示系統中現有Rj類資源K個。

(2)最大需求矩陣Max

最大需求矩陣Max。這是一個n×m的矩陣，它定義了系統中n個程序中的每一個程序對m類資源的最大需求。如果Max［i,j］=K，則表示程序i需要Rj類資源的最大數目為K。

(3)配置設定矩陣Allocation

配置設定矩陣Allocation。這也是一個n×m的矩陣，它定義了系統中每一類資源目前已配置設定給每一程序的資源數。如果Allocation［i,j］=K，則表示程序i目前已分得Rj類資源的數目為K。

(4)需求矩陣Need

需求矩陣Need。這也是一個n×m的矩陣，

用以表示每一個程序尚需的各類資源數。

如果Need［i,j］=K，則表示程序i還需要Rj類資源K個，方能完成其任務。

Need［i,j］=Max［i,j］-Allocation［i,j］

2、銀行家算法

設Requesti是程序Pi的請求向量，如果Requesti［j］=K，表示程序Pi需要K個Rj類型的資源。當Pi發出資源請求後，系統按下述步驟進行檢查:

（1）檢查請求數是否超越動态的需求量

如果Requesti［j］≤Need［i,j］，便轉向步驟2；否則認為出錯，因為它所請求的資源數已超過它所宣布的最大值;

（2）檢查請求數是否超越可利用量（餘量）

如果Requesti［j］≤Available［j］，便轉向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。

（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）執行安全性算法

系統執行安全性算法，檢查此次資源配置設定後，系統是否處于安全狀态。若安全，才正式将資源配置設定給程序Pi，以完成本次配置設定；否則， 将本次的試探配置設定廢棄，恢複原來的資源配置設定狀态，讓程序Pi等待。

銀行家算法流程

3、安全性算法

（1）設定兩個向量

• ① 工作向量Work: 它表示系統可提供給程序繼續運作所需的各類資源數目，它含有m個元素，在執行安全算法開始時，Work∶=Available;
• ② Finish: 它表示系統是否有足夠的資源配置設定給程序，使之運作完成。開始時先令Finish[i]∶=false; 當有足夠資源配置設定給程序時，再令Finish[i]∶=true。

（2）檢查所有程序目前的安全性

• (2)從程序集合中找到一個能滿足下述條件的程序:

  ①Finish［i］=false; ②Need［i,j］≤Work［j］；

  若找到，執行步驟(3)，否則，執行步驟(4)。

• (3)當程序Pi獲得資源後，可順利執行，直至完成，并釋放出配置設定給它的資源，故應執行：

  Work［j］:=Work［j］+Allocation［i,j］;//算出pi釋放後的workj

  Finish［i］:=true;

  go to step 2;

• (4)如果所有程序的Finish［i］=true都滿足， 則表示系統處于安全狀态；否則，系統處于不安全狀态。

安全性算法流程

4、銀行家算法之例

• 假定系統中有五個程序｛P0, P1, P2, P3, P4｝和三類資源｛A, B, C｝，各種資源的數量分别為10、5、7，在T0時刻的資源配置設定情況如圖所示。

  

• 找出一個安全序列<p1,p3,p4,p0,p2>
• 計算T0時刻執行安全性算法

  

• (2) P1請求資源：P1送出請求向量Request1(1，0，2)，系統按銀行家算法進行檢查：
  • ① Request1(1, 0, 2)≤Need1(1, 2, 2)
  • ② Request1(1, 0, 2)≤Available1(3, 3, 2)
  • ③ 系統先假定可為P1配置設定資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如中的紅色字型所示。

    

  • ④ 再利用安全性算法檢查此時系統是否安全。

  

• (3)随後P3,P4,P0,P2陸續提出資源請求，系統再配置設定前執行銀行家算法和安全性算法

死鎖避免優缺點

• 優點：
  • 無須搶占；
  • 比死鎖預防限制少；
  • 允許更多的程序并發執行。
• 缺點：
  • 要預先聲明資源的最大需求量；
  • 資源和程序的數目必須固定；
  • 可能導緻程序的長時間阻塞。

死鎖與餓死的不同

• (1) 從程序狀态考慮，死鎖程序都處于等待狀态，而處于就緒狀态的程序也可能被餓死；
• (2) 死鎖程序等待永遠不會被釋放的資源，餓死程序等待會被釋放但卻不會配置設定給自己的資源；
• (3) 死鎖一定發生了循環等待，而餓死則不然。這也表明通過資源配置設定圖可以檢測死鎖存在與否，但卻不能檢測是否有程序餓死；
• (4) 死鎖一定涉及多個程序，而饑餓或被餓死的程序可能隻有一個。

3.7死鎖的檢測與解除

3.7.1死鎖的檢測

• 當系統為程序配置設定資源時，若未采取任何限制性措施，則系統必須提供檢測和解除死鎖的手段，為此系統必須：
  • 儲存有關資源的請求和配置設定資訊；
  • 提供一種算法，以利用這些資訊來檢測系統是否已進入死鎖狀态。
• 死鎖檢測：
  • 允許死鎖發生，作業系統不斷監視系統進展情況，判斷死鎖是否發生
  • 一旦死鎖發生則采取專門的措施，解除死鎖并以最小的代價恢複作業系統運作
• 檢測時機：
  • 當程序等待時檢測死鎖
  • 定時檢測
  • 系統資源使用率下降時檢測死鎖

當每類資源隻有一個資源

• 死鎖檢測算法：
  • 每個程序和資源指定唯一編号

  • 設定一張資源配置設定表

    記錄各程序與其占用資源之間的關系

  • 設定一張程序等待表

    記錄各程序與要申請資源之間的關系

• 反複檢測這兩張表，列出所有等待與配置設定的關系，若出現循環等待，則出現了死鎖！

每類資源含有多個資源的死鎖檢測-資源配置設定圖

• 定義: G=(V,E), V=P∪R, P={p1,p2,…,pn}, R={r1,r2,…,rm},

  E={(pi,rj)}∪{(rj,pi)}, piP, rjR.

  申請邊(pi,rj): pi申請rj；

  配置設定邊(rj,pi): rj配置設定pi;

• 申請邊：由程序到資源類；

  配置設定邊：由資源執行個體到程序。

  

• 申請：pi申請rj中的一個資源執行個體，由pi向rj畫一申請邊，如可滿足，改為配置設定邊。
• 釋放：去掉配置設定邊。
• 例：P={p1,p2,p3}, R={r1(1),r2(2),r3(1),r4(3)} E={(p1,r1),(p2,r3),(r1,p2),(r2,p1),(r2,p2),(r3,p3)}

無環路，無死鎖

增加邊（p3,r2）

• 例2

  

  有環路，無死鎖！（環路經過的是一類資源的不同子資源故無死鎖）

• 無環路，無死鎖！

  有環路，可能死鎖！

資源配置設定圖的簡化

• 1.在資源配置設定圖中找出一個既不阻塞又非獨立的程序結點Pi，在順利的情況下運作完畢，釋放其占有的全部資源。
• 2.由于釋放了資源，這樣能使其它被阻塞的程序獲得資源繼續運作。
• 3.在經過一系列簡化後若能消去圖中的所有的邊，使所有程序結點都孤立，則稱該圖是可完全簡化的，反之是不可完全簡化的。

死鎖定理

S狀态為死鎖狀态的充分必要條件是當且僅當S狀态的資源配置設定圖是不可完全簡化的。

• 例

  

  初始狀态，紅色虛線為申請邊，藍色實線為配置設定邊

  

  p1首先運作完畢釋放資源

p2運作完畢并釋放資源，此時p3,p4出現了循環等待，無法再釋放資源，滿足死鎖定理出現死鎖。

3.7.2死鎖的解除

當發現程序死鎖時，便應立即把它們從死鎖狀态中解脫出來。常采用的方法是：

• 重新啟動：簡單但代價高！
• 剝奪資源：從其他程序剝奪足夠數量的資源給死鎖程序以解除死鎖狀态。
• 撤銷程序：最簡單的是讓全部程序都死掉；溫和一點的是按照某種順序逐個撤銷程序，直至有足夠的資源可用，使死鎖狀态消除為止。
• 程序回退：貌似完善但開銷驚人！

死鎖處理方法比較