12. Process Synchronization 3

 

이화여자대학교 반효경 교수님의 운영체제 강의 13강을 듣고 정리한 내용이다.

 

✏️ Bounded-Buffer-Problem(Producer-Consumer-Problem)

 

• 공유 데이터 - buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)
• Producer(생산자) - 생산자 프로세스는 공유 버퍼에 데이터를 하나 만들어서 집어넣는 역할
  1. Empty 버퍼가 있는지 확인하고, 없으면 기다린다.
  2. 공유 데이터에 lock을 건다.
  3. Empty 버퍼에 데이터를 입력하고 버퍼를 조작한다.
  4. lock을 푼다.
  5. Full 버퍼가 하나 증가한다.
• Consumer(소비자)
  1. Full 버퍼가 있는지 확인하고, 없으면 기다린다,
  2. 공유 데이터에 lock을 건다.
  3. Full 버퍼에서 데이터를 꺼내고 버퍼를 조작한다.
  4. lock을 푼다.
  5. Empty 버퍼가 하나 증가한다.
• 발생 가능한 동기화 문제 - 공유 버퍼이기 때문에 생산자 여러 명이 동시에 한 버퍼에 데이터를 쓰거나 수정할 수 있으며, 마찬가지로 생산자가 동시에 한 버퍼의 데이터를 읽어갈 수 있음
• 동기화 변수
  • 상호 배제 - 이진 세마포어(공유 데이터의 상호배제를 위해)
  • 자원 개수 카운트 - 계수 세마포어(남은 Full/empty 버퍼의 수 표시)

• Mutex - lock을 걸고 푸는 용도로, 공유 버퍼에 단 하나의 프로세스가 접근할 수 있게 1
• Full - 데이터가 들어있는 버퍼를 나타내기 위한 용도로, 처음에는 비어있으니 0
• Empty - 데이터가 비어있는 버퍼를 나타내기 위한 용도
• Producer
  1. P 연산을 통해 empty 버퍼가 있는지 확인하고, 없으면 대기
  2. 빈 버퍼가 있다면 mutex를 0으로 만들고 공유 데이터에 lock을 걸은 다음 자원 획득
  3. 버퍼에 데이터를 입력함
  4. V 연산을 통해 mutex 값을 1로 만들고, lock을 풀어줌
  5. V 연산을 통해 full 버퍼를 1 증가하고 임계 구역에서 나옴
• Consumer
  1. P 연산을 통해 Full 버퍼가 있는지 확인하고, 없으면 대기
  2. Full 버퍼가 있다면 mutex를 0으로 만들고 임계 구역에 진입
  3. 버퍼에 데이터를 뺴감
  4. V 연산을 통해 mutex 값을 1로 만듦
  5. V 연산을 통해 empty 버퍼를 1 증가하고 임계 구역에서 나옴

---

✏️ Readers-Writers Problem

• 한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안됨
• read는 동시에 여럿이 해도 됨
• solution
  • writer가 db에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader들을 다 db에 접근하게 해준다
  • writer는 대기 중인 reader가 하나도 없을 때 db 접근이 허용된다
  • 일단 writer가 db에 접근 중이면 reader들은 접근이 금지된다
  • writer가 db에서 빠져나가야만 reader의 접근이 허용된다
• 공유 데이터 - DB 자체, 현재 DB에 접근 중인 reader의 수를 나타내는 readcount

int readcount = 0;
DB 자체;

• 동기화 변수

semaphore mutex = 1, db = 1;

• mutex - 공유 변수 readcount를 접근하는 코드의 상호 배제 보장을 위해 사용
• db - reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

• Writer - starvation 발생 가능

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

• Reader

P(mutex);
readcount++;
if(readcount==1){
	P(db);    /* block writer */
    V(mutex);    /* readers follow */
   
...
reading DB is performed
...

P(mutex);
readcount--;
if(readcount==0){
    V(db);    /* enable writer */
    V(mutex);

---

✏️ Dining-Philosophers Problem

• 동기화 변수

semaphore chopstick[5];    /* Initially all values are 1 */

• 철학자 $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;
semaphore mutex = 1;

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

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

void test(int i) {
    if(state[(i+4) % 5]!=eating && state[i]==hungry && state[(i+1) % 5]!=eating) {
        state[i] = eating;
        V(self[i]);
    }
}

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

---

✏️  Monitor

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

V(mutex);
/* critical section */
P(mutex);

• Deadlock

P(mutex);
/* critical section */
P(mutex);

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

monitor monitor-name {
    shared variable declarations
    procedure body P1(...) {
       ...
    }
    procedure body P2(...) {
       ...
    }
    procedure body Pn(...) {
       ...
    }
    {
       initialization code
    }
}

monitor

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

condition x, y;

• 조건 변수는 wait와 signal 연산에 의해서만 접근 가능 - x.wait()를 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend 된다

x.wait();

• x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

x.signal();

• 모니터에서는 lock을 걸거나 풀 필요가 없음