07. 死結 (Deadlock)

7.1 System Model

每一種資源都有一定的instances,像是可能有五個disk,不止一個的I/O devices,每一個

process 要利用資源都有以下三種階段

  1. 要求資源
  2. 使用資源
  3. 釋放資源

7.2 Deadlock Character

要死結必須要滿足以下四個條件

  1. Mutual exclusion:一個資源一次只能被一個process所使用
  2. Hold and Wait: process取得一個資源之後等待其他的資源
  3. No preemption:資源只能由process自己釋放,不能由其他方式釋放
  4. Circular wait:每個process都握有另一個process請求的資源,導致每一個process都在等待另一個process釋放資源

System Model可以用Resource-Allocation Graph(RAG)的方式去用圖表描述,如果圖表中沒有

cycle,就不會發生死結,如果有cycle,則看資源的是不是只有一個instances,若只有一個,

則會發生deadlock,若不只一個,則有可能發生deadlock。

7.3 Method for handling

一般而言,我們可以處理死結問題(deadlock problem)使用下列三個方式其中之一

  1. 我們可以使用一個協議(protocol)去預防或是避免死結(deadlocks),確定系統永遠不會進入死結狀態(deadlocked state)。
  2. 我們可以允許系統進入死結狀態(deadlocked state),然後偵測它,恢復它。
  3. 我們可以完全無視這些問題,假裝這些問題從來不曾發生過。

第三種方法是其中最多作業系統使用的方式,包括Linux、Windows,它讓程式開發者自己來處

理這些問題。

接下來我們簡單解釋這三個處理死結(deadlocks)的方法,在7.4到7.7再來詳細解釋其演算法。

在開始前,我們應該提到有些學者認為沒有任何單獨的基本方法可以符合所有範圍的作業系統資

源分配問題(resource-allocation problems)。然而基本的方法可以組合,讓我們可以選擇一個

最佳的方法針對系統的個別資源。

為了確認死結(deadlocks)永遠不會存在,系統可以使用死結預防(deadlock-prevention)跟死結

避免(deadlock-avoidance)方案。

死結預防(Deadlock prevention)提供一組方法去確認至少一個必要的死結情況(7.2.1有談到)

不會發生。這些方法靠著限制資源的需求來達成預防死結。我們在7.4會討論這些方法。

死結避免(Deadlock avoidance)要求作業系統給出額外的資訊,關於一個程序(process)在他的

生命期限(lifetime)裡會要求的資源(resource)。有了這些額外的資訊,作業系統可以決定是否

讓程序的要求繼續等候。為了決定現在的要求是否能滿足,作業系統必須考慮現在資源的存量、

資源的分配量、和未來資源的要求與釋放。我們將在7.5討論這些方法。

如果一個系統沒有使用死結預防(deadlock-prevention)或死結避免(deadlock-avoidance)演算

法,那死結情形(deadlock situation)就有可能產生。在這種環境底下系統可以提供一個演算法

進入一個狀態來判斷死結是否產生,並且加以恢復。我們將在7.6和7.7討論這些議題。

在我們連偵測跟恢復的演算法都沒有的情況下,我們可能發生一個情形,系統正在一個死結狀態

(deadlocked state)之下,但是我們無法發現。

在這個情形之下,沒被發現的死結可能導致系統效能的惡化,因為資源被程序掌握了,會有越來

越多的程序進入死結狀態,直到你的電腦超過負荷。

雖然這個方法沒有一個可見的形式針對死結問題,但他還是最常被使用在作業系統,無視死結的

可能性是比其他的方法更加的有效率,因為在大多數的系統上死結的情形並不常發生。除此之外

用來恢復其他狀況的方法有可能被用來處理死結狀況。在有些環境下,系統是在凍結狀態(frozen

state)而非死結狀態。系統必須有手動恢復方法來處理這些狀況,而且也能簡單的利用這些技術

來恢復死結狀態。

7.4 Deadlock pretention預防死結

針對7.2提到的死結必須滿足的條件去做預防

  1. Mutual exclusion:對不可共用的資源類型而言,互斥一定成立,而可共用的資源類型,因為可以同時讀取相同檔案,所以一定不會產生。
  2. Hold and Wait:process必須保證一個行程在要求一項資源時,不可以佔用任何其它的資源。
  3. No preemption:只要某個處理元要不到所要求的資源時,便把它已經擁有的資源釋放,然後再重新要求所要資源。
  4. Circular Wait:確保循環式等候的條件不成立,我們對所有的資源型式強迫安排一個線性的順序。

7.5 Deadlock Avoidance死結的避免

為了確保死結不會發生,我們定義一個安全的狀態--能夠分配給所有process資源而不會造成死

結,在不安全的狀態下則有可能發生死結,假設我們知道

  1. 系統目前可用的資源數量(Available)
  2. 各process對資源的最大需求量(max)
  3. 各process目前持有的資源量(allocation)

