식사하는 철학자 문제
철학자 다섯이서 원형 식탁에 둘러앉아 생각에 빠지다가, 배고플 땐 밥을 먹는다. 그들의 양쪽엔 각각 젓가락 한 짝씩 놓여있고, 밥을 먹으려 할 땐 다음의 과정을 따른다.
1. 왼쪽 젓가락부터 집어든다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때 까지 생각하며 대기한다.
2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 1번과 마찬가지로 들 수 있을 때까지 생각하며 대기한다.
3. 두 젓가락을 모두 들었다면 일정 시간동안 식사를 한다.
4. 식사를 마쳤으면 오른쪽 젓가락을 내려놓고, 그 다음 왼쪽 젓가락을 내려놓는다.
5. 다시 생각하다가 배고프면 1번으로 돌아간다.
발생할 수 있는 문제
식사하는 철학자 문제는 교착상태(Deadlock)의 대표적인 예제이다. 위의 상황을 프로그램으로 만들어 실행하면 잘 돌아가다가 어느순간 멈춰버리는 것을 확인할 수 있는데, 그 이유는 식사하는 철학자 문제가 데드락 발생의 4가지 필요조건을 모두 만족하고 있기 때문이다. 만약 모든 철학자가 동시에 배가 고파서 왼쪽 젓가락을 집어든다면 어떻게 될까? 오른쪽 젓가락은 이미 자신의 우측에 앉은 철학자가 집어들엇을 것이므로, 모두가 영원히 오른쪽 젓가락을 들지 못하게 된다. 그렇게 상단 과정의 2번에서 더이상 진행하지 못했고 철학자들은 영원히 생각에 빠지게 되는데 이런 현상을 컴퓨터 과학에선 교착상태(Deadlock)라고 한다. 한번 교착상태에 빠진 철학자들은 계속 고뇌만 하다가 기아현상(Starvation)으로 굶어 죽는다.
교착상태 4가지 필요조건
1. 상호 배타(Mutual Exclusion)
젓가락은 한 번에 한 철학자만 사용할 수 있다.
2. 보유 및 대기(Hold and Wait)
집어든 젓가락은 계속 들은채로 사용중인 반대쪽 젓가락을 기다린다.
3. 비선점(No Preemption)
이미 누군가 집어든 젓가락을 강제로 뺏을 수 없다.
4. 환형대기(Circular Wait)
모든 철학자들이 자신의 오른쪽에 앉은 철학자가 젓가락을 놓기를 기다린다.
교착상태 해결(Deadlock)해결
위 문제에서 철학자는 프로세스, 젓가락은 자원을 상징한다. 실제 컴퓨터 시스템에서 교착상태가 발생했을 경우 자칫 감당해야하는 피해가 어마어마해질 수도 있기에, 교착상태는 반드시 예의주시하고 해결해야 할 문제이다. 교착상태의 해결은 위의 4가지 조건을 프로그램이 전부 성립하는 일이 없게끔 하면 된다 4가지중 하나만 어겨도 데드락이 발생하지 않기 때문이다.