CS/운영체제

[공룡책🦖] ch7 Synchronization Examples

설기똥꼬 2023. 7. 21. 12:41

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

Classic Problems of Synchronization

다수 동시성 제어의 고전적 문제

  • Bounded-Buffer Problem (유한 버퍼 문제)
  • Readers-Writers Problem (읽기 쓰기 문제)
  • Dining-Philosophers Problem (철학자들의 저녁식사 문제)

 

1. Bounded-Buffer Problem

Producer-Consumer 문제

소비자와 생산자가 공유하는 데이터

  • 각각 하나의 항목을 보유할 수 있는 n개의 버퍼와 상호배제를 제공하는 이진 semaphore로 구성된 풀이 있다고 가정
  • 생산자는 소비자를 위해 버퍼를 가득 채워야 함
  • 소비자는 생산자를 위해 버퍼를 비워야 함

 

생산자 프로세스 코드

while (true) {
    /* produce an item in next produced */
    wait(empty);
    wait(mutex);
    /* add next produced to the buffer */
    signal(mutex);
    signal(full;
}
  • empty 세마포가 0보다 클 때 (빈 공간이 있을 때) 
  • mutex가 존재할 때 (락을 얻을 수 있을 때) 

임계구역에 진입해서 버퍼에 데이터를 입력할 수 있다.

 

 

소비자 프로세스 코드

while (true) {
    wait(full);
    wait(mutex);
    /* remove an item from buffer to next consumed */
    signal(mutex);
    signal(empty);
    /* consume the item in next consumed */
}
  • full 세마포가 0보다 클 때 (버퍼에 데이터가 있을 때)
  • mutex가 존재할 때 (락을 얻을 수 있을 때) 

임계구역에 진입해서 버퍼를 소비할 수 있다.

 

유한 버퍼 문제 프로세스

 

 

Readers-Writers Problem

공유되는 DB에서 readers와 writers process가 있을 때, reader는 동시 접근이 가능하지만 writer는 동시 접근 시 문제가 된다.

따라서 writer는 쓰기 시 데이터베이스에 대해 배타적 접근 권한을 가져야 한다.

 

1. 우선 순위 활용

  • first readers-writers problem reader에게 우선 순위를 준다 ⇒ writer에서 starvation 발생 가능
  • seconde readers-writers problem
  • writer에게 우선 순위를 준다 ⇒ reader에게 starvation 발생 가능

⇒ 두 case 모두 starvation이 발생하기에, semaphore를 이용해 문제를 해결한다.

 

 

2. first readers-writers problem with semaphore

  • Reader process는 자신 이외의 reader process가 종료되기 전까지 wait() 을 호출할 수 없음
  • 즉, Writer 프로세스는 Reader 프로세스 모두가 종료될 때까지 대기함을 의미
    ⇒ Reader 프로세스가 계속해서 물밀듯이 들어오면 writer 프로세스는 기아(Starvation) 상태에 빠질 수 있음

 

2. Second readers-writers problem with semaphore

  • 만약 writer 프로세스가 오브젝트에 접근하면, 새로운 reader 프로세스는 실행할 수 없음
    • writer 프로세스에게 우선 순위를 높게 주어 먼저 실행하게 만드는 것
    • 또한 writer 프로세스가 물밀듯이 들어올 경우 reader 프로세스가 기아 상태에 빠질 수 있음

 

첫번째 readers-writers problem (독자에게 우선권을 주는 문제)에 대해 더 알아보자.

semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0; // reader의 개수
  • rw_mutex : reader, writer 사이의 상호 배제를 위해 사용됨
  • mutex : 공유 변수인 read_count에 대한 상호 배제를 위해 사용
  • read_count : 얼마나 많은 프로세스가 읽고 있는지 나타내기 위해 사용
    read_count = 0 → writer 프로세스 진입

 

while(true) {

    wait(rw_mutex); // 독자로부터 신호가 오면 진입
    
    /* writing is performed */
    
    signal(rw_mutex);
}

while(true) {

    wait(mutex); // 공유 자원 접근을 위한 요청
	read_count++; // 읽고 있는 프로세스의 수 더하기
    if(read_count == 1)
    	wait(rw_mutex); // 독자 프로세스는 여러 프로세스가 진입이 가능하다.
    signal(mutex);
    
    /* reading is performed */
    
    wait(mutex); // 공유 자원 접근을 위한 요청
    read_count --;
    if (read_count == 0)
    	signal(rw_mutex);    
    signal(mutex); 
}
  • Writer 프로세스가 임계 영역에 접근하면 많은 Reader 프로세스는 waiting 상태에 빠짐
  • 한 개의 Reader 프로세스는 rw_mutex에서, 나머지 독자 프로세스는 mutex에서 대기
  • Writer가 signal(rw_mutex) 연산을 실행할 때 대기중인 Writer/Reader 프로세스 실행 여부는스케줄러에 의해 결정
  • 어떤 프로세스의 우선 순위를 높이느냐에 따라 해결책이 갈림
    ⇒ 독자 프로세스의 우선 순위를 높인다면 첫번째 방법, 작가 프로세스의 우선 순위를 높인다면 두번째 방법이 될 것이다.

 

독자-작가 문제 프로세스

 

 

Dining-Philosophers Problem

테이블에 앉은 철학자는 자신의 양쪽에 놓인 젓가락을 집어야 식사를 할 수 있다.

철학자들에게 제공된 젓가락은 딱 다섯 개이다.

철학자들은 배가 고파지면 두 개의 젓가락이 있어야 음식을 먹을 수 있다.

만약 인접한 철학자가 동시에 배고파지면, 한 철학자는 젓가락을 못잡을 것이다.

 

이 상황은 여러 자원을 여러 프로세스가 공유하고 있는 상황으로, 모두가 아무 것도 할 수 없는 deadlock 상황(교착 상태)이 발생한다.

(철학자 = process, 젓가락 = resource)

 

Semaphore Solution

while (true) {
    wait (chopstick[i]); // Left
    wait (chopstick[(i+1) % 5]); // Right
    
    /* eat for a while */
	
    signal (chopstick[i]);
    signal (chopstick[(i+1) % 5]);
    
    /* think for a while */
}
  • 각 젓가락에 세마포어를 부여해주는 방식
  • 철학자들은 젓가락을 잡을 때 wait() 연산, 젓가락을 놓을 때 signal() 연산을 실행하여 상호 배제 보장
  • 5명의 철학자가 동시에 배고파지기라도 하면, 그 누구도 양쪽의 젓가락을 집을 수 없음
    ⇒ 데드락과 기아 문제를 해결하지 못한 방법

 

해결 방법

(1) 최대 4명만 동시에 앉음

(2) 양쪽 젓가락이 가용할 때만 집도록 허용

(3) 비대칭 방법 ⇒ 홀수/짝수 번호별로 다르게 동작

 

 

 

Monitor Solution

  • 모니터를 이용해 해결하는 방법
  • 철학자들은 양쪽의 젓가락이 모두 놓여져 있을 때 젓가락을 집음
  • 철학자들의 상태를 3가지로 구분
enum {THINKING, HUNGRY, EATING} state[5];
  • 이웃들이 Eating이 아닐 때 Eating 상태가 될 수 있다.
(state[i+4)%5] != EATING) and (state[(i+1) % 5] != EATING)

 

