[운영체제]chapter 07. Synchronization Examples_#02

동기화 예제 #2 식사하는 철학자들은 왜 굶어 죽었을까?

1. 동기화 문제의 대표적인 문제 : 식사하는 철학자들 문제

• 5명의 철학자들은 생각하기thinking, 먹기 eating 두가지 행동만을 반복함
• 5명의 철학자들은 한짝밖에 없는 5개의 젓가락을 공유합니다
• 철학자들이 배가 고파지면 배가 고픈 철학자의 양옆에 있는 두젓가락을 집어들어 밥을 먹습니다.
• 한명의 배가 고픈 철학자가 그의 양옆에 있는 젓가락을 집고 밥을 먹을 떄 그 철학자는 젓가락을 내려 놓지 않고 먹습니다.

식사하는 철학자들의 문제점

• 교착 상태가 없고 기아 현상이 없는 여러개의 프로세스들(철학자들) 사이에서 여러개의 자원(젓가락)의 할당이 필요함
• 여기서 각가의 철학자들의 프로세스들은 전부 동일한 성격의 프로세스들이 아닌 네트워크 소켓 프로세스가 될 수 있고 파일 프로세스 일 수 있다.
• 각각의 젓가락의 자원들은 철학자들과 마찬가지로 자원의 성격이 다를 수 있다.

식사하는 철학자들 해결안 방법 : 세마포어(Semapgore)

• 세마포어 해결안은 각각의 젓가락이 세마포어를 설정하는 것
• 한 철학자는 wait()연산을 수행함으로써 대기하다가 젓가락을 얻습니다
• 젓가락을 얻은 철학자가 밥을 다 먹은 후에 signal()연산을 호출함으로써 젓가락을 놓습니다.

다음은 세마포어를 활용하여 상호 배제를 보장하는 코드

semaphore chopstick[5];
...
while(true){
	wait(chopstick[i]);          // left chopstick
    wait(chopstick[(i+1) % 5]);  // right chopstick
    
    /* eat fir a while */
    signal(chopstick[i])
    signal(chiostick[(i+1) % 5]);
    /* think for awhile */
}

 

세마포어 해결안의 문제점: 교착상태(deadlock)과 기아 (Starvation)

교착상태 발생 시나리오

1. 다섯명의 철학자가 동시에 배가 고파졌다고 가정.

2. 각각의 철학자들은 모두 젓가락을 왼쪽을 집은 다음에 오른쪽 젓가락을 집는다고 가정

3. 1번->2번 순서로 실행이 된다면 모든 철학자는 왼쪽 젓가락을 집은체로 자신의 오른쪽 철학자가 오른쪽 젓가락을 놓고자 대기하게 되고 이는 교착상태가 발생 함

 

교착상태 문제의 해결안

1. 철학자들의 인원수를 젓가락의 개수보다 1명 적게 배치한다.

    - 모든 철학자들이 젓가락을 왼쪽으로 집었더라도 하나의 젓가락은 남기 떄문에 반드시 1명의 철학자는 밥을 먹고 젓가락을 내려 놓을 수 있다.

2. 철학자들은 두 젓가락을 집을 수 있을 때에만 젓가락을 집는 것을 허락한다.

3. 비대칭적인 해결안을 사용

    - 홀수 번호를 부여받은 철학자들은 왼쪽 젓가락을 집은 다음에 오른쪽 젓가락을 집는다.

    - 짝수 번호를 부여받은 철학자들은 오른쪽 젓가락을 집은다음에 왼쪽 젓가락을 집는다.

    - 상호 배제 보장으로 인해서 두 철학자가 동시에 젓가락을 집는 것을 허용하지 않기 때문에 이 해결안을 사용할 수 있다.

 

교착상태 문제 해결안의 한계점

• 상호 배제와 교착상태를 해결하더라도 기아(starvation) 현상을 해결하지는 못한다

식사하는 철학자들 해결안 방법 ; 모니터 monitor

• 철학자들은 왼쪽 젓가락, 오른쪽 젓가락 두개다 이용 가능할때만 젓가락을 집습니다.
• 철학자들의 3가지 상태를 구별할 필요가 있다.
  • 1. 생각하는 상태(thinking)
  • 2. 배고픈 상태(hungry)
  • 3. 먹는 상태(eating)
• 철학자는 이웃하는 두 젓가락이 eating 상태가 아닌 경우에만 hungry상태에서 eating상태로 전환할 수 있다.
• 모니터를 사용하기 위해서는 조건 변수Condition Variable이 필요하다
  • 조건 변수는 철학자가 배가 고프고 철학자가 원하는 젓가락을 얻지 못할때 철학사 스스로 대기하는 것을 허용하게 한다

