2020-11-14 운영체제 기초 - 동기화문제

동기화의 문제

  • Bounded-Buffer-Problem
  • Readers and Writers Problem
  • Dining-Philosophers Problem

Bounded-Buffer-Problem

  • 버퍼는 Circular Buffer의 형태

  • Producer-Consumer 문제가 있다.

  • 이 구조에서 Producer 프로세스와 Consumer 프로세스가 있다. Producer는 공유버퍼에 데이터를 만들어서 넣는다.

  • Producer의 역할

    • Empty 버퍼가 있나 체크. 없으면 기다린다.
    • 공유데이터에 lock을 건다.
    • Empty Buffer에 데이터 입력 및 Buffer 조작
    • Lock을 푼다.
    • Full Buffer 하나 증가

  • Consumer의 역할

    • full 버퍼가 있는지 체크. 없으면 기다린다.
    • 공유데이터에 lock을 건다.
    • Full Buffer에서 데이터를 꺼내고 Buffer를 조작.
    • Lock을 푼다.
    • Empty Buffer 하나 증가

  • Shared data : Buffer 자체 및 Buffer 조작 변수(empty/full buffer의 시작 위치)

  • 세마포어변수 : semaphore full =0, empty = n, mutex = 1(lock을 걸기 위해)

    • // Producer
do {
  ...
  P(empty);
  V(mutex);
  ..
    add x to buffer
    ...
  V(mutex);
  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-Wirters Problem

  • 한 프로세스가 DB에 쓰기 중일때는 다른 프로세스가 접근하면 안된다.
  • 읽기는 동시에 여럿이 해도 된다.
  • 해결법
    • Writer가 데이터베이스에 접근 허가를 아직 얻지 못한 상태에서는 대기중인 모든 Reader들은 다 데이터베이스에 접근하게 해준다.
    • Writer는 대기중인 Reader가 하나도 없을 때 데이터베이스 접근이 허용된다.
    • 일단 Writer가 데이터베이스에 접근 중이면 Reader들은 접근이 금지된다.
    • Writer가 데이터베이스에서 빠져나가야만 Reader의 접근이 허용.
  • Shared Data
    • 데이터베이스 자체
    • readcount => 현재 데이터베이스에 접근 중인 Reader의 수.
  • 동기화 변수
    • mutex : 공유변수 readcount를 접근하는 코드(critical section)의 mutex exclusion 보장을 위해 사용
    • db : Reader, Writer가 공유 데이터베이스 자체를 올바르게 접근하게 하는 역할
// shared data
int readcount = 0;
// synchronization variables
semaphore mutex = 1, db = 1;

// Writer
P(db);
...
writing DB is performed
...
V(db);
// Reader

P(mutex);
readcount++;
if (readcount == 1) P(db); // block writer
V(mutex);
...
  reading db is performed
...
P(mutex);
readcount--;
if (readcount == 0) V(db); // enable writer
V(mutex); => starvation 발생가능.
  • writer가 오래 기다리면 starvation이 발생할 수 있다.

Dining-Philosophers Problem

  • 출처 : https://miro.medium.com/max/383/1*YABO-JVRfRKZNd-hAnJnjQ.png

  • 동기화 변수 : 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);
  • 위 코드는 데드락의 문제점이 존재, 모든 철학자가 동시에 배가 고파서 왼쪽 젓가락을 집어버린 경우
  • 해결 방안
    • 4명의 철학자만 테이블에 동시에 앉을 수 있게한다.
    • 젓가락을 2개 모두 집을 수 있을때만 젓가락을 집을 수 있게한다.
    • 비대칭
      • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집는다.

Monitor

  • 세마포어의 문제점

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

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

    • monitor monitor-name {
  // shared variable declartion
  procedure body P1(....) {
    ...
  }
   procedure body P2(....) {
    ...
  }
   procedure body P3(....) {
    ...
  }

  {
    initialization code
  }
}

  • 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능

  • 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다.

  • 프로세스가 모니터안에서 기다릴 수 있도록 하기 위해 condition variable 사용 => condition x, y;

  • condition variable은 wait, signal 연산에 의해서만 접근 가능. => x.wait()

  • x.wait()를 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke 하기전까지 suspend된다.

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

  • Bounded-Buffer problem 모니터 코드

    • {
  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 to *x
      empty.signal();
  }
}
Written on November 14, 2020