Deadlock2

Deadlock Detection and Recovery

- Deadlock Detection

1. Resource type 당 single instance인 경우

• 자원할당 그래프에서의 cycle이 곧 deadlock을 의미

2. Resource type 당 multiple instance인 경우

• Banker's algorithm과 유사한 방법 활용

 

- Wait-for graph 알고리즘

1. Resource type 당 single instance인 경우

2. Wait-for graph

• 자원할당 그래프의 변형
• 프로세스만으로 node 구성
• Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj

3. Algorithm

• Wait-for graph에 사이클이 존재하는 지를 주기적으로 조사
• O(n^2)

- Recovery

1. Process termination

• Abort all deadlocked processes
• Abort one process at a time until the deadlock cycle is eliminated

2. Resource Preemption

• 비용을 최소화할 victim의 선정
• safe state로 rollback하여 process를 restart
• Starvation 문제(동일한 프로세스가 계속해서 victim으로 선정되는 경우, cost factor에 rollback 횟수도 같이 고려)

 

 

 

Deadlock Ignorance

- Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음

• Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
• 만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처
• UNIX, Windows 등 대부분의 범용 OS가 채택