首頁

# Deadlock Characterization


Deadlock 意思是系統中存在一組 process 陷入互相等待對方所擁有的資源的情況，造成所有的 process 無法往下執行，使得 CPU 利用度大幅降低

Deadlock 發生須符合以下四項充要條件（四個條件都要成立 for possible deadlock）：

  1. Mutual Exclusion : 資源不可共享
  2. Hold and Wait : 已分配資源的 process 可再請求其他資源
  3. No Preemption : 資源不可被強制奪取
  4. Circular Wait :
    • 存在一個 waiting processes set
    • P0→P1→P2→...→Pn→P0P_0\rightarrow P_1\rightarrow P_2\rightarrow ... \rightarrow P_n\rightarrow P_0（deadlock 不會存在於 single process 環境中）

# Deadlock vs Starvation

# Deadlock Detection

  • 沒 cycle 就一定不會發生 deadlock，Circular wait 這個條件不會成立
  • 如果圖有 cycle
    • 每個 resource type 只有一個 instance → deadlock
    • 每個 resource type 有多個 instances → 可能有 deadlock

# Handling Deadlocks

  • 確保系統永不進入 deadlock state
    • deadlock prevention
      • 事前避免
      • 確保四個條件至少有個條件不成立
    • deadlock avoidance
      • 執行過程間避免
      • 在分配之前，動態檢查 resource-allocation state
      • 沒有 deadlock 危險性才會讓過
  • 允許進入 deadlock state 而後要能 recover
    • deadlock detection
    • deadlock recovery
  • 忽略問題和假裝 deadlock 從未發生在 system
    • 交由使用者自己去解決，選一個砍掉

# Deadlock Handling Strategies

  • prevention 和 avoidance 保證系統不會進入 Deadlock，但資源利用度低
  • 而 detection 資源利用度較高，但若 Deadlock 需要做 recovery，則 cost 極高

# Deadlock Prevention

打破必要條件四項之一，即可保證 Deadlock 永不發生

  • Mutual exclusion：
    • 如果資源是分享的，就不用擔心他會產生 deadlock
      e.g. read-only data
    • 有些資源不是 sharable
      e.g. printer
  • Hold and wait：
    • 行程要求一個資源時不能握有任何資源
    • 除非 proces 可以一次取得所有工作所需的資源，才允許持有資源
    • 資源使用率低，想要用，卻不能用，可能產生 starvation
  • Preemption : 讓高優先 process 搶低優先 process 的資源，會造成 starvation
  • Circular waiting：Process 須按照資源編號遞增方式申請資源
    • Let R=R0,R1,...,RNR={R_0, R_1, ..., R_N} be the set of resource types
    • When request RkR_k, should release all RiR_i where i>ki>k
    • 例：
      • F(tape drive) = 1, F(disk drive) = 5, F(printer) = 12
      • 行程必須要求 tape、disk drive 在 printer 之前
      • 若是已經有了 printer，此時想要 tape，必須先將 printer free 掉

# Deadlock Avoidance


process 提出資源申請時，OS 會執行 Banker algorithm 來判斷系統在「假設核准該申請後」是否處於 Safe state，是則核准，否則請 process 等待

  • safe state : 存在 safe sequence
  • unsafe state : 可能有 deadlock

# Algorithms

  • Single instance of a resource type：resource-allocation graph (RAG) algorithm based on circle detection
  • Multiple instances of a resource type：banker’s algorithm based on safe sequence detection

# Resource-Allocation Graph (RAG) Algorithm

  1. Request edge
    Pi→RjP_i \rightarrow R_j（代表 process 請求資源）
  2. Assignment edge
    Rj→PiR_j \rightarrow P_i（代表資源已分配給 process）
    釋放資源時，assignment edge 轉為 claim edge
  3. Claim edge
    Pi⇢RjP_i \dashrightarrow R_j（代表 process 未來可能會請求資源）
    請求資源時，則將 claim edge 轉為 request edge
  • resource 在試驗前一定要先被 claim
  • 只有當沒有 cycle 被產生才能核准 request
    • 使用 cycle-detection algorithm, O(n2)O(n^2)
  • 一個 request 若被改成 assignment 可能會產生 cycle，則被 reject 或 delay

# Safe state

  • safe state : 存在 safe sequence
  • unsafe state : 可能有 deadlock
  • deadlock avoidance：確保系統永不進入 unsafe state
  • 定義
    • 如果存在 sequence of allocations 去滿足所有行程的 request，則說 system 處在 safe state
    • 此 sequence of allocations，稱作是 safe sequence

# Banker’s algorithm

  • Banker algorithm
    • 使用通用的 safety algorithm 去提早決定在分配之後，是否有 safe sequence 存在
    • safe sequence 存在時，才會去執行分配動作
  • Safety algorithm
    1. 假設 processes 需要 maximum resources
    2. 找到一個行程，若是分配後 available resources 能被滿足即分配給他
      釋放被該行程使用的資源
      反覆執行直到所有的行程都被滿足
  • Single instance : topological sort (using wait-for graph)
    • 使用 adjcent matrix：O(n2)O(n^2)
    • 使用 adjcent list：O(V+E)O(V+E)
  • Several instance : 用 Banker algorithm 判斷系統是否已經在 unsafe state

Recovery scheme :

  • 終止 process (成本都高)
    • 全部刪除
    • 一次刪一個 process，直到打破 deadlock。
  • 資源搶奪
    • 剝奪 victim process 資源 (可能造成 starvation)
    • 恢復無該資源前狀態 (cost 高)

# Single Instance of Each Resource Type

  • 若有 circle 就是死結
  • 將 request/assignment edges 轉成 wait-for graph
  • 如果有 cycle 存在 wait-for graph，deadlock 存在

# Multiple-Instance for Each Resource Type

  • Total instances: A:7, B:2, C:6
  • Available instances: A:0, B:0, C:0
  • safe state → <P0, P2, P3, P1, P4> → no deadlock
  • If P2 request = <0, 0, 1> → no safe sequence → deadlock
process Allocation(A B C) Request(A B C)
P0 0 1 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 0
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2

# Process termination

  1. 中斷所有 deadlocked 的行程
  2. 一次中斷一個行程，直到 cycle 排除
    哪個行程我們應該先中斷？

# Resource preemption

  1. 選一個受害者去 preempt
    which one to preempt？
  2. rollback
    • checkpoint
    • 部份 rollback 或全部 rollback？
  3. starvation
    可以同一個行程被 preempted？

# Ref Notes

  • Kipper’s Note
  • Chang-Chia-Chi’s Note
  • 陳品媛的筆記
  • Mr. Opengate. OS - Ch7
  • WillyWangkaa’s Note