배고픈(식사하는) 철학자들 문제와 해결책 이해

배고픈 철학자의 문제는

운영체제시간에 언급된 적이 있었다. 공부에 신경쓰지 않던 때라 흘려 들었던 터라, 현재 공부하다가 관련된 내용이 나와서 간단히 정리한다.

여러 프로세스가 공유되는 자원을 사용하기 때문에 발생하는 문제에  대한 것을 이해하기에 흥미롭게 만든 것이다. 

그냥 위키피디아 내용에 내가 이해한 내용을 살포시 얹었다.

식사하는 철학자들 문제

위키백과, 우리 모두의 백과사전.

(철학자들의 만찬 문제에서 넘어옴)

둘러보기로 가기 검색하러 가기

다섯 명의 철학자와 포크

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

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

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

해결책[편집]

에츠허르 데이크스트라의 해결책은 다음과 같다. 각각의 철학자를 ${\displaystyle P_{1},P_{2},P_{3},P_{4},P_{5}}$라고 하고, 각 철학자의 왼쪽 젓가락을 ${\displaystyle f_{1},f_{2},f_{3},f_{4},f_{5}}$라고 하자. ${\displaystyle P_{5}}$를 제외한 네 명은 먼저 ${\displaystyle f_{n}}$를 집은 후 ${\displaystyle f_{n+1}}$를 집는 방식을 취한다. 그리고 ${\displaystyle P_{5}}$는 이와 반대로, ${\displaystyle f_{1}}$를 먼저 집은 후 ${\displaystyle f_{5}}$를 집는다. 이것은 원래 방식의 대칭성을 제거하고, 따라서 교착 상태를 막을 수 있다.

*해결책 이해

각자 각자 서로 겹치지 않게 젓가락을 사용하는 경우는 생각 할 필요 없고,

젓가락 사용이 겹치는 상황을 생각해보자.

P1~P5모두가 동시에 스파게티를 먹으려고 하면,

P1~P4는 모두 왼쪽 젓가락(F1~F4)을 들겠지, P5는 오른쪽 젓가락을 들려고 할거란 말이야, P5가 우선 들려고 하는 젓가락은 자신의 오른쪽 젓가락 즉 F1

이다. 근데 이건 이미 P1이 쥐고 있으니, 첫번째 젓가락이 없으니, 두번째로 들어야 할 젓가락(F5)를 가지려고 하진 않는단 말이지. 그럼 P4는 두번째로

쥐어야 할 F5를 쥐게 될거고, 식사를 할 수가 있다. P4가 식사를 마치고 나면, 자신의 젓가락들을 다 내려놓을테니 다음 사람도 순차적으로 젓가락 사용이

가능해지는 것.

극한의 디테일적으로 생각한다면...

(여기서 P1~P5가 동시에 첫 젓가락을 쥐는데, F1을 P1이 아닌 P5가 먼저 쥘 수도 있는데, 누가 먼저 쥐던 이해에 상관 없음. 완벽하게 동시에 쥐려고 하면 어쩌나 궁금한 사람도 있을지 모르는데, 프로세스들이 완벽히 동시에 순간에 자원에 접근하는 타이밍이 같기도 힘들기 때문에 상관 없음. 같다면 둘다 다시 접근하라고 하면, 타이밍 달라지겠지 뭐.)