操作系統精髓與設計原理讀書筆記10

來自專欄 學渣的救贖之路

死鎖

死鎖的定義

一組進程中，每個進程都無限等待被該組進程中另一進程所佔有的資源，因而永遠無法得到的資源，這種現象稱為進程死鎖，這一組進程就稱為死鎖進程

如果死鎖發生，會浪費大量系統資源，甚至導致系統崩潰

參與死鎖的所有進程都在等待資源

參與死鎖的進程是當前系統中所有進程的子集

互斥使用(資源獨佔)

一個資源每次只能給一個進程使用

佔有且等待(請求和保持，部分分配)

進程在申請新的資源的同時保持對原有資源的佔有

不可搶佔(不可剝奪)

資源申請者不能強行的從資源佔有者手中奪取資源，資源只能由佔有者自願釋放

循環等待

存在一個進程等待隊列 {P1 , P2 , … , Pn},

其中P1等待P2佔有的資源，P2等待P3佔有的資源，…，Pn等待P1佔有的資源，形成一個進程等待環路

資源分配圖：

用有向圖描述系統資源和進程的狀態

二元組G=（V，E）

V：結點的集合，分為P(進程)，R(資源)兩部分

P = {P1, P2, … , Pn}

R = {R1, R2, … , Rm}

E：有向邊的集合，其元素為有序二元組

(Pi, Rj) 或 (Rj, Pi)

如果資源分配圖中沒有環路，則系統中沒有死鎖，如果圖中存在環路則系統中可能存在死鎖

如果每個資源類中只包含一個資源實例，則環路是死鎖存在的充分必要條件

資源圖化簡步驟：

1）找一個非孤立、且只有分配邊的進程結點

去掉分配邊，將其變為孤立結點

2）再把相應的資源分配給一個等待該資源的進程

即將該進程的申請邊變為分配邊

重複1）、2）

死鎖預防：

不考慮此問題（鴕鳥演算法）

不讓死鎖發生

死鎖預防

在設計系統時，通過確定資源分配演算法，排除發生死鎖的可能性

具體的做法是：防止產生死鎖的四個必要條件中任何一個條件發生

靜態策略：設計合適的資源分配演算法，不讓死鎖發生

死鎖避免

一個進程序列{P1，…，Pn}是安全的，如果對於每一個進程Pi(1≤i≤n）：

它以後還需要的資源量不超過系統當前剩餘資源量與所有進程Pj (j < i )當前佔有資源量之和

則稱系統處於安全狀態

仿照銀行發放貸款時採取的控制方式而設計的一種死鎖避免演算法

當進程Pi提出資源申請時，系統執行下列步驟：

（1）若Request[i] ≤ Need[i]，轉（2）；

否則，報錯返回；

（2）若Request[i] ≤ Available，轉（3）；

否則，進程等待；

（3）假設系統分配了資源，則有：

Available = Available - Request[i];

Allocation[i] = Allocation[i] + Request[i];

Need[i] = Need[i] - Request[i];

若系統新狀態是安全的，則分配完成

若系統新狀態是不安全的，則恢復原來狀態，進程等待

動態策略：以不讓死鎖發生為目標，跟蹤並評估資源分配過程，根據評估結果決策是否分配

讓死鎖發生

死鎖檢測與解除

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

一旦死鎖發生則採取專門的措施，解除死鎖並以最小的代價恢復操作系統運行

semaphore fork[5] = {1}; semaphore room = {4}; int i; void philosopher (int i) { while (true) { think(); P (room); P (fork[i]); P (fork [(i+1) mod 5]); eat(); V (fork [(i+1) mod 5]); V (fork[i]); V (room); } } void main() { parbegin ( philosopher (0), philosopher (1),philosopher (2), philosopher(3),philosopher (4) );

推薦閱讀：