[OS] Deadlock

Deadlock(데드락): 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

 

Resouce(자원)이란?

• 하드웨어, 소프트웨어 등을 포함하는 개념
• ex) I/O Device, CPU Cycle, Memory Space, Semaphore 등
• 프로세스가 자원을 사용하는 절차(request, allocate, use, release)

 

Deadlock 예시

왼:https://slideplayer.com/slide/13154091/79/images/6/Example+of+Deadlock+A+system+has+two+tape+drives%2C+which+processes+P1+and+P2+need..jpg / 오: https://images.slideplayer.com/15/4796093/slides/slide_5.jpg

 

DeadLock 발생 조건 4가지

1. Mutual Exclusion : 매 순간 하나의 프로세스만이 자원을 선점할 수 있다

2. No Preemption : 프로세스는 스스로 자원을 내놓기 전까지는 강제로 빼앗기지 않는다

3. Hold and Wait : 자원을 가진 프로세스가 추가 자원을 기다릴 때 보유한 자원을 포기하지 않는다

4. Circular Wait : 자원을 기다리는 프로세스들 간에 사이클이 형성된다

반대로, 이 중 조건을 하나라도 만족하지 않으면 데드락이 형성되지 않는다 ❗❗

 

Resource - Allocation Graph

http://1.bp.blogspot.com/_SuTNOAulagU/SpZRQ_dxV1I/AAAAAAAAANk/T1DVYmlt9_c/s320/yii.png

resource-allocation graph는 어떤 프로세스가 어떤 자원을 점유하고 있고, 현재 어떤 자원을 요구하는지 나타낸 그래프이다.

이 graph에서 cycle이 생기지 않으면, 데드락이 발생하지 않는다. 또한 resource마다 instance가 하나밖에 없으면 데드락이 발생할 수 있다.

 

데드락은 예방, 방지, 탐지 및 복구, 무시 방법을 통해 처리할 수 있다

 

Deadlock Prevention

: 자원 할당 시 데드락의 4 가지 필요 조건 중 어느 하나가 성립하지 않도록 하는 것

1. 공유해서는 안 되는 자원의 경우 반드시 성립해야 함
2. 프로세서가 자원 요청 시 다른 어떤 자원도 가지고 있지 않아야 함
   • 프로세스 시작 시 모든 필요한 자원을 한번에 할당
   • 자원이 필요할 경우 보유 자원을 모두 포기하고 다시 요청
3. 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨.
   • 모든 필요한 자원을 얻을 수 있을 때 해당 프로세스 다시 시작
   • State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)
4. 모든 자원 유형에 할당 순서를 정해 그 순서대로만 자원 할당

하지만 utilization 저하, throughput 감소, starvation 문제가 발생할 수 있다.

 

Deadlock Avoidance

: 자원 요청에 대한 부가적인 정보를 이용해서 데드락 가능성이 없을 때 에만 자원 할당

ex) 프로세스들이 필요로 하는 각 자원 별 최대 사용량을 미리 선언하도록 정의

safe state: 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

safe sequence

• 프로세스의 sequence <P1, P2, ... , Pn)이 safe하려면 Pi의 자원 요청이 "가용 자원 + 모든 Pj (j<i)의 보유 자원"에 의해 충족되어야 함
• 조건 만족 시 다음 방법으로 모든 프로세스의 수행 보장
  • Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj (j<i)가 종료될 때 까지 기다린다
  • Pi-1이 종료되면 Pi의 자원 요청을 만족시켜 수행

➡ system이 unsafe state에 들어가지 않는 것을 보장한다 ❗

 

Avoidance 알고리즘에는 두 가지 종류가 있다

1. Single instance per resource types - Resourse Allocation Graph Algorithm

2. Multiple instances per resources types - Banker's Algorithm

Deadlock Detection and Recovery

Detection

• Resource type 당 single instance인 경우: 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미
• Resource type 당 mutiple instance인 경우: banker's algorithm과 유사한 방법 활용

+ Wait-for graph 알고리즘(Resource type 당 single instance인 경우): 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 Ignore

: 데드락이 발생하지 않는다고 생각하고 아무런 조치도 취하지 않는다 ❗

• 데드락이 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드를 불러올 수 있다
• 만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처
• 의외로 UNIX, Window 등 대부분의 범용 OS가 이것을 채택하고 있다