Chapter 5 Deadlock(死結)

前一章 | 首頁 | 下一章

Deadlock Def:

一組processes陷入互相等待的情況(Circular waiting)
造成processes接無法往下執行,使得CPU utilization及Throughput大幅降低

Deadlock vs Starvation

Deadlock Starvation
一組processes形成circular waiting,導致processes無法往下執行 某(些)processes形成infinite Blocking
∵長期無法取得完成工作所需資源
不允許資源preemptive 易發生在不公平、preemptive的環境
CPU utilization及Throughput會大幅下降 與此無關聯
相似點:皆為資源分配及協調出了問題

Deadlock之例子

Deadlock成立的四個必要條件

  1. Mutual exclusion(互斥)
    Def:
    資源在同一時間內,至多只允許一個process使用(不允許≥2個processes同時使用)
    其它欲使用此resource的process必須wait,直到該process釋放resource為止
    eg. printer、Disk、CPU etc.
    eg. 不具mutual exclusion→Read-only File
  2. Hold & wait(持有並等待) (Partial Allocation)
    Def:
    process持有部分資源且又在等待其它processes所持有的資源
  3. No preemption(不可強取豪奪)
    Def:
    process不可搶奪其它waiting process所持有的資源,除非其自願釋放
  4. Circular waiting(循環等待)
    Def:
    存在一組process
    P0→P1→P2→...→Pn→P0
    P0~Pn形成Circular waiting

OSC:

  1. Mutual Exclusion
    not required for sharable resources; must hold for nonsharable resources.
  2. Hold and Wait
    must guarantee that whenever a process requests a resource, it does not hold any other resources.
  3. No Preemption
  4. Circular Wait
    impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration.

Resource Allocation Graph(資源分配圖)

  1. Def:
    令G=<V, E>為一有向圖
    其中V:Vertex(頂點集合)
    可分為二類型態:
    1. Process:以?表示
    2. Resource:以?表示
    而E:Edge(邊集合)亦分為二類
    1. Allocation Edge(配置邊)
    2. 記為Ri→Pj
      資源Ri已分配給Processj
    3. Request Edge(申請邊)
    4. 記為Ri←Pj
      Processj申請資源Ri
  2. 結論(★)
    1. No cycle→No Deadlock
    2. 有cycle不一定有Deadlock(針對if各類資源之數量>1個 [Multiple instances])(★)
    3. 說明:
      此圖雖有cycle存在,但系統不會有死結
      ∵一旦P3完成工作,會釋放R2給P2,則cycle就不存在
      即不存在cycle,則無Deadlock
    4. if所有資源皆為單一量(single instance)
      則有cycle←→有死結

Deadlock Prevention(死結預防)

  1. 觀念:
    打破四個必要條件之其一,就可保證死結永不發生
  2. 作法:
    1. 打破"Mutual Exclusion"
    2. 很困難(不可能)打破
      ∵Mutual Exclusion是(某些)Resources與生俱來的性質
    3. 打破"Hold&Wait"
    4. 作法:OS可採取下列二個協定之一即可
      1. 協定一
      2. 除非process可以一次取得完成工作所需的全部資源,才允許process持有資源,否則不准持有任何資源
      3. 協定二
      4. 允許process在執行之初可先持有部分資源,一旦要申請新資源,則必須先釋放持有的全部資源,才可以提申請
    5. 打破"No Preemption"
    6. 作法:改為preemption即可
      process可以搶奪waiting process所持有的Resource
      Note:死結不會發生。但有可能產生starvation
      解決:採取類似"Aging"技術(將被搶奪的次數,列為提高優先權之依據)
    7. 打破"Circular Waiting"
    8. 作法:OS需採取下列措施:
      1. 給予每個Resource唯一的(unique)資源編號(ID)
      2. 規定process需依資源編號遞增的方式提出申請
      3. eg.  持有          申請
         1    R1      →     R3  ok
         2    R3      →     R1  需先釋放R3,才可申請R1
         3    R1,R5   →     R3  釋放R5, 留R1, 即可申請R3
        
        證明:[反證法]
        假設在這樣的規定下,系統仍存在一組形成circular waiting的process如下:
        P0(R0)→P1(R1)→P2(R2)→...→Pn(Rn)→P0(R0)
        且令各process所持有的資源編號分別為:R0, R1, ..., Rn
        且R0≠R1≠R2≠...≠Rn
        根據遞增申請的規則
        竟可推出R0<R1<R2<R3<...<Rn<R0
        得出Rn<R0此一矛盾現象
        ∴假設不成立,即系統不存在有Circular Waiting之情況!!
  3. Summary:

Deadlock Avoidance(避免)

  1. Def:
    當process提資源申請(Request)時,則OS需依據下列資訊:
    1. 系統目前可用的資源數量
    2. 各process對資源的需求量
    3. 各process目前持有的資源量
    執行Banker's Algorithm(內含Safety Algorithm)判斷系統核准後,是否處於Safe state,若是,則核准申請,否則(處於unsafe state),則否決此次申請,Process則等待依段時間後再重新申請

Banker's Algorithm

