Intro

必須滿足以下所有條件 :

  • Mutual Exclusion : 獨佔資源
  • Hold and wait : request不滿足時不會release現有資源
  • No preemption : 不能強制收回資源
  • Circular waiting : 存在round概念，每個process都在等別人

處理方式

Prevention

  • 破壞mutual exclusion : 共享資源
  • 破壞hold and wait : request之前先release
  • Preemption : 強制收回
  • 破壞circular waiting : 對Allocation設定線性順序

Avoidance

Banker’s Algorithm

假定系統處在Safe state, 若分配後導致不安全，則拒絕

維護Available, Max, Allocation, Need, 其中 :

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

流程如下 :

  • Initial check
    • $Request[i] \leq Need[i]$
    • $Request[i] \leq Available$
  • Tentative allocation
    • 假設暫時分配如下(還沒分配)
    • $Available = Available - Request[i]$
    • $Allocation[i] = Allocation[i] + Request[i]$
    • $Need[i] = Need[i] - Request[i]$
  • Safety check
    • 搜尋安全順序
    • 假設 $Work=Available, \quad Finish[i]=false$
    • 對所有process遍歷, 若滿足則 $Work = Work + Allocation[i]; Finish[i]=true$
    • 如果結束時所有 $Finish[i]=true$ 則系統安全
  • Allocate
    • 檢查通過才會分配

Detection

  • Single : 對RAG做拓樸排序, 如無法偵測到環則無deadlock
  • Multiple : 檢查unsafe state (Banker’s Algo)

Recovery

  • Terminate process : 殺到沒有deadlock
  • Preempt resource

Ignore

  • Modern OS ignore deadlock
    • 使用者需要手動重啟Windows