目錄

死鎖概念

饑餓與餓死概念

饑餓和死鎖對比

死鎖類型

死鎖條件（Coffman條件）

死鎖恢復方法

死鎖避免

安全狀態與安全進程序列：

銀行家算法：?

死鎖檢測時機（了解）：

死鎖檢測

死鎖案例

過河問題

---

死鎖概念

定義：一組進程中的每一個進程，均無限期地等待此組進程中某個其他進程占有的資源，因而永遠無法得到的資源，這種現象稱為進程死鎖。

由定義可得：參與死瑣的進程至少有二個； 每個參與死鎖的進程均等待資源。

饑餓與餓死概念

饑餓：沒有時間上界的等待。排隊等待、忙式等待。

餓死：等待時間超過極限，進程即使完成也不再具有實際意義時

饑餓和死鎖對比

1、死鎖進程處于等待狀態，餓死進程已經死了。

2、死鎖（一定發生了循環等待）可以檢測，餓死不可以。

3、死鎖進程等待永遠不會被釋放的資源，餓死進程等待會被釋放但卻不會分配給自己的資源，其等待時限沒有上限。

4、死鎖一定涉及多個進程，而饑餓或被餓死的進程可能只有一個。

死鎖類型

1. ?競爭資源引起的死鎖：

??例如：P1需要4臺打印機，P2需要兩臺打印機。P1申請了3臺，P2申請了一臺，造成死鎖。

?2、進程通訊引起的死鎖

?3、其它原因引起的死鎖

死鎖條件（Coffman條件）

1、資源獨占（mutual exclusion）：資源被進程占用

2、不可搶占（non preemption）：不可強制搶奪被進程占用的資源

3、保持申請（hold-while-applying）：申請新資源并不釋放它占用的資源

4、循環等待（circular wait）：存在一個進程循環等待序列，P1等P2,P2等P3，P3等P1的循環等待。

死鎖恢復方法

1. 系統重新啟動：? 簡單，代價大

2.終止進程(process termination)：終止環路上占有資源的進程并收回它們占有的資源。

3.剝奪資源(resource preemption)：剝奪進程所占用的全部或部分資源。

4.進程回退(rollback)：回退到以前沒有發生死鎖的狀態。

死鎖避免

死鎖避免是保證系統不會進入死鎖狀態的動態策略。

安全狀態與安全進程序列：

安全狀態：所有進程可以按照某一次序安全運行，說明系統處于安全狀態。

安全進程序列： 系統出于安全狀態，可以按照某一次序安全運行，這個次序叫安全進程序列

銀行家算法：?

數據結構：

m:資源類總數   n:進程總數
int Available:[m];   //系統可用資源
int Claim[n,m];      //進程最大需求
int Allocation[n,m]; //當前分配
int Need[n,m];       //尚需資源
int Request[n,m];    //當前請求資源
int Work[m];         //記錄可用資源 
int Finish[n];       //記錄進程是否可以執行完

安全性檢測算法?

1、初始化Work數組=Available數組，Finish = {false}。

2、循環查找Need[i]<=Work[i] 且 Finish[i]=false，找到轉3，未找到轉4。

3、Work+=Allocation[i]（相當于釋放資源），Finish[i]=true，記錄i到安全序列。

4、對于所有i，存在Finish[i]=true，則系統處于安全狀態，從而得到安全序列。

資源分配算法

1、判斷請求資源量是否小于需求資源量，若沒有則返回錯誤。

2、判斷請求資源量是否小于可用資源量，若沒有則等待。

3、分配資源，可用資源減少，進程占用資源增加，需求資源減少。

4、運行安全性檢測算法，檢測系統是否安全，不安全則歸還分配資源，并轉入等待。

5、系統安全則確認資源分配。

死鎖檢測時機（了解）：

考慮因素：死鎖發生頻度，死鎖影響的進程。

1、等待時檢測

2、定時檢測

3、資源（eg. CPU）利用率下降時檢測

死鎖檢測

1、初始化Work=Available，Finish={false}。

2、查找滿足條件Request[i]<=Work，Finish[i]=false的i，轉到3，沒找到轉到4。

3、Work+=Allocation[i]（相當于釋放資源），Finish[i]=true,繼續轉2。

4、對于所有i，存在Finish[i]=true，則系統未死鎖，反之系統死鎖。

?死鎖案例

過河問題

? ? ? ? 這里要求找到S最大人數，不會死鎖情況下，橋上可以容納的最大人數。其次每一個S0-S8代表石塊，P(Sn) 代表石塊占用，V(Sn)代表石塊釋放。