[IT 기술면접 준비자료] 교착상태(Deadlock)와 식사하는 철학자들(Dining Philosophers)

교착상태(DeadLock)은 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. (출처: 위키피디아 한국어판 교착상태 문서) 컴퓨터 쪽으로 해석을 해 본다면, 운영체제나 소프트웨어가 자원(Resource)관리를 잘못하여, 둘 이상의 프로그램이 다운되거나 운영체제가 멈춰버리는 현상이다.

▶교차로가 꽉 막혀있는데.. 어떻게 풀어야 할까?

교착상태가 발생하는 조건은 4가지가 있는데, 4가지 모두 만족해야만 교착상태가 일어난다. 조건 4가지는 다음과 같다.

교착상태의 발생조건

1. 상호 배제(Mutual exclusion)

2. 점유 상태로 대기(Hold and wait)

3. 선점 불가(No preemption)

4. 순환성 대기(Circular wait)

1. 상호 배제(Mutual exclusion)

 상호 배제는 프로그램들이 공유 자원을 동시에 쓸 수 없는 상황을 일컫는다. 상호 배제를 해제하는 것는 가장 확실한 교착상태 제거 방법이지만 (자원을 여럿이서 동시에 사용하니까) 용도가 명확하므로 잘 사용하지 않는다. (프로세스나 스레드의 동시성 제어에 활용) 줄여서 Mutex라고도 부른다. (※참고: [IT 기술면접 준비자료] 상호배제와 상호배제 알고리즘)  

2. 점유 상태로 대기 (Hold and wait)

 말 그대로 (공유)자원을 점유한 상태에서 다른 자원을 기다린다는 것. 할당받은 자원을 사용하지 않으면서 계속 점유하면 그 자원이 필요한 프로세스는 계속 대기하게 된다. 여기에 더하여 만약 순환성 대기(A->B->C->A)가 발생한다면...

3. 선점 불가(No preemption)

 자원을 어떤 프로세스가 점유 중일 때, 다른 프로세스가 그 자원을 뺏을 수 없다는 것이다. 하지만 앞서 언급한 '점유 상태로 대기'와 같은 특수한 상황이 아니라면 자원을 뺏어오는 것은 매우 위험하다.

4. 순환성 대기(Circular wait)

 대기가 꼬리에 꼬리를 문 상황이다. 연쇄 대기를 해결하려고 해도 결국 자기 자신으로 돌아와 버리니 해결할 수가 없다.

 이렇게만 설명하면 모호한 것 같으니, 식사하는 철학자(Dining Philosopher) 문제를 적용해보려고 한다. 5명의 철학자가 원탁에 앉아 있고 각자의 앞에는 스파게티가 있다. 그리고 양 옆에 포크가 하나씩 있다. 각각의 철학자는 스파게티를 먹으려면 포크를 2개 사용해야하며, 다른 철학자에게 말을 걸 수 없고 포크를 빼앗을 수 없다는 조건이 있다.

▶식사하는 철학자(Dining Philosophers) 문제. 교착상태를 설명하는 대표적인 문제이다

 

 이 상황에서 철학자들이 동시에 오른쪽 포크를 집어든다면? (철학자들이 프로세스, 포크가 자원이라고 생각하면 편하다.) 철학자들은 포크를 공유할 수 없고(상호 배제), 자신의 왼쪽에 앉은 철학자가 포크를 놓을 때까지 기다린다.(점유 상태로 대기) 철학자들은 왼쪽 철학자의 포크를 빼앗을 방법도 없으며,(선점 불가) 각 철학자들은 자신의 왼쪽 철학자의 포크를 대기한다.(순환대기)

 이러한 교착 상태를 회피하려면 발생조건 4가지 중 한가지만 해제하면 된다. 상호 배제와 선점 불가의 경우, 문제의 조건 때문에 해소가 불가능 하다. '점유 상태로 대기'를 해제하려면 왼쪽 포크를 집을 수 없을 때, 오른쪽 포크를 식탁 위에 내려놓는 방법이 있다. '순환 대기'를 해소하려면 포크에 우선 순위를 매기는 방법이 있다.

-끝-

출처

그림1: http://hyacinth.byus.net/moniwiki/wiki.php/%EB%8D%B0%EB%93%9C%EB%9D%BD

그림2: https://ko.wikipedia.org/wiki/