[운영체제] Synchonization의 문제점

Deadlock과 Starvation

• Deadlock
  둘 이상의 프로세스가 상대방에 의해 충족시킬 수 있는 event를 무한히 기다리는 현상입니다.
  • 예를 들어, Semaphore S와 Q를 동시에 사용해야하는 프로세스가 두 개가 Pi와 Pj가 있을 때. Pi는 S를 먼저 차지하고, Pj는 Q를 먼저 차지한 상황에서 무한히 누군가가 S/Q를 사용하고 반납하기를 기다릴 수 있습니다.
• Starvation
  프로세스가 suspend된 이후에 이를 빠져나가지 못하는 현상입니다.

Bounded-Buffer Problem (Producer-Consumer Problem)

위의 그림처럼, 자원을 생상하는 주체와 소비하는 주체가 나눠져있을 경우, 동시성 문제가 발생할 수 있습니다. 이 문제를 해결하기위해서 세 개의 Semaphore를 활용합니다.

• full : 사용가능한 자원의 개수. 초기값 0.
• empty : 비어있는 자원의 개수. 초기값 n.
• mutex : lock변수(1이면 critical section에 들어갈 수 있음. 0이면 반대)Producer
• do { P(empty); P(mutex); 버퍼에 삽입 V(mutex); V(full); } while (1);

Consumer

do {
  P(full);
  P(mutex);
  버퍼에서 삭제
  V(mutex);
  V(empty);
} while (1);

Readers-Writers Problem

DB에 쓸 때는 DB에 영향을 주지만, DB를 읽을 때는 DB에 영향을 주지않습니다. 따라서, Writer는 Reader가 없을 때만 쓸 수 있도록 하고, Reader는 항상 읽을 수 있되 Writer가 쓰지 않을 때만 읽지 못하도록 구현해야합니다. 이 문제도 semaphore를 활용할 수 있습니다.

공유 데이터와 Synchronization 변수

• 공유 데이터
  • DB
  • int readerCount = 0;
• Synchronization 변수
  • db : db에 접근 가능한지 여부.
  • mutex : readCount에 접근 가능한지 여부

Writer

P(db); /* db가 1이면 접근하고 아니면, sleep; */
DB에 쓰기
V(db);

Reader

P(mutex)
readerCount++;
if (readerCount == 1) P(db); /* 첫 리더이면, db를 0으로 바꾸어 Writer가 접근하지 못하도록 한다.*/
V(mutext)

DB 읽기

P(mutex)
readerCount--;
if (readerCount == 0) V(db); /* 마지막 리더이면, db를 1로 바꾸어 읽을 수 있도록 한다.*/
V(mutex)

문제점

위의 방법은 Writer가 startvation을 겪을 수 있습니다. 리더가 끊임없이 들어오면, 라이터는 영원히 DB에 접근할 수 없습니다. 이 문제를 해결하기 위해서 신호등처럼 일정 시간마다 Reader의 접근을 막고 Writer가 기다리지 않고 사용할 수 있도록 할 수 있습니다.

Dining-Philosophers Problem

철학자들이 위와 같은 식탁에 둘러 앉아, 생각과 먹는 행위를 반복합니다. 하지만, 먹기위해서는 양쪽에 놓인 두 젓가락을 모두 가지고 있어야만하는 조건이 있습니다.

위의 상황에서는 DeadLock의 가능성이 있습니다. 만약 모든 철학자들이 동시에 배가 고파서 왼쪽에 있는 젓가락을 집게 된다면, 모두 영원히 기다려야합니다.

이 문제는 세 가지 방법으로 해결할 수 있습니다.

1) 짝수만 한 테이블에 앉게 한다.
2) 젓가락을 모두 집을 수 있을 때에만 젓가락을 집게 한다.
3) 짝수번째 철학자는 왼쪽 젓가락부터, 홀수번째 철학자는 오른쪽 젓가락부터 집게한다.

Monitor

Semaphore의 문제점

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

Monitor

위와 같은 문제점을 해결하기 위해서, Monitor이 등장합니다. 이는 높은 수준의 synchronization 구조체로서, 동시에 수행되는 프로세스 사이의 안전한 공유를 보장합니다. 모니터 안에서는 애초에 모니터에 대한 프로세스의 동시접속을 허용하지 않습니다. 동시에 들어가고자한다면, 줄을 서야합니다. 따라서 따로 lock을 걸 필요가 없어 편리합니다.

condition variable을 사용합니다. 이는 wait와 signal 연산에 의해서만 접근이 가능합니다.

• wait
  • conditaion var.wait()를 invoke한 프로세는 다른 프로세스가 x.signal()을 invoke할 때까지 suspend됩니다.
• signal
  • x.signal은 정확하게 하나의 suspend된 프로세스를 resume합니다. syspend된 프로세스가 없으면 아무일도 일어나지 않습니다.