식사하는 철학자들 문제 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:An illustration of the dining philosophers problem.png|섬네일|원탁에 둘러앉은 다섯 명의 철학자와 다섯 접시의 스파게티, 그리고 다섯 개의 포크]]
'''식사하는 철학자들 문제'''는 [[전산학]]에서 [[동시성]]과 [[교착]] 상태를 설명하는 예시로, 여러 [[프로세스]]가 동시에 돌아갈 때 교착 상태가 나타나는 원인을 직관적으로 알 수 있다.

다섯 명의 [[철학자]]가 [[원탁]]에 앉아 있고, 각자의 앞에는 [[스파게티]]가 있고 양옆에 [[포크]]가 하나씩 있다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없다. 이때 철학자가 스파게티를 먹기 위해서는 양 옆의 포크를 동시에 들어야 한다. 이때 각각의 철학자가 왼쪽의 포크를 들고 그 다음 오른쪽의 포크를 들어서 스파게티를 먹는 알고리즘을 가지고 있으면, 다섯 철학자는 동시에 왼쪽의 포크를 들 수 있으나 오른쪽의 포크는 이미 가져가진 상태이기 때문에 다섯 명 모두가 무한정 서로를 기다리는 [[교착]] 상태에 빠지게 될 수 있다.

또한 어떤 경우에는 동시에 양쪽 포크를 집을 수 없어 식사를 하지 못하는 기아 상태가 발생할 수도 있고, 몇몇 철학자가 다른 철학자보다 식사를 적게 하는 경우가 발생하기도 한다.

== 해결책 ==
[[에츠허르 데이크스트라]]의 해결책은 다음과 같다. 각각의 철학자를 <math>P_1, P_2, P_3, P_4, P_5</math>라고 하고, 각 철학자의 왼쪽 포크를 <math>f_1, f_2, f_3, f_4, f_5</math>라고 하자. <math>P_5</math>를 제외한 네 명은 먼저 <math>f_n</math>를 집은 후 <math>f_{n+1}</math>를 집는 방식을 취한다. 그리고 <math>P_5</math>는 이와 반대로, <math>f_1</math>를 먼저 집은 후 <math>f_5</math>를 집는다. 이것은 원래 방식의 대칭성을 제거하고, 따라서 교착 상태를 막을 수 있다.

== 같이 보기 ==
* [[생산자-소비자 문제]]
* [[독자-저자 문제]]
* [[잠자는 이발사 문제]]

{{전거 통제}}

[[분류:1965년 도입]]
[[분류:병행성]]
[[분류:계산 문제]]
[[분류:에츠허르 데이크스트라]]