在多道程序環境中,多個進程可以競爭有限數量的資源。當進程申請資源時,如果沒有可用資源,那么這個進程進入等待狀態。有時,如果所申請的資源被其它等待進程占有,那么該進程可能再也無法改變狀態。這種情況稱為死鎖。
一、系統模型
資源分為多種類型,每種類型有一定數量的實例。
- 資源類型R1, R2, . . ., Rm, 如CPU, 內存空間, I/O 設備,文件
- 每個資源類型Ri有Wi個實例
正常操作模式下,進程只按如下順序使用資源:
- 申請:進程請求資源
- 使用:進程對資源進行操作
- 釋放:進程釋放資源
當一組進程中的每個進程都在等待一個事件的發生,而這一事件只能由這一組進程的另一進程引起,那么這組進程就處于死鎖狀態
二、死鎖特征
1.必要條件
如果在一個系統如下四個條件同時成立,就會引起死鎖:
- 互斥(mutual excusive):至少有一個資源只能由一個進程占用(非共享)
- 占用并等待:一個進程應占用至少一個資源,并請求/等待另一個資源
- 非搶占:資源不能被搶占
- 循環等待:有一組等待進程{P0, P1, …, Pn},P0等待的資源被P1所占用,P1等待的資源被P2 所占用,…,Pn–1等待的資源被Pn所占用,Pn等待的資源被P0所占用
2.資源分配圖
通過系統資源分配圖的有向圖可以更精確的描述死鎖。
資源分配圖由一個節點集合V和一個邊集合E組成。
1.節點集合V分為進程集合P和資源集合R
- 進程節點集合:P = {P1, P2, …, Pn}
- 資源節點集合:R = {R1, R2, …, Rm}
2 邊集合E
- Pi → Rj,表示進程Pi 已經申請使用資源類型Rj的一個實例,并等待這個資源
- Rj → Pi,表示資源類型Rj的一個實例已經分配給進程Pi
上圖一個成環是死鎖,一個成環不是死鎖
根據資源分配圖的定義,可以證明:
- 如果分配圖沒有環,就沒有死鎖
- 如果分配圖有環,就有可能發生死鎖如果每個資源類型只有一個實例,就肯定會發生死鎖
如果每個資源類型有多個實例,就有可能處于死鎖
三、死鎖處理方法
一般來說,處理死鎖問題有三種方法:
預防或避免(prevention or avoidance)
- 預防死鎖:確保?少?個必要條件不成?
- 避免死鎖:利?事先得到進程申請資源和使?資源的額外信息,判斷每當發?資源請求時是否會發?死鎖
發生死鎖,檢測并恢復。確定死鎖是否確實發?, 并提供算法從死鎖中恢復
忽視死鎖問題,認為死鎖不會發生
四、死鎖預防
發生死鎖有4個必要條件,所以只要確保至少一個必要條件不成立,就能預防死鎖發生
1.互斥
通常不能通過否定互斥條件來預防死鎖
可共享的資源不要求互斥訪問,如只讀?件;但不可共享的資源本身就是非共享的,必須要確保互斥,如打印機,一個互斥鎖
2.占用并等待
為否定這一條件,應保證:當一個進程請求一個資源時,它不能占有其他資源。
實現的方法如下:
- 每個進程在執?前申請并獲得所有資源
- 另一種是進程只有在不占?資源時, 才允許申請資源
注意:讓互斥和占?并等待不成?、兩種?法的缺點是資源利?率低和可能發?饑餓問題
3.非搶占
為了確保這一條件不成立,可以是使用如下協議:
如果一個進程占有資源并申請另一個不能分配的資源(也就是說,這個進程應該等待),那么其現已分配的資源可被搶占。
如果一個進程申請一些資源,那么首先檢查它們是否可用。
- 如果可?,就分配。
- 如果不可?,檢查這些資源是否已分配給其他等待額外資源的進程,如果是,那么就搶占。
- 如果不可?,且也沒有被其他等待額外資源的進程占有,那么就等待
4.循環等待
確保其不成立地一個方法:對所有資源類型進行完全排序,且要求每個進程按遞增順序來申請資源。
假設資源類型集合R={R1,R2…Rn},為每個資源類型分配一個唯一的整數,形式地,定義一個函數F:R → N(N為自然數集合)
可采用如下協議預防死鎖:
每個進程只能按遞增順序來申請資源,即一個進程開始可以申請任何數量的資源類型Ri的實例,之后,僅當F(Rj)>F(Ri)時,進程才能申請資源類型Rj的實例
五、死鎖避免
采用上述死鎖預防中的的方法來預防死鎖有副作用:設備使用率低和系統吞吐率低。
避免死鎖的另一種方法,需要額外信息,即如何申請資源。在獲悉每個進程的請求和釋放的完整順序后,系統可以決定,在每次請求時是否應該等待以避免未來可能的死鎖。
需要掌握的額外信息包括:
- 當前可用資源
- 已分配給每個進程的資源
- 每個進程將來要申請或釋放的資源
- 每個進程可能申請的每種資源類型實例的需求
針對每次申請,系統在做決定時考慮現有可用資源、現已分配給每個進程的資源、每個進程將來申請和釋放的資源來申請與釋放資源
鑒于這些先驗信息,可構造算法確保系統不會進入死鎖狀態。避免死鎖是動態的方法,它根據進程申請資源的附加信息決定是否申請資源
1.安全狀態
如果系統按一定順序(存在一個順序)為每個進程分配資源(不超過它的最大需求),且能避免死鎖,那么系統狀態就是安全的,如果沒有,系統狀態就是非安全的
避免死鎖指的是確保系統不進入不安全狀態
2.資源分配圖法
適用于每個資源具有單個實例。
由上一節的資源分配圖的變形可以避免死鎖
除原來的申請邊和分配邊,引入了新的類型邊叫需求邊。需求邊用虛線Pi - - > Rj,表示進程Pi可能在將來某個時刻申請資源Rj;當進程Pi申請資源Rj時,需求邊變成申請邊(虛線變成實線);當進程Pi釋放資源Rj時,分配變成需求邊
算法規則:只有在將申請邊變成分配邊而不會導致資源分配圖形成環時,才允許申請資源。
假設進程Pi申請資源Rj,對資源的申請,把申請邊變成分配邊后,如果沒有環就允許申請,如有環就不允許申請
下圖中如果將R2分配給P2,就會創建一個環,表示系統處于非安全狀態。
3.銀行家算法
適用于每個資源具有多個實例
當一個新進程進入系統時,它應聲明可能需要的每種類型資源實例的最大數量,當然這不能超過系統資源總和。當用戶申請一組資源時,系統應確定這些資源的分配是否會使系統處于安全狀態,如果會,就可以分配;否則進程應等待,直到某個進程釋放了做夠多的資源為止。
為實現這一算法,引入一些數據結構,這些數據結構都資源分配系統的狀態進行了記錄
Available ( vector 向量): 表示可分配的資源數。Available[j] = k 表示資源Rj 的可用資源數是k個
Max(n x m 矩陣): 表示資源最大需求數。Max[i,j] = k 表示進程Pi可能請求的資源Rj的實例個數是k.
Allocation(n x m 矩陣): 表示占有的資源數。Allocation[i,j] = k 表示Pi已經占有的資源Rj.實例的個數是k.
Need(n x m 矩陣): 為完成任務可能仍然需要的資源。Need[i, j] = k, 表示進程Pi可能需要的資源Rj實例數是k.
安全性算法:確定計算機系統是否處于安全狀態的算法。
//Work 和Finish 分別為長度m 和n的向量
Work = Available;//可用資源數
For all i, Finish[i] = false;//初始化,各個進程狀態
//這里并不是簡單的遍歷一遍,而是不斷查找
For all i do
//表示當前進程可以獲得資源,并執行
IF ( Finish[i] == false && Need i<= Work)
Work = Work + Allocation i//釋放進程i原來的占有資源
Finish[ i ] = true//表示執行完成
End IF
End For
//所有進程都執行完
IF for all i, Finish[i] == true
Then the system is safety
End IF
STEP 1:
Work 和Finish 分別為長度m 和n的向量, 分別初始化為:
Work = Available //可分配的資源數
Finish [ i ] = false for i = 0, 1, …, n- 1
STEP 2:
查找i使其滿足:Finish [ i ] = false && Need i <= Work
如果沒有滿足以上條件的i, 那么就跳轉到STEP 4
STEP 3:
Work = Work + Allocation i
Finish[ i ] = true
返回到STEP 2
STEP 4:
如果對所有i, Finish[i] == true 那么系統處于安全狀態,如果不是就處于不安全狀態
資源請求算法:判斷是否可安全允許請求的算法。
每次進程請求資源的時候,運行資源請求檢測算法,確認是否允許請求
IF ( Request i <= Need i) //檢測資源的請求是否合法
IF (Request i <= Available i){ //檢測可用資源能否滿足請求
Available i = Available i– Request i ;
Allocation i = Allocation i + Request i ;
Need i = Need i– Request i ;
do Safety Check Algorithm; //檢測分配資源后是否安全
ELSE
waiting;
End IF
ELSE
error
End IF
設Request i 為進程P i 的請求向量,當進程Pi作出資源請求時,采取如下操作:
STEP 1:
如果Requesti <= Need i , 那么轉到STEP 2. 否則,產生出錯條件,這是因為進程Pi 已超過了其最大請求
STEP 2:
如果Requesti <= Available, 那么轉到STEP 3. 否則Pi必須等待,這是因為沒有可用資源
STEP 3:
假定系統可以分配給進程Pi所請求的資源,則修改資源分配狀態,進入安全性檢查
- 如果所產生的資源分配狀態是安全的,那么Pi 可分配到其所需要資源.
- 如果所產生的資源分配狀態是不安全的,那么Pi 必須等待并恢復到原來資源分配狀態
4.銀行家算法實例
假設一個系統,有5個進程:P0、P1、P2、P3、P4。3 種資源類型: A (10個實例), B (5個實例),C (7個實例)。
假定在時間T0,系統資源分配狀態如下:
執行算法過程:
查找滿足如下條件的i :Finish [ i ] = false && Needi <= Work
發現P1滿足以上條件,則Finish[1] 設置為1,
Work = Work + Allocationi;
Work = 【3,3,2】+ 【2,0,0】
繼續往下查找,
發現P3 滿足條件,則Finish[3]設置為1,
Work = 【5,3,2】+ 【2,1,1】= 【7,4,3】;
繼續往下查找,
發現P4 滿足條件,則Finish[4]設置為1,
Work = 【7,4,3】+ 【0,0,2】= 【7,4,5】;
繼續往下查找,
發現P0滿足條件,則Finish[0]設置為1,
Work = 【7,4,5】+ 【0,1,0】= 【7,5,5】;
繼續往下查找,
發現P2滿足條件,則Finish[2]設置為1,
Work = 【7,5,5】+ 【3,0,2】= 【10,5,7】;
此時Finish都為true,說明分配資源后,系統仍出于安全狀態,安全順序為【P1,P3,P4,P0,P2】
對上述例子及銀行家算法和安全狀態的理解:
銀行家算法算的是是否可以分配給某個進程某些資源,所以假設系統把資源分配后,去判斷系統是否仍處于安全狀態。上面例子T0時刻的資源狀態,其實就是某個進程請求了某些資源后的一個狀態,算法需要去判斷這個狀態是否安全,如果安全便可以分配。
上文提到了什么是安全狀態,即在當前資源分配下,存在一個序列使所有進程運行不死鎖。關鍵在于如何知道存在,銀行家算法模擬了最壞情況,即進程每次都請求最大數量的Need(顯然實際環境中進程可能只請求一個實例),如果這樣分配資源仍然能使所有進程都完成,那顯然這個序列就是存在的,系統就是安全的
六、死鎖檢測
如果一個系統既不采用死鎖預防算法也不采用死鎖避免算法,那死鎖可能出現,這種環境下系統可以提供:
- 檢測算法:確定系統是否進入死鎖
- 恢復算法:從死鎖狀態中恢復
需要從如下兩個方面分別考慮這個問題:
- 第一個方面,每個資源類型有單個實例
- 另一個方面,每個資源類型有多個實例
1.每種資源類型只有單個實例
檢測算法:用等待圖,它是資源分配圖的一個變形,從資源分配圖中刪除所有資源類型節點,合并適當邊,就能得到等待圖。
- 每個節點是進程
- Pi → Pj 意味著進程Pi等待進程Pj釋放一個Pi所需的資源
如等待圖中有環,系統中存在死鎖。
為檢測死鎖,系統需要維護等待圖,并周期性的調用在圖中進行搜索環的算法
2.每種資源類型可有多個實例
類似于銀行家算法
3.應用檢測算法
何時調用算法取決于:
- 死鎖發生的頻率
- 死鎖發生時,有多少進程會受影響
每次資源請求調用檢測算法
每次資源請求不被允許時調用檢測算法
七、死鎖恢復
當檢測算法確定已有死鎖是,需要打破。打破死鎖有兩個選擇,一個是簡單的終止一個或多個進程來打破循環等待;另一個是從一個或多個進程那里搶占一個或多個資源
1.終止進程
兩種方法:
- 終止所有死鎖進程
- 一次只終止一個進程直到取消死鎖循環為止
如果采用部分終止,我們應該終止造成最小代價的進程,許多因素影響了選擇哪個進程:
- 進程的優先級
- 進程已計算了多久,進程在完成指定任務之前還需要多久
- 進程使用了多少數量的何種類型的資源
- 進程需要多少資源以完成
- 多少資源需要被終止
- 進程是交互的還是批處理的
2.資源搶占
通過搶占資源以取消死鎖,逐步從進程中搶占資源給其他進程使用,直到死鎖被打破為止。
需要處理三個問題
- 選擇犧牲品:搶占哪些資源和哪個進程
- 需要考慮饑餓:避免同一個進程總成為犧牲品
- 回滾(Rollback):必須把不能正常運行的進程,回滾到某個安全狀態,以便重啟進程
-
cpu
+關注
關注
68文章
10855瀏覽量
211610 -
內存
+關注
關注
8文章
3020瀏覽量
74012 -
死鎖
+關注
關注
0文章
25瀏覽量
8077 -
程序
+關注
關注
117文章
3785瀏覽量
81009
發布評論請先 登錄
相關推薦
評論