고전 문제
생산자-소비자 문제 (Bounded Buffer)
- 크기 N의 버퍼를 공유한다.
- 생산자는 버퍼에 넣고(가득 차면 대기), 소비자는 버퍼에서 꺼낸다(비면 대기)
- 세마포 3개를 사용한다.
empty = N // 빈 칸 수 (카운팅)
full = 0 // 찬 칸 수 (카운팅)
mutex = 1 // 버퍼 보호 (이진)
생산자: wait(empty); wait(mutex); put(); signal(mutex); signal(full);
소비자: wait(full); wait(mutex); get(); signal(mutex); signal(empty);- 생산자가
signal(full)하면 소비자가 깨어난다 (A가 signal, B가 wait) - 버퍼 자체의 상호 배제를 위해 mutex도 사용한다.
- wait 순서 주의 :
wait(mutex)를wait(empty)보다 먼저 하면 데드락이 발생한다 (버퍼 락을 쥔 채 빈 칸을 기다림)
Reader-Writer 문제
- 읽기 전용 프로세스와 쓰기 프로세스에 모두 락을 걸면 성능 문제가 심각해짐
- 따라서 읽기는 동시에 해도 되고 쓰기는 독점하도록 하면 효율적임
- 읽기+읽기 O / 읽기+쓰기 X / 쓰기+쓰기 X
- 읽기 카운터를 뮤텍스로 보호하고, 쓰기 배타용 세마포 하나를 둬서 구현한다.
// 첫번째 reader가 들어올 때 write 락을 잠그고,
// 마지막 reader가 나갈 때 write 락을 풀어준다
// rc : 읽기 카운터
read: lock(rc_mutex); rc++; if (rc==1) wait(rw); unlock(rc_mutex);
... 읽기 ...
lock(rc_mutex); rc--; if (rc==0) signal(rw); unlock(rc_mutex);
write: wait(rw); ... 쓰기 ... signal(rw);- 읽기 작업 끼리는 동시에 실행할 수 있으므로 읽기들이 계속 이어서 실행되면 쓰기 연산이 낄 수가 없다.
- 그래서 쓰기 작업에 우선순위를 부여한다면 읽기가 낄수가 없다.
- 두 경우 모두 기아 현상이 발생한다.
- 해결 : 대기 큐로 순서 보장 → 양쪽 기아 방지
DB의 공유 락(S) / 배타 락(X) 의 모델이다
식사하는 철학자 문제
철학자들이 원탁에 앉아 있고, 젓가락은 각 철학자의 왼쪽에 하나씩 있다.
식사를 하려면 양쪽 젓가락이 필요하다.
이때 모두가 왼쪽을 먼저 집고 오른쪽을 기다리면, 각자 젓가락 하나씩 쥔 채 서로를 영원히 기다리게 된다.
→ 데드락(순환 대기) 발생
뒤에 나옴
실제 적용 사례
Java
| 개념 | Java |
|---|---|
| 모니터 (자동 상호배제 + 조건변수) | synchronized + wait() / notify() |
| 뮤텍스 (소유권·재진입) | ReentrantLock |
| 세마포 (카운팅/신호) | java.util.concurrent.Semaphore |
| Reader-Writer | ReentrantReadWriteLock, StampedLock |
| 원자적 명령 (CAS) | AtomicInteger 등 Atomic* |
| 가시성·순서 | volatile, happens-before |
데이터베이스
- 공유/배타 락 (S/X) : Reader-Writer 문제의 해법
- 비관적 락 (
SELECT ... FOR UPDATE) : 데이터를 먼저 잠그고 접근 (뮤텍스) - 낙관적 락 (
@Version) : 데이터를 잠그지 않고, 커밋 시 버전 비교로 충돌 탐지 후 롤백 (CAS / ABA 해법)
OS / 런타임
- futex (fast userspace mutex): 경합이 없으면 유저 공간에서 원자적 연산(CAS) 으로 처리하고, 경합이 있을 때만 커널로 진입해 블로킹한다. 하이브리드(스핀 + 블로킹)의 실제 구현이며, 리눅스 뮤텍스/세마포의 토대가 된다
pthread_mutex,pthread_cond등이 그 위에 세워진 POSIX 표준 도구
