[운영체제] 프로세스 동기화 (2/2)

본 게시글은 KOCW 이화여자대학교 반효경 교수님의 <운영체제> 강의를 듣고,
<혼자 공부하는 컴퓨터구조 + 운영체제> 책을 참고하여 정리한 내용입니다.
게시글에 포함되는 이미지 자료는 <운영체제> 강의에 포함된 강의 자료입니다.

Synchronization과 관련된 고전적인 문제

• Bounded-Buffer Problem (Producer-Consumer Problem)
• Readers and Writers Problem
• Dining-Philosophers Problem

1. Bounded-Buffer Problem(Producer-Consumer Problem)

 

시나리오

두 종류의 프로세스 존재

1. 생산자(producer) 프로세스: 데이터 생산해서 공유 버퍼에 넣음

2. 소비자(consumer) 프로세스: 데이터를 버퍼에서 꺼내가서 소비

 

발생 가능한 문제

1. lock과 관련된 문제

생산자, 소비자 프로세스가 공유 버퍼의 데이터에 동시에 접근할 수 있다. - 버퍼에 대한 lock이 필요

 

2. 버퍼가 유한하기 때문에 생기는 문제

생산자 입장에서는 비어있는 버퍼가 자원이기 때문에 버퍼가 다 찼다면 empty 버퍼가 생길 때까지 기다려야 함

소비자 입장에서는 데이터가 들어있는 버퍼가 자원이기 때문에 empty 버퍼 뿐이라면 생산자가 데이터를 생산해 버퍼에 넣어줄 때까지 기다려야 함

 

생산자-소비자 문제에서 필요한 세마포어의 역할

1. 공유 데이터(shared data)의 상호배제(lock 걸고 푸는 작업)를 위한 세마포어

2. 가용 버퍼를 카운트해주는 세마포어

 

Synchronization variables

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

/*
full: 데이터 들어있는 버퍼 개수
empty: 비어있는 버퍼 개수
mutex: 공유 버퍼에 하나의 프로세스만 접근하게 하기 위한 변수 (lock)
*/

Producer

do {
    produce an item in x
    
    P(empty); // 빈 버퍼가 있다면 하나 획득 (empty 1 감소)
    P(mutex); // 버퍼에 접근해 데이터를 집어넣기 위해 lock
    
    add x to buffer
    
    V(mutex); // 데이터 삽입 작업 끝나면 unlock
    V(full); // full 1증가(소비자 깨워줄 수 있도록)
} while(1)

Consumer

do {
    P(full); // full 버퍼 있다면 하나 획득 (full 1 감소)
    P(mutex); // 획득했다면 버퍼 전체에 lock
    
    remove an item from buffer to y
    
    V(mutex); // unlock
    V(empty); // empty 1증가
    
    comsume the item in y
} while(1);

2. Readers-Writers Problem

시나리오

공유 자원에 데이터를 읽기만 하는 reader 와 데이터를 변경할 수 있는 writer 존재

- reader: 공유 데이터에 동시에 여러 프로세스가 접근해도 됨 (문제x)

- writer: 하나의 프로세스가 데이터에 접근 중이면 다른 프로세스들의 접근 금지됨

 

Shared data

int readcount = 0; // 현재 DB에 접근 중인 reader의 수
DB; // 공유데이터

Synchronization variables

semaphore mutex = 1, db = 1; 

/* 
mutex: readcount를 위한 lock
db: DB에 대한 lock
*/

Writer

P(db); // lock

writing DB is performed;

V(db); // unlock

Reader

P (mutex); // readcount 에 대한 lock (writer가 접근하면 데이터가 변경되므로)
readcount++;
if (readcount == 1) P(db); // 처음으로 접근하는 reader 라면 db에 lock
V(mutex); // unlock

reading DB is performed

P(mutex);
readcount--;
if (readcount == 0) V(db);  // reader 가 있다면, writer는 기다렸다가 접근 가능
V(mutex); // unlock

 

reader가 DB에 접근해서 읽는 작업을 수행하고 있는 도중에 writer가 접근하려고 한다면 writer는 reader의 작업이 끝나고 lock이 풀릴 때까지 기다려야 합니다. 기다리는 중에 reader가 계속 들어온다면 writer는 모든 reader가 나갈때까지 계속 기다려야 하기 때문에 starvation 문제가 발생할 수 있습니다.

3. Dining-Philosophers Problem

시나리오

5명의 철학자가 원탁에 둘러앉아서 밥을 먹는데 젓가락이 철학자 양 옆으로 1개씩 총 5개 놓여있습니다.
철학자는 생각을 하거나 식사를 할 수 있는데, 젓가락 양쪽을 모두 집어야 식사를 할 수 있습니다.

 

Synchronization variables

Semaphore chopstick[5] = { 1 }; // 양 옆 철학자가 공유하는 자원인 젓가락

Philosopher i

