Deadlock이란

두 개 이상의 프로세스 혹은 스레드가 일부 리소스를 가지고 있으면서 서로가 가진 리소스를 기다리는 상태

※ 프로세스가 자원을 사용하는 절차

• Request(요청)
• Allocate(할당)
• Use(사용)
• Release(반납)
  
  

Deadlock의 4가지 조건

1. Mutual Exclusion
   • 리소스는 하나의 프로세스에서만 사용할 수 있고 공유해서 사용할 수 없다.
2. Hold and Wait
   • 프로세스가 이미 하나 이상의 리소스를 취득한(hold) 상태에서,
     보유한 리소스를 포기하지 않고 다른 프로세스가 사용중인 리소스를 기다린다(wait).
3. No Preemption
   • 리소스 반환(release)은 강제로 빼앗을 수 없고, 리소스를 취득한 프로세스만 할 수 있다.
4. Circular Wait
   • 프로세스들이 순환(circular) 형태로 리소스를 기다린다.

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

• 자원 할당 그래프를 보고 데드락의 발생 여부를 판별할 수 있다.
• 왼쪽 그래프는 사이클이 없기 때문에 데드락이 아니지만,
  오른쪽 그래프는 순환 형태로 리소스를 기다리고 있기 때문에 데드락이다.

Deadlock 해결방법

1. Deadlock Prevention(데드락 방지)

   • 4가지 조건 중 한가지 조건을 충족하지 못하게 방지

   
   
   	1. mutual exclusion
   	- 리소스를 공유 가능하게 한다. (리소스를 공유할 수 없는 리소스가 있어서 현실적으로 불가능)
   	
       2. hold and wait
       - 프로세스가 자원을 요청할 때 다른 자원을 가지고 있지 않아야 한다.
   		- 1. 프로세스를 시작하기 전에 사용할 리소스들을 모두 획득
           - 2. 리소스가 필요할 경우, 보유한 리소스를 release하고 요청
       - 사용중이지 않은 리소스도 보유하고 있기 때문에, 리소스 사용효율이 떨어진다.
       - 요청이 많은 자원을 다른 프로세스에서 계속 사용하여 프로세스가 장시간 자원에 접근을 못할 수 있다. (starvation)
       
       3. no preemption
       - 추가적인 리소스가 필요하다면 다른 프로세스가 선점하게 하고, 모든 리소스에 접근할 수 있을 때 시작한다.
       - cpu의 context switching과 유사
       
       4. circular wait
       - 모든 리소스에 순서를 할당하여 정해진 순서대로만 리소스를 할당

2. Deadlock Avoidance

   • 리소스 요청에 대한 부가적인 정보를 이용하여 데드락 발생을 회피하고 안전한 경우에만 할당
   • 일반적인 모델의 경우 프로세스들이 필요로 하는 리소스들의 최대 사용량을 미리 선언
   • Banker Algorithm
     - 리소스 요청을 허락했을 때 데드락이 발생할 가능성이 있으면, 리소스를 할당해도 안전할 때까지 계속 요청을 거절하는 알고리즘
     

3. Deadlock Detection and recovery

   • 데드락을 허용하고 데드락이 발생하면 복구
     1. 프로세스를 종료 (전체 프로세스를 종료하거나 단계별로 종료)
     2. 데드락이 발생하면 리소스의 일시적인 선점을 허용
     

4. Deadlock Ignorance

   • 데드락이 일어나도 조치를 취하지 않고 무시
   • 데드락의 발생 빈도가 높지 않기 때문에 데드락을 위해 조치를 취하는 것이 낭비일 수 있음
   • 만약 데드락이 발생한다면 사용자가 직접적으로 프로세스를 죽이는 조치를 취함