進程與進程管理 | 死鎖的基本概念處理死鎖的基本方法

處理死鎖的基本方法

• 預防與避免死鎖
• 檢測與解除死鎖

預防死鎖

靜態預防死鎖的方法

靜態分配資源：

在作業調度時為選中的作業分配它所需要的所有資源，當 資源一旦分配給該作業後，在其整個運行期間這些資源為它獨佔。

破壞了產生死鎖所需要的請求與保持條件，所以系統不會進入死鎖狀態。

缺點：

• 資源利用率低；
• 進程的運行可能被推遲；（一旦其中的某個條件不能滿足，則整個作業不能運行）

動態預防死鎖的方法

採用有序資源分配策略：

• 將所有的系統資源按類型進行線性排隊，並賦予不同的序號；
• 所有進程對資源的請求應嚴格按資源序號遞增順序提出。

破壞了產生死鎖的四個必要條件中的循環等待條件。不會進入死鎖。

如上圖中，將需要使用的系統資源（磁帶機、掃描儀、印表機等使用序號進行標記。），當同一個進程P1需要使用掃描儀和繪圖儀時，系統會按照這些資源的序號進行按序號順序遞增分配給P1進程。

優點：

較之前面兩種方法資源利用率高，系統吞吐量大。

缺點：

• 為系統中各種資源類型分配序號時，必須相對穩定， 從而限制了新設備的增加；
• 會出現作業使用的資源順序與系統規定的順序不同的情況，造成資源的浪費。

避免死鎖

安全狀態定義：

所謂安全狀態，是指系統能按某種進程順序(P1, P2, …，Pn)(稱〈P1, P2, …, Pn〉序列為安全序列)，來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統無法找到這樣一個安全序列，則稱系統處於不安全狀態。

安全狀態之例：

我們通過一個例子來說明安全性。假定系統中有三個進程P1、 P2和P3，共有12台磁帶機。進程P1總共要求10台磁帶機，P2和P3分別要求4台和9台。假設在T0時刻，進程P1、P2和P3已分別獲得5台、2台和2台磁帶機，尚有3台空閑未分配，如下表所示：

如上圖中，我們目前可用的磁帶機為3台，如果按照 P2， P1， P3 的運行次序，可以保障正常運行P2進程，且其結束後釋放的磁帶機與原先可用磁帶機之和可以滿足P1進程的需求，同理P1進程運行結束後，可以滿足P3進程的需求。

由安全狀態向不安全狀態的轉換

如果不按照安全順序分配資源，則系統可能由安全狀態進入不安全狀態。

不安全狀態之例

例：假定系統有三個進程P1、P2和P3，有12台磁帶機。

在T0時刻P3又申請了一台磁帶機，若將剩餘3台中的一台分配給P3 則系統就會應為剩餘的資源無法滿足對P1，P2，P3進程的全部正常運行而導致進入不安全狀態。

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

避免死鎖演算法中最有代表性的演算法是Dijkstra E.W 於1968年提出的銀行家演算法：它的模型基於一個小城鎮的銀行家，該演算法可描述如下：假定一個銀行家擁有資金，數量為∑，被N個客戶共享。銀行家對客戶提出下列約束條件：

• 每個客戶必須預先說明自己所要求的最大資金量；
• 每個客戶每次提出部分資金量申請和獲得分配；
• 如果銀行滿足了某客戶對資金的最大需求量，那麼，客戶在資金運作後，應在有限時間內全部歸還銀行。

銀行家演算法中的數據結構

① 可利用資源向量Available[m]。

其中的每一個元素代表一類可利用的資源數目

Available[j]=K，則表示系統中現有Rj類資源K個。

② 最大需求矩陣Max[1..n,1..m]

該矩陣定義了系統中n個進程對m類資源的最大需求。

Max[i,j]=K，則表示進程i需要Rj類資源的最大數目為K。

③ 分配矩陣Allocation[1..n,1..m]

該矩陣表示系統中每個進程當前已分配到的每類資源數量。

Allocation[i,j]=K，表示進程i當前已分得Rj類資源的數目為K。

④ 需求矩陣Need[1..n,1..m]

該矩陣表示每個進程尚需的各類資源數。Need[i,j]=K，則表示進程i還需要Rj類資源K個，方能完成其任務。

Need[i,j]=Max[i,j]-Allocation[i,j]

⑤ 請求向量Requesti of integer;

某進程申請需要某類資源的資源數

銀行家演算法描述

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

⑴ 若Request[i]≤Need[i],轉⑵；否則錯誤返回； // 判斷請求是否合法，在其需求之內

⑵ 若Request[i]≤Available，轉⑶；否則，表示尚無足夠資源，Pi須等待；

⑶系統嘗試把資源分配給進程Pi，並修改以下數據結構：

Available:= Available-Request[i]; // 可用的

Allocation[i]:= Allocation[i]+Request[i]; // 已分配的

Need[i]:= Need[i]-Request[i]; // 還需要

⑷ 執行安全性演算法：

檢查此次資源分配後，系統是否處於安全狀態。若安全，則將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程Pi等待。

安全性演算法描述

① 設置兩個臨時向量：

1）工作向量Work: 它表示系統可提供給進程繼續運行所需的各類資源數目，它含有m個元素，在執行安全演算法開始時，Work=Available;

