---
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