do {
    P(chopstick[i]);
    P(chopstick[(i + 1) % 5];
    
    eat();
    
    
    V(chopstick[i]);
    V(chopstick[(i + 1) % 5];  
    
    think();
    
    
} while(1);

 

위 코드의 문제점

• Deadlock의 가능성
• 모든 철학자가 동시에 왼쪽 젓가락을 집어버린 경우 아무도 식사를 하지 못하고 오른쪽 젓가락을 계속 기다림

해결 방안

• 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다. (인원 수 줄이기)
• 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
• 비대칭: 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다. (젓가락에 우선순위를 두기)

enum { thinking, hungry, eating } state[5]; // 철학자의 상태
semaphore self[5] = 0; // 양쪽 젓가락을 잡을 권한. 처음엔 전부 권한이 없음(0)
semaphore mutex = 1; // lock - 옆 철학자의 상태가 바뀌면 나의 젓가락을 집을 권한에도 영향이 오기 때문에 상태를 바꾸기 전에 lock 을 걸어야

do {
    pickup(i);
    eat();
    putdown(i);
    think();
} while(1);


void pickup(int i) {
    P(mutex); // lock for state
    state[i] = hungry;
    test(i); // 젓가락 잡을 수 있는 권한에 대한 조건 체크
    V(mutex); // unlock
    P(self[i]); // self[i] 1 -> 0 만약 젓가락을 잡을 수 있다면 젓가락 사용, 없다면 대기.
}

void putdown(int i) {
    P(mutex); // lock for state
    state[i] = thinking;
    // 양 옆 철학자가 내가 젓가락을 쥐고있어서 밥을 못먹었다면 먹을 수 있게 해줌
    test((i + 1) % 5); // 오른쪽
    test((i - 1) % 5); // 왼쪽
    V(mutex); // unlock
}

void test(int i) {
    // 조건: 양 쪽이 식사중이 아니면서 나의 state는 hungry
    if (state[(i - 1) % 5] != eating && state[i] == hungry && state[(i + 1) % 5] != eating) {
        state[i] = eating;
        V(self[i]); // self[i]  0 -> 1 젓가락을 잡을 권한 부여
    }
}

 

위의 코드로 보는 세마포어의 문제점

• 코딩하기 힘들다
• 정확성의 입증이 어렵다
• 인터페이스 없이 자발적 협력이 필요하다
• 한번의 실수가 모든 시스템에 치명적 영향

P(mutex)
critical section
V(mutex)

// 만약 실수로 코드 잘못 쓴다면1 - Mutual exclusion 깨짐
V(mutex)
critical section
P(mutex)

// 만약 실수로 코드 잘못 쓴다면 - Deadlock
P(mutex)
critical section
P(mutex)

해결책 3: Monitor

프로그래밍 언어차원에서 프로세스 동기화 문제를 해결하는 방법으로, 동시 수행중인 프로세스 사이에서 추상자료형을 안전하게 공유할 수 있게 보장해주는 high-level synchronization construct 입니다.

 

• 공유 자원에 동시 접근을 막는 것을 모니터 차원에서 지원 (프로그래머 입장에서 훨씬 수월한 방법)
• 공유 자원과 공유 자원에 접근하기 위한 인터페이스(통로)를 묶어 관리
• 프로세스는 반드시 인터페이스를 통해서만 공유 자원에 접근할 수 있도록 함
• 모니터 안에 항상 하나의 프로세스만 들어오도록 하여 상호 배제를 위한 동기화를 제공
• 공유 자원을 다루는 인터페이스에 접근하기 위한 큐(= 모니터에 진입하기 위한 큐)를 만들고, 모니터 안에 프로세스가 있다면 큐에 삽입해 줄을 세움
• 모니터 안에 있는 active한 프로세스의 수가 0이 될 때 큐의 프로세스들이 접근할 수 있게 됨

모니터의 실행 순서 제어를 위한 동기화 방법

모니터 내에서는 한번에 하나의 프로세스만이 활동 가능합니다. 이를 제어하기 위해 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없으며, 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable(조건 변수)을 사용합니다.

 

condition variable

• 값을 가지는 변수가 아니며, 어떤 프로세스를 잠들게 하고 줄 세우기 위한 변수
• wait, signal 연산에 의해 접근 가능
  • wait: 공유 자원에 여분이 없을 때 signal 호출 전까지 프로세스 잠들게 함
  • signal: 프로세스를 깨우는 역할. 이전에 공유 자원에 접근한 프로세스가 나가면서 호출함. suspended 가 없으면 아무 일도 일어나지 않음.

코드 구현 예시

Bounded-Buffer

공유 버퍼가 모니터 내부에 있으면서, 생산자 or 소비자 프로세스가 접근하려고 할 때 monitor 내부 코드를 실행해야 하기 때문에 한번에 하나의 프로세스만 활성화됩니다. (lock/unlock 필요x)

monitor bounded_buffer {
    int buffer[N];
    condition full, empty; 
    /* 
    값을 가지지 않고, 자신의 큐에 프로세스를 매달아서 sleep 시키거나 큐에서 프로세스를 깨워주는 역할만 함
    full: 데이터가 있는 버퍼를 기다리는 프로세스를 줄세움
    empty: 데이터가 없는 버퍼를 기다리는 프로세스를 줄세움
    */
    
    void produce(int x) {
        if there is no empty buffer
            empty.wait(); // 생산자 기준 자원 없음 -> 잠들도록
        add x to an empty buffer
        full.signal(); // 소비자 깨움
    }
    
    void consume(int x) {
        if there is no full buffer
            full.wait(); // 소비자 기준 자원 없음 -> 잠들도록
        add x to an full buffer
        empty.signal(); // 생산자 깨움
    }
}

Dining Philosophers

코드 구현은 세마포어와 비슷하지만 차이점은 lock/unlock 작업이 없다는 점입니다. (대신 if문으로 상태체크 후 프로세스 잠들도록)

monitor dining_philosopher {
    enum { thinking, hungry, eating } state[5];
    condition self[5];
    
    void pickup(int i) {
        state[i] = hungry;
        test(i); // 젓가락 2개를 다 잡을 수 있는지에 대한 권한 체크
        if (state[i] != eating) 
            self[i].wait(); // cf) semaphore 일 땐 P 연산
    }

    void putdown(int i) {
        state[i] = thinking;
        test((i + 1) % 5);
        test((i - 1) % 5);
    }

    void test(int i) {
        if (state[(i - 1) % 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 {
    do {
        pickup(i); // 모니터 내부 연산을 이용
        eat();
        putdown(i); // 모니터 내부 연산을 이용
        think();
    } while(1);
}