식사하는 철학자들(The Dining-Philosophers) 문제 규칙
식사하는 철학자들 문제
가정
- 5명의 철학자가 원형 테이블을 공유하는 상황
- 테이블 중앙에는 밥이 있고, 테이블에는 5개의 젓가락이 존재
- 철학자가 생각(행동) 할 때, 다른 동료들과 상호작용하지 않음
밥을 먹을 때의 규칙
- 자신에게 가장 가까이 있는 2개의 젓가락을 집으려고 시도
- 옆 사람이 들고 있는 젓가락은 집을 수 없다.
- 가까이 있는 2개의 젓가락
→ 자신과 자신의 왼쪽 철학자, 그리고 오른쪽 철학자 사이에 있는 젓가락을 뜻함
- 철학자는 한 번에 한 개의 젓가락만 집을 수 있음
- 배고픈 철학자가 동시에 젓가락 2개를 집는 경우
- 젓가락을 놓지 않고 식사를 한다.
- 식사를 마치면 2개의 젓가락 모두 내려놓고 다시 대기한다.
식사하는 철학자 문제의 의의
- 고전적인 동기화 문제로 간주 ← 많은 부류의 병행 제어의 한 예이기 때문
- 해당 방식은 교착 상태와 기아 상태를 발생시키지 않음
- 여러 스레드에게 여러 자원을 할당해야 할 필요를 단순하게 표현한 것
세마포 해결안(Semaphore Solution)
해결 방식
- 간단한 해결책 중 하나
- 각 젓가락을 하나의 세마포로 표현하는 것
- 젓가락(세마포)을 집으려고 시도할 때 →
wait() 연산을 실행
- 젓가락(세마포)을 놓을 때 →
signal() 연산을 실행
semaphore chopstick [5]; : 이 해결 방식의 공유 자료
철학자 i의 구조
while(true){
// 2개의 젓가락이 사용가능해질때까지 대기
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
// 젓가락 2개를 획득한 후,
...
/* 식사 */
...
// 2개의 젓가락을 내려 놓음
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
...
/* 생각 */
...
}
세마포 해결안의 특징
- 해당 방식은 인접한 두 철학자가 동시에 식사하지 않음을 보장
- But, 교착 상태(DeadLock) 발생 가능성이 있기 때문에 사용할 수 없음
- 5명의 철학자가 모두 동시에 배가 고파서, 각각 자신의 왼쪽 젓가락을 집을 경우
→ chopstick의 모든 원소가 0이 됨
→ 각 철학자는 오른쪽 젓가락을 집으려면 영원히 대기
교착 상태 문제에 대한 해결책
- 최대 4명의 철학자만 테이블에 동시에 앉을 수 있도록 한다.
- 한 철학자가 젓가락 2개를 모두 집을 수 있을 때만 젓가락을 집도록 허용
- 해당 방식을 사용하기 위해서는 임계구역 안에서만 젓가락을 집어야 함
- 비대칭 해결안 사용
- 홀수 번호의 철학자는 왼쪽부터, 짝수 번호의 철학자는 오른쪽부터 집게 한다.
모니터 해결안(Monitor Solution)
- 철학자 문제에 대한 교착 상태가 없는 해결하기 위해 모니터 사용
해결 방식
- 철학자는 양쪽 젓가락 모두 얻을 수 있을 때만 젓가락을 집을 수 있다는 제한을 강제
→ 이를 구현하기 위해 철학자의 상태를 3가지로 구분
- 철학자 상태에 대한 자료구조 도입
enum {THINKING, HUNGRY, EATING} state [5];
- 철학자 i는 양쪽에 이웃한 철학자가 식사하지 않을 때만
state [i] = EATING 설정
condition self [5];
- self는 철학자 i가 배고프지만, 원하는 젓가락을 집을 수 없을 때 집는 것을 미루게 함
- 젓가락의 분배는 모니터 DiningPhilosophers에 의해 제어
해결 순서
- 각 철학자는 식사하기 전에
pickup() 연산을 반드시 호출해야 함
- 해당 행동은 철학자 프로세스의 일시 중지를 낳을 수도 있음
- 연산이 성공적으로 끝나면 철학자는 식사를 진행
- 식사 후, 철학자는
putdown() 연산을 호출해야 함
DiningPhilosophers.pickup(i);
...
eat
...
DiningPhilosophers.putdown(i);
모니터 해결안의 구조
monitor DiningPhilosophers
{
enum{THINKING, HUNGRY, EATING} state[5];
condition self[5]; // EATING을 하지 못하고 잠시 미룰때 씀
// i번째 철학자가 젓가락을 든다.
void pickup(int i){
state[i] = HUNGRY;
test(i); // 양쪽에 철학자를 확인
// 먹을 수 없는 상태면 self에 추가하고 대기
if(state[i] != EATING) self[i].wait();
}
// i번째 철학자가 식사 후 젓가락을 내려놓는다.
void putdown(int i){
state[i] = THINKING;
// 양 옆에 있는 철학자가 식사할수있도록 호출
test((i+4) % 5);
test((i+1) % 5);
}
// 양쪽에 있는 철학자가 EATING 상태인지를 확인
void test(int i){
// i번째 철학자 상태가 배고픔
// && i번째 철학자와 이웃한 철학자가 EATING 상태가 아닐때만
if((state[(i+4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
((state[(i+1) % 5] != EATING)){
state[i] = EATING;
self[i].signal(); // 대기해뒀던 i번째 철학자를 깨움
}
}
// 초기엔 THINKING으로 초기화
initialization_code(){
for(int i = 0; i < 5; i++)
state[i] = THINKING;
}
}
- 해당 방식의 장점
- 두 철학자가 동시에 식사하지 않는다.
- 교착 상태가 발생하지 않는다.
- 해당 방식의 단점