Operating System - CH7 Deadlocks

deadlock example

sempohere A and B =1,

  P0              P1

wait(A)     wait(B)

wait(B)     wait(A)

7.1 System Model

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

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

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

7.2 Deadlock Character

要死結必須要滿足以下四個條件，缺一不可

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

Resource-Allocation Graph

• 沒有 cycle -> 沒有deadlock
• 如果有cycle
  • 每個resource裡 只有一個instance的話，則有cycle -> 有 deadlock
  • 每個resource裡 有好幾個instance的話 -> 可能有deadlock

Graph with a cycle but no deadlock

• 可以把p4佔據的資源free掉，但p4可能starvation

Method for Handling Deadlocks

1. ensure never enter deadlock
2. allow enter deadlock, but can recovery
3. ignore

Deadlock處理策略

1. deadlock prevention
   • 避免上述四條件發生
     1. mutual exclusion: not sharable resource, but 違反常理
     2. ...
2. deadlock avoidence
   • 當某個process 提出申請時，OS會執行banker's algo, 判斷系統是否處於safe state，若是unsafe state 就可能會deadlock，會讓process過一段時間再申請。
   • safe state: 代表有一個 safe sequence<P1, P2, ...Pn> of all the processes in the system
   • 檢查process不會發生Circular Wait狀況
   • Avoidance algo
     • single instance of a resource type: use resource-allocation graph (將request edge 轉換成 assignment edge時， 要避免形成cycle)
     • multiple instance of a resource type: use the banker's algo (優點:避免產生死結 缺點:耗時)
3. deadlock detection & recovery
   • allow the system enter a deadlock state and then recover
   • 用 detect algorithm
   • recovery from deadlock
     • 一次關閉一個process，直到沒有deadlock後
     • resource preemption
       • 選一個犧牲者- min cost
       • rollback- 回到safe state, restart the process
       • 可能造成startvation (prcoess 一直被犧牲)
4. ignored

1.2.

優點 保證system不會發生deadlock

缺點 (1) resource utilization 偏低 (2)可能會有starvation

3

優點 resource utilization throughput 較高

缺點 (1) 系統會發生deadlock  (2) detection & recovery 的cost較高