各系統還需多少資源(need) = max - allocation

Safety演算法:

定義:

1.Work[1..m]:    表示系統目前可用資源數量之累計

2.Finish[i]的值: True:Pi已完成工作

                  False:尚未完成工作

判斷:

step

1.Work = Available

Finish[i] = False, 1≤i≤n

2.找出Pi,滿足兩個條件:

(1)Finish[i] = False

(2)Needi≤Work

若可以找到,到step3,否則到step 4

3.設定Finish[i] = True且Work = Work + Allocationi

  到step2

4.檢查Finish陣列,若皆為True,則系統處於Safe State,否則處於Unsafe State

Note:

存在≥1組"Safe Sequence"使得processes依此順序執行,皆可完成工作就是安全的狀態,如果

找不出一組Safe Sequence就是在不安全的狀態。

Resource_Allocation_Graph演算法結論:

在資源為多樣(multiple instances):

沒有循環就沒有死結

有循環不一定有死結

但如果所有資源皆為單一量(single instance),則有cycle就有死結

Banker's演算法:

假設n為process數目,m為resource數目

定義:

1.Request_i[1..m] :Process_i的資源申請量
EX:Request_i[j] = k,表Pi申請k個Resourcej(Rj)

2.MAX[1..n,1..m] :表示各process對各類資源的最大需求量
EX:MAX[i,j] = k,表示Process_i對於Resourcej(Rj)的最大需求量為k

3.Allocation[1..n,1..m] :表示各process目前持有的資源量
EX:Allocation[i,j] = k,表示processi(Pi)目前持有k個Resourcej(Rj)

4.系統資源總量 Available[1..m]

  Available_i = 資源總量- Allocation_i

5.Process需求量Need[1..n,1..m]

  Need_i = MAX_i - Allocation_i

判斷:

Steps:

1.檢查Request_i ≤ Need_i
若不成立,則OS終止此process
否則到step2

2.檢查Request_i ≤ Available
若不成立,則Process_i必須wait直到Resource Available
否則到step3

3.計算
Allocation_i = Allocation_i + Request_i
Need_i = Need_i - Request_i
Available = Available – Request_i

4.執行"Safety Algorithm"
如果系統判斷會處於Safe state則核准申請,不行則否決此次申請,稍後再重新申請

此演算法所需時間太多,不可能應用在實務上,共花費:O(n*n*m)

7.6.Deadlock Detection死結的偵測

(1)系統中可能存在Deadlock(if prevention and avoidance不用)

   偵測死結是否存在,若死結存在,則必須打破死結,恢復正常的機制。

(2)優點:resource utilization較高,Throughput↑

   缺點:cost太高

Deadlock detection algorithm

定義:

1.Available[1..m] 表系統目前可用資源數量

2.Allocation[1..n,1..m] 各process目前所持有的資源量

3.Request[1..n,1..m] 表示目前各process所提出的各類資源申請數量

4.Work[1..m] 目前可用資源數量之累計

5.Finish[1..n] of boolean
Finish[i] = false:尚未完成且Allocation!=0

              trun:已完成

判斷:

Steps:

1.設定初值

Work = Available
Finish[i] = false, if Allocation != 0

           true, otherwise

2.找到Pi滿足

Finish[i]=false

Requesti≤Work

若找到,則goto 3 ,否則 goto 4

3.設定Finish[i]=true 且 Work = Work + Allocationi goto 2

4.檢查Finish鎮列,若皆為true,則表示system無死結存在
否則,Deadlock存在 (且那些Finish[i]為false的processes陷入死結)

7.7死結的恢復

一旦檢測出死結,則就要採取一些策略使系統從死結中恢復,常有以下方法來從死結中恢復:

(1)結束所有死結進程。即強制性地從系統中撤銷死結進程,並剝奪它們的資源給剩下的進程使

   用。(使前面的工作全部損失)

(2)將死結進程退回到前一個檢查點,並重新從該檢查點啓動這些進程(前提是系統必須提供檢

   查點和重新啓動的機制)。

(3)相繼的逐個結束死結進程直至死結不再存在。在每個進程結束後,都要使用死結檢測算法以

   確定死結是否依然存在。

(4)相繼的逐個搶佔死結進程的資源,直至死結不再存在。但搶佔資源的方法是否可行,往往與

   資源特性有關。有時搶佔資源還需要人工干預,例如搶佔激光印表機時就需將原來影印的紙

   張先放到一邊去,並使被搶佔進程回到當初獲得資源時的斷點。

由於所有使死結進程相繼結束和強佔資源策略均涉及損失了這些進程已完成工作的開銷。因此要

基於成本的基礎上選擇結束進程的次序。首先要優先選擇以下死結進程:

1.選擇使用最少處理器時間的進程。

2.選擇使用最少輸出工作量的進程。

3.選擇具有最多剩餘時間的進程。

4.選擇分的最少資源進程。

5.具有最小優先級的進程。