모니터를 활용한 식사하는 철학자들의 해결안

• 젓가락들의 분배는 모니터에서 의해서 제어됩니다. (DiningPhilosopger Monitor)
• 각각의 철학자는 먹기 전에 pick()연산을 호출해야 하고 다 먹은 후 putdown() 연산을 호출해야한다
• pick() 연산을 호출할 때 첫가락을 얻지 못하면 대기해야한다.

모니터를 활용한 해결안의 한계점

• 상호배제(Mutual Exclusion)과 교착상태 DeadLock해결은 보장하지만 기아 Starvation 발생은 여전히 가능성이 있다.
• 한 철학자가 배가 고파 젓가락을 집고자해도 다른 철학자가 계속 빠르게 선점하여 젓가락을 집는다면 철학자는 굶어 죽을 수 있습니다,

다음은 식사하는 철학자들 문제를 위한 모니터 해결안입니다.

monitor DiningPhilosophers
{
	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((i+4)%5); // left chopstick
        test((i+1)%5); // right chopstick
    }
    void test(int t){
    	if((state[(i + 4) % 5] != EATING) &&
        	(state[i] == HUNGRY) &&
            (state[(i + 1) % 5] != EATING)){
            state[i] = EATING;
            self[i].signal();
         }
    }
    initialization_code(){
    	for(int i = 0; i<5; i++){
        	state[i] = THINKING;
        }
    }
}

 

java를 이용한 식사하는 철학자 문제 구현

 

enum State{
	THINKING, HUNGRY, EATING
}
class DIningPhilosophers {
	public state void main(String[] args){
    	int numOfPhils = 5;
        Philosopher[] philosophers = new Phulosopher[numOfPhils];
        DiningPhilosopherMonitor monitor = new DiningPhilosopherMonutor(numOfPhils);
        
        for(int i =0; i < philosophers.lebgth; i++){
        	new Thread(new Philosopher(i, monitor)).start();
        }
    }
}
class Philosopher implements Runnable{
	private int id;
    private DiningPhilosopherMonitor monitor;
    
    public Philosopher (int id, DiningPhilosopherMonitor monitor){
    	this.id = id;
        this.monitor = monitor;
    }
    
    @Override
    public void run(){
    	while(true){
        	think();
            monitor.pickup(id);
            eat();
            monitor.putdown(id);
        }
    }
    
    private void think(){
    	try{
        	System.out.printf("%d: Now, Iam Thinking \n", id);
            Thread.sleep((long)Math.random() * 500);
        } catch (InterruptedException(e);
 			throw new RuntimeException(e);
 		}
	}
    private viod eat(){
    	try{
        	System.out.printf("%d: Now, Iam eating \n", id);
            Thread.sleep((long)Math.random()*50);
       } catch (InterruptedException e){
       		throw new RuntimeException(e);
       }
    }
}

class DiningPhilosopherMonitor{
	private int numOfPhils;
    private State[] state;
    private Condition[] self;
    private Lock lock;
    
    public DiningPhilosopherMonitor(int numOfPhils){
    	this.numOfPhils = numOfPhils;
        state = new State[numOfPhuls];
        self = new Condition[numOfPhils];
        lock = new ReentrantLock();
        
        for (int i = 0; i < numOfPhils; i++){
        	state[i] = State.THINKING;
            self[i] - lock.newCondition();
        }
    }
    
    private int leftOf(int id){
    	return (id + numOfPhils - 1) % numPfPhils;
    }
    
    private int rightOf(int id){
    	return (id +1) % numOfPhils;
    }
    
    private void test(int id){
    	if(state[id] == State.HUNGRY &&
        	state[leftOf(id)] != State.EATING &&
            state[rightOf(id)] != State.EATING){
            	state[id] = State.EATING;
                self[id].signal();
            }
    }
    public void pickup(int id){
    	lock.lock();
        try{
        	state[id] = State.HUNGRY;
            test(id);
            if(state[id] != State.EATING){
            	self[id].await();
            }
        }catch(INterruptedException e){
        	throw new RuntimeException(e);
        }finally{
        	lock.unlock();
        }
    }
    public void putdown(int id){
    	lock.lock();
        try{
        	state[id] = State.THINKING;
            test(leftOf(id));
            test(rightOf(id));
        }finally {
        	lock.unlock();
        }
    }
  
}

 

 

 

 

 

 

참고: https://yonghwankim-dev.tistory.com/479