7. Deadlock

-The Deadlock Problem

Deadlock(교착상태)

• 그림과 같이 누군가 희생을 하지 않고 자원(길목)을 가지고 있으면서 상대방의 자원(다른 길목)을 요구하는 상황

출처 : https://denninginstitute.com/itcore/processes/Dead.html

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

Resource(자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념 (ex : I/O device, CPU cycle, semaphore 등)
• 프로세스가 자원을 사용하는 절차 (Request, Allocate, Use, Release)

Deadlock Example 1 

• 시스템에 2개의 tape drive가 있다.
• 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.

Deadlock Example 2

• Binary semaphores A and B

P0	P1
P(A);	P(B);
P(B);	P(A);

 

- Deadlock 발생의 4가지 조건(모두 만족)

• Mutual exclusion(상호배제) : 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
• No preempthon(비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• Hold and wait(보유대기) : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
• Circular wait(순환대기) : 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

---

- Resource-Allocation Graph(자원할당그래프)

• P → R : 프로세스가 자원을 요청한 상태
• R → P : 프로세스가 자원을 획득한 상태
• 자원 안의 검은 점 : instance를 나타냄

* 그래프에 Cycle이 없으면 Deadlock이 아니다.

* 그래프에 cycle이 있으면 

• if only one instance per resource type, then deadlock
• if several instances per resource type, possibility of deadlock

위의 그림은 Deadlock

이유 : 자원 2가 2개의 instance를 가지지만 두 개의 cycle이 형성되어 있기 때문에

---

- Deadlock 처리 방법

• Deadlock Prevention(예방) 
  - 자원 할당 시 Deadlock의 4가지 필요 요건 중 어느 하나가 만족되지 않도록 하는 것
  → Utilization 저하, throughput 감소, starvation 문제
• Deadlock Avoidance(예방)
  - 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
  - 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
• Deadlock Detection and Recovery(회복)
  - Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover
• Deadlock Ignorance(회복) 
  - Deadlock을 시스템이 책임지지 않음
  
  • UNIX를 포함한 대부분의 OS가 채택 
  • Deadlock이 매우 드물게 발생하므로 Deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
  • 사용자가 직접 process를 죽임으로써 deadlock을 해결