死鎖概念
一組程序中，每個程序都無限等待被該組程序中另一程序所占有的資源，因而永遠無法得到該資源，這種現象稱為程序死鎖(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 已不能滿足任何程序的需要，不能配置設定