假設n為process數目,m為resource數目
  1. Data Structure Used
    1. Requesti[1..m] (會給)
    2. 表示Processi的資源申請量
      其中Requesti[j]=k,表Pi申請k個Resource Rj
    3. MAX[1..n,1..m] (會給)
    4. 表示各process對各類資源的最大需求量
      其中MAX[i,j]=k,表示Pi對於Resourcej的最大需求量為k
    5. Allocation[1..n,1..m] (會給)
    6. 表示各process目前持有的資源量
      其中Allocation[i,j]=k,表示Pi目前持有k個Resourcej
    7. 系統資源總量 (會給)
    8. Available[1..m] (算)
    9. Available=資源總量-ΣAllocationi
    10. Need[1..n,1..m] (算)
    11. Needi=MAXi-Allocationi
  2. Procedures
  3. Steps:
    1. 檢查Requesti≤Needi
      若不成立,則OS終止此process
      否則goto step 2
    2. 檢查Requesti≤Available
      若不成立,則Processi必須wait直到Resource Available
      否則goto step 3
    3. (暫時核准)(試算)
      Allocationi=Allocationi+Requesti
      Needi=Needi-Requesti
      Available=Abailable-Requesti
    4. 執行"Safety Algorithm"
      if 系統判斷會處於Safe state
      then 核准申請
      else 否決此次申請,稍後再重新申請

Safety Algorithm

  1. Data Structure Used
    1. Work[1..m]
      表示系統目前可用資源數量之累計
    2. Finish[1..n] of Boolean
      Finish[i]的值
      1. True:Pi已完成工作
      2. False:尚未完成工作
  2. Procedures
  3. Steps:
    1. 設定初值
      Work=Available
      Finish[i]=False, 1≤i≤n
    2. 找出Pi,滿足兩個條件:
      1. Finish[i]=False
      2. Needi≤Work
      若可以找到,則goto step 3
      否則goto step 4
    3. 設定Finish[i]=True且Work=Work+Allocationi
      goto step 2
    4. 檢查Finish陣列,若皆為True,則系統處於Safe State,否則處於Unsafe State
Note:
  1. Safe State
  2. Def:
    存在≥1組"Safe Sequence"使得processes依此順序執行,皆可完成工作
    if 找不出一組Safe Sequence
    then Unsafe State
  3. Safe, Unsafe, 與Deadlock之關係
例題:

Banker's Algorithm分析

針對"每類資源皆為single instance"之情況,有較為簡易的Avoidance作法

使用Resource Allocation Graph+claim edge

  1. Def:
    在Resource Allocation Graph中多加入一種邊,稱為claim edge(宣告邊)
    Pi...→Rj,表示Pi在未來將會對資源Rj提出申請
  2. 作法:當Processi提出對資源Rj之申請後,則執行下列steps:
    1. 將claim edge Pi...→Rj改為Request edgePi→Rj
    2. 再將Request edge改為Allocation EdgePi←Rj
    3. 偵測圖形中是否有cycle存在(O(n2),n:process數),若有,則表示system為unsafe state
      ∴拒絕此次申請,否則,核准
例:

定理(記)

若系統中有n個processes,共享m個資源(同一類)
則system id Deadlock Free的話,必須滿足:
  1. 1≤Maxi≤m
  2. i=1nMaxi<n+m (Maxi表Processi的資源最大需求量)

例1:[計算型]
若系統中有6部printer,每個process最多需要2部才可以完成工作
試問在確保system is Deadlock Free,最多可允許?個process在系統內執行。

Ans:
m=6, Maxi=2
條件:

  1. 1≤Maxi(2)≤m(6)
  2. i=1nMaxi<n+m⇒2n<n+6⇒n<6
∴n最多為5個

例2:[證明型]
pf:
假設Deadlock存在
i=1nAllocationi=m
根據Banker's Algo
i=1nNeedi=i=1nMaxi-i=1nAllocationi
i=1nNeedi+i=1nAllocationi=i=1nMaxi
依條件二
i=1nNeedi+m<n+m
i=1nNeedi<n⇒∴至少有一個process的Needi為0(即不給額外資源,此process仍能完成)
依條件一(Maxu>1)
∴此process完成工作後,必定會釋放出≥1個resource(∵Allocationi≥1)可供其它process使用,並陸續完成工作(即有safe sequence)
∴system is Deadlock Free (P5-27,第三題)

DeadLock Detection&Recovery

  1. 系統中可能存在Deadlock(if prevention and avoidance不用)
    ∵有必要提供:
    1. 偵測死結是否存在
    2. 若死結存在,則必須打破死結,恢復正常的機制
  2. 優點:resource utilization較高,Throughput↑
    缺點:cost太高

Deadlock Detection Algorithm

  1. Data Structure Used
    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:已完成
  2. Procedures
    steps
    1. 設定初值
      Work = Available
      Finish[i]=
      • false, if Allocation≠0
      • true, otherwise
    2. 找到Pi滿足
      1. Finish[i]=false
      2. Requesti≤Work
      若找到,則goto 3 ,否則 goto 4
  3. 設定Finish[i]=true 且 Work = Work + Allocationi goto 2
  4. 檢查Finish鎮列,若皆為true,則表示system無死結存在
    否則,Deadlock存在 (且那些Finish[i]為false的processes陷入死結)