동기화 tools들을 고전적인 동기화 문제에 적용시켜보자. 이 부분은 아주 아주 간단하게 개념만 정리했다.

고전적인 동기화 문제들

Bounded-Buffer Problem

• productor-consumer model

• n개의 buffer로 구성된 pool이 존재하고, 각 buffer는 하나의 item을 저장한다

• shared data structure

int n;
semaphore mutex = 1; // -> binary semaphore
semaphore empty = n;
semaphore full = 0;

mutex : binary semaphore, process가 동시에 접근하는 것을 방지
empty, full : counting semaphores. empty / full buffer의 개수

producer
wait(empty) : 빈 buffer가 생길때까지 기다린다
wait(mutex) : 다른 process들이 critical section에 없을때까지 기다린다.
--write--
signal(mutex) : mutex 반납. critical section에서 exit했음을 알린다.
signal(full) : full buffer가 하나 추가됨

consumer
wait(full) : full buffer가 생길때까지 기다린다
wait(mutex) : 다른 process들이 critical section에 없을때까지 기다린다.
--write--
signal(mutex) : mutex 반납. critical section에서 exit했음을 알린다.
signal(empty) : consumer들에게 가져가라고 알려주기

Readers-Writers Problem

여러개의 프로세스들이 concurrently 하게 돌면서 shared data에 접근하는 것은 마찬가지인데,
어떤 프로세스들은 내용을 읽기만 하고 싶어하고(reader), 어떤 프로세스들은 갱신(writer)하고 싶어하는 경우를 생각해보자.

다수의 reader가 db에 접근하는 것은 상관이 없는데, writer들은 mutual exclusion을 보장받아야 할 것이다

변형들

1. No reader should wait for other readers to finish, simply because a writer is waiting
단순히 writer가 기다리고 있기 때문에 reader도 다른 reader들이 끝날때까지 기다리면 안된다

-> writer가 starvation 문제에 빠질 수 있다.

2. If a writer is waiting to access the object, no new readers may start reading

-> reader가 starvation 문제에 빠질 수 있다.

---

첫번째 변형에 대한 해결방법만 생각해보자.

semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

read_count : reader의 개수
rw_mutex : reader와 writer가 공유해서 사용
mutex : read_count를 갱신할 때 상호 배제를 보장

식사하는 철학자들 문제

다섯명의 철학자는 thinking 또는 eating 두가지 상태에 있을 수 있다.
젓가락은 철학자들의 사이에 하나씩만 존재한다. 젓가락 두개가 있어야 eating 이 가능하다.

-> 젓가락에 대한 race condition이 발생한다.
젓가락을 잡는 행위에 mutual exclusion을 처리하면 좋겠다. 여러개의 자원(젓가락)에 대한 여러개의 프로세스(철학자) 문제.

아직도 해결이 잘 안됨

semaphore solution

각 젓가락에 semaphore. 항상 philosopher가 젓가락을 잡기 전에 wait, 다 먹고나서 signal

-> mutual exclusion은 해결되었으나 deadlock과 starvation이 쉽게 발생할 수 있다. 모든 사람이 자신의 왼쪽 젓가락을 잡으면 다 굶어죽는다.

해결하는 쉬운 방법은
1. 철학자 네명만 동시에 테이블에 앉도록
2. 양 젓가락이 available할 때만 젓가락을 잡도록
3. 홀수 번호 철학자는 왼쪽 젓가락을 먼저 잡고, 오른쪽 젓가락을 잡고, 짝수 번호 철학자는 오른쪽 젓가락을 먼저 잡고, 왼쪽 젓가락을 잡는다.

deadlock free는 가능하지만 starvation은 해결하지 못하더라...

monitor solution

양쪽 젓가락이 모두 availabe할 때만 젓가락을 집도록 제한한다.

critical section problem을 해결하기 위한 대안

트랜잭션 메모리

메모리 트랜젝션 : 메모리 읽기와 쓰기 연산의 원자적인 연속적 순서

예를 들어, 공유 데이터를 수정하는 update() 함수를 구현한다고 할 때,
락이나 세마포어와 같은 동기화 기법은 교착 상태와 같은 잠재적인 문제들을 야기할 수 있고, 스레드 개수가 증가할수록 락을 소유하기 위한 스레드의 경쟁 수준이 높아진다.

-> 트랜잭션 메모리 시스템은 원자성을 보장하므로 이를 이용해서 문제를 해결

OpenMp

critical section 으로 지정하는 명령어가 존재, 한 번에 하나의 스레드만 실행하도록 보장해준다.

함수형 프로그래밍 언어

함수형 언어에서는 애초에 상태를 유지하지 않는다. 그렇기에 race condition이나 교착 상태같은 쟁점을 신경쓸 필요가 없다.