[OS] Synchronization Problems & Monitor

애이용·2021년 6월 7일
0

OS

목록 보기
5/16
post-thumbnail

Classical Problems of Synchronization

여러 개의 프로세스를 어떻게 동기화할 것인지에 대한 고전적 문제

1️⃣ Bounded-Buffer Problem (Producer-Consumer Problem)

Producer(생산자) : 자원(데이터)을 버퍼에 넣는다.
Consumer(소비자) : 버퍼에 남아있는 자원이 있다면, 해당 자원을 버퍼에서 꺼내 가져온다.

Producer 과정

1. Empty 버퍼가 있는지 확인한다. 
   Empty 버퍼가 없으면(모두 full 상태) 기다린다.
2. 공유 데이터에 lock을 건다.
3. Empty buffer에 데이터 입력 및 buffer를 조작한다.
4. Lock을 푼다.
5. Full buffer가 하나 증가한다.

Consumer 과정

1. Full 버퍼가 있는지 확인한다.
   Full 버퍼가 없으면(모두 empty 상태) 기다린다.
2. 공유 데이터에 lock을 건다.
3. Full buffer에서 데이터를 꺼내고 buffer를 조작한다.
4. Lock을 푼다.
5. Empty buffer가 하나 증가한다.

발생하는 문제

  • 복수의 생산자가 동시에 접근
  • 복수의 소비자가 동시에 접근
  • 버퍼가 full인 상태에서 생산자의 접근
  • 버퍼가 empty인 상태에서 소비자의 접근

✔️ Shared data

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

✔️ Synchronization variables

  • mutual exclusion(mutex) -> binary semaphore 필요 (shared data의 mutual exclusion을 위해(한 번에 1개의 process만 접근))
  • resource count -> integer semaphore 필요(남은 full/empty buffer의 수 표시(가용 자원에 대한 문제))

✔️ 코드로 살펴보자

// Synchronization variables
semaphore full = 0, empty = n, mutex = 1;
// full, empty : integer semaphore(resource count)
// mutex : binary semaphore(for mutual exclusion)

// Producer
do { ...
    producer an item in x
    ...
    P(empty); // empty 버퍼를 확인 후 기다리거나 획득
    P(mutex); // semaphore를 건다. (버퍼 획득 시 lock을 건다.)
    ...
    add x to buffer
    ...
    V(mutex); // 버퍼 반납 후 lock을 푼다.
    V(full); // 데이터 넣은 버퍼 개수(full)를 증가시킨다.
} while(1); // empty 버퍼가 없어질 때까지 반복한다.

// Consumer
do {
    P(full); // full 버퍼 있는지 확인(1을 빼본다.)
    P(mutex); // semaphore를 건다. (버퍼 획득 시 lock을 건다.)
    ...
    remove an item from buffer to y
    ...
    V(mutex); // 버퍼 반납 후 lock을 푼다.
    V(empty); // empty 버퍼 개수 증가
    ...
    consume the item in y
    ...
} while(1);

관련 정리

유한한 개수의 물건(데이터)을 임시로 보관하는 보관함(버퍼)에 여러 명의 생산자들과 소비자들이 접근한다. 생산자는 물건이 하나 만들어지면 그 공간에 저장한다. 이때 저장할 공간이 없는 문제가 발생할 수 있다. 소비자는 물건이 필요할 때 보관함에서 물건을 하나 가져온다. 이 때는 소비할 물건이 없는 문제가 발생할 수 있다.

생산자-소비자 문제는 생산자가 데이터를 생상하면 소비자는 그것을 소비하는 형태에서 발생하는 문제를 말한다. 컴퓨터 세계에서 예를 들면 웹 서버와 웹 클라이언트로 들 수 있다. 웹 서버가 데이터를 생산하여 웹에 관련되어 보여주는 작업들을 수행하고 웹 클라이언트는 웹 주소로 접속해 화면을 통해 보게 되는 형태의 소비 작용을 한다.

일반적으로 생산하는 속도와 소비하는 속도에 차이가 존재한다. 실제로 생산되는 속도가 소비하는 속도보다 빠른 경우가 많아서 생산된 데이터는 바로 소비되지 못한다. 이를 보안하기 위해 생산된 데이터를 보관하는 버퍼라는 공간이 존재한다. 생산자가 데이터를 생산하면 버퍼에 보관을 하게 되고 소비자는 버퍼에서 데이터를 빼내어 사용한다. 하지만 현실 시스템에는 버퍼의 크기가 유한하다. 크기가 정해져 있는 버퍼이기 때문에 Bounded Buffer라고 불린다. 생산자는 버퍼가 가득 차면 더 이상 넣을 수가 없다. 반대로 소비자는 버퍼가 비면 뺄 수가 없다.

2️⃣ Readers-Writers Problem

  • 하나의 프로세스가 DB에 write 중일 때, 다른 프로세스가 접근하면 안 된다.
  • 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 exclusion 보장을 위해 사용된다.
  • db : Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 하는 역할

✔️ 코드로 살펴보자

// Shared data
int readcount = 0;
DB 자체;

// Synchroniation variables
semaphore mutex = 1, db = 1;

// Writer : 단순
P(db); // Starvation 발생 가능(Reader가 계속 들어와있는 경우, Writer 순서가 오지 않음)
...
writing DB is performed
...
V(db);

