天天看點

程序死鎖——銀行家算法

死鎖概念

  一組程序中,每個程序都無限等待被該組程序中另一程序所占有的資源,因而永遠無法得到該資源,這種現象稱為程序死鎖(Deadlock),這一組程序就稱為死鎖程序。

1、死鎖産生的原因

  • 競争資源引起程序死鎖(資源配置設定政策)(可剝奪和非剝奪資源)
  • 程序推進順序不當引起死鎖

PS:關于死鎖的一些結論:

  • 參與死鎖的程序最少是兩個(兩個以上程序才會出現死鎖)
  • 參與死鎖的程序至少兩個已經占有資源
  • 參與死鎖的所有程序都在等待資源
  • 參與死鎖的程序是目前系統中所有程序的子集
  • 如果死鎖發生,會浪費大量的系統資源,甚至導緻系統崩潰

2、死鎖的四個必要條件

  • 互斥條件:設計的資源是非共享的
  • 不可搶占條件:不能強行剝奪程序擁有的資源
  • 請求和保持條件:程序在等待一新資源時繼續占有已配置設定的資源
  • 環路條件:存在一種程序的循環鍊,鍊中的每一個程序已獲得的資源同時被下一個程序所請求
程式死鎖——銀行家算法

3、處理死鎖的方法

  • 預防死鎖:通過設定某些限制條件,去破壞死鎖四個必要條件中的一個或多個,來防止死鎖。
  • 避免死鎖:不事先設定限制條件去破壞産生死鎖的條件,而是在資源的動态配置設定過程中,用某種方法去防止系統進入不安全狀态,進而避免死鎖的發生。
  • 檢測死鎖:允許死鎖發生,但可通過檢測機構及時檢測出死鎖的發生,并精确确定與死鎖有關的程序和資源,然後采取适當措施,将系統中已發生的死鎖清除掉。
  • 解除死鎖:與檢測死鎖相配套,用于将程序從死鎖狀态解脫出來。常用的方法是撤消或挂起一些程序。以回收一些資源,再将它們配置設定給處于阻塞狀态的程序,使之轉為就緒狀态

4、避免死鎖——銀行家算法

  • 可利用資源向量Available。它是一個含有 m個元素的數組,其中每個元素代表一類 可利用資源的數目。
  • 最大需求矩陣Max。n*m矩陣,表示n個程序的每一個對m類資源的最大需求。
  • 配置設定矩陣Allocation 。n*m矩陣,表示每個程序已配置設定的每類資源的數目。
  • 需求矩陣Need 。n*m矩陣,表示每個程序還需要各類資源數。

銀行家算法步驟:

當程序Pi提出資源申請時,執行下列步驟:

(1)若Requesti[j]≤Need[i,j],轉(2);

          否則錯誤傳回

(2)若Requesti[j] ≤Available[j],

          轉(3);否則程序等待

(3)假設系統配置設定了資源,則有:

       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[j]:=Available[j];

      Finish[i]:=false;

(2) 尋找滿足下列條件的i:

      a).  Finish[i]=false;

      b).  Need[i,j]≤Work[j];

  如果不存在,則轉(4)

(3) Work[j] :=Work[j]+Allocation[i,j];

      Finish[i]:=true;

      轉(2)

(4) 若對所有i,Finish[i]=true,則系統處于安全狀态,否則處于不安全狀态

程式死鎖——銀行家算法

可得:      Need[i,j]= Max[i,j]- Allocation[i,j]

例:

設系統有五個程序和三類資源,每類資源分别有10、5、7。在T0時刻資源配置設定情況如下:

程式死鎖——銀行家算法

T0時刻可以找到一個安全序列<P1, P3, P4, P2, P0>,系統是安全的。

程式死鎖——銀行家算法

P1送出請求Request(1,0,2),執行銀行家算法

程式死鎖——銀行家算法

可以找到一個安全序列{P1,P3,P4,P0,P2},系統是安全的,可以将P1請求資源配置設定給它。

程式死鎖——銀行家算法

若是:P4送出請求Request(3,3,0), 執行銀行家算法

Available=(2 3 0)

不能通過算法第2步( Requesti[j]≤Available[j] ),是以P4等待。

例:如下:若P0送出請求Request(0,2,0),執行銀行家算法

程式死鎖——銀行家算法

Available{2,1,0}已不能滿足任何程序需要,是以系統進入不安全狀态,P0的請求不能配置設定。

練習題:有三類資源A(17)、B(5)、C(20)。有5個程序P1~P5。T0時刻系統狀态如下:

程式死鎖——銀行家算法

問:

(1)、T0時刻是否為安全狀态,給出安全系列。

(2)、T0時刻,P2: Request(0,3,4),能否配置設定,為什麼?

(3)、在(2)的基礎上P4:Request(2,0,1),能否配置設定,為什麼?

(4)、 在(3)的基礎上P1:Request(0,2,0),能否配置設定,為什麼?  

解:(1) T0時刻的出安全系列

先求出Need和Work

程式死鎖——銀行家算法
程式死鎖——銀行家算法
程式死鎖——銀行家算法

(2)  P2: Request(0,3,4)

因(Available =2 3 3)< Request(0,3,4) 是以不能配置設定。

(3)  P4:Request(2,0,1)       Available =2 3 3

程式死鎖——銀行家算法

有安全序列P4 P5 P3 P2 P1 可以配置設定

程式死鎖——銀行家算法

(4)  P1:Request(0,2,0)

程式死鎖——銀行家算法

0  1  2 已不能滿足任何程序的需要,不能配置設定

繼續閱讀