교착 상태(Dead Lock)

Goal

• 교착 상태 발생하는 이유(조건)에 대해 설명할 수 있다.
• 교착 상태가 발생했을 때 해결할 수 있는 방안 몇 가지를 설명할 수 있다.

---

교착 상태(Dead Lock)란?

교착 상태(dead lock)란 두 개 이상의 작업(task)이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.

Dead Lock

교착 상태란 다중 프로그래밍 환경에서 흔히 발생할 수 있는 문제이다.

 

이 문제를 해결하는 일반적인 방법은 아직 없는 상태이다.

현재의 대부분의 운영 체제들은 교착 상태를 막는 것은 불가능하다. 교착 상태가 발생하면 여러 운영 체제들은 제각기 다른 비표준 방식들로 이러한 교착 상태에 대응한다.

 

그렇다면 교착 상태는 어떤 상황에서 발생하고 어떻게 해결해야 할까?

 

교착 상태의 조건

• 상호배제(Mutual exclusion) : 임계구역에 하나의 스레드만 진입할 수 있다.
• 점유대기(Hold and wait) : 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
• 비선점(No preemption) : 점유 중인 자원을 빼앗아 올 수 없다.
• 순환대기(Circular wait) : 여러개의 스레드가 순환적으로 요구하는 자원을 가지고 있다.

이 조건 중에서 한 가지라도 만족하지 않으면 교착 상태는 발생하지 않는다. (4가지 조건을 모두 만족해야 함)

 

이중 순환대기 조건은 점유대기 조건과 비선점 조건을 만족해야 성립하는 조건이므로, 위 4가지 조건은 서로 완전히 독립적인 것은 아니다.

 

상호 배제(Mutual exclusion)를 보장하기 위해 락(Lock)을 계속 사용하다 보면 교착 상태에 빠지는 경우가 있다. 그렇기 때문에 최대한 Lock을 사용하지 않도록 설계를 할 필요가 있으며, 반드시 Lock이 필요한 상황인지 고려해볼 필요가 있다.

 

교착 상태 처리 방법

1. 예방(Prevention)

말 그대로 데드락이 발생하지 않도록 설계하는 방법으로, 데드락 조건 4가지 중 하나를 무력화 시켜 예방한다.

 

2. 회피(Avoidance)

자원 할당량을 조절하여 데드락을 회피하는 방법이다.

자원을 할당하다가 데드락을 유발할 가능이 있다고 판단되면 자원 할당을 중단하고 지켜보는 형태이다.

이 방법은 얼만큼의 자원을 할당해야 하는지 아는 경우에만 작동하기 때문에 실효성이 적다.

 

회피 알고리즘

• 자원 할당 그래프 알고리즘 (Resource Allocation Graph Algorithm)
• 은행원 알고리즘 (Banker's algorithm) 

 

3. 검출(Detection)과 회복(Recovery)

 

검출(detection)

detection 알고리즘으로 데드락 발생을 체크하는 방식.

데드락 발생 여부를 계속 주시한다.

 

검출 방법 예시

• timeout을 이용한 검출 : 일정 시간동안 작업이 진행되지 않을 경우 데드락이 발생했다고 간주
• 자원할당 그래프 이용 : cycle이 발생 했을 경우, 데드락이 발생했다고 간주

회복(Recovery)

교착 상태가 검출 됐을 때, 데드락을 유발하는 하나 이상의 프로세스(또는 스레드)를 종료 시킴으로서 데드락을 해결한다.

이 때, 어떤 기준으로 프로세스(스레드)를 종료 시킬지 기준을 세울 필요가 있다.

 

예시)

우선 순위가 낮은 프로세스를 먼저 종료 시킨다.

자원을 많이 사용하는 프로세스를 먼저 종료 시킨다.

등등..

 

4. 무시(ignore)

데드락의 발생 확률이 비교적 낮은 경우 별다른 조치를 취하지 않는 방법 (해결 방법은 아님)

예시)

- 1년에 1번 발생하는 경우

- 발생해도 크리티컬한 부분이 아니고 재실행을 통해 해결이 가능한 경우