(36) Dining Philosophers Problems (철학자들의 만찬 문제) (Synchronization Problems)

### Dining Philosophsers Problems (철학자들의 만찬문제) ###​

: Deadlock(교착)상태를 설명하기 위한 문제

​

< 설명 >

5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.

(꼭! 포크 2개를 들고 밥을 먹어야한다)

​

1. 왼쪽 포크가 사용 가능해질 때까지 생각을 한다. 만약 사용 가능해지면 집어든다.

2. 오른쪽 포크가 사용 가능해질 때까지 생각을 한다. 만약 사용 가능해지면 집어든다.

3. 양쪽의 포크를 잡으면 정해진 시간만큼 식사를 한다.

4. 오른쪽 포크를 내려놓는다.

5. 왼쪽 포크를 내려놓는다.

6. 다시 1번으로 돌아간다.

​

​

간단하게, 만약 모든 철학자(process)들이 동시에 자신의 왼쪽 포크(공유 자원)를 잡는다면,

모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다.

그런데 모든 철학자들이 그러고 있다.

이 상태에서는 모든 철학자가 영원히 2번 상태에 머물러있어 음식을 먹을 수 없는 상태가 교착(Deadlock)상태이다.

 

 

 

 

< 해결 방안>

< Semaphore solution >

(fork = chopstick = semaphore)

while (true){
	wait(fork[i]);
    wait(fork[(i+1) % 5]);
    
    // 먹는 동안 
    
    signal(fork[i])
    signal(fork[(i+1) % 5]);
    
    // 생각
}

 

 

< Deadlock >

: 임의의 philosophers는 두 이웃이 동시에 식사를 하지 않는다는 것을 보장하지만

그럼에도 deadlock(교착)상태를 야기할 수 있다.

(philosophsers들이 동시에 배가 고파 각1개의 포크를 움켜지었을 때는 더이상 집을 포크가 없어 0이 된다

(lock이 걸린다) => 그래서 각 philosophers들이 포크의 lock이 풀리기를 무한히 기다리는 상황)

 

 

 

< Deadlock 해결 방안 >

1. table에서의 philosophers의 수에 제약을 건다.

​

2. philosophers가 2개의 포크 모두 사용 가능한 경우에만 포크를 집게한다.

​

3. 비대칭적인 해결책 사용

: 홀수 philosophers은 왼쪽포크 -> 오른쪽포크

: 짝수 philosophers은 오른쪽포크 -> 왼쪽포크

​

​

​

​

< Deadlock-free solution >

: deadlock 없다

: starvation 있을 수 있다.

monitor Philosophers{
// 자신의 양쪽에 있는 philosophers가 EAT 상황이 아닐 때 자신을 EAT으로 바꾼다.

	enum {THINK, HUNGRY, EAT} state[5];
    condition self[5];

    void test(int i){
    	if ((state[(i + 4) % 5] != EAT) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EAT)){
        	state[i] = EAT;
            self[i].signal();
        }
    }
    
 
    void pickup_fork(int i){
    	state[i] = HUNGRY;
        test(i);
        
        if (state[i] != EAT){
        	self[i].wait()
        }
    }
    
    void putdown_fork(int i){
    	state[i] = THINK;
        test((i + 4) % 5);
        test((i + 1) % 5);
    }
    
    
    code(){
    	for (int i = 0; i < 5; i++){
        	state[i] = THINK;
        }
    }
    
}