운영체제 Reader-Writers & Dining Philosophers

고전적인 동기화 문제 중에 Reader-Writers문제와 Dining Philosophers문제를 어떻게 해결하는지 알아보자.

 

 

Reader-Writers

 

데이터베이스에서 데이터에 접근할 때, Reader와 Writer가 존재한다. Reader는 읽기만 하고 데이터를 수정하진 않고 Writer는 읽고 수정도 할 수 있다. 이런 상황에서 writer가 수정하고 있는데 다른 누군가가 읽거나 수정한다면 동기화의 문제가 생긴다. 

 

이렇게 데이터를 수정할 때는 하나의 writer만 할 수 있도록 해야 하고 수정할 때는 reader도 읽어갈 수 없어야 한다.

 

binary semaphore로 해결하면, "mutex"라는 공유 변수를 만들어서 1로 초기화한다.

다음으로 "read_count"라는 int 변수를 만들어 0으로 초기화하여 몇 명의 reader가 CS에 존재하는지 체크한다.

또한 "rw_mutex"라는 공유 변수를 만들어서 1로 초기화한다. rw_mutex는 한 명의 writer만 들어갔는지 확인하는 변수로 사용한다. 

 

Reader의 동작 구조는 다음과 같다.

 

while(1) {
    wait(mutex);
    
    read_count++;
    if ( read_count == 1 )
        wait(rw_mutex);
    
    signal(mutex);
    
    
    /* Critical section */  
   
   
   wait(mutex);
   
   read_count--;
   if ( read_coint == 0 )
       signal(rw_mutex);
   
   signal(mutex);
   
}

 

wait(mutex) :

- 먼저 mutex를 확인한다. 1이라면 mutex를 0으로 만든다

 

if ~ :

- 첫 번째로 진입하는 프로세스는 CS에 writer가 있는지 없는지 확인한다.

 

wait(rw_mutex) :

- rw_mutex가 0이라면 writer가 있다는 뜻이니 대기한다.

 

signal(mutex) :

- writer가 없다면 mutex를 1로 만들고 CS에 들어가서 정보를 읽는다.

 

if ~ :

- 만약 마지막 reader라면 rw_mutex를 1로 만들어줘서 writer와 동기화해준다.

 

 

잘 모르겠다면 semaphore가 어떻게 동작하는지 아래 포스팅을 보고 오면 더 이해가 쉬울 것이다.

 

2022.05.12 - [내가 하는 전자공학/운영체제 (OS)] - 운영체제 Mutex Locks & Semaphore

운영체제 Mutex Locks & Semaphore

 

 

Writer의 동작은 어떻게 될까?? 굉장히 간단하다

 

while(1) { 
    wait(rw_mutex);
    
    /* CS */
    
    signal(rw_mutex);
}

 

rw_mutex를 이용하여 reader와 다른 writer가 들어갈 수 없게 한다.

 

이렇게 semaphore를 이용하여 문제를 해결할 수 있다. 하지만 reader가 계속 들어온다면 writer는 계속 대기해야 하는 starvation이 발생될 수 있다.

 

 

Dining Philosophers 

 

굉장히 재밌는 설정으로 문제를 만들었다. 살짝 이야기 듣는 느낌으로 들었던 기억이 있다.

 

5명을 예로 들어보자 (5개의 프로세스)

다음과 같이 식탁이 있고 양쪽에 1개의 젓가락만이 있다. 이 젓가락을 집을 때는 동시에 양쪽에 있는 젓가락을 집을 수 없고, 하나씩 집어야 한다. 예를 들면 오른쪽 젓가락 집고 왼쪽 젓가락을 집는 것처럼 말이다. (4명이면 4개의 젓가락)

 

중앙에는 식사가 있는데 이 식사는 1번에 1명만 먹을 수 있는데 2개의 젓가락으로 먹어야 한다. 또한 대화를 할 수 없는 식탁이다. 당연하지만 뺏을 수도 없다.

 

 

 

어떻게 할까?? semaphore를 이용해보자 "젓가락[5]"라는 변수를 만들어 1로 초기화 하자

 

가장 간단하게는 다음과 같이 해결할 수 있다.

 

while (true){
    wait ( 젓가락[i] ); // grab her left chopstick
    wait ( 젓가락[ (i + 1) % 5] ); // grab her right chopstick
    
    /* eat for awhile (the critical section) */
    
    signal ( 젓가락[i] ); // release her left chopstick
    signal ( 젓가락[ (i + 1) % 5] ); // release her right chopstick
    /* think for awhile (the remainder section) */
}

 

먼저 왼쪽에 있는 젓가락을 집는다. 그리고 오른쪽에 있는 젓가락을 집는다. 이때 만약 없다면 계속 대기하게 된다. 이 방법은 mutual exclusion을 보장한다. 하지만 가장 큰 문제인 dead lock을 발생시킬 수도 있다.

5명 동시에 왼쪽에 있는 젓가락을 집었을 때 문제가 생긴다. 오른쪽 젓가락을 집어야 밥을 먹고 다시 젓가락을 놓을 텐데 오른쪽 젓가락이 없으면 무한 대기하기 때문이다.

 

이 문제에 대한 간단한 해결방법으로는 

1. 인원보다 젓가락 수를 -1 해서 놓는다. 그렇다면 dead lock이 발생하지 않는다.

2. 집기 전에 먼저 확인하고 집는다. 두 젓가락이 이용 가능한지 확인하고 집는 방법이다. 

3. 홀수는 왼쪽, 짝수는 오른쪽을 먼저 집게 하면 발생하지 않는다. 

 

이 중에서 2번째 방법인 먼저 확인하는 방법으로 monitor를 이용하여 구현해보자

 

 

프로세서 2가 접근할 때 모니터가 보호한다. 이때 중간 상태를 집어넣는다. 먹거나 생각하거나 둘 중에 하나만 했다면 배고픔이라는 상태를 집어넣어서 먹을 수 있는지 없는지 확인하는 것이다. 코드를 보자 

 

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 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 () ;
        }
    }

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

 

dead lock은 완전히 해결됐지만 starvation일 발생할 수도 있다.