Deadlock이란?

상호 배제(Mutual Exclusion)에 의해 나타나는 문제점.
둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 서로 무한정 기다리는 현상.

위 그림과 같이 자동차(프로세스)들이 현재 위치한 길(자원)을 점유함과 동시에 다른 차가 사용하는 길(자원)을 사용하려고 대기하고 있지만, 다른 길(자원)을 사용할 수 없으며 현재 길(자원)에서도 벗어나지 못하는 개노답상태이다.

Deadlock 발생의 필요충분 조건

데드락 상태가 되기 위해서는 다음 네 조건이 모두 충족되어야 한다.

• 상호 배제 (Mutual Exclusion)
  한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.
• 점유와 대기 (Hold & Wait)
  최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
• 비선점 (Non-Preemptive)
  다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
• 환형 대기 (Circular Wait)
  공유 자원과 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.

Deadlock 해결 기법

1. 예방

교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법
앞서 살펴본 교착상태 발생의 네 가지 조건 중 어느 하나를 제거함으로써 수행된다.
자원의 낭비가 심한 기법이다.

2. 회피

교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해가는 방법으로, Banker's Algorithm이 사용된다.

3. 발견

시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것.
교착상태 발견 알고리즘, 자원 할당 그래프 등을 사용할 수 있다.

4. 회복

교착상태를 일으킨 프로세스를 종료시키거나, 교착상태의 프로세스에 할당된 자원을 선점(preempt)하여 프로세스나 자원을 회복하는 것