Dead Lock (교착 상태)

운영체제에서 교착 상태란, 둘 이상의 프로세스가 자원을 보유하고 있는 상황에서 다른 프로세스가 점유하고 있는 자원을 서로 기다려 무한한 대기 상태에 빠지는 상황을 일컫는다.

교착 상태 발생 조건

1. 상호 배제 (Mutual Exclusion)

   • 한 자원에 대하여 하나의 프로세스만 해당 자원을 사용할 수 있다. 사용 중인 자월을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.

2. 점유 대기 (Hold and wait)

   • 한 프로세스가 하나 이상의 자원을 점유한 채 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재할 때
   • 할당된 자원을 가진 상태에서 다른 자원을 기다리는 상태

3. 비선점 (No Preemption)

   • 이미 할당된 자원을 강제로 뺏을 수 없음

4. 순환 대기 (Circular Wait)

   • A라는 프로세스는 Y라는 자원을 소지한 상태에서 다음 작업을 위해 X라는 자원이 필요하므로 대기 상태에 있고, B라는 프로세스는 X라는 자원을 소지한 상태에서 다음 작업을 위해 Y라는 자원을 기다리는 상태를 칭한다.
   • 즉, 두 개 이상의 프로세스나 스레드가 서로 다음 자원을 기다리며 무한정 대기하는 상태를 뜻한다.

교착 상태 해결 방법

교착 상태 해결 방법에는 예방, 회피, 탐지 및 회복이 있다.

1. 예방 (Prevention)

교착상태의 예방 방법은 교착상태가 애초에 일어나지 않도록 방지하는 방법으로 교착 상태의 발생 조건 4가지 중 하나를 부정함으로써 교착 상태를 예방하는 것을 뜻한다.

(1) 상호 배제 예방

여러 개의 프로세스가 동시에 공유 자원을 사용할 수 있음

(2) 비선점 예방

모든 자원에 대한 선점을 허용

(3) 점유 대기 부정

프로세스가 실행되기 전에 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나, 자원이 점유되지 않은 상태에서만 자원을 요청 받도록 함

(4) 순환 대기 부정

자원을 선형으로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유번호보다 앞이나 뒤 한 쪽 방향으로만 자원을 요구하도록 함

---

하지만, 교착 상태 발생조건을 방지해서 데드락을 예방하는 방법은 시스템 처리량이나 자원 사용의 효율성을 감소시키는 단점이 존재한다.

2. 회피 (avoidance)

교착 상태가 발생할 가능성이 있는 자원 할당(Unsafe allocation)을 하지 않고 안전한 상태(Safe state)에서만 자원 요청을 허용하는 방법이다.

안전한 상태(Safe state)
Safe sequence(어떤 순서로 할당했을 시 데드락은 발생하지 않고, 모든 프로세스의 요구를 처리할 수 있는 순서)가 존재하여 모든 프로세스가 정상적으로 종료될 수 있는 상태
Safe state에서 시스템은 각 프로세스에게 자원을 할당하는 모든 요청을 만족할 수 있는 safe sequence가 존재하면 데드락을 피할 수 있다.

교착상태 회피를 하기 위해서는 아래와 같은 가정이 필요하다.
(1) 프로세스 수 고정
(2) 자원의 종류와 수 고정
(3) 프로세스가 요구하는 최대 자원 수를 알아야 함
(4) 프로세스는 자원 사용 후 반드시 반납

교착 상태를 회피하기 위한 알고리즘으로는 크게 2개가 있다.

(1) 은행원 알고리즘 (Banker's Algorithm)

다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구를 충족할 수 있도록 현금을 대출해주는 것에서 유래했다. 은행원 알고리즘은 자원 할당 결정 전에 예상되는 모든 자원의 최대 할당량을 가지고 시뮬레이션을 하여 safe state에 들 수 있는지 여부를 검사하여 교착상태의 가능성을 최소화하는 것을 뜻한다.
이때, 전제 조건은 "CPU는 최소한 하나의 프로세스에게 할당해줄 만큼의 자원을 항상 보유하고 있어야 한다"이다.

(2) 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)

자원 할당 그래프에 예약 간선을 추가하여 예약 간선으로 설정한 자원에 대해서만 자원 할당을 요청할 수 있고 사이클이 형성되지 않을 때만 할당받는 방법이다.

3. 탐지 및 회복(Detection and Recovery)

데드락이 발생하는지에 대한 여부를 탐색하고 회복 기법 알고리즘에 활용하는 것을 뜻한다.
즉, 교착상태가 탐지되었다면 회복 기법을 통해 교착상태를 복구한다.