동기화 예제

동기화 예제

고전적인 동기화 문제들

동기화 방법들을 검증하는데 사용되는 동기화 문제들

유한 버퍼 문제

동기화 기본요소(뮤텍스, 세마포어 등)들의 능력을 설명하기 위하여 사용되는 문제다.

 

생산자 소비자는 다음과 같은 자료 구조를 공유한다.

int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

• n개의 버퍼로 구성된 풀이 있으며, 각 버퍼는 한 아이템을 저장할 수 있다.
• mutex 이진 세마포어는 버퍼 풀에 접근하기 위한 상호 배제 기능을 제공하며 1로 초기화 된다.

while(true) {                                      
    /* 버퍼에 넣을 아이템 생성 */
    ...
    wait(empty);
    wait(mutex);
    ...
    /* 버퍼에 아이템 추가 */
    ...
    signal(mutex);
    signal(full);
}                                                   

while(true) {                                      
    wait(full);
    wait(mutex);
    ...
    /* 버퍼에서 아이템을 꺼냄 */
    ...
    signal(mutex);
    signal(empty);
    /* 아이템 소비 */
}                                                   

wait(), signal()이 서로 대칭이다. 생산자는 버퍼가 비어있길 기다리며, 소비자는 버퍼가 가득차길 기다린다.

 

mutex는 동시에 버퍼에 접근할 수 없도록 락을 걸어준다.

Readers-Writers 문제

• readers
  • 데이터베이스의 내용을 읽기만 함
• writers
  • 데이터베이스를 갱신(읽고, 쓰기) 할 수 있음

두 reader가 동시에 공유 데이터에 접근하면 문제가 발생하지 않음, 그러나 하나의 write와 다른 스레드(reader 또는 writer)가 동시에 공유 데이터에 접근하면 문제가 발생할 수 있다.

 

따라서 writer가 쓰기 작업 동안에 공유 데이터에 배타적 접근을 가지게 할 필요가 있다.

 

Readers-writers 문제의 여러가지 변형들

• 첫 번째 문제
  • writer가 공유 데이터 사용 허가를 받은 경우가 아니라면, reader들은 대기 상태에 놓여서는 안된다.
  • 어떤 reader들도 writer가 대기하고 있다고 해서 대기하면 안됨
  • writer가 기아 상태에 빠질 수 있음
• 두 번째 문제
  • writer가 준비되면 가능한 빨리 쓰기를 수행하 것을 요구한다.
  • writer가 객체에 접근하려고 기다리고 있다면 새로운 reader들은 읽기 작업을 시작할 수 없음
  • reader가 기아 상태에 빠질 수 있음

readers-wrtiers 문제 해결안

semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

• rw_mutex는 reader, writer 모두가 공유한다.
• mutex 세마포는 read_count를 갱신할 때 상호 배제를 보장하기 위해 사용한다.
  • read_count는 현재 몇 개의 프로세스들이 객체를 읽고 있는지 알려준다.
• rw_mutex 세마포는 writer들을 위한 상호 배제 세마포다.
  • 첫 번째 reader와 임계구역을 빠져나오는 마지막 reader에 의해서도 사용된다.

Writer 프로세스의 구조

while (true) {
    wait(rw_mutex);
    ...
    /* 쓰기 수행 */
    ...
    signal(rw_mutex);
}

Reader 프로세스의 구조

while (true) {
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);
    ...
    /* 읽기 수행 */
    ...
    wait(mutex);
    read_count--;
    if (read_count == 0) 
        signal(rw_mutex);
    signal(mutex);
}

몇몇 시스템에서는 read-writer락을 제공한다.

• 읽기, 쓰기 모드 인지 지정해야 한다.
• 프로세스가 공유 데이터를 읽기만 원한다면 읽기 모드의 reader-writer 락을 요청한다.
  • 여러개의 프로세스가 락을 획득 하는 것이 가능
• 수정을 원한다면 쓰기 모드의 락을 요청
  • 공유 자원에 배타적으로 접근해야 하므로 하나의 프로세스만이 락을 획득

