식사하는 철학자 문제(Dining Philosopher Problem)

목표

식사하는 철학자 문제를 해결할 수 있다.

 

식사하는 철학자 문제란?

철학자 다섯 명이 원형 식탁에 앉아 밥을 먹으려고 합니다. 그들의 양쪽엔 각각 젓가락 한 짝씩 놓여 있고, 밥을 먹으려 할 땐 다음의 과정을 따릅니다.

1. 왼쪽 젓가락부터 집어 듭니다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때까지 대기합니다.
2. 왼쪽을 들었으면 오른쪽 젓가락을 듭니다. 들 수 없다면 대기합니다.
3. 두 젓가락을 모두 들었다면 일정 시간 동안 식사를 합니다.
4. 식사를 마쳤으면 오른쪽 젓가락을 내려 놓은 후 왼쪽 젓가락을 내려놓습니다.
5. 다시 배고프면 1번부터 진행합니다.

철학자는 프로세스 젓가락은 자원으로 가정한 후 모든 철학자가 왼쪽 젓가락을 들은 상황을 가정해봅시다. 그렇다면 모든 철학자는 오른쪽 젓가락을 집기 위해 대기하는 교착상태가 발생합니다. 조금 더 자세하게 교착상태 발생의 4가지 필요충분조건을 만족하는지 확인해보겠습니다.

 

상호 배제 -> 젓가락은 한 번에 한 철학자만 사용할 수 있습니다.

점유와 대기 -> 왼쪽 젓가락을 점유하면서 오른쪽 젓가락을 대기합니다.

비선점 -> 이미 누군가가 집어 든 젓가락을 강제로 뺏을 수 없습니다.

환형 대기 -> 모든 철학자들이 오른쪽에 앉은 철학자가 젓가락을 놓기를 기다립니다.

 

따라서 식사하는 철학자 문제는 교착상태의 대표적인 예제라고 볼 수 있습니다! 이어서 식사하는 철학자 문제를 해결하는 방법에 대해서 말씀드리겠습니다.

 

해결 방법 ①

왼쪽 젓가락을 집은 후 오른쪽 젓가락을 사용할 수 있는지 확인하고 사용할 수 없으면 젓가락을 모두 내려놓고 랜덤 시간 동안 기다린 다음 방금 과정을 다시 반복합니다. 랜덤한 시간 동안 기다리기 때문에 만약 모두 동시에 왼쪽 젓가락을 집었다고 하더라도 서로 기다리는 시간이 다르므로 결국에 식사를 하는 사람이 생깁니다. 하지만 낮은 확률로 여전히 기아 현상이 발생할 수 있다는 문제점이 있습니다.

 

해결 방법 ②

식사할 수 있는 상황을 하나의 key로 관리합니다. 즉 뮤텍스(Mutex) 형태로 관리하면 한 명은 식사할 수 있습니다. 하지만 반대편도 식사할 수 있는 상황이라 조금 더 나은 해결 방법이 필요해 보입니다.

 

해결 방법 ③

뮤텍스 형태가 아닌 세마포어 형태로 관리하면 식사하는 철학자 문제를 완벽하게 해결할 수 있습니다. 철학자의 상태를 식사 중, 식사 대기 중으로 표현하고 자신의 양쪽이 식사 중이 아니면 식사를 할 수 있도록 세마포어 형태로 관리하면 주어진 상황에서 최대한 많은 철학자들이 식사를 할  수 있습니다.