Philosophers

식사하는 철학자 문제

주제

이 프로젝트에서는 프로세스 스레딩의 기본 사항과 동일한 메모리 공간에서 작업하는 방법을 배웁니다. 스레드를을 만드는 방법을 배웁니다. 뮤텍스, 세마포어 및 공유 메모리에 대해 배웁니다.

목표

deadlock문제를 해결하여 철학자가 굶어죽지 않는 프로그램을 작성한다.

문제

식사하는 철학자 문제는 deadlock의 대표적인 예제이며, deadklock의 4가지 발생 조건을 모두 만족한다.

Deadlock의 4가지 발생 조건

Deaklock : 철학자가 식사를 하지 못해 굶어 죽음(Starvation)

1. Mutual Exclusion : 포크(이하 젓가락)는 한번에 한 철학자만 사용할 수 있음.
2. Hold and Wait : 집어든 젓가락을 계속 들을 채로 반대쪽 젓가락을 기다림.
3. No Preemption : 다른 철학자의 젓가락을 강제로 뺏을 수 없음.
4. Circular Wait : 모든 철학자들이 자신의 오른쪽에 앉은 철학자가 젓가락을 놓기를 기다림.

일반적인 해결 방법

철학자는 스레드 혹은 프로세스, 젓가락은 공유 메모리(자원)을 상징한다.
deadlock의 발생 조건 4가지 중 하나만 해결하여도 deadlock을 해결할 수 있다.

에츠허르 데이크스트라의 해결책은 다음과 같다.

각각의 철학자를 P₁, P₂, P₃, P₄, P₅라고 하고, 각 철학자의 왼쪽 포크를 f₁, f₂, f₃, f₄,f₅라고 하자. P₅를 제외한 네 명은 먼저 f_n를 집은 후 f_n+1를 집는 방식을 취한다. 그리고 P₅는 이와 반대로, f₁를 먼저 집은 후 f₅를 집는다. 이것은 원래 방식의 대칭성을 제거하고, 따라서 교착 상태를 막을 수 있다.

이 프로젝트의 해결 방법

철학자에게 강제적으로 비대칭성을 부여한다. 예를 들면, 홀수 철학자들은 짝수철학자들보다 포크를 1초 늦게 집게 한다.

규칙 정의

1. 철학자는 3가지 행동을 한다: 먹기, 자기, 생각하기
2. 동시에 2가지 행동을 할 수 없다.
3. 포크를 양 손에 하나씩 즉, 2개를 집어야 먹을 수 있다.
4. 철학자는 굶어 죽으면 안되고, 반드시 먹어야 한다.
5. 철학자를 서로 이야기를 하지 않으며, 누가 언제 죽을지 모른다.
6. 철학자가 잠을 다 자면, 생각하기 시작한다.
7. 아래의 프로그램들은 다음의 인자를 받을 수 있다.
   • number_of_philosophers : 철학자 수(포크 수)
   • time_to_die : 식사를 하지 않으면 죽는 시간
   • time_to_eat : 먹는데 걸리는 시간
   • time_to_sleep : 자는데 걸리는 시간
   • number_of_times_each_philosopher_must_eat(optional) : 프로그램 종료까지 반드시 먹어야 하는 횟수
8. 철학자는 원탁에 앉아 있으며, 1번부터 시작한다.
9. N번 철학자는 N - 1번 철학자와 N + 1번 철학자 사이에 위치한다.
10. 출력이 뒤엉켜서는 안된다.
11. 철학자가 죽으면 10ms안에 출력해야 한다.

philo_one

thread, mutex

• 각 철학자 사이에 1개의 포크가 있으며, 철학자의 왼쪽과 오른쪽에 위치한다.
• 포크의 상태를 mutex로 보호한다.
• 각 철학자는 thread이다.

philo_two

thread, semaphore

• 모든 포크가 테이블 중앙에 있다.
• 포크의 상태를 저장하지 않고, 포크의 갯수를 semaphore로 나타내야한다.
• 각 철학자는 thread이다.

philo_three

process, semaphore

• 모든 포크가 테이블 중앙에 있다.
• 포크의 상태를 저장하지 않고, 포크의 갯수를 semaphore로 나타내야한다.
• 각 철학자는 process이다.

용어 정리

1. Deadlock
2. Starvation
3. 스레드와 프로세스