철학자들의 만찬 문제

5명의 철학자들이 있습니다. 이 철학자들은 원형 테이블에 앉아 있고 각자 앞에는 먹음직스러운 스파게티가 놓여있습니다. 그리고 스파게티 접시 사이에는 5개의 포크가 있습니다. 철학자는 생각할 때는 어떤 일도 하지 않고 배가 고파지면 가장 가까이에 놓인 두 개의 포크를 이용해 스파게티를 먹습니다.(반드시 두 개의 포크를 이용해야 합니다.) 옆 사람이 사용하고 있는 포크는 사용할 수 없습니다. 이 상황에서 어떻게 하면 철학자 모두 스파게티를 잘 먹을 수 있을까요? (이 문제는 젓가락 두 쪽과 밥으로 표현되기도 합니다.)

단순하고 어쩌면 기이한 이 논제는 대학에서 컴퓨터공학을 공부하는 사람이라면 한번쯤 접하는 `철학자들의 만찬 문제(The Dining-Philosophers Problem)'입니다.

네덜란드 출신으로 1972년 튜링상을 수상한 컴퓨터과학자 에츠허르 데이크스트라(Edsger W. Dijkstra, 1930~2002)가 고안한 이 문제는 컴퓨터 내에서 구현 중인 프로그램인 프로세스의 활동을 나타냅니다. 컴퓨터에서 프로그램을 실행시키면 프로세스가 생성되어 구동합니다. 이 프로세스는 컴퓨터로부터 자원을 할당받아 일하고 우리는 그 결과를 받아봅니다. 이것이 우리가 프로그램을 실행하고 구동하는 방법입니다. 쉽게 생각해서 철학자가 두 개의 포크로 스파게티를 먹는 행위는 포크라는 자원(CPU와 메모리 등)을 이용해서 스파게티라는 과제를 처리하는 것입니다.

물론 이런 방식으로 하나의 프로세스만 동작한다면 문제가 없지만 우리가 사용하는 컴퓨터는 여러 프로세스가 동시에 일을 처리하고 자원을 원하기 때문에 문제가 발생합니다. 몸은 하나인데 여러 명과 연애를 하려다보니 문제가 발생하는 것이지요. 이럴 경우 사람들을 만나는 규칙을 정하고 일정을 잘 조정해야겠지요. 컴퓨터도 마찬가지입니다. 원활한 자원의 사용을 위해서는 작업의 규칙을 정하고 수행시기를 조정하는 동기화가 필요합니다. 

만약 규칙이나 동기화 없이 한 프로세스가 자원을 독점한다면 다른 프로세스는 스파게티를 먹지 못해 기아상태(Starvation)에 빠질 것입니다. 또 모든 프로세스가 하나의 포크만 들고 기다린다면 그들은 계속 다른 포크를 기다려야하는 교착상태(deadlock)에 빠지고 컴퓨터는 작동하지 않을 것입니다. 

데이크스트라는 이런 상호간의 문제들을 해결하기 위해 이 논제를 고안하여 발생할 수 있는 문제들을 생각해보고 해결방법을 찾았습니다. 그렇다면 기아나 교착상태를 막기 위해서는 어떻게 해야 하는 것일까? 

우선 세마포어(Semaphores)라고 하는 동기화 도구를 이용할 수 있습니다. 데이크스트라가 고안한 세마포어는 공유자원에 대한 접근을 제한하여 문제를 해결합니다. 간단히 설명하면 컴퓨터 작동을 관리하는 오퍼레이팅시스템(OS)에 세마포어 값을 두고 덧셈과 뺄셈으로 값을 변화시켜 자원 접근권한을 부여하는 것입니다. 그러나 세마포어가 모든 교착상태 문제를 해결해주지는 못합니다.

다른 여러 가지 교착상태 해결책을 열거해보면 다음과 같습니다. 최대 4명의 철학자들만 테이블에 동시에 앉도록 허용할 수 있습니다. 또 한 철학자가 포크 두 개를 모두 집을 수 있을 때만 포크를 집도록 허용하는 것도 방법입니다. 혹은 비대칭 해결안을 사용합니다. 예를 들면, 철학자들에게 번호를 매겨 짝수의 철학자는 오른쪽 젓가락을 집고 다음에 왼쪽 젓가락을 잡도록 하는 반면, 홀수의 철학자는 반대로 규칙을 정하는 것입니다. 

하지만 정해진 답은 없습니다. 컴퓨터공학을 연구하는 사람이라면 효율적이고 창조적인 규칙을 찾아보는 것도 학문을 하는 하나의 즐거움일 것입니다. 

어떻게 하면 철학자들이 스파게티를 효율적으로 잘 먹을 수 있을지 여러분들도 한번쯤 생각해 보는 것은 어떻겠습니까?

해결 방법

에츠허르 데이크스트라의 해결책은 다음과 같다. 각각의 철학자를 P1,P2,P3,P4,P5라고 하고, 각 철학자의 왼쪽 젓가락을 f1,f2,f3,f4,f5라고 하자. P5를 제외한 네 명은 먼저 fn를 집은 후 fn + 1를 집는 방식을 취한다. 그리고 P5는 이와 반대로, f1를 먼저 집은 후 f5를 집는다. 이것은 원래 방식의 대칭성을 제거하고, 따라서 교착 상태를 막을 수 있다.

***

데드락(교착 상태)

교착 상태(膠着狀態, deadlock)란 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. 예를 들어 하나의 사다리가 있고, 두 명의 사람이 각각 사다리의 위쪽과 아래쪽에 있다고 가정한다. 이때 아래에 있는 사람은 위로 올라 가려고 하고, 위에 있는 사람은 아래로 내려오려고 한다면, 두 사람은 서로 상대방이 사다리에서 비켜줄 때까지 하염없이 기다리고 있을 것이고 결과적으로 아무도 사다리를 내려오거나 올라가지 못하게 되듯이, 전산학에서 교착 상태란 다중 프로그래밍 환경에서 흔히 발생할 수 있는 문제이다. 이 문제를 해결하는 일반적인 방법은 아직 없는 상태이다.

교착 상태의 조건

1971년에 E. G. 코프만 교수는 교착상태가 일어나려면 다음과 같은 네 가지 필요 조건을 충족시켜야 함을 보였다.

상호배제(Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.

점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺐을 수 없다.

순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

이 조건 중에서 한 가지라도 만족하지 않으면 교착 상태는 발생하지 않는다. 이중 순환대기 조건은 점유대기 조건과 비선점 조건을 만족해야 성립하는 조건이므로, 위 4가지 조건은 서로 완전히 독립적인 것은 아니다.

상호 배제(mutual exclusion, Mutex, 뮤텍스)는 동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘으로, 임계 구역(critical section)으로 불리는 코드 영역에 의해 구현된다.

공유 불가능한 자원의 예로는 동시에 실행되고 있는 프로그램간의 통신에 사용되는 비트 단위의 깃발, 계수기, 큐 등이다. 문제는 스레드가 언제라도 정지되거나 시작될 수 있다는 것이다.

예) 프로그램의 일부분이 여러 단계를 거치면서 데이터를 읽고 쓰고 있다고 하자. 그런데 예상치 못한 사건 등에 의해 다른 스레드가 동작하기 시작했다. 첫 번째의 스레드가 쓰고 있는 영역에서, 이 두 번째의 스레드가 또 다른 작업을 시작한다면, 해당 영역의 값은 부적절하며 예상할 수 없는 상태에 놓이게 된다. 게다가 두 번째의 스레드가 값을 덮어 써버리기라도 한다면, 복구 불가능한 상태로 되고 만다. 그러므로 공유 데이터를 접근하는 프로그램 내부의 이른바 임계 구역이라는 부분은 홀로 수행되도록 보호되어야 하며, 다른 스레드가 동일한 부분의 프로그램을 수행해서 동일한 공유 데이터를 접근하는 것을 막아야 한다.

단일 프로세서 시스템에서, 상호 배제를 구현하는 가장 단순한 방법은 인터럽트를 억제해서 공유 데이터가 손상되는 것을 막는 것이다. 성능에 최소한의 영향을 주기 위해 인터럽트가 발생하지 않을 명령어 집합의 수는 가능한 최소로 유지시키는 것이 좋다.

상호배제를 처음으로 소프트웨어를 통해 해결한 사람은 네덜란드 수학자 데커(Dekker)이며 그 알고리즘을 데커의 알고리즘이라 한다.

상호배제는 교착상태의 4가지 필요조건 중 하나이다.