Deadlock, 데드락

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
• Resource: HW, SW 등을 포함하는 개념
  • I/O device, CPU cycle, memory space, semaphore 등등..

데드락 발생 4가지 조건

데드락은 다음 4가지 조건을 모두 만족해야만 발생한다.

1. Mutual Exclusion(상호 배제)
   • 매 순간 하나의 프로세스만 자원을 사용할 수 있음
2. No preemption(비선점)
   • 프로세스는 자원을 스스로 내어놓을 뿐 뺏을 수 없음
3. Hold and wait(보유 대기)
   • 자원을 가진 프로세스가 다른 자원을 기다릴 때 자원을 놓지 않고 계속 가지고 있음
4. Circular wait(순환 대기)
   • 자원을 기다리는 프로세스간에 싸이클이 형성되어야 함
   • e.g) P0 -> P1 -> P2 -> P0

데드락 처리 방법

데드락을 처리하는 방법에는 다음과 같은 4가지 방법이 있음

1. Deadlock Prevention(데드락 예방)
   • 자원 할당 시 위 Deadlock 4가지 조건 중 어느 하나를 만족되지 않도록 하는 것
2. Deadlock Avoidance(데드락 회피)
   • 자원 요청에 대해서 부가적인 정보를 이용해 Deadlock 가능성이 없는 경우에만 자원 할당
   • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
3. Deadlock Detection and Recovery(데드락 탐지 및 회복)
   • Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두고 Deadlock 발견시에 recover
4. Deadlock Ignorance(데드락 무시)
   • Deadlock을 시스템이 책임지지 않음
   • UNIX 포함한 대부분 OS가 채택

1. Deadlock Prevention

생기지도 않을 데드락에 대해서 제약조건을 많이 달아두기 때문에 이용률이 저하되고, 성능 저하, starvation 문제등이 발생할 수 있음

• Mutual Exclusion 예방
  • 막을 수 있는 조건이 아님, 애초에 여러 프로세스가 동시에 공유할 수 있는 자원이었다면 deadlock 이 발생하지도 않았을 것이기 때문
• Hold and Wait 예방
  • 프로세스가 자원을 요청할 때 어떤 자원도 가지고 있지 않도록 함
  • 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 => 자원이 비효율적으로 관리되는 단점이 있음
  • 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청 => wait하기 전 이미 hold한 자원을 모두 뱉어냄
• No preemtion 예방
  • 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작
  • state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용함(CPU, memory)
• Circular Wait 예방
  • 모든 자원 유형에 할당 순서를 정해서 정해진 순서대로만 자원을 할당시킴

2. Deadlock Avoidance

• 프로세스가 시작될 때 자신이 평생 쓸 자원의 총량을 미리 선언하도록 하게 함
• 자원 요청에 대한 부가정보를 이용해 deadlcok으로부터 안전할때만 자원을 할당함 => 여분이 있어도 안줌
• safe sequence가 존재하는 상태에만 자원을 할당해줌 즉, 항상 safe state를 유지하려고 함
• 자원의 갯수(Instance)에 따라 크게 두 가지 알고리즘이 있음
  • Single Instacne: 자원 할당 그래프 사용
  • Multiple Instance: Banker's Algorithm 사용

자원 할당 그래프 알고리즘

• 실선: process가 자원을 요청한 상태
• 점선: process가 미래에 적어도 한번 요청할 것이라는 상태 (요청 시 실선으로 변경됨)
• 사이클이 생기지 않는 경우에만 요청 자원 할당 => 자원을 사용하는 프로세스가 아무도 없어도 할당해주지 않음

Banker's Algorithm

• process가 앞으로 요구할 자원의 총량(Need)을 가용 자원(Available)의 instance로 충족시킬 수 있을 경우에만 할당해줌
  • e.g) P1이 (1,0,2) 요청하면 Available=(3,3,2)로 Need=(1,2,2)를 충분히 충족할 수 있기 때문에 P1에 (1,0,2)개의 자원을 할당해줌
  • e.g) P0가 (0,2,0) 요청하면 Available=(3,3,2)로 Need=(7,4,3)을 충족하지 못하기 때문에 요청을 거절하고 할당해주지 않음
• sequence <P1, P3, P4, P2, P0> 가 존재하기 때문에 시스템은 safe state 임

3. Deadlock Detection and Recovery

• 발생하지도 않은 데드락을 예방하기 위해서 성능을 포기하느니 성능을 위해 데드락을 허용하고 발생 시에 이를 처리한다는 개념

Deadlock Detection

• 자원의 instace에 따라 두 가지로 나뉨
  • single instance: 자원 할당 그래프 사용, 예방을 위한 사용이 아니기에 점선은 사용하지 않음
  • multiple instance: Banker's algorithm과 유사한 방법 활용, 예방과는 다르게 Need(미래에 요구할 총량) 는 사용하지 않음

Deadlock Recovery

• 데드락이 발생했을 때 이를 복구하는 방법은 크게 두 가지가 있음
• 1. Process termination(프로세스 중지)
  • 데드락에 관여된 모든 프로세스 모두 abort 하는 방법
  • 데드락 싸이클이 없어질 때까지 프로세스를 하나씩 abort 하는 방법
• 2. Resource Preemption(자원 선점)
  • 비용을 최소화할 수 있는 victim process 선정한 후, safe state로 rollback해서 process를 restart함
  • Starvation 문제 발생할 수 있음
    • 동일한 프로세스가 계속해서 victim으로 선정되는 경우가 있음
    • 그래서 cost factor에 rollback된 횟수도 같이 고려해서 victim을 선정함

4. Deadlock Ignorance

• deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
• deadlock은 매우 드물게 발생하기 때문에 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
• 만약 시스템에 deadlock이 발생하면 시스템이 비정상적으로 작동하는 것을 사람이 직접 느낀 후에 직접 process를 죽이는 등의 방법으로 대처함
• UNIX, Windows등 대부분의 범용 OS가 채택한 방법임

---

출처: http://www.kocw.net/home/search/kemView.do?kemId=1046323