---
# System prepended metadata

title: 作業系統 ch8 Deadlock
tags: [作業系統]

---

---
tags: 作業系統
---

# 作業系統 ch8 Deadlock

- Deadlock condition
    - mutual excludsion
    - hold and wait
    - circle waiting
    - no preemption

- Resource allocation
    - request edge、allocation edge
    - vertice two type: process、resource
    - have cycle and resource have only one instance => deadlock

- handle deadlock
    - deadlock avoidence、prevention
    - recover from deadlock
    - ignore
    

- deadlock prevention
    - mutual excludsion: read-only file 可共用資源
    - hold and wait: request resource 的時候，手上不可握有其他資源 (lead to low resource utilization)
    - circle waiting: 安排資源使用線程
    - no preemption: if request resource failed，release allocated resource

- deadlock avoidence
    - priori (info about max number of resource needed)
    - safe state \ unsafe state ( probable deadlock )
    - single instance (resource-allocation graph)
    - multi instance (Banker's Algorithm)

- resource-allocation graph (single、multi instance)
    - claim edge
    - request edge
    - assignment edge
(wait-for graph - only suitable for single instance)

- Banker's Algorithm
    - use in multi-instance resource
    - avaliable (work)：現有可分配資源
    - max：process 所需最大資源量
    - allocation：已分配資源數
    - need（request）：尚需要多少資源
    - if exist finish[i] = false  => deadlock

- deadlock detection (periodically)
    - allow enter deadlock
    - single instance of each resource type
    - wait-for graph (only process、one resource instance)
    - allocation[i] != 0 => Finish = false
    - problem: how often to invoke detection
    - How to recovery from deadlock
        - process termination (abort all or chosen one)
        - resource preemption
            - select victim
            - rollback: return to safe state
            - starvation
