[운영체제 #09] Synchronization Examples

앞장에서 배운 Synchronization Tools로 어떤 문제들을 해결할 수 있는지 알아본다.

Bounded-Buffer Problem

제한된 버퍼에 데이터를 채우고 가져가는 문제, 생산자-소비자 문제와 동일

사이즈 n의 버퍼, 3개의 Semaphore 사용한다.

• mutex : 초기값 1, binary
• full : 데이터가 있는 부분의 양, 초기값 0, 0~n
• empty : 데이터가 없는 부분의 양, 초기값 n, 0~n

Bounded-Buffer Problem

 

생산자는 비어있는 상태를 보고 데이터를 추가해야하므로, empty를 고려한다.

• wait(empty) : 데이터 하나를 추가할 것이므로 empty를 1 감소
• wait(mutex) : mutex가 1이면 mutex를 1 감소시키고 critical section으로 접근
• critical section(add item to buffer) : 버퍼에 해당 아이템을 추가
• signal(mutex) : critical section을 나왔으므로 mutex를 다시 1 증가
• signal(full) : 데이터 하나가 증가했으므로 full을 1 증가

소비자는 데이터를 가져와야 하므로, full을 고려한다.

• wait(full) : 데이터 하나를 가져올 것이므로 full을 1 감소
• wait(mutex) : mutex가 1이면 mutex를 1 감소시키고 critical section으로 접근
• critical section(remove an item from buffer) : 버퍼(ex. Linked List)에서 해당 아이템을 제거
• signal(mutex) : critical section을 나왔으므로 mutex를 다시 1 증가
• signal(empty) : 데이터 하나가 감소했으므로 empty를 1 증가

---

Readers and Writers Problem

여러 Reader들이 문제 없이 동시에 reading이 가능하면서 Writer와도 충돌이 없어야 하는 문제

이를 해결하기 위해 shared data인 read_count를 사용한다 : 현재 읽고 있는 reader의 수

또한 다음과 같은 Semaphore 2개를 사용한다.

• rw_mutex : 초기값 1, writer와 reader 사이에 필요한 mutex
• mutex : 초기값 1, reader들 사이에 필요한 mutex

 

Readers and Writers Problem

 

Reader

• shared data인 read_count는 여러 프로세스가 동시에 연산을 하면 안된다.
• 따라서 read_count를 증가하고 감소하는 부분이 여기서 critical section이다.
• read_count가 1이 되면 현재 읽고 있는 Reader가 있다는 뜻이므로 rw_mutex를 1 감소시켜 Writer 접근을 막는다.
• 반대로 Reading이 끝나면 read_count를 1 감소시키고, read_count가 0이 되면 마지막 Reader까지 Reading이 끝난 것이므로 rw_mutex를 1 증가시켜 Writer 접근을 허용한다.

Writer

• 코드상으로 rw_mutex는 0 혹은 1이므로 단 하나의 Writer만 접근할 수 있다.
• 또한 Reader 코드에서, Reading 작업 중인 Reader가 없어야 (read_count == 0) rw_mutex가 1이 되어 작업 가능하다.

이 방법을 보면, Reader의 우선순위가 높고, Writer의 우선순위가 낮다고 볼 수 있다.
그래서 Reader의 수가 과하게 많거나 끊임없이 들어오는 경우에 bounded-wait이 없어 rw_mutex 값이 계속 0으로 유지된다. 즉, Writer가 실행하지 못하여 starvation 상태에 빠질 수 있다.

---

Dining-Philosophers Problem

Dining-Philosophers Problem Concept

 

이번 문제는 상호관계가 없는 사람들이 원탁에 앉았는데, 원탁에 있는 젓가락을 옆사람과 같이 쓰면서 밥을 가져와야 하는 상황을 뜻한다. 이를 프로세스에 대입하면, 리소스 2개가 있어야만 데이터를 사용할 수 있는 것이다.

 

그래서 이 리소스마다 semaphore로 설정한다. 한 프로세스가 2개를 모두 사용한 뒤(wait) 2개를 모두 내려놓으며(signal) 프로세스들이 리소스를 충돌 없이 사용할 수 있게 한다.

 

그러나 이 알고리즘도 문제가 있다.

• 만약 5개의 프로세스가 모두 chopstick[i]를 동시에 wait하면, 남아있는 chopstick이 없어 2번째 wait을 넘어갈 수 없다.
• 이 같은 문제를 deadlock이라고 한다. 일어날 수 없는 일을 기다리고 있는 상태인, 일종의 희망고문이다.