14 - 교착 상태

교착 상태란

위 사진과 같이 꽉 막힌

도로 상황을 본 적이 있을 것이다.

 

프로세스 실행 과정에서도

두 개 이상의 프로세스가

각자 가지고 있는 자원을 무작정 기다린다면

이와 같은 상황이 일어난다.

이를 교착 상태라고 한다.

 

식사하는 철학자 문제

출처: Wikipedia

식사하는 철학자 문제는

(Dining philosophers problem)

교착 상태를 설명하는 예시 중 하나다.

 

동그란 원탁에 철학자 다섯 명이 앉아

식사를 하는 상황인데 포크는

각 철학자 사이에 하나 씩만 주어졌을 때,

각 철학자는 다음과 같은 조건을

따른다고 가정해보자.

 

1. 왼쪽 포크가 사용 가능하면 집어든다.

2. 오른쪽 포크가 사용 가능하면 집어든다.

3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사한다.

4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.

5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.

6. 이 과정을 1번 부터 반복한다.

 

언뜻 보았을 때에는

별 문제가 없을 것 같다.

 

그러나 만약 모든 철학자가

동시에 포크를 집어든다면

아무도 식사할 수 없는 상태가 된다.

 

이렇게 일어나지 않을 사건을 기다리며

진행이 멈춰 버리는 현상을

교착 상태(Deadlock)라고 한다.

 

이러한 교착 상태를 해결하기 위해서는

먼저 교착 상태가 발생한 상황을 정확히 표현하고,

근본적인 이유를 알아야 한다.

 

자원 할당 그래프

교착 상태가 발생한 상황을

표현하는 도구에는

자원 할당 그래프가 있다.

(Resource-allocation graph)

 

자원 할당 그래프는

다음 과정을 통해 나타낼 수 있다.

 

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.

2. 사용할 수 있는 자원의 개수는 사각형 내에 점으로 표현한다.

3. 프로세스가 자원을 할당받을 때에는 자원 -> 프로세스 방향으로 화살표를 표시한다.

4. 프로세스가 자원을 할당받기 위해 대기 중일 때에는 프로세스 -> 자원 방향으로 화살표를 표시한다.

교착 상태가 발생한 '식사하는 철학자 문제'를

자원 할당 그래프로 나타내보면

원의 형태를 띄고 있음을 알 수 있다.