[운영체제] 프로세스 동기화 Process Synchronization

이전 포스팅

https://soyeonnnb.tistory.com/30

6-1. 프로세스 동기화 Process Synchronization

---

Classical Problems of Synchronization

1. Bounded-Buffer Problem (Producer-Consumeer Problem)
2. Readers and Writers Problem
3. Dining-Philosophers Problem

Bounded-Buffer Problem (생산자-소비자 문제 Producer-Consumer Problem)

• Shared data
  • buffer 자체 및 buffer 조작 변수 (empty/full buffer 의 시작 위치)
• Synchronization variables
  • mutual exclusion → Need binary semaphore(shared data의 mutual exclusion을 위해)
  • resource count  → Need integer semaphore(남은 full/empty buffer의 수 표시)

구현

• Synchronization variables
  • semaphore full = 0, empty = n, mutex = 1(공유 버퍼를 1개의 프로세스만 접근 가능);
• Producer

do {
    produce an item in x
    ...
    P(empty);	// 비어있는 버퍼가 있으면
    P(mutex);	// lock을 걸고
    ...
    add x to buffer
    ...
    V(mutex);	// lock을 품
    V(full);
} while (1);

• Consumer

do {
    P(full);
    P(mutex);
    ...
    remove an item from buffer to y
    ...
    V(mutex);
    V(empty);
    ...
    consume the item in y
    ...
} while (1);

Readers-Writers Problem

• 한 프로세스가 DB에 write 중일 때 다른 process가 접근하면 안됨
• read는 동시에 여럿이 해도 됨
• solution
  • Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.
  • Writer는 대기 중이 Reader가 하나도 없을 때 DB 접근이 허용된다.
  • 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
  • Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.
• Shared data
  • DB자체
  • readcount: 현재 DB에 접근중이 Reader의 수
• Synchronization variables
  • mutex: 공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclustion 보장을 위해 사용
  • db: Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

구현

• shared data
  • int readcount = 0;
  • DB자체
• synchronization variables
  • semaphore mutex = 1, db = 1;
• Writer

P(db);
...
writing DB is performed
...
V(db);

→ Starvation 발생 가능 !!!

reader가 계속해서 들어오게 되면 writer의 차례는 오지 않음. 그래서 우선순위 큐같은 곳에 writer의 우선순위를 높여서 해소하는 등의 방법을 사용할 수 있음

• Reader

P(mutex);
readcount++;
if (readcount == 1) P(db);	// Writer의 접근을 막고
V(mutex);			// readers follow
...
reading DB is performed
...
P(mutex);
readcount--;
if (readcount == 0) V(db); // 다시 Writer가 접근 가능하도록 함
V(mutex);

→ 읽는 작업 같은 경우는 동시에 해도 되는데, 읽는 작업도 한 개의 프로세스만 가능함

그래서 readcount라는 변수를 사용하게 된다. 내가 최초의 reader라면 2, 3번째 줄에 의해 readcount == 1이 되어 db에 락을 건다. 그리고 내가 마지막으로 빠져나온 reader라면 마지막에서 2, 3 째 줄에 의해 db의 락을 풀게 된다.

Dining-Philosophers Problem

• Synchronization variables
  • semaphore chopstick[5];
    • initially all values are 1
• Philosopher i

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

• 앞의 solution의 문제점
  • Deadlock 가능성이 있다.
  • 모든 철학자가 동시에 배가 고파져서 왼쪽 젓가락을 집어버린 경우
• 해결 방안
  • 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
  • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
  • 비대칭
    • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 
• 해결방안 2번째꺼 코드

enum {thinking, hungry, eating} state[5];
semaphore self[5] = 0; // 0은 잡을 수 없는 상태
semaphore mutex = 1; // 5명의 상태를 바꿀 수 있는 건 다른 철학자(옆의 철학자)도 바꿀 수 있다. 
// 즉 여러 철학자가 한 철학자의 상태를 바꿀 수 있고, 이러한 공유 변수에 대한 동시 접근을 
// 막기 위해 lock을 사용하기 위해 mutex를 사용한다.

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

void pickup(int i) {
    P(mutex);
    state[i] = hungry;
    test(i);
    V(mutex);
    P(self[i]);
}

void putdown(int i) {
    P(mutex);
    state[i] = thinking;
    test((i+4)%5);
    test((i+1)%5);
    V(mutex);
}

void test(int i) {
    if (state[(i+4)%5] != eating && state[i] == hungry && state[(i+1)%5] != eating) {
        state[i] = eating;
        V(self[i]); // 0 -> 1로 바꾼다
    }
}

이 코드는 semaphore의 원리에 맞게 잘 짜여진 코드라고는 할 수 없다. 그냥 이해만 !

Monitor

• Semaphore의 문제점
  • 코딩하기 힘들다
  • 정확성(correctness)의 입증이 어렵다
  • 자발적 협력(voluntary cooperation)이 필요하다
  • 한번의 실수가 모든 시스템에 치명적 영향
  • 예

원래 P  → V 해야하는데 V  → P를 한다거나 P만 두번 한다거나 하면 오류가 발생한다.

• Monitor: 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct

공유데이터가 있을 때, 밖에서 공유데이터에 접근을 막기 위해 모니터 내부에 공유데이터와 이 공유 데이터에 접근할 수 있는 operation들을 정의해둔다. 그래서 해당 공유데이터에 접근하기 위해서는 정의된 operation들을 통해서만 접근 가능하도록 한다. 이렇게 하면 프로그래머 입장에서는 lock을 걸 필요가 없어진다 !! semaphore같은 경우에는 접근을 하기 전에 락을 걸고 접근 후에 락을 푸는 작업을 프로그래머가 해야 했다. 하지만 모니터와 같은 경우에는 모니터 자체에 동시 접근을 막을 수 있도록 설계가 되어 있어서 프로그래머 입장에서 그냥 데이터에 접근하면 된다. 그러면 모니터에서 알아서 동시 접근을 막아주고, 접근하지 못한 프로세스들은 entry queue에서 기다리게 된다.

Monitor 특징

• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
  • 모니터 안에서 어떤 조건이 충족이 안되서 프로세스가 잠들게 하고 줄세우기 위한 변수들. 조건을 뜻함
  • condition x, y;
• Condition variable은 wait와 signal 연산에 의해서만 접근 가능
  • x.wait();
    • x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke 하기 전까지 suspend 된다.
  • x.signal();
    • x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

Bounded-Buffer Problem + Monitor

monitor bounded_buffer {
    int buffer[N];
    condition full, empty;
    // condition var.은 값을 가지지 않고 자신의 큐에 프로세스를 매달아서 sleep 시키거나
    // 큐에서 프로세스를 깨우는 역할만 함
    
    void produce (int x) {
        if there is no empty buffer
       	    empty.wait();
        add x to and empty buffer
        full.signal();
    }
    
    void consume (int *x) {
        if there is no full buffer
            full.wait();
        remove an item from buffer and store it to *x
        empty.signal();
    }
}

 Dining Philosophers + Monitor

Each Philosopher:
    {
        pickup(i);
        eat();
        putdown(i);
        think();
    } while (1);

monitor dining_philosopher {
    enum {thinking, hungry, eating} state[5]; // 공유데이터. 옆 사람이 내 상태 바꿀 수 있으니까
    condition self[5];
    
    void pickup (int i) {
        state[i] = hungry;
        test(i);
        if (state[i] != eating) // 여기가 semaphore와의 차이점 ! semaphore에서는 락을 걺
            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(); // i가 자고 있으면 깨워줌
    }
}

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