2） Finish[n]: 它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish［i］=false; 當有足夠資源分配給進程時， 再令Finish[i］=true。

②從進程集合中找到一個能滿足下述條件的進程：

1） Finish［i］=false;

2）Need［i,j］≤Work［j］；

若找到， 執行步驟③ ， 否則，執行步驟④ ；

③ 當進程Pi獲得資源後，可順利執行，直至完成，並釋放 出分配給它的資源，故應執行：

Work［j］∶= Work［j］+Allocation［i,j］;

Finish［i］∶= true;

go to step ②;

④ 如果所有進程的Finish［i］=true都滿足， 則表示系統處於安全狀態；否則，系統處於不安全狀態

銀行家演算法舉例

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

（1）T0時刻的安全性；

（2）P1請求資源：Request1（1，0，2）；

(1) 需要進行安全性檢驗，

創建兩個新的向量 work 和 finish。

finish 初值都為 false。 work 初值為 available。

根據第一個 work，我們可以隨意選擇 P1 和 P3 進程中的一個先進行運行。

這裡我選擇了 P1 進程先執行，然後依次執行得到上圖。安全。

（2）當P1請求資源：Request1（1，0，2）時：

① Request1（1，0，2）≦ Need1 （1，2，2）

② Request1（1，0，2）≦ Available（3，3，2）

③試分配資源後，修改數據結構。

④對如上圖所示的修改完數據結構後的新狀態下試分配後狀態進行安全性檢查：

由於此時存在安全序列{P1, P3, P4, P2, P0},故系統是安全的，可為P1分配上述資源。

死鎖的檢測

死鎖的檢測是在恰當的時候檢查系統是否有死鎖發生，是通過對資源分配圖的簡化來完成的。

資源分配圖

圓圈表示一個進程，一個矩形表示一類資源，矩形內部的小圓圈表示這一類資源的數量。有向邊表示進程與資源之間的關係。有向邊由資源指向進程，表示進程已經佔據這些資源。有向邊由進程直線資源，表示進程需要申請這些資源。

死鎖定理

簡化資源分配圖，如果資源分配圖能完全簡化，則系統中沒有死鎖；否則系統存在死鎖。

資源分配圖簡化過程：

（1）在資源分配圖中，找出一個既不阻塞又非獨立的進程節點Pi，如果找到轉(2)否則轉(3)。

如上圖中的 P3 節點就是一個獨立節點， 它是可以順利運行的。而非獨立節點就是該進程與資源存在一定的關聯（擁有資源分配邊（擁有資源）或者具有資源請求邊（提出資源請求））。不阻塞表示該進程要麼只有資源分配邊，要麼有資源請求邊但是系統目前可以滿足該進程的資源請求，不需要等待。

在上圖中，我們的 P1和 P2 進程都是非獨立節點。

上圖中的 r2資源已經分配給 P2 進程一個剩餘一個資源可以滿足 P1 進程的請求。所以P1進程就是既不阻塞又非獨立的節點。

（2）去掉Pi的所有邊，使其成為一個獨立節點，並轉（1）；

此時的 r1 只有隻分配了一個資源給 P2，還剩餘兩個資源足夠P2資源的申請。所以此時的 P2 節點也是既不阻塞又非獨立的節點。

（3）判斷是否所有節點都成為獨立節點？如果是，稱為資源分配圖能完全簡化，系統無死鎖；否則系統存在死鎖。

死鎖檢測演算法：

數據結構：

• 可利用資源向量Available[m];
• 資源分配矩陣Allocation[n,m];
• 資源請求向量Requesti；
• 工作向量Work=Available
• 進程集合L ：獨立進程節點的集合

演算法描述：

L= ｛Li| Allocation_i =0 ∩ Request_i = 0｝//獨立節點For all Li ? L do // 非獨立節點{ for all Requesti ≤ Work do { Work = Work + Allocationi; Li ∪ L; }}Deadlock = !(L== {P1,P2,P3,…,Pn}); // 所有的進程節點都是獨立節點

死鎖檢測時機：

（1）進程進行資源請求時；（檢測及時，但是由於進程申請資源的頻率很高，所以會導致系統檢測開銷較大。）

（2）周期性檢測；如SQL SERVER；（最常用的檢測方法）

（3）根據CPU的使用效率檢測。（當CPUU的利用率低於某個設定的下限值時進行檢測）

死鎖的解除：

前提是能檢測出死鎖

當前系統中使用的解除死鎖的辦法有兩種：(剝奪資源，撤消進程)。

1. 剝奪資源：使用掛起/激活機制
2. 撤銷進程：
1. 撤銷進程的原則：
1. 撤銷的進程數最少；
2. 撤銷代價最小：
1. 進程優先數；
2. 進程類的外部代價；
3. 進程運行代價

死鎖習題舉例

（1）某系統中有5個並發進程，每個進程都需要4個同類資源才能運行完成並釋放出所佔用的資源，則系統不會發生死鎖的最少資源數是_______個。

可以假設每個進程都只獲得了3個同類資源。此時若系統沒有任何資源，則系統會進入死鎖狀態。如果還有一個資源就可以完成。所以答案是 16。

（2）某系統中有11台印表機，N個進程共享這些印表機資源，每個進程要求3台，當N的值不超過______時，系統不會發生死鎖。

N*2+1 <= 11， N = 5。答案是 5 。