reader-writer 락은 다음과 같은 상황에서 가장 유용하다.

• 공유 데이터를 읽기만 하는 프로세스와 쓰기만 하는 프로세스 스레드를 식별하기 쉬운 어플리케이션
• Writer보다 Reader의 개수가 많은 어플리케이션
  • 일반적으로 reader-writer 락을 설정하는데 드는 오버헤드가 세마포나 상호 배제 락을 설정할 때 보다 크다.
  • 이 오버헤드는 동시에 여러 reader가 읽게 하여 병행성을 높임으로써 상쇄할 수 있음

식사하는 철학자들 문제

• 철학자들 5명이 있고 양 옆에는 젓가락이 있음
• 철학자는 생각하고 있다가, 배가 고파지면 식사를 한다.
• 철학자들은 밥을 먹으려면 자신의 양 옆에 있는 젓가락을 사용해야 한다.
  • 철학자는 옆 사람이 젓가락을 들고 있는 경우 젓가락을 집을 수 없음
• 철학자가 젓가락을 집으면 식사를 한다. 식사를 마치면 다시 생각을 시작한다.

식사하는 철학자문제는 고전적인 동기화 문제이다.

• 교착 상태와 기아를 발생시키지 않고 여러 스레드에게 여러 자원을 할당해야 하는 상황을 단순하게 표현함

식사하는 철학자 문제의 해결방법(세마포 사용)

semaphore chopstick[5];

• wait() 연산을 실행하여 젓가락을 집으려고 시도하고, singal() 연산을 실행해서 자신의 젓가락을 내려놓는다.

while (true) {
    wait(chopstick[i]);
    wait(chopstick[i+1] % 5);
    ...
    /* 식사 */
    ...
    signal(chopstick[i]);
    signal(chopstick[i+1] % 5);
    ...
    /* 생각 */
    ...
}

위의 해결안은 두 철학자가 동시에 식사하지 않는다는 것을 보장하지만, 교착 상태를 야기한다.

• 모든 철학자가 왼쪽에 있는 젓가락을 잡은 상태에서 오른쪽 젓가락을 잡으려고 하면 영원히 기다려야 한다.

교착 상태 문제를 해결하기 위한 방법

• 최대 4명의 철학자만 테이블에 동시에 앉을 수 있게 한다.
  • 세 명이 젓가락을 한 개씩 가지고 있더라도 나머지 한 명은 식사를 할 수 있음
  • 한 명이 식사를 마치면 다른 철학자들도 식사를 할 수 있음
• 한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집도록 허용
  • 모니터를 이용해 해결 가능하다.
• 비대칭 해결안 사용한다. 홀수 번호 철학자는 왼쪽 젓가락을 집고 오른쪽 젓가락을 집는다. 짝수 번호 철학자들은 오른쪽 젓가락을 집고 왼쪽 젓가락을 집는다.
  • 순환 대기(Circular wait)을 방지한다.

그러나 기아 상태를 해결하지 못함

• 일부 철학자에게 지속적으로 자원이 할당되지 않을 수 있음

모니터 해결안

철학자는 양쪽 젓가락 모두 얻을 수 있을 때만 젓가락을 집을 수 있다. 이 해결안을 구현하려면 철학자의 상태를 세 가지로 구분할 필요가 있다.

enum {THINKING, HUNGRY, EATING} state[5];

철학자 i는 양쪽 이웃이 식사하지 않을 때(state[(i+4) % 5] != EATING, state[(i+1) % 6 != EATING])만 state[i] = EATING으로 설정할 수 있다.

 

또한 다음 변수가 필요하다.

condition self[5];

self는 철학자 i가 배고프지만 자신이 원하는 젓가락을 집을 수 없을 때 젓가락 집기를 미룰 수 있도록 한다.

 

식사하는 철학자 모니터 해결안 연산

DiningPhilosophers.pickup(i);
...
식사
...
DiningPhilosophers.putdown(i);

식사하는 철학자 모니터 정의

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

교착 상태를 방지하지만, 기아 상태를 방지하지는 못함