DPP (dining philosophers problem) ; 식사 중인 철학자들 문제

DPP는 Dijkstra가 프로세스들 간에 자원 할당에 관해 도입한 문제이다. DPP는 자원 할당에 관한 이론을 시험하고 비교하는데 보편적인 방법이며, 모델이다. Dijkstra는 완전히 결정론적인 자동장치라고 간주될 수 있는 기계를 만듦으로써 계층화된 운영체계를 만드는데 도움을 주기 위해, 이것이 사용되기를 희망했다.

이 문제는 하나의 유한한 프로세스 세트로 구성되는데, 이들은 한번에 오직 한 개의 프로세스에 의해서만 사용될 수 있는 유한한 량의 자원을 공유함으로써, 잠재적인 교착상태가 유도될 수 있다.

DPP는 이것을 둥근 식탁에 둘러앉아 있는 일련의 철학자들로 시각화하였는데, 식탁에는 이웃하는 철학자 사이마다 포크가 한 개씩 놓여져 있다. 각 철학자는 자신의 왼쪽과 오른쪽에 있는 포크 중 어느 것을 사용할지를 마음대로 결심할 수 있지만, 각 포크는 한번에 오직 한사람의 철학자에 의해서만 사용될 수 있다.

이를 위해 가능한 몇 가지 해결방안을 생각해 보면 다음과 같다.

  • 세마포어 - 단순하지만, 각 자원들이 이진 세마포어인 곳에서는 불공평한 해결책이며, 교착상태나 기아(飢餓 )상태를 피하기 위해 추가적인 세마포어들이 사용된다.
  • 크리티컬 리전 - 각 프로세서는 그것이 배타적으로 자원을 사용하는 동안에는 방해로부터 보호된다.
  • 모니터 - 프로세스는 모든 필요한 자원들이 활용 가능한 상태까지 기다렸다가, 필요한 모든 것을 차지한다.
최적의 해결책은, 프로세스의 현재 상태 (배고픈 상태, 식사 중, 생각 중 ... 등) 를 추적하기 위해 배열을 사용함으로써, 어떠한 수의 프로세스(철학자들)에 대해서도 최대의 병렬성을 허락한다. 이 해결책은, 만약 필요한 포크가 사용중이라면 자원을 갖기 위해 노력하는 배고픈 철학자들이 차단할 수 있도록 세마포어의 배열을 유지한다.
이 정보는 2000년 4월 11일에 수정되었습니다.
영어판(whatis.com)