deadlock PS

Problem Analysis

DEF

(1) Mutual Exclusion

  • resource는 동시에 하나의 thread만 사용 가능

  • 예: lock, mutex

(2) Hold and Wait

이미 resource를 가진 상태에서 추가 resource를 기다림

(3) No Preemption
  • resource를 강제로 뺏을 수 없음
(4) Circular Wait

주체들(thread/process) 간에 wait cycle 존재

  • A → B → C → A

Solution

methods for handling problems
  1. never deadlock state: prevention / avoidance
  2. detect & recover
  3. ignore
    • used by most OS

1. prevention

위 발생 necessary condition 중 하나 이상 깨기

1. No 'mutual exclusion'
  • sharable resource는 가능
    • 예: read-only file.
  • non-sharable resource는 불가능
    • 예: printer
2. NO 'hold & wait'
  • process가 필요한 resource를 처음에 전부 한 번에 받거나
  • 아니면 resource를 하나도 안 들고 있을 때만 새 resource를 request하게 만든다.
  • CONS
    • bad resource utilization
    • [(draft yet): starvation] 가능
3. NO 'no preemption'

기다릴 거면 들고 있던 걸 내려놓게 만든다.

  • CONS
    1. rollback/restart cost가 큼
    2. 모든 resource에 적용하기 어렵다. 특히 CPU register, memory page 같은 건 가능할 수 있지만, printer / file write lock / mutex lock / DB transaction / device IO 처럼 중간에 뺏기 어려운 resource도 있음
4. NO 'circular wait'
  • 모든 resource type에 total ordering을 부여하고, process가 항상 increasing order로 request하게 한다.

2. avoidance

매 request마다 “이걸 허용하면 나중에 deadlock 위험 상태로 가는가?”를 검사하고, 위험하면 거절하는 방식

  1. check the request whether it results in "safe state"
  2. If right, grant. Otherwise do not.
safe state

i) single instance of a resource type

use resource-allocation graph ALG

ii) multiple instances of a resource type

use Banker's ALG

3. detection -> recover

i) single instance of a resource type

use [(draft yet): wait-for graph ALG]

ii) multiple instances of a resource type

use detection ALG

recover 1 — process termination

  1. abort all deadlocked processes
  2. Abort one process at a time until the deadlock cycle is eliminated
In which order should we choose to abort?
  • Priority of the process
  • How long process has computed, and how much longer to completion
  • Resources the process has used
  • Resources process needs to complete
  • How many processes will need to be terminated
  • Is process interactive or batch?

recover 2 — resource preemption

select a victim and rollback to a safe state then restart

  • CONS:
    • starvation possible same process picked as victim repeatedly
    • include number of rollback in cost factor