식사하는 철학자 문제

김성준·2021년 12월 2일

식사하는 철학자들 문제

(Dining Philosophers Problem)

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

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

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

교착상태 (Dead Lock)

교착상태는 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만을 기다리며 작업을 더 이상 진행하지 못하는 상태를 의미한다.

교착상태는 교착상태 필요조건을 모두 만족해야 발생한다. 이 중 단 하나라도 충족하지 않으면 교착상태는 발생하지 않는다.

교착 상태 필요조건
1. 상호배재 (mutual exclusion)
한 리소스는 한번에 한 프로세스만이 사용 할 수 있음.
2. 비선점 (non-preemption)
프로세스가 테스크를 마친 후 리소스를 자발적으로 반환할 때 까지 기다림. (강제로 빼앗지 않는다)
3. 점유와 대기 (hold and wait)
어떤 프로세스가 하나 이상의 리소스를 점유하고 있으면서 다른 프로세스가 가지고 있는 리소스를 기다리고 있음.
4. 원형 대기 (circular wait)
점유와 대기관계의 프로세스들이 서로를 기다림.

교착상태의 해결

교착상태를 해결하는 방법으로는 예방, 회피, 검출, 회복이 있다.

- 예방 기법 (Deadlock Prevention)

교착상태가 발생되지 않도록 사전에 예방하는 방법이다.
교착상태 발생 조건 네 가지 중 적어도 하나가 성립하지 않게 만드는 방법이다.
순환 대기를 막는 방법이 네 가지 중 가장 효율적이다. 자원에 순서를 부여하고, 각 프로세스가 오름차순으로 자원을 요청하도록 구현한다.
예방 기법은 일반적으로 자원 사용 효율성이 떨어지고 비용이 많이 드는 문제점이 있다.

- 회피 기법 (Deadlock Avoidance)

교착상태가 발생하는 조건인지 확인하면서 적절히 회피하는 방법이다.
Circular wait가 발생하지 않도록 자원 할당 상태를 검사하면서, 시스템이 안전 상태(Safe state)인지 확인한다.
자원 할당 그래프 알고리즘 (Resource-Allocation Graph Algorithm) : 자원 할당에 대한 그래프를 구성한 후, 그래프에 사이클이 없을 때에만 자원을 할당한다.
은행원 알고리즘 (Banker's Algorithm) : 자원 할당 그래프 알고리즘은 프로세스가 하나의 자원만 사용하는 시스템에서 사용된다. 이에 반해 은행원 알고리즘은 프로세스가 자원을 여러 개 사용하는 경우에도 사용할 수 있는 알고리즘이다.

- 탐지와 회복 기법 (Deadlock Detection & Recovery)

시스템에 교착 상태가 발생했는지 확인하기 위해 시스템의 상태를 검사한다.
탐지 후, 교착 상태를 일으킨 프로세스를 종료하거나, 교착상태의 프로세스에 할당된 자원을 선점하여 교착상태를 제거한다.

- 무시 기법 (Deadlock Ignorance)

교착상태 자체를 무시하고, 특별한 조치를 취하지 않는다. 교착상태의 발생 확률이 낮은 상황에서 효율적이다.
만약 교착상태가 발생한다면, 프로세스를 종료하거나 자원을 선점하여 회복한다.
UNIX, Windows 등 대부분의 운영체제가 이 방법을 사용한다.

42 Seoul Philosopher 과제

philo라는 이름의 프로그램을 만들어야 한다.

프로그램은 4~5개의 인자를 받을 수 있다. (num_of_philo, time_to_die, time_to_eat, time_to_sleep, each_philo_must_eat) -> each_philo_must_eat인자는 선택적이다.

철학자 개인은 스레드여야 한다.

메인 스레드의 순서도
routine 스레드의 순서도
monitor 스레드의 순서도
과제에서 교착상태 발생의 예

철학자들이 죽으면 안되는 인자인 4 410 200 200을 넣었다. 철학자가 사이좋게 밥을 먹는다면 살아야겠지만 교착상태가 발생해 죽어버렸다.
철학자들이 동시에 각자의 오른쪽에 있는 포크를 집고 다른 철학자가 포크를 내려놓기만을 기다리고 있다.
그러다 밥을 먹지못한 시간이 time_to_die시간인 410ms를 초과해서 1번 철학자가 죽은 모습이다.
내가 교착상태를 해결한 방법

철학자들이 동시에 포크를 집는게 문제이므로 짝수와 홀수번째 철학자들이 각기 다른행동을 하게해줬다.
짝수번 철학자는 스레드의 시작에서 usleep(50)만큼 쉬고 시작한다.
또한 짝수번 철학자는 왼쪽 포크부터 집고, 홀수번 철학자는 오른쪽 포크부터 집게 해줬다. 그럼 항상 서로 같은 포크를 먼저 집어야하므로 둘 다 다른 포크를 집고 서로를 기다리는 상황을 피할 수 있다.
첫번째 평가

인자를 5개 이상 주었을 때 예외처리 하지 않음.
프로그램이 메모리를 해제하는 부분에서 해제한 메모리에 접근하여 segfault.(필로의 수가 많은 경우에서)