식사하는 철학자들 문제 - 위키백과, 우리 모두의 백과사전
원탁에 둘러앉은 다섯 명의 철학자와 다섯 접시의 스파게티, 그리고 다섯 개의 포크 식사하는 철학자들 문제는 전산학에서 동시성과 교착 상태를 설명하는 예시로, 여러 프로세스가 동시에 돌
ko.wikipedia.org
식사하는 철학자들 문제는 전산학에서 동시성과 교착 상태를 설명하는 예시로, 여러 프로세스가 동시에 돌아갈 때 교착상태가 나타나는 원인을 직관적으로 알 수 있다.
교착상태 : 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 말함.
다섯 명의 철학자가 원탁에 앉아 있고, 각자의 앞에는 스파게티가 있고 양옆에 포크가 하나씩 있다.
각각의 철학자는 다른 철학자에게 말을 할 수 없다.
이 때 철학자가 스파게티를 먹기 위해서는 양 옆의 포크를 동시에 들어야 한다.
이 때 각각의 철학자가 왼쪽의 포크를 들고 그 다음 오른쪽의 포크를 들어서 스파게티를 먹는 알고리즘을 가지고 있으면, 다섯 철학자는 동시에 왼쪽의 포크를 들 수 있으나 오른쪽의 포크는 이미 가져가진 상태이기 때문에 다섯 명 모두가 무한정 서로를 기다리는 교착상태에 빠지게 될 수 있다.
또한 어떤 경우에는 동시에 양쪽 포크를 집을 수 없어 식사를 하지 못하는 기아 상태가 발생할 수도 있고, 몇몇 철학자가 다른 철학자보다 식사를 적게 하는 경우가 발생하기도 한다.
에츠허르 데이크스트라의 해결책은 다음과 같다. 각각의 철학자를 P1, P2, P3, P4, P5라고 하고, 각 철학자의 왼쪽 포크를 F1, F2, F3, F4, F5라고 하자. P5를 제외한 네 명은 먼저 Fn을 집은 후 F(n+1)을 잡는 방식을 취한다. 그리고 P5는 이와 반대로, F1을 먼저 집은 후 F5를 집는다. 이것은 원래 방식의 대칭성을 제거하므로 교착상태를 막을 수 있다.
