[OS] 식사하는 철학자들 문제(The Dining-Philosophers Problem)

 

 

식사하는 철학자들 문제(_The Dining-Philosophers Problem)

---

생각하고 먹으면서 그들의 생애를 보내는 5명의 철학자를 고려해 봅시다. 철학자들은 원형 테이블을 공유하며, 이 테이블은 각각 한 철학자에 속하는 5개의 의자로 둘러싸여 있습니다. 테이블 중앙에는 한 사발의 밥이 있고, 아래의 그림과 같이 테이블에는 다섯 개의 젓가락이 놓여 있습니다.

식사하는 철학자의 상황

철학자가 생각을 할 때는 다른 동료들과 상호 작용을 하지 않습니다. 때때로 철학자들은 배가 고파지는데 그럴 때에는 자신에게 가장 가까이 있는 두 개의 젓가락(왼쪽 젓가락을 먼저 집습니다)을 집으려고 시도합니다. 철학자는 한 번에 한 개의 젓가락만 집을 수도 있으며, 이미 옆 사람의 손에 들어간 젓가락을 집을 수는 없습니다. 배고픈 철학자가 동시에 젓가락을 두 개를 집으면, 젓가락을 놓지 않고 손에 들고 있는 채로 식사를 합니다. 그러다가 식사를 마치면, 젓가락 두 개를 모두 놓고 다시 생각에 빠집니다.

 식사하는 철학자들 문제는 고전적인 동기화 문제로 간주하는데, 그 이유는 실용적으로 중요하거나 혹은 컴퓨터 과학자들이 철학자를 싫어해서가 아니라 많은 부류의 병행 제어 문제의 한 예이기 때문입니다.  만약 모든 철학자가 동시에 배가 고프고 각 철학자가 왼쪽에 있는 젓가락을 잡으면 더 사용 가능한 젓가락이 없기에 모든 철학자들은 영원히 누군가 포기하지 않는 이상 영원히 오른쪽 젓가락을 사용할 수 있을 때까지 기다립니다.

 우리는 이런 상황을 교착 상태(Deadlocks)라고 부릅니다. 또 다른 좋은 예도 있습니다. "두 기차가 교차로에서 서로 접근할 때는, 둘 다 완전히 정지해야 하며 상대방이 없어지지 않는 한 누구도 다시 출발할 수 없다."입니다. 이러한 교착상태와 해결방안에 대해서는 다음 게시글에서 더 자세하게 정리해 보도록 하고 이번 게시글 에서는 식사하는 철학자들 문제의 상황을 해결하는 두 가지 방법에 대해 알아보겠습니다.

(1) 세마포 해결안(_Semaphore Solution)

한 가지 간단한 해결책은 각 젓가락을 하나의 세마포로 표현하는 것입니다. 철학자는 그 세마포에 wait() 연산을 실행하여 젓가락을 집으려고 시도합니다. 그는 또한 해당 세마포에 signal() 연산을 실행함으로써 자신의 젓가락을 놓습니다. 그러므로 공유 자료는 다음과 같습니다.

semaphore chopstick[5];

여기서 chopstick의 원소들은 모두 1로 초기화되어 있습니다. 철학자 i의 구조는 아래 소스에 나타나 있습니다.

철학자 i의 구조

 이 해결안은 인접한 두 철학자가 동시에 식사하지 않는다는 것을 보장하지만, 교착상태를 야기할 가능성이 있기 때문에 채택할 수 없습니다. 5명의 철학자 모두가 동시에 배가 고프게 되어, 각각 자신의 왼쪽 젓가락을 잡는다고 가정해 봅시다. chopstick의 모든 원소들은 이제 0이 될 것입니다. 각 철학자가 그의 오른쪽 젓가락을 집으려고 하면 영원히 기다려야 할 것입니다.

 식사하는 철학자의 교착상태 문제에 대한 여러 가지 해결책들은 다음과 같습니다.

• 최대 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
• 한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 허용한다(이렇게 하려면 철학자는 임계 구역 안에서만 젓가락을 집어야 한다).
• 비대칭 해결안을 사용한다. 즉, 홀수 번호의 철학자는 먼저 왼쪽 젓가락을 집고 다음에 오른쪽 젓가락을 집는다. 반면에 짝수 번호의 철학자는 오른쪽 젓가락을 집고 다음에 왼쪽 젓가락을 집는다.

그러나 식사하는 철학자드의 문제에 대한 만족할만한 해결안들은 반드시 철학자 중 어느 하나가 굶어 죽을 가능성이 생기지 않도록 방지해야 한다는 것을 주의해야 합니다. 교착상태가 없는 해결안이 반드시 기아의 가능성도 제거하는 것은 아닙니다.

(2) 모니터 해결안(_Monitor Solution)

다음으로 식사하는 철학자 문제에 대한 교착 상태가 없는 해결안을 제시함으로써 모니터 개념을 설명해보겠습니다. 이 해결안은 철학자는 양쪽 젓가락 모두 얻을 수 있을 때만 젓가락을 집을 수 있다는 제한을 강제합니다. 이 해결안을 구현하려면, 철학자가 처할 수 있는 세 가지 상태들을 구분할 필요가 있습니다. 이러한 목적으로 다음의 자료구조를 도입합니다.

enum {THINKING, HUNGRY, EATING} state[5];

철학자 i는 그의 양쪽 두 이웃이 식사하지 않을 때만 변수 state[i] = EATING으로 설정할 수 있습니다(조건 (state[(i+4)%5] != EATIHG) 그리고 (state[(i+1)%5] != EATING)이 성립할 때만).

 또한 다음을 선언할 필요가 있습니다.

condition self[5];

self는 철학자 i가 배고프지만 자신이 원하는 젓가락을 집을 수 없을 때 젓가락 집기를 미룰 수 있게 합니다.

 우리는 이제 식사하는 철학자 문제에 대한 우리의 해결안을 기술할 수 있습니다. 젓가락의 분배는 모니터 DiningPhilosophers에 의 해 제어됩니다. 이 모니터가 정의가 아래 소스에 나와 있습니다.

식사하는 철학자 문제에 대한 모니터 해결안

각 철학자는 식사하기 전에 pickup() 연산을 반드시 호출해야 합니다. 이 행동은 철학자 프로세스의 일시 중지를 낳을 수도 있습니다. 연산이 성공적으로 끝나면, 철학자는 식사할 수 있습니다. 식사를 마친 후, 철학자는 putdown() 연산을 호출합니다. 따라서 철학자 i는 반드시 다음과 같은 순서로 pickup()과 putdown() 연산을 호출해야 합니다.

DiningPhilosophers.pickup(i);
... eat ...
DiningPhilosophers.putdown(i);

 이 해결안이 이웃한 두 철학자가 동시에 식사하지 않는 것과 교착 상태가 발생하지 않는다는 것을 보장한다는 것을 보이기는 쉽습니다. 그러나 우리는 철학자가 굶어죽는 것이 가능하다는 것에 유의해야 합니다(기아상태에 빠지는 철학자가 있을 수 있음)