식사하는 철학자 문제
1. 개요
[image]
Dining philosophers problem.
운영체제의 교착(Deadlock)상태를 설명하기 위한 문제. 1965년에 에츠허르 데이크스트라가 만든 문제이다.
2. 설명
5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.
"포크 하나로 식사하면 되지!"라고 생각하는 위키니트들이 있다면, 4번 가정을 다시 읽어보길 바란다. 대학 수업에서도 이걸로 딴지거는 학생들이 제법 있었는지, 포크를 젓가락 한 짝으로 바꾼 버전도 있다.1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.
간단하게 생각해, 만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡는다면, 모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다. 그런데 모든 철학자들이 그러고 있다. 이 상태에서는 모든 철학자가 영원히 3번 상태에 머물러있어 아무것도 진행할 수가 없게 되는데, 이것이 교착(Deadlock)상태이다.
2.1. 멀티태스킹에 대한 부연설명
"아니, 옛날 컴퓨터는 싱글코어라 동시 작업은 생각할 필요도 없는 거 아닌가?"라고 생각한다면, 운영체제가 작업을 처리하는 방식을 이해할 필요가 있다.
운영체제는 사용자에게 멀티태스킹을 제공하기 위해 돌리고 있는 프로세스들을 굉장히 짧은 시간[1] 동안 수행하고 다른 프로세스가 CPU를 사용할 수 있게 해 준다. 인간의 반응 속도는 그렇게 빠르지 않기 때문에, CPU가 동시에 여러 작업을 수행하는 것처럼 보인다.
문제를 단순화시켜, 두 명의 철학자와 두 개의 포크만 있다고 생각을 해 보자. 그리고 중재자가 있어 행동을 취할 수 있는 권리를 한명에게만 할당한다. 다음의 상황을 가정해 보자.[2]
위의 예시처럼 싱글코어임에도 운영체제가 선점적 멀티태스킹[3]을 사용한다면, 충분히 교착 상태에 빠질 수 있다.1. 행동권을 할당받은 철학자가 왼쪽 포크를 집는다.
2. 그 때 중재자가 행동권을 뺏어 다른 철학자에게 넘겨준다.
3. 행동권을 넘겨받은 철학자는 자신의 왼쪽 포크를 집고 오른쪽 포크가 돌아오길 기다린다
4. 중재자가 행동권을 다른 철학자에게 넘겨준다
5. 이 철학자도 자신의 오른쪽 포크가 돌아오기를 기다리고 있다.
3. 해결법
3.1. OS 차원의 해결법
한 철학자가 포크를 잡는다면, 반대쪽 포크를 잡을 때까지 행동권을 넘길 수 없게 하는 것이다. 현실 세계에서는 CPU의 인터럽트를 무시하는 방식[4]으로 구현할 수 있다. 하지만 이는 커널 레벨에서만 가능한 방식으로, 사용자에게 인터럽트 제어권을 넘겨준다면 악의적으로 사용해 혼자 CPU를 쳐묵쳐묵하는 상황이 발생할 수 있다.
단, 멀티쓰레드 환경이라면 사용자 레벨에서 구현할 수 있는 방식이 있다. 사용자가 Semaphore나 Mutex lock등을 이용해 Critical Section(공유 자원에 Write를 수행하는 경우 등)에서 자신이 만든 다른 쓰레드가 CPU를 잡지 못하게 만들어 쓰레드간의 교착 상태를 방지할 수 있다.
3.2. 하드웨어 아키텍쳐 차원의 해결법
CPU에서 관련 명령어를 제공할 경우, 이것을 이용할 수도 있다. 양쪽 포크를 동시에 잡게 하는 명령어를 사용하면 두 철학자가 동시에 하나의 포크만 잡는 상황은 벌어지지 않는다. 이런 명령어는 쪼갤 수 없는 명령어라는 의미로 Atomic Instruction이라고도 한다.
3.3. 소프트웨어 차원의 해결법
여러 가지 방법이 있다.
- 타임아웃 설정. 철학자가 포크를 집고 일정 시간 내에 다른 쪽 포크를 획득하는데 실패(…)한다면, 포크를 반납하게 한다. 가장 간단하지만 타임아웃에 따른 딜레이가 있다.
- 철학자들 중 하나는 포크를 오른쪽부터 잡게 한다고 생각해 보자. 예를 들어 1번 철학자는 왼쪽부터, 2번 철학자는 오른쪽부터 잡는다. 1번 철학자가 왼쪽 포크만 잡은 상태에서 행동권이 2번 철학자에게 넘어간다고 하더라도, 2번 철학자는 자신의 오른쪽 포크가 현재 사용 불가능하기 때문에, 첫번째 포크를 잡으려는 상황에서 멈춰 있게 된다. 이 상황에서 1번 철학자로 다시 행동권이 넘어오게 되면 1번 철학자는 자신의 오른쪽 포크를 잡고 다시 식사를 할 수 있게 된다.
- 포크 하나하나에 비교 가능한 고유 값을 부여하여, 고유 값이 높은(또는 낮은) 순서대로 포크를 집게 만든다. 고유 값은 보통 해시를 사용하는 게 일반적이며, 서로 겹치면 안 된다.
예를 들어, 포크 다섯 개의 고유번호가 각각 순서대로 295, 329, 683, 591, 274이고 고유번호가 높은 순서대로 포크를 집는다고 가정하자, 3번 철학자는 3번과 4번 포크를 사용할 텐데, 그 포크들의 값은 683, 591이므로 3번 철학자는 683의 값을 가진 3번 포크를 먼저 집는다. 반대로 1번 철학자는 1번과 2번 포크를 사용할 텐데, 그 포크들의 값은 295, 329이므로 1번 철학자는 329의 값을 가진 2번 포크를 먼저 집는다. 이렇게 하면 절대로 모든 철학자가 하나의 포크를 집고 대기하는 일이 없으므로(a > b > c > d > e > a, 또는 반대일 수는 없으므로) 문제를 해결할 수 있다.