동기화 문제의 사례들

이번 시간에는

Concurrency-Control의 고전적인 문제들에 대해서 알아보겠다.

1. The Bounded-Buffer Problem (The Producer-Consumer Problem)
2. The Readers-Writers Problem
3. The Dining-Philosophers Problem

---

The Bounded-Buffer Problem

데이터 n개를 담을 수 있는 버퍼를 Producer가 채우고, Counsumer가 비우는 상황

상호 배제를 위한 mutex, 빈 상태와 가득 찬 상태를 위한 counting semaphore를 쓴다.

int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

The structure of the producer process

The structure of the consumer process

 

empty 세마포어와 full 세마포어를 교차해서 활용함으로써 Produer-Consumer 문제를 해결한다.

empty를 n으로 초기화함으로써 0이 될때까지 n개의 Producer 스레드가 동시 접근 가능하지만,

mutex는 Producer이든 Consumer이든 1개만 들어갈 수 있게 막는다.

full을 0으로 초기화하는 이유는 Producer가 먼저 insert할 수 있도록 하기 위함이다.

최대 n개의 Producer가 insert할 수 있고 full은 최대 n까지 찰 수 있다.

 

왜 세마포어가 복잡하고 실수가 발생하는지 알겠다..

모니터를 활용한 Java 코드 github 링크

---

The Readers-Writers Problem

단순히 Producer, Consumer가 아니라 Reader, Writer라면 어떨까?

Reader끼리는 동시 접근하더라도 race condition이 발생하지 않기 때문에 이야기가 조금 다르다.

따라서 Reader와 Writer를 똑같이 취급할 필요가 없다.

 

방법 1: Reader와 Writer에게 access 권한을 동등하게 부여

만약  Reader가 100개 Writer가 1개면 Writer가 Starvation되어 write를 못할 수 있다..

semaphore rw_mutex = 1; //reader와 writer의 'contents'에 대한 동시 접근 제어
semaphore mutex = 1; //reader들이 'read_count'를 update할 때의 동시 접근을 제어
int read_count = 0; //동시에 reading하고 있는 reader 스레드의 수 표시

The structure of a writer process

The structure of a reader process

처음 read하려는 스레드가 rw_mutex 락을 얻기까지 기다리는 동안, 나머지 reader들은 mutex 락을 얻기를 기다린다.

 

방법 2: Writer에게 더 높은 우선순위 부여

Writer가 더 중요한 경우가 많기 때문에 이게 낫다. 하지만 Reader가 starvation되면 반응성이 떨어질 수 있다.

 

둘 다 starvation 문제가 발생할 수 있다.. 더 좋은 방법이 없을까?

 

더 좋은 방법: Reader-Writer Locks

writer들에 대한 exclusive access를 보장해주는 Reader-Writer lock을 제공한다. (API로 제공해주기도 한다)

read 모드냐 wirte 모드냐에 따라 구분해야 한다.

read mode에서는 여러 reader 스레드가 진입 가능하고, write 모드에서는 하나의 스레드만 진입 가능하다.

 

read를 위한 락 획득, write를 위한 락 획득을 따로 만든다.

writing 중이 아니면 reader끼리는 대기하지 않고 동시에 read 가능하다

writing 중이 아니고 현재 읽고 있는 reader가 없을 경우에만 쓰기가 가능하다

Java 코드 링크

 

---

The Dining-Philosophers Problem

5명의 철학자가 원탁에 둘러앉아 식사를 하는데, 젓가락은 낱개로 5개 뿐이다. 그들은 모두 굶어 죽었다. 왜 일까?

양쪽에 있는 젓가락을 동시에 집으려 해서다.

 

[간단한 솔루션]

각각의 젓가락을 세마포어로 표현해보자.

semaphore chopstick[5];

The structure of philosopher i.

wait()를 이용해 젓가락을 획득하고, signal()을 이용해 내려 놓는다.

mutual exclusion은 지켰지만, deadlock과 starvation이 발생한다.

5명의 철학자가 동시에 왼쪽 젓가락을 집은 후 오른쪽을 집으려한다면 데드락이 발생한다.

 

데드락을 해결할 수 있는 방법

1. 가능하다면, 최대 4명의 철학자만 한 테이블에 배치한다.
2. 양쪽 젓가락을 이용할 수 있을 때만 젓가락을 들게 한다.
   모니터로 구현해보자.
   젓가락의 분배는 모니터에 의해 통제된다.
   ※ condition variable에 접근하는 것끼리는 동기화된다
   

   

   putdown()에서 호출하는 test(왼쪽), test(오른쪽)으로 wait()가 풀리게 된다

   

   양쪽이 available하다면 자원을 획득한다

3. 홀수번째 철학자는 왼쪽부터 들고, 짝수번째 철학자는 오른쪽부터 들게 한다. 사이의 하나는 뮤텍스로 해결.

하지만 위 방법들은 starvation을 막지는 못한다.

 

Java 버전 코드 링크

---

 

뮤텍스 락, 세마포어, 모니터 등을 사용하는 Concurrent한 애플리케이션은 멀티코어 환경에서 성능이 매우 좋지만, 

race condition이나 deadlock 같은 문제도 따른다.

이러한 문제의 근본적 해결은 어려우나, 아래과 같은 thread-safe한 대안책이 있다.

1. Transactional Memory
   transactional memory를 통해 메모리 읽기와 쓰기 연산을 원자적 연산(atomic operation)으로 만들 수 있다
2. OpenMP
   OpenMP에서 #pragma omp critical 컴파일러 디렉티브로 임계 구역을 지정해 줄 수 있다.
3. Functional Programming Language
   함수형 프로그래밍 언어들은 명령형 프로그래밍 언어와 달리 상태를 유지하지 않으므로 경쟁조건이 나 교착상태가 아예 발생하지 않는다

 

---

 

참고 자료 & 이미지 출처
운영체제 공룡책 강의 (주니온 님)
Operating System Concepts, 10th Ed (Silberschatz et al)
쉽게 배우는 운영체제 (조성호 님)