DeadLock

정의

- 상호 배제에 의해 나타나는 문제점으로, 두 개 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리기만 하는 현상

4가지 필요충분 조건

1. Mutual Exclusion (상호 배제)
   "한 번에 한 프로세스만 해당 자원을 사용할 수 있다."
   
   
2. Hold & Wait (점유 및 대기)
   "프로세스가 한 개 이상의 자원을 할당받은 후 다른 프로세스에 할당된 자원을 기다리는 상태"
   
   * 제거 조건
   프로세스가 수행되기 전에 필요한 모든 자원을 할당시켜 줌
   자원이 점유되지 않은 상태에서만 자원을 요구하도록 함
   
   
3. Non-preemption (비선점)
   "다른 프로세스가 사용중인 자원을 강제로 뺏을 수 없다."
   
   
4. Circular Wait (환형대기)
   "프로세스들이 순환을 이루어서 존재"

해결방안

• Prevention (예방 기법)
  - 사전에 시스템을 제어하는 방법으로, 4가지 필요충분 조건 중에서 어느 하나를 제거한다.
  
  - 상호배제 부정
  "한번에 여러개의 프로세서가 공유 자원을 사용할 수 있도록 하는 것이지만 실제로 구현X"
  
  - 점유 및 대기 부정
  "프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구 하도록 함"
  
  - 비선점 부정
  "점유하고 있는 자원을 반납하고 요구한 자원을 사용하기 위해 기다리게 함"
  
  - 환형대기 부정
  "선형 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하는 것"
  
  
• Avoidance (회피 기법)
  - 발생 가능성을 인정하고 deadlock이 발생하려고 할 때, 가능성을 피해가는 방법.
  - 은행원 알고리즘(Banker's Algorithm)이 사용
  
  
• Detection (발견 기법)
  - deadlock이 발생했는지 점검하여 발견하는 기법
  
  
• Recovery (회복 기법)
  - deadlock을 일으킨 프로세스를 종료하거나 할당된 자원을 선점하여 자원을 회복하는 것
  - 교착상태에 있는 모든 프로세스 중지
  - 교착상태에 포함된 프로세스를 하나씩 종료
  

---

* 은행원 알고리즘
- 프로세스가 자원을 요구할 때 시스템이 자원을 할당한 후 안정 상태로 남아있게 되는지를 사전에 검사하여 deadlock을 회피하는 기법
- 자원을 할당하기 전 알고리즘을 사용하여 시스템 상태를 점검한 후 자원 할당 여부를 결정
- Dijkstra(다익스트라)가 제안
- 교착상태가 발생할 수 있는 상태를 불안전 상태

- 불안전상태의 모든 시스템은 궁극적으로 교착상태에 빠지진 않음