동기화 문제 해결책을 고전적 문제들에 간단히 적용해본다.
7.1 고전적인 동기화 문제들
7.1.1 유한 버퍼 문제
int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;- empty : 비어있는 버퍼 수
- full : 차있는 버퍼 수
생산자 구조
while(true){
wait(empty);
wait(mutex);
/* 버퍼를 채운다 */
signal(mutex);
signal(full);
}소비자 구조
while(true){
wait(full);
wait(mutex);
/* 버퍼를 채운다 */
signal(mutex);
signal(empty);
}이렇게 하면 생산자는 empty세마포가 양수인 경우만, 소비자는 full 세마포가 양수인 경우만 critical section에 진입한다.
양쪽다 mutex 세마포를 이용해 상호배제를 만족한다.
7.1.2 Readers-Writers 문제
-
특정 데이터베이스가 공유될 때, 데이터베이스의 내용을 읽기를 원하는 프로세스(Reader)와 갱신하기를 원하는 프로세스(Writer)로 구분할 수 있다.
-
동시에 두 Reader프로세스가 접근하는 건 문제가 되지 않지만 여러개의 Writer가 동시에 접근하면 문제가 발생한다. 따라서 동기화가 필요하다.
해결안
Reader-Writers문제는 Reader와 Writer 중 어떤 유형의 프로세스에 우선 접근권을 주냐에 따라 기아을 발생시킨다. 따라서 특정 유형에 절대적 우선권을 주는 해결안에서 변형된 해결안을 제시한다.
자료구조
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count =0;- rw_mutex: writer, reader 프로세스 모두 공유
- mutex: read_count 갱신 시 상호베제를 보장하기 위해 사용
Writer 프로세스 구조
while (true) {
wait(rw_mutex);
/* 쓰기 작업 */
signal(rw_mutex);
}Reader 프로세스 구조
while (true){
wait(mutex);
read_count++;
if(read_count==1)
wait(rw_mutex);
signal(mutex);
/* 읽기 작업 */
wait(mutex);
read_count--;
if(read_count==0)
signal(rw_mutex);
signal(mutex);
}
- 만약 읽고 있는 프로세스가 이미 존재한다면 진입한다.
- 읽고 있는 프로세스가 없는 경우, Writer 프로세스의 진입 여부를 확인하고 진입한다.
Reader-writer 락은
1. 공유데이터를 읽기만 하는 프로세스와 쓰기만 하는 프로세스를 식별하기 쉬운 경우
2. Writer보다 Reader 개수가 많은 경우 유용하다. (동시에 여러 Reader가 읽게 하여 병행성을 높임)
7.1.3 식사하는 철학자들 문제
- 5명의 철학자가 원탁에 앉아서 식사한다.
- 철학자는 자신과 가장 가까운 젓가락(왼쪽, 오른쪽 순서)를 집으려고 시도한다.
- 한 번에 한개의 젓가락만 집을 수 있고, 다른 철학자의 젓가락을 뺏을 수 없다.
- 젓가락 두개를 집으면 식사를 시작하고, 마치면 내려놓는다.
7.1.3.1 세마포 해결안
젓가락을 하나의 세마포로 표현하여 상호배제를 구현한다.
semaphore chopstick[5];이 해결안은 인접한 두 철학자가 동시에 식사하지 않는다는 것을 보장한다. (동일한 젓가락을 동시에 사용할 수 없다는 것을 보장하기 때문이다.)
하지만 교착상태를 야기할 가능성이 있다.
- 모든 철학자가 자신의 왼쪽 젓가락을 잡은 상태에서 오른쪽 젓가락을 집기 위해서는 영원히 대기해야 한다.
교착상태에 대한 해결책들은 다음과 같다.
- 최대 4명의 철학자만 테이블에 앉는다. (젓가락 여유분이 생김)
- 젓가락 두개를 모두 집을 수 있을 때만 젓가락을 집도록 허용한다.
- 홀수번째는 왼쪽 젓가락 먼저, 짝수번째는 오른쪽 젓가락 먼저 집는다.
교착상태가 없다고 해서 기아문제를 해결하는 것은 아니다.
7.1.3.2 모니터 해결안
monitor DiningPhilosophers
{
enum {THINKING, HUNGREY, EATING} 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] != EATEING) %%
(state[(i+1) % 5] != EATEING) &&
(state[i] == HUNGRY)) {
state[i] = EATING;
self[i].signal();
}
}
} -
test(int i)
i번째 철학자가 식사가 가능하고, 식사를 원하는 경우 식사를 진행한다. -
pickup(int i)
i번째 철학자가 식사를 시도한다. 불가능한 경우 대기한다. -
putdown(int i)
i번째 철학자가 식사를 마친다.
i번째 철학자 양 옆에 있는 철학자 번호로 test()를 호출한다.
