식사하는 철학자 문제 : 대표적인 데드락 문제를 알아봅시다.

 식사하는 철학자 문제는 deadlock을 단적으로 보여주는 문제 중 하나입니다. 젓가락이 5개가 있고, 식사를 하기 위해서, 철학자는 자신의 왼쪽, 오른쪽에 있는 젓가락을 들어야 한다고 해 봅시다. 그런데, 사람들이 자기 왼쪽에 있는 젓가락을 든 상태에서, 오른쪽에 있는 젓가락을 얻으려고 한다면 어떨까요? 그리고, 누군가 젓가락을 뺏을 수 없다면? 이럴 때, deadlock이 발생하게 됩니다.

 

 

---

 그러면 이 문제를 풀기 위해서 어떻게 해야 하는지 봅시다.

 

 

 먼저, flag가 있습니다. 이것은 젓가락이 누군가에 의해 집어진 상태인지를 나타냅니다. 5명이 있으니 int형 5개를 저장하는 array를 선언하였습니다. 그리고 people은 현재 식사를 하고 있는 철학자의 수를 의미하는데요. 왜 이 변수를 썼는지 밑에서 차근차근 설명해 드리도록 하겠습니다.

 

 

 wantsToEat 함수의 원형은 다음과 같습니다. 5개의 행동을 하게 되어 있고, 이들 클래스의 run을 호출하면, 문제에서 무언가를 수행하게끔 되어 있습니다. 계속 코드를 봅시다.

 

 

 왼쪽, 오른쪽 젓가락 번호는 어렵지 않게 모듈러 연산으로 구할 수 있고.. 23번째 줄에 people이 4이면, wait 함수를 호출하는 것을 알 수 있어요. 그러면 다른 친구가 notify나, notifyAll을 호출할 때 깨워질 겁니다. 이 조건은 왜 들어갔는지 이해 불가입니다. 이것만 보면요. 27번째, 30번째 줄을 봅시다.

 

 27번째 줄은 자신의 왼쪽 젓가락을 누군가가 쓴다면 block이 되고, 30번째 줄은 오른쪽을 쓰면 block이 된다는 루틴입니다. 그러면, 다음과 같이 수행이 되었다고 가정해 봅시다.

 

 

 1 ~ 5번 쓰레드가 28번째 줄까지 수행했어요. 이 때, 자신의 왼쪽에 있는 것만 집었기 때문에, wait가 걸릴 일이 없습니다. 문제는 그 다음에, 1번이 30번째 줄을 수행할 때인데요.

 

 

 1번이 eat를 하기 위한 젓가락은 2번에 의해 점유되어 있습니다. 2번이 오른쪽 젓가락을 들으려고 할 때, 그것은 3번에 의해 점유되어 있습니다. 

 

 

 어떠한 자원 a를, 철학자 b가 얻으려면 a에서 b 방향으로 연결이 되어 있습니다. 어떠한 자원 a를 철학자 b가 물고 있으면, b에서 a로 연결이 되어 있습니다. 이걸 그래프로 그려 보았을 때 익숙한 사이클 그림이 나옵니다. 그 말은, 각 철학자가 자신의 왼쪽에 있는 젓가락만 들었을 때, 누군가 젓가락을 내려놓지 않는다면 계속 wait만 한다는 것입니다.

 

 예를 들자면, 3번이 right를 얻어야 할 때에는 4번이 들고 있는 것을 내려놓아야 하는데.. 먹지 않았을 때, 강제로 내려놓는 과정이 없다면, 4번 또한 음식을 먹기 위해서 5번이 들고 있는 것을 내려놓기를 기다려야 하기 때문입니다. 그러면, 식사를 하기 위해 앉은 철학자의 수가 4명이면 어떻게 될까요?

 

 

---

 사실, 우리가 생각할 수 있는 최악의 경우는, 어떤 사람이 자신의 왼쪽의 젓가락을 짚는 순간, 다른 사람이 또 왼쪽 젓가락을 짚는 시나리오가 될 겁니다. 만약에 중간에 누군가 right를 들 수 있어서 식사를 한다면, 먹기 위한 도구 2개를 먹고 나서 내려놓을 수 있습니다. 사람들 입장에서 보았을 때에는, 먹을 수 있는 도구가 2개가 추가로 생기는 상황입니다. 상황이 나빠지지 않습니다.

 

 상황이 나빠진다. 안 나빠진다. 극한의 경우에 이렇게 된다. 이것을 이용한 greedy 기법도 있다고 들었습니다. 이것은 제 역량을 넘어서기 때문에 추가적으로 언급하지는 않겠습니다.

 

 

 synchronized 블록 안에 people이 증가하고 감소하는 연산이 있기 때문에, 식사를 하기 위해 앉은 철학자의 수는 잘 갱신이 될 겁니다. 그러면 1 left, 2 left, 3 left, 4 left가 수행된 후에, 다시 5번 Thread가 left를 수행하려는 순간 people이 4이기 때문에, block이 걸릴 겁니다.

 

 

 그렇다면, 하나의 도구는 사용 가능합니다. i번 사람이 (i+4)%5번과 i번 젓가락을 사용 가능하다고 한다면 이 때 그래프는 아래와 같이 그릴 수 있습니다.

 

 

 그러면, 1번 프로세스는 오른쪽 젓가락을 택할 수 있습니다. 1번이 left를 집는 과정을 수행했고, 나머지 사람 0, 3, 4가 right를 집는다고 해 봅시다. 그러면 각각 0번, 3번, 4번이 점유중이기 때문에, 30번째 while Loop에 걸려버립니다.

 

 

 따라서, wait가 호출이 되고, 1번이 notifyAll을 호출할 때 까지 block이 될 겁니다. 그런데 1번 리소스 (젓가락)은 아직 점유가 된 상태가 아니므로 1번 쓰레드는 30번째 줄에 있는 while Loop에 걸리지 않고, 31번째 줄부터 수행을 할 수 있게 됩니다.

 

 

 그 후에 0번, 1번 리소스를 release 하게 됩니다. 내려 놓게 되면, 0번이 자신의 우측에 있는 것을 쓸 수 있게 됩니다. 테이블에 2번만 못 앉았을 때, 3번만 못 앉았을 때, 4번만 못 앉았을 때 이것도 비슷합니다. 위상이 다르지 않습니다. 따라서 5개의 젓가락이 있고 5개의 앉을 수 있는 자리가 있을 때, 4명만 앉게 하면 젓가락을 얻기 위해 서로가 무한정 대기하는 현상은 발생하지 않습니다.

 

 이 방법 말고도, 다른 방식으로 avoid를 하는 방법도 있습니다. 이 부분은 찾아보시고, 왜 이게 가능한지에 대해 곰곰히 생각해 보시면 도움이 많이 될 듯 싶습니다.