핵심 키워드 : 교착 상태, 식사하는 철학자 문제, 자원 할당 그래프, 교착 상태 발생 조건

식사하는 철학자 문제

식사하는 철학자 문제(dining philosophers problem) 는 교착 상태를 설명하기 위한 문제 상황입니다.

예제) 동그란 원탁에 다섯 명의 철학자가 앉아 있다. 이 철학자들 앞에는 맛있는 식사가 있고, 철학자들 사이 사이에는 식사에 필요한 포크가 있다. 그리고 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이라 가정한다.

철학자들은 아래와 같은 순서로 식사를 한다

  1. 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
  2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
  3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
  4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
  5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
  6. 다시 1번부터 반복한다.

언뜻 보면 아무런 문제가 없어 보인다. 실제로 한두 명의 철학자가 식사할 때는 아무런 문제가 없다.

하지만 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황이 발생할 수 있다. 모든 철학자가 왼쪽 포크를 집어들면 모두가 오른쪽 포크를 집어들 수 없기 때문이다. 다시 말해 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다린다.

이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 **교착 상태(deadlock)**라고 한다.

식사하는 철학자 문제