[OS] 프로세스 동기화 (3)

위영민(Victor)·2021년 5월 17일

Classical Problems of Synchronization

Bounded-Buffer Problem

(= Producer-Consumer Problem, 생산자 소비자 문제)

= 공유 버퍼의 크기가 유한한 환경에서 생기는 문제

생산자-소비자 문제

두 개의 생산자 혹은 소비자가 동시에 데이터 접근 시
소비자/생산자 없이 생산자/소비자만 드글드글(자원 부족)

아래와 같이 공유버퍼에 두 종류의 프로세스가 있다.

Producer (buffer에 데이터 넣기)

Empty buffer(자원)가 있나? (없으면 기다림)
공유 데이터에 lock을 건다
Empty buffer에 데이터 입력 및 buffer 조작
Lock을 푼다
Full buffer 하나 증가 (pointer)

Consumer (buffer에서 데이터 꺼내기)

Full buffer(자원)가 있나? (없으면 기다림)
공유 데이터에 lock을 건다
Full buffer에서 데이터를 꺼내고 buffer 조작
Lock을 푼다
Empty buffer 하나 증가 (pointer)

언제 동기화문제가 발생하나 ?

자원에 대한 동시접근

Producer의 경우

빈 버퍼의 두 생산자가 버퍼가 비어있음을 보고, 동시에 버퍼를 채우려고하는 상황
- 공유버퍼에 대한 Lock을 줘서, 작업하고 있는 버퍼에 나 이외에 다른 생산자 or 소비자가 버퍼에 접근할 수 없도록 해야함

Consumer의 경우

하나의 채워진 버퍼 데이터에 경우, 두 Consumer가 동시에 꺼내 먹으려 하는 경우
- 공유 버퍼에 대한 Lock을 줘서, 작업하고 있는 버퍼에 다른 생산자 or 소비자가 버퍼에 접근할 수 없도록 해야함

Bounded Buffer여서 발생하는 문제

자원의 관점에서

Producer

빈 버퍼가 곧, 자원임
버퍼가 모두 채워져 있으면, 자원이 없는(채울 공간이 없는)것

Consumer

채워진 버퍼가 자원임
버퍼가 모두 비어있으면, 자원이 없는(빼먹을 수 없는)것

Shared Data

Buffer 자체 및 Buffer 조작 변수( empty / full Buffer의 시작위치 )

Synchronized Variable

Lock 제어 변수 = binary semaphore 필요
Resource(버퍼) count 변수 = integer semaphore 필요 (남은 empty / full 버퍼 수)

// - Producer
do {
    produce an item in x
        ...
    P(empty);             // 빈 퍼버가 있는지 확인
    P(mutex);             // 있다면, lock을 건다
        ...
    add x to buffer
        ...
    V(mutex);             // lock을 푼다
    V(full);              // full buffer의 개수 1 증가
}

// - Consumer
do {
    P(full);              // full 버퍼가 있는지 확인
    P(mutex);             // 있다면, lock을 건다
        ...
    remove an item from buffer to y
        ...
    V(mutex);             // lock을 푼다
    V(empty);             // empty buffer의 개수 1 증가
        ...
    consume the item in y
}

Reader-Writer Problem(읽는자-쓰는자 문제)

= reader와 writer 두 개의 프로세스가 DB를 공유하는 환경

문제

한 프로세스가 DB(공유자원)에 write 중일 때, 다른 프로세스가 접근하면 안 됨
read는 동시에 여럿이 해도 됨 (=> 모든 상황에 lock걸면 비효율)

해결법

Writer가 DB에 아직 접근 허가를 못받은 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근하게 해줌
Reader들을 다 DB에 접근하게 해줌
Writer는 대기 중인 Reader가 하나도 없을 때, DB 접근이 허용됨
일단 writer가 DB에 접근 중이면 Reader들은 접근이 금지됨
Writer가 DB에서 빠져 나가야만 Reader의 접근이 허용됨

Shared Data

