식사하는 철학자 문제

식사하는 철학자 문제 (Dining Philosophers Problem)는 컴퓨터 공학에서 동시에 실행되는 프로세서의 동기화 문제에 관한 문제이다. 컴퓨터 공학 학부과정의 운영체제 교과서에 나오는 문제이다.

 

다음 그림과 같은 원형 탁자에 철학자 5명이 스파게티를 먹으려고 한다. 철학자 사이에는 포크가 하나씩 있다. 철학자들은 생각을 하고 스파게티를 한 입 먹고 다시 생각하기를 반복한다. 이 때 철학자들이 스파게티를 먹기 위해서는 양옆에 있는 2개의 포크를 사용해야 한다고 가정한다.

 

식사하는 철학자 문제

 

이와 같은 문제에서 5명의 철학자들이 모두 오른쪽 포크를 들면 모든 철학자들의 왼쪽 포크가 없어 스파게티를 먹지 못한다. 모든 철학자들이 왼쪽 포크가 내려 오기를 기다리면 교착상태 (Deadlock)에 빠진다. 즉, 영원히 스파게티를 먹지 못하고 왼쪽 포크만을 기다리게 된다.

 

식사하는 철학자에 대한 몇 가지 해결법이 있다. 그 중 한가지는 1번에서 4번의 철학자는 오른쪽 포크를 먼저 들고 왼쪽 포크를 들고 5번째 철학자는 왼쪽 포크를 먼저 들고 오른쪽 포크를 들어서 식사하는 방법이다. 

 

☞ 비잔틴 장군 문제