[바미] 철학자의 식사시간 문제

안녕하세요. 오늘은 철학자의 식사시간 문제(Dining Philosophers Problem)에 대해 알아보도록 하겠습니다.

 

철학자의 식사시간 문제(Dining Philosophers Problem) 는동시성 제어(concurrency control)와 관련된 전통적인 문제로, 자원 공유와 교착 상태(deadlock)의 개념을 설명하는 데 자주 사용됩니다. 

 

이 문제는 다섯 명의 철학자가 원탁에 앉아 식사를 하려는 상황을 가정합니다. 철학자들은 생각하거나 먹는 두 가지 행동만을 하며, 스파게티를 먹기 위해서는 두 개의 포크가 필요합니다. 이때, 철학자들이 다음과 같은 규칙을 따르게 됩니다.

1. 모든 철학자는 자신의 왼쪽에 있는 포크를 먼저 집습니다.
2. 왼쪽 포크를 집은 후, 오른쪽 포크를 집습니다.
3. 두 개의 포크를 모두 집었을 때만 스파게티를 먹을 수 있습니다.
4. 식사를 마친 후에는 두 개의 포크를 내려놓습니다.

이 문제를 통해 교착 상태(deadlock)를 설명할 수 있는데 교착 상태란 여러 프로세스가 서로의 자원을 기다리느라 영원히 멈추는 상태를 의미합니다. 철학자의 식사시간 문제에서 교착 상태는 다음과 같이 발생합니다.

1. 모든 철학자가 동시에 왼쪽 포크를 집습니다.
2. 각 철학자는 오른쪽 포크를 집기를 기다리지만, 오른쪽 포크는 이미 다른 철학자가 왼쪽 손으로 잡고 있기 때문에 잡을 수 없습니다.
3. 이 상태가 지속되면 모든 철학자는 서로의 오른쪽 포크를 기다리며 영원히 대기하게 됩니다. 따라서 아무도 스파게티를 먹지 못하는 상태가 됩니다.

이러한 교착 상태를 방지하기 위해 다양한 해결 방법이 제안되었는데 대표적인 해결 방법으로는 다음과 같은 방법들이 있습니다.

• 자원 계층화(Resource Hierarchy) - 철학자들이 포크를 항상 특정 순서로 집도록 하는 것입니다.
  예를 들어, 모든 철학자가 항상 번호가 낮은 포크를 먼저 집고 그 다음에 번호가 높은 포크를 집도록 합니다.
  이렇게 하면 교착 상태가 발생하지 않습니다.
• 하나의 포크만 집기 - 철학자가 먼저 왼쪽 포크를 집고, 잠시 대기한 후에 오른쪽 포크를 집도록 합니다.
  이 방법은 교착 상태를 피하기 위해 충분히 긴 대기 시간을 설정해야 합니다.
• 임의의 시간 대기 - 철학자가 포크를 집지 못하면 일정 시간 대기한 후 다시 시도하도록 합니다.
  이 방법은 교착 상태를 완전히 피할 수는 없지만, 교착 상태에 빠질 확률을 줄일 수 있습니다.