DB 그 자체
read count = 현재 DB에 접근중인 Reader의 수

Synchronized Variable

mutex = read count에 접근하는 코드(Critical Section)의 상호배제 보장(Reader간 readcount에 lock 역할)
db = Reader와 Writer가 공유 DB에 자체에 올바르게 접근하게 하는 역할(DB에 대한 lock)

// - Writer
P(db);                  // writer가 들어가면 lock을 건다
...
writing DB is performed
...
V(db);                  // lock을 풀어줌

// - Reader
P(mutex);               // readcount를 증가시키기 위한 lock 걸기
readcount++;            // readcount 1 증가
if (readcount == 1) P(db); // 내가 처음 들어온 reader라면 DB lock 걸기
V(mutex);               // readcount에 대한 lock 풀기
...
reading DB is performed
...
P(mutex);               // readcount를 감소시키기 위한 lock 걸기
readecount--;
if (readcount == 0) V(db); // 내가 마지막 reader라면 DB lock 풀기
V(mutex);               // readcount에 대한 lock 풀기

치명적인 문제점

starvation 발생 가능

reader 집단이 엄청 많은 상황에서, 마지막 reader가 빠져 나가기 전에, 또 많은 reader 집단이 또 오는.. = writer는 언제 DB에 접근할 수 있을지 모름
개선방법 : 어느 정도의 reader가 빠져 나가면 writer에게 차례 줌
(신호등 생기면 언젠가는 건널 수 있다!)

Dining-Philosopher Problem(식사하는 철학자 문제)

5명의 철학자는 생각하거나 / 밥을 먹는 두 가지 행위를 할 수 있다.
인접한 철학자끼리는 젓가락을 공유하고, 왼쪽과 오른쪽 젓가락 두 개를 획득해야 밥을 먹을 수 있다.

Synchronization variables

semaphore chopsticks[5]; (초기값은 모두 1: 혼자서만 젓가락을 잡을 수 있음)

Philosopher i
do {
    P(chopstick[i]);            // 왼쪽 젓가락을 잡는 행위
    P(chopstick[(i+1) % 5]);    // 오른쪽 젓가락을 잡는 행위
    ...
    eat();                      // 밥 먹는 중..
    ...
    V(chopstick[i])             // 왼쪽 젓가락 놓기
    V(chopstick[(i+1) % 5])     // 오른쪽 젓가락 놓기
    ...
    think();
}

문제점

= deadlock 가능성 (모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집은 경우)

해결법 (이론적)

4명의 철학자만이 테이블에 동시에 앉도록 한다.
젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
비대칭(짝수/홀수) 철학자는 왼쪽/오른쪽 젓가락부터 집도록(같은 젓가락!)

변수

enum { thinking, hungry, eating } state[5]; (상태표현)
semaphore self[5] = 0; (젓가락 두 개 확보 가능해 밥먹을 권리 부여)
semaphore mutex = 1; (상태를 동시에 바꾸지 못하도록 lock걸기)

// Philosopher i
do {
    pickup(i);
    eat();
    putdown(i);
    think();
}

void pickup(int i) {
    P(mutex);           // 상태 바꾸기 전 lock 걸기
    state[i] = hungry;  // hungry로 상태 변경
    test(i);            // 젓가락 둘 다 집을 수 있는지 테스트
    V(mutex);           // lock 풀고
    P(self[i]);         // 밥 먹을 수 있는 권리 해제(1->0)
}

void test(int i) {
    if (state[(i+4)%5] != eating && state[i] == hungry && state[(i+1)%5] != eating) {// 양쪽 철학자가 먹고있지 않고 내가 배고플 때
        state[i] = eating; // eating으로 상태 변경
        V(self[i]);        // 밥 먹을 수 있는 권리 부여(0->1)
    }
}

void putdown(int i) {
    P(mutex);
    state[i] = thinking;
    test((i+4)%5);      // 혹시 나 땜에 못먹었는지 양쪽 철학자 테스트
    test((i+1)%5);
    V(mutex);
}