식사하는 철학자들 문제

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
다섯 명의 철학자와 포크

식사하는 철학자들 문제전산학에서 동시성교착 상태를 설명하는 예시로, 여러 프로세스가 동시에 돌아갈 때 교착 상태가 나타나는 원인을 직관적으로 알 수 있다.

다섯 명의 철학자원탁에 앉아 있고, 각자의 앞에는 스파게티가 있고 양옆에 젓가락이 한 짝씩 있다. 그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없다. 이때 철학자가 스파게티를 먹기 위해서는 양 옆의 젓가락 짝을 동시에 들고 있어야 한다. 이때 각각의 철학자가 왼쪽의 젓가락 짝을 들고 그 다음 오른쪽의 젓가락 짝을 들어서 스파게티를 먹는 알고리즘을 가지고 있으면, 다섯 철학자가 동시에 왼쪽의 젓가락 짝을 든 다음 오른쪽의 젓가락 짝을 들 때까지 무한정 기다리는 교착 상태에 빠지게 될 수 있다.

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

해결책[편집]

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

같이 보기[편집]

바깥 고리[편집]