1. 동시성 제어의 고전적 문제들
1.1 Bounded-Buffer
- 생산자-소비자 문제에서, n개의 버퍼가 있고, 각 버퍼가 한 개의 아이템을 가질 수 있다.
- 생산자는 소비자를 위해 버퍼를 가득 채우고, 소비자는 버퍼를 전부 비운다.
- mutex라는 바이너리 세마포어는 버퍼 접근을 동시에 하는것을 막아준다.
- 두 개의 counting 세마포어는 비어있는 버퍼와 그렇지 않은 버퍼의 수를 센다.
1.2 Readers-Writers
-
여러 프로세스들이 동시에 실행되는데, 어떤 프로세서는 shared data를 read만 하고, 어떤 프로세스는 write만 하는 경우가 있다.(동시 실행되는 프로세스 간 공유되는 데이터베이스:예시) reader는 데이터 베이스를 읽기만 하고 싶을 수 있다. 일반적으로 reader들이 동시에 접근하더라도 부-효과를 발생시키지 않는다. 하지만 writer들이 동시에 데이터 베이스에 접근하는 경우. 반드시 혼란(chaos)가 발생한다.
-
이 문제의 변형이 있다.
(1) 우선순위와 관련된 문제다. 바로 first reader-writer 문제다. 이는 그 어떤 reader들은 다른 reader들이 끝날 때까지 대기할 필요 없다는 것이다.
(2) second readers-writers, writer가 객체 접근을 위해 대기하는 경우, 어떤 reader들도 읽기를 시작할 수 없다.
위의 두 경우 모두 starvation(기아) 문제가 발생할 수 있다.
1.2.1 solution to the first readers-writers
rw_mutex는 reader와 writer가 공유하며, mutex는 상호 배제를 보장하기 위해 사용되며, read_count는 얼마나 많은 프로세스가 객제를 읽고있는지 기록한다.
writer 하나가 임계영역을 진입하는 경우 n개의 reader가 대기한다. 한 개의 reader은 rw_mutex에서 대기하고, n-1 reader는 mutex에서 대기한다. 복수의 signal(rw_mutex)가 관찰되는 경우 스케줄러에 의해 선택이 이뤄진다.
- Reader-Writer Locks
위의 문제는 일반화가 이뤄졌으며, Reader-Writer Lock를 통해 문제를 해결한다.
1.3 Dining-Philosophers
한국어로, 철학자들의 저녁식사 문제, 라고 부른다. 다섯 철학자들이 먹고, 생각하기를 반복하며, 다섯개의 젓가락이 있다. 배고파지면 가장 가까운 두 개의 젓가락을 집어서 음식을 먹는다. 인접한 철학자 둘이 동시에 젓가락을 집는 경우, 경쟁 상태가 발생한다.
일반화 해서 말하자면, 복수의 프로세스에게 데드락과, 기아문제를 일으키지 않으며 복수의 자원을 할당하는 문제다.
세마포어를 통해 상호 배제를 달성할 수는 있다. 젓가락을 들고, 놓을때 wait(), signal()을 하는 것이다. 하지만 이 경우 데드락과 기아문제가 발생한다. 모든 철학자가 동시에 배가 고파지고, 각자가 왼쪽의 젓가락을 드는경우, 아무도 오른쪽의 젓가락을 잡을 수 없다.
가능한 해결방법은, 최대 4명의 철학자로 인원을 제한하거나, 양 쪽 젓가락을 잡을 수 있을 때만 젓가락을 드는 것이다. 또다른 방법은 asymmetric한 방법이다. 홀수 번째 철학자와 짝수 번째 철학자가 젓가락을 짚는 순서를 서로 반대로 가져가도록 설정하는 것이다.
하지만 이 문제들로 데드락은 해결할 수 있어도, 기아 문제는 해결할 수 없다.
여기서는 Monitor-solution을 살펴볼 것이다. 철학자들은 양쪽 젓가락을 들 수 있을 떄에만 젓가락을 들려고 할 수 있다. 따라서 철학자는 세 가지 상태를 가진다. (1) 생각중, (2) 배고픔, (3) 식사중. 철학자는 양쪽의 철학자가 식사를 하고 있지 않을 떄에만, 식사를 시작할 수 있다.
젓가락은 DiningPhilosopher를 통해 통제된다.(pickup(),putdown()) 이렇게 해서 데드락까지 해결할 수는 있으나, 기아 문제는 여전히 발생할 수 있다.
1.4 Thread Safe Concurrent Application
Concurrrent application은 멀티코어 시스템에서 굉장히 좋은 성능을 보여주나, 경쟁상태, liveness hazard의 가능성이 높아진다. 따라서 thread-safe concurrent application 설계를 위한 대안들이 있다.
(1) Transactional Memmory
(2) OpenMP
(3) Functional Programming Language