한 철학자가 음식을 먹으려면, 인접한 두 철학자가 eating 상태가 아니어야 한다.

또한, 상태 변수를 이용하여 철학자가 hungry 상태이지만 음식을 먹을 수 없을 때 스스로를 지연시키도록 한다.

 

class DiningPhilosopherMonitor {
    private int numOfPhils;
    private State[] state;
    private Condition[] self; // Condition Value
    private Lock lock;

    public DiningPhilosopherMonitor(int num) {
        numOfPhils = num;
        state = new State[num];
        self = new Condition[num];
        lock = new ReentrantLock();
        for (int i = 0; i < num; i++) {
            state[i] = State.THINKING;
            self[i] = lock.newCondition(); // Condition
        }
    }

    private int leftOf(int i) {
        return (i + numOfPhils - 1) % numOfPhils;
    }

    private int rightOf(int i) {
        return (i + 1) % numOfPhils;
    }

    private void test(int i) {
        if (state[i] == State.HUNGRY && state[leftOf(i)] != State.EATING && state[rightOf(i)] != State.EATING) {
            state[i] = State.EATING;
            self[i].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) {

        } finally {
            lock.unlock();
        }
    }

    public void putdown(int id) {
        lock.lock();
        try {
            state[id] = State.THINKING;
            test(leftOf(id));
            test(rightOf(id));

        } finally {
            lock.unlock();
        }
    }
}

 

  • monitor인 DiningPhilosopher에 의해 젓가락의 분배가 이뤄짐
DiningPhilosophers.pickup(i);
	...
   	eat
    ...
DiningPhilosophers.putdown(i);

 

  • 이웃한 두 사람이 동시에 식사하지 않고 deadlock이 일어나지 않음을 보장
  • 그러나 starvation이 발생할 수 있음