[면접] Dining philosophers

철학자 5명이 원형 식탁에 둘러앉아 생각에 빠지다가, 배고플 땐 밥을 먹는다. 그들의 양쪽엔 각각 젓가락 한 짝씩 놓여있고, 밥을 먹으려 할 땐 다음의 과정을 따른다.

1. 왼쪽 젓가락부터 집어든다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때까지 생각하며 대기한다.

2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 1번과 마찬가지로 들 수 있을 때까지 생각하며 대기한다.

3. 두 젓가락을 모두 들었다면 일정 시간동안 식사를 한다.

4. 식사를 마쳤으면 오른쪽 젓가락을 내려놓고, 그 다음 왼쪽 젓가락을 내려놓는다.

5. 다시 생각하다가 배고프면 1번으로 돌아간다.

프로그래밍으로 만들었을 때 발생할 수 있는 문제점이 무엇일까?

만약 모든 철학자가 동시에 배가 고파서 왼쪽 젓가락을 들면 어떻게 될까?

오른쪽 젓가락은 이미 자신의 우측에 앉은 철학자가 집어들었기 때문에, 모두가 영원히 오른쪽 젓가락을 들지 못하게 된다. 그렇게 2번에서 더이상 진행하지 못하고 철학자들은 영원히 생각에 빠지게 되는데, 이런 현상을 교착상태(Deadlock)라고 한다.

Dining philosophers 문제가 교착상태인 것은 데드락 발생의 4가지를 모두 만족하기 때문이다.

데드락 발생 4가지 필요조건

1. 상호배타(Mutual Exclusion)

젓가락은 한번에 한 철학자만 사용할 수 있다.

2. 보유 및 대기(Hold and Wait)

집어든 젓가락은 계속 들은 채로 사용중인 반대쪽 젓가락을 기다린다.

3. 비선점(No Preemption)

이미 누군가 집어든 젓가락을 강제로 뺏을 수 없다.

4. 환형대기(Circular Wait)

모든 철학자들이 자신의 오른쪽에 앉은 철학자가 젓가락을 놓기를 기다린다.

그렇다면 해결 방법은 없는 것일까?

1. 최대 4명의 철학자만이 테이블에 앉을 수 있게 한다.

2. 한 철학자가 두 개를 모두 집을 수 있을 때만 젓가락을 들 수 있도록 한다.

3. 비대칭 해결안을 사용한다.

   홀수 번째 철학자는 왼쪽 젓가락부터 짝수 번째 철학자는 오른쪽 젓가락부터 집어야 한다.

이 중에서 한 가지의 조건을 추가하면 된다.