[OS] 운영체제 동기화의 문제들(Bound-Buffered, Readers-Writers, Dining-Philosophers)

Bound-Buffered Problem

• shared data
  • semaphore full = 0, empty = n, mutex = 1
  • producer-consumer 문제와 동일하다.
  • empty는 counting semaphore로 초기값에 따라 wait 통과할 수 있는 개수가 달라진다.
  • empty는 남아 있는 buffer의 수를 의미하고, full은 이미 차 있는 buffer의 수를 의미한다.

/* Producer Process */

do {
    ...
    produce an item in nextp
    ...
    wait(empty); // n개가 통과한다
    wait(mutex);
    ...
    add nextp to buffer
    ...
    signal(mutex);
    signal(full);
} while(1);

/* Consumer Process */

do {
    wait(full); // 1 넘어야 가져올 수 있다
    wait(mutex);
    ...
    remove an item from buffer to nextc
    ...
    signal(mutex);
    signal(empty);
    ...
    consume the item in nextc
    ...
} while(1);

• mutex는 critical section 문제를 해결하기 위해 추가되어 있다.
• full의 waiting queue에 대기 중이던 프로세스들은 signal(full)에 의해 전부 깨어나서 ready queue로 이동한다. 프로세스가 여러 개인 경우 이들 중 하나가 스케줄링에 의해 선택된다. 나머지 프로세스는 다시 waiting queue로 돌아간다.
• 좀 더 자세히 이 과정을 살펴보면, (RR 알고리즘을 사용하는 경우) 선택되지 못한 프로세스로 time quantum이 넘어오면 이 프로세스는 선택되지 않아-lock 때문에-실행될 수 없으므로 이때 waiting queue로 돌아간다.

Readers-Writers Problem

• Shared data
  • semaphore mutex = 1, wrt = 1; int readcount = 0;
  • readcount는 같이 수행되는 read 프로세스의 수를 의미한다.
  • R/W conflict rule에서 R-R의 동시 수행만이 가능하다. 나머지(R-W, W-R, W-W)는 불가능하다.
  • semaphore가 두 개인 이유는 read/write lock을 위한 mutex 하나만 존재하는 경우 R-R이 불가능하기 때문이다.
  • first readers-writers 알고리즘을 살펴보자. 이 알고리즘은 R과 W가 혼재된 프로세스들이 동시에 수행될 때 나중에 온 R들도 함께 읽을 수 있는 알고리즘이다. writer starvation 문제가 발생할 수 있다.
    • W 이후 R 실행시 W가 끝날 때까지 기다릴 수도 있다. 이는 second readers-writers 알고리즘이다. reader starvation 문제가 발생할 수 있다.

/* Writer Process */

do {
    wait(wrt);
    ...
    writing is performed
    ...
    signal(wrt);
} while(1);

/* Reader Process */

do {
    wait(mutex);
    readcount++;
    if(readcount == 1) wait(wrt);
    signal(mutex);
    ... reading is performed ...
    wait(mutex);
    readcount--;
    if(readcount == 0) signal(wrt);
    signal(mutex);
} while(1);

Dining-Philosophers Problem

• 공통 자원에 접근하기 위해 필요한 자원에 여러 프로세스가 접근할 수 있을 때 생기는 문제이다.
• 가령, 원형의 식탁 가운데에 음식이 있고 다섯 명의 철학자가 앉아 있다고 해 보자. 이들은 앉아서 생각에 잠겨 있다 배가 고파지면 식사를 한 후 다시 생각에 잠긴다. 철학자들 사이마다 식기가 놓여 있다. 따라서 식기의 개수는 총 다섯 개인데, 누군가 식사를 하고자 하면 자신의 양쪽에 놓인 식기를 이용한다.
• Shared data
  • semaphore chopstick[5];
  • 초기값은 모두 1이다.

Philosopher i :
do {
    wait(chopstick[i]);
    wait(chopstick[(i+1)%5]);
    ...
    eat
    ...
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
    ...
    think
    ...
}while(1);

• 위와 같은 알고리즘의 문제는 무엇일까?

  • 모든 철학자가 동시에 자신의 왼쪽에 있는 식기를 들면 모두가 식기를 하나밖에 가지고 식사를 하지 못하는 deadlock 문제가 발생한다.

• 이를 해결하기 위해 어떤 방법을 사용할 수 있을까?

  • 한 번에 4명만 식탁에 앉게 할 수 있다.
  • 누군가 식사를 하고자 할 때 자신의 양쪽에 앉은 철학자가 식사 중인지 확인하고 두 식기를 동시에 잡을 수 있다.
  • 어떤 사람은 왼쪽 식기, 또 다른 어떤 사람은 오른쪽 식기를 먼저 집도록 정해 둘 수 있다.
  • 가운데 철학자를 제외하고 그의 양쪽 철학자가 번갈아서 식사를 하게 할 수 있다.
    • 이는 deadlock을 해소할 수 있지만 가운데 철학자에게 starvation 문제를 일으킬 수 있다.

• monitor와 condition을 사용하면 deadlock과 starvation을 모두 해결할 수 있다.

monitor dp {
    enum {thinking, hungry, eating} state[5]; // initial value = thinking
    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); // test left neighbor
        test((i+1)%5); // test right neighbor
    }

    void test(int i){
        if((state[(i+4)%5] != eating) && (state[i] == hungry) &&
                state[(i+1)%5] != eating)) {
            state[i] = eating;
            self[i].signal();
        }
    }

    void init(){
        for(int i = 0; i < 5; i++) state[i] = thinking;
    }

}

Philosopher i:
    dp.pickup(i);
  ...
  eat
  ...
  dp.putdown(i);

• hungry는 젓가락을 잡으려고 하는 상태라고 할 수 있다.
  • 가령 4번 철학자가 생각을 하다 식사를 하려고 한다고 해 보자. 우선 식기를 들어야 한다. (pickup) 상태를 hungry로 변경하고 그의 양쪽 철학자(3번과 5번 철학자)가 음식을 먹는 중인지와 자신의 상태를 확인한다. 자신이 배고픈 상태이고 양쪽 모두 식사 중이지 않으면 상태를 eating으로 변경하고 나에게 먹으라는 신호를 보낸다.
  • 식사를 마치고 다시 생각에 잠기려고 식기를 내려 놓을 때가 되면(putdown) 우선 자신의 상태를 변경한다. 그 후 자신의 양옆에 철학자들에 대해 test를 수행한다. 이때, 만약 양쪽의 철학자 중 hungry 상태였던 철학자가 있다면 그가 식사를 시작하게 된다.
  • 만약 4번 철학자가 식사 중이었을 때 3번 철학자가 식사를 시도했다면(pickup) 그는 test에 실패하고 상태를 식사 중으로 변경하지 못해 기다리고 있던 상태(self[i].wait())였을 것이다.