1. Bounded-Buffer Problem (Producer-Consumer)
1.1 구조
- Producer: 데이터를 생산하여 Buffer에 저장
- Consumer: Buffer에서 데이터를 꺼내 소비
- 공유 변수: Buffer (Shared memory)
1.2 필요한 Semaphore
| Semaphore | 유형 | 초기값 | 역할 |
|---|---|---|---|
mutex | Binary | 1 | Buffer 접근의 Mutual exclusion |
empty | Integer (Counting) | n | 빈 Buffer 수 |
full | Integer (Counting) | 0 | 채워진 Buffer 수 |
1.3 코드
semaphore full = 0, empty = n, mutex = 1;
// Producer
do {
/* produce an item in nextp */
P(empty); // 빈 버퍼가 있을 때까지 대기
P(mutex); // 버퍼 접근 잠금
/* add nextp to buffer */
V(mutex); // 버퍼 접근 해제
V(full); // 채워진 버퍼 수 증가
} while (1);
// Consumer
do {
P(full); // 채워진 버퍼가 있을 때까지 대기
P(mutex); // 버퍼 접근 잠금
/* remove an item from buffer to nextc */
V(mutex); // 버퍼 접근 해제
V(empty); // 빈 버퍼 수 증가
/* consume the item in nextc */
} while (1);핵심 포인트:
P(empty)/P(full)은 자원 개수를 확인 (Integer semaphore)P(mutex)/V(mutex)은 Buffer라는 공유 데이터의 상호 배제 보장 (Binary semaphore)- 순서 중요:
P(empty)→P(mutex)순서를 바꾸면 Deadlock 발생 가능
2. Readers-Writers Problem
2.1 문제 정의
- Writer: DB에 쓸 때 배타적 접근(Exclusive access) 필요
- Reader: 여러 Reader가 동시에(Concurrently) DB를 읽을 수 있음
우선순위 선택:
- 방법 A: Reader 우선 - 한 Reader가 읽기 시작하면 다른 Reader도 모두 진입 허용. 마지막 Reader가 끝나면 Writer 시작
- 방법 B: Writer 우선 - Writer가 대기 중이면 새 Reader는 진입 불가
2.2 Reader 우선 해법 (방법 A)
semaphore mutex = 1, db = 1;
int readcount = 0;
// Writer
P(db); // DB 배타적 접근
/* writing is performed */
V(db);
// Reader
P(mutex); // readcount 접근 잠금
readcount++;
if (readcount == 1) P(db); // 첫 번째 Reader가 Writer를 차단
V(mutex);
/* reading is performed */
P(mutex);
readcount--;
if (readcount == 0) V(db); // 마지막 Reader가 Writer 허용
V(mutex);핵심 포인트:
readcount도 공유 변수이므로mutex로 보호- 첫 번째 Reader가
P(db)를 호출하여 Writer를 차단 - 마지막 Reader가
V(db)를 호출하여 Writer를 허용
3. Dining-Philosophers Problem
3.1 문제 정의
5명의 철학자가 원형 테이블에 앉아 생각하기(Think)와 먹기(Eat)를 반복한다. 각 철학자 사이에 Chopstick이 하나씩 있고, 먹으려면 양쪽 Chopstick 두 개가 모두 필요하다.
3.2 단순 Semaphore 해법 (Deadlock 위험!)
semaphore chopstick[5]; // 모두 1로 초기화
// Philosopher i
do {
P(chopstick[i]); // 왼쪽 젓가락 집기
P(chopstick[(i+1) % 5]); // 오른쪽 젓가락 집기
/* eat */
V(chopstick[i]); // 왼쪽 젓가락 내려놓기
V(chopstick[(i+1) % 5]); // 오른쪽 젓가락 내려놓기
/* think */
} while (1);문제: 5명 모두 동시에 왼쪽 젓가락을 집으면 - Deadlock (모두 오른쪽을 기다리며 영원히 대기)
3.3 Deadlock 방지 전략
| 전략 | 설명 |
|---|---|
| 양쪽 동시 집기 | 두 젓가락을 Critical section 안에서 한꺼번에 집음 |
| 비대칭 코딩 | 홀수 철학자는 왼쪽 먼저, 짝수 철학자는 오른쪽 먼저 |
| 인원 제한 | 최대 4명만 동시에 앉을 수 있도록 제한 |
4. Deadlock과 Starvation
4.1 Deadlock
두 개 이상의 프로세스가 서로가 유발해야 할 이벤트를 무한히 기다리는 상태
Semaphore S = 1, Q = 1;
P0: P1:
P(S); P(Q); <- 각자 하나씩 보유(hold)
P(Q); P(S); <- 서로의 것을 대기(wait)
... ...
V(S); V(Q); <- 여기까지 도달 못함
V(Q); V(S);
4.2 Starvation
프로세스가 Semaphore의 대기 큐에서 무한히 제거되지 않는 상태. 예: LIFO 큐를 사용하는 Semaphore에서 새 프로세스가 계속 들어오면 맨 아래 프로세스는 영원히 실행 못 함.
5. Semaphore의 문제점
- 코딩이 어렵다
- 정확성 증명이 어렵다
- 오류가 재현되지 않는 경우가 많다 (Timing-dependent)
- 자발적 협력(Voluntary cooperation)에 의존
- 단 하나의 잘못된 사용이 전체 시스템에 영향
6. Monitor
6.1 개념
Monitor는 Abstract data type과 유사한 고수준 동기화 구조로, 공유 데이터의 안전한 접근을 보장한다.
monitor monitor-name {
shared variable declarations // Private data
procedure P1(...) { ... } // Public methods
procedure P2(...) { ... }
{ initialization code }
}
핵심 특성: Monitor 내부에서는 한 번에 하나의 프로세스만 활성화될 수 있다 - Race condition을 원천적으로 방지
6.2 Condition Variable
Monitor 내에서 프로세스가 대기할 수 있도록 하는 변수:
condition x, y;x.wait(): 이 연산을 호출한 프로세스는 다른 프로세스가x.signal()을 호출할 때까지 일시 중단(Suspend)x.signal(): 중단된 프로세스 중 정확히 하나를 재개. 중단된 프로세스가 없으면 아무 효과 없음
6.3 Monitor로 Dining-Philosophers 해결
monitor dining_philosopher {
enum {thinking, eating, hungry} state[5];
condition self[5];
void pickup(int i) {
state[i] = hungry;
test(i);
if (state[i] != eating)
self[i].wait(); // 먹을 수 없으면 대기
}
void putdown(int i) {
state[i] = thinking;
test((i+4) % 5); // 왼쪽 이웃 확인
test((i+1) % 5); // 오른쪽 이웃 확인
}
void test(int i) {
if (state[(i+4) % 5] != eating && // 왼쪽이 안 먹고 있고
state[i] == hungry && // 내가 배고프고
state[(i+1) % 5] != eating) { // 오른쪽도 안 먹고 있으면
state[i] = eating;
self[i].signal(); // 대기 중인 나를 깨움
}
}
void init() {
for (int i = 0; i < 5; i++)
state[i] = thinking;
}
}
// Each Philosopher i:
do {
pickup(i);
eat();
putdown(i);
think();
} while (1);이 해법의 장점:
- Monitor가 Mutual exclusion을 자동 보장
test()에서 양쪽 이웃이 모두 먹지 않을 때만 먹을 수 있으므로 Deadlock 방지putdown()시 이웃을 깨워주므로 Starvation 가능성 감소
6.4 Conditional-wait
x.wait(c); // c는 우선순위 번호x.signal()호출 시, 가장 작은 Priority 번호를 가진 프로세스가 먼저 재개- 시스템 정확성을 위해:
- 사용자가 항상 올바른 순서로 Monitor를 호출해야 한다
- 비협조적 프로세스가 Monitor를 우회하여 공유 자원에 직접 접근하지 않도록 해야 한다