식사하는 철학자 문제

<교착상태와 기아상태>
- 교착상태
  - 자원을 자유롭게 할당한 결과 자원부족 상태
  
- 기아상태(Starvation)
  - 교착상태를 예방하기 위해 무한히 기다림
    - 작업이 결코 사용할 수 없고 계속 기다려야 하는 자원을 할당할 때 발생하는 결과





<식사하는 철학자 문제(Dinning-Philosophers Problem)>
- 교착상태나 기아회피 필요를 단순하게 표현하는 고전적인 동기 문제
  - 철학자 5명은 대부분의 시간을 생각하고 먹는데 소비
  - 한 철학자가 생각 중일 때에는 다른 철학자가 간섭하지 않음
  - 철학자는 한 번에 하나의 젓가락만 들 수 있음 
    - 왼쪽 먼저, 오른쪽 나중
    - 이웃 철학자가 들고 있는 것은 취할 수 없음
    - 식사를 마치면 모두 내려놓고 다시 생각함




<철학자 i의 구조>
- 공유 데이터: 
  - Bowl of rice(data set)
  - Semaphore chopstick[5] initialized to 1

do{
wait(chopStick[i]);
wait(chopStick[(i+1) % 5]);

//eat

signal(chopStick[i]);
signal(chopStick[(i+1) % 5]);

//think

} while(true);

- 상호 배제 요건은 만족
- 교착 상태 발생 가능 
  모든 철학자가 동시에 왼쪽 젓가락을 잡으면? 교착상태 발생





<철학자들의 교착상태 원인>
- 순환 요청/대기
  - 5명 모두 왼쪽 젓가락을 가지고 오른쪽 젓가락을 요청하는 순환고리
  - 순환 고리는 스스로 인식이나 해제 불가





<몇 가지 해결 방안>
- 순환 요청/대기가 생기지 않도록
  - 철학자 4명만 테이블에 동시에 앉도록 함
  - 철학자는 양쪽 젓가락을 모두 사용 가능할 때에만 집을 수 있도록 허용
    - 임계영역 내에서 수행
 
  - 비대칭 해결법 적용
    - 홀수번째 철학자는 왼쪽 젓가락을,
       짝수번째 철학자는 오른쪽 젓가락을 먼저 집게 한다






<식사하는 철학자 컴퓨터 시스템>
- 식사하는 철학자 문제는 교착 상태 문제를 비유
  - 철학자 : 프로세스(스레드)
  - 젓가락(포크) : 자원
  - 스파게티 : 처리할 작업




<식사하는 철학자 문제의 주요 이슈>
- 어떤 철학자도 굶어 죽는 일이 없어야 한다
  - 교착상태에 대한 해결책은 기아상태의 가능성을 제거할 수 없다
 
  - 해결을 위해 먼저 기다리는 작업을 발견하고 각 작업이 기다린 시간을 조사/추적해야 한다

  - 시스템은 기아상태를 발결하면 즉시 새로운 작업의 시작을 보류하도록 조취해야한다
    - 빈번한 시스템 보류로 처리량이 감소할 수 있으므로 신중한 접근이 요구된다






<Solution to Dinning Philosophers - 예시>
monitor DP{
enum{  THINKING; HUNGRY, EATING  } state[5];
condition self[5];

void pickup(int i){
state[i] = HUNGRY; 
test(i);
if(state[i] != EATING) self[i].wait;
}

void putdown(int i){
state[i] = THINKING;
//test left and right neighbors
test((i+4) % 5);
test((i+1) % 5);
}

void test(int i){
if( (state[ (i+4) % 5 ] != EATING) //내 앞의 요소(내 앞의 철학자)
  (state[i] == HUNGRY)
(state[ (i+1) % 5] != EATING) ) //내 다음의 요소(내 다음의 철학자){ 
state[i] = EATING; //내가 먹는 상태로 설정
self[i].signal(); //내 번호에 대한 값을 1로 증가, self는 세마포어로 가정
}
}

initialization_code(){
for(int i=0; i<5; i++)
state[i]  = THINKING;
}
}
----------------------------------------------------------
DiningPhilosophers.pickup(i);

//EAT

DiningPhilosophers.putdown(i);