// Reader 
P(mutex); // readcount도 mutex가 보장되어야 하므로 readcount lock 시킨다.
readcount++;
if (readcount == 1) P(db); // block writer : 최초의 reader 접근 시에만 writer lock 시킨다.
V(mutex); // readers follow
...
reading DB is performed // DB 읽기
...
P(mutex);
readcount--;
if (readcount == 0) V(db); // enable writer (writer lock을 푼다.)
V(mutex);

이는 Starvation 발생이 가능하다.
-> Reader가 계속 들어와있는 경우, Writer 순서가 오지 않는다.

3️⃣ Dining-Philosophers Problem

동시성과 교착 상태를 설명하는 예시로, 여러 프로세스가 동시에 돌아갈 때 교착 상태가 나타나는 원인을 직관적으로 알 수 있다.

철학자 5명이 원형 테이블에서 식사를 하려고 하려고 한다.
테이블 중앙에 음식이 있고 5개의 젓가락이 철학자 사이에 놓여져 있다.
철학자가 배고파져서 밥을 먹고자 할 때 왼쪽, 오른쪽 두 젓가락을 다 잡아야 식사를 할 수 있다.
그 후 식사가 끝나면 젓가락 두 개를 테이블에 놓고 다시 생각에 빠지는 구조이다.

여기서 DeadLock과 Starvation이 생기지 않도록 해결해야 한다.
첫번째 해결책을 먼저 보자.

// 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) 을 야기할 수 있는 문제점이 있다.
-> 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우, 서로 기다린다.

해결방안

1. 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
모두 동시에 왼쪽 젓가락을 들더라도, 한 개의 여유 젓가락이 생기게 되어 한 명의 최악의 경우에도 한 명의 철학자가 식사를 시작하고 마칠 수 있게 된다.
2. 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다. (한 번에 집기)
현재 문제가 일단 왼쪽 젓가락은 무조건 집고, 오른쪽을 확인하기 때문에 교착 상태가 발생한다. 두 개가 모두 사용 가능할 때만 젓가락을 집게 하면 교착 상태가 일어나지 않는다.
3. 비대칭 : 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다.
모든 철학자가 자신의 양 옆에 있는 철학자들과 젓가락을 집는 방향이 달라져서 서로가 한 쪽을 바라보며 서로를 기다려야하는 상황이 발생하지 않는다.

✔️ 2번 해결방안 코드

enum {thinking, hungry, eating} state[5];
semaphore self[5] = 0;
semaphore mutex = 1;

// Philosopher i
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 test(int i) {
   if (state[(i + 4) % 5] != eating && state[i] == hungry && state[(i + 1) % 5] != eating) {
 	state[i] = eating;
        V(self[i]);
   }
}

// 한 번에 한 철학자만 내린다.
void putdown(int i) {
    P(mutex);
    state[i] = thinking;
    test((i + 4) % 5); // 왼쪽 사람에게 알린다.
    test((i + 1) % 5); // 오른쪽 사람에게 알린다.
    V(mutex);
}

Semaphore의 문제점

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

예시

// 원래는 P -> V
V(mutex)
Critical Section
P(mutext)

👉 Mutual exclusion이 깨진다.

P(mutex)
Critical Section
P(mutex)

👉 Deadlock

Monitor

동시 수행 중인 프로세스 사이의 abstract data type(ADT)의 안전한 공유를 보장하기 위한 high-level synchronization construct이다.
모니터는 프로그래머가 정의한 함수에 mutual exclusion을 제공한다.
또한 모니터 안에서 항상 하나의 프로세스만 running 할 수 있다.

  • 모니터 내에서는 한 번에 하나의 프로세스만이 활동 가능하다.
  • 프로그래머가 동기화 제약 조건(세마포어)를 명시적으로 코딩할 필요가 없다. (객체 자체가 보장)
  • 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 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인 프로세스가 없으면 아무 일도 일어나지 않는다.

✔️ Monitor를 이용한 Bounded-Buffer Problem 해결 코드

// 전체가 세마포어로 묶여져 있다.
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 an empty buffer
      full.signal(); 
   }
   void consume(int x)
   {
   	if there is no full buffer	
     	  full.wait(); 
        remove an item from buffer and store it top x
        empty.signal(); 
    }
}

✔️ Monitor를 이용한 Dining Philosophers Problem 해결 코드

세마포어 모두 사라진 것을 볼 수 있다.

Each Philosopher;
do {
   pickup(i); // Enter monitor
   eat();
   putdown(i); // Enter monitor
   think();
} while(1);

monitor dining_philosopher
{
  enum {thinking, hungry, eating} state[5];
  semaphore self[5] = 0;
  semaphore mutex = 1;

  // 젓가락 집기
  void pickup(int i) {
      state[i] = hungry;
      test(i);
      if (state[i] != eating)
      	self[i].wait(); // wait here
  }

  void test(int i) {
     if (state[(i + 4) % 5] != eating && state[i] == hungry && state[(i + 1) % 5] != eating) {
      state[i] = eating;
          self[i].signal(); // wake up P[i]
     }
  }

  // 한 번에 한 철학자만 내린다.
  void putdown(int i) {
      state[i] = thinking;
      // test left and right neighbors
      test((i + 4) % 5); // 왼쪽 사람에게 알린다.
      test((i + 1) % 5); // 오른쪽 사람에게 알린다.
  }
  
  void init() {
  	for (int i = 0; i < 5; i++) {
    	state[i] = thinking;
    }
  }
}

참고 링크 1
참고 링크 2
참고 링크 3

profile
애이용
로그를 남기자 〰️
이전 포스트

[OS] Process

다음 포스트

[OS] Deadlock

0개의 댓글