이번 글에서는 3가지의 classic한 synchronization 문제들에 대해서 다루어 보도록 하겠습니다.
1. Bounded - Buffer Problem
2. Readers and Writers Problem
3. Dining - Philosophers Problem
Bounded - Buffer Problem
n 사이즈를 가지는 버퍼가 존재하고 하나의 홀드에는 하나의 아이템이 저장될 수 있다. Producer는 아이템을 생성하고 Consumer는 아이템을 사용한다.
1. Semaphore mutex는 1로 초기화 된다.
- buffer에 하나의 프로세스만 접근할 수 있도록 설정.
2. Semaphore full은 0으로 초기화 된다.
- full은 버퍼에 들어있는 아이템의 숫자를 의미한다. 예시에서는 하나의 아이템이 존재하므로 full = 1이다.
3. Semaphore empty는 n으로 초기화 된다.
- empty는 비어있는 버퍼의 갯수를 의미한다. 버퍼의 초기 생성 시에는 아이템이 들어있지 않으므로 n으로 초기화하고, 예시에서는 4의 값을 가진다.
Producer
: wait(empty)를 통해서 empty의 값이 0이면 대기하도록 설정되었다. 즉, 비어있는 버퍼가 없다면 아이템을 생성하지 못하고 대기하는 것이다. 또한 아이템을 생성하기 위해 버퍼에 접근할 때는 semaphore mutex로 감싸서 producer와 consumer가 동시에 접근하는 것을 방지한다. 버퍼에서 아이템을 생성한 뒤에는 signal(full)을 호출해 full의 값을 1 증가시킨다.
Consumer
: wait(full)을 통해서 버퍼에 아이템이 없다면 아이템을 사용하지 못하고 대기한다. producer와 마찬가지로 버퍼에 접근할 때는 semaphore mutex를 통해 critical section problem을 방지한다.
아이템을 사용한 후에는 signal(empty)를 호출해 empty 값을 1 증가시킨다.
Readers - Writers Problem
Readers
: 오직 데이터를 읽을 수만 있다. reader들은 데이터를 업데이트할 수 없다.
Writers
: 읽고 쓰는 작업이 모두 가능하다.
Problem : reader들은 데이터를 수정하지 않으므로 동시에 여러 reader가 데이터에 접근할 수 있다. 하지만 writer는 데이터를 수정해야 하므로 한 번에 하나의 writer만 접근할 수 있다.
First, readers - writers problem
: writer가 쓰고 있지 않다면 reader는 바로 접근할 수 있어야 한다.
Second, readers - writers problem
: writer가 대기 중이라면, 새롭게 접근하는 reader들은 read가 허용되지 않는다.
The reader processes share the following
1. read_count는 0으로 초기화된다.
2. Semphore mutex는 1로 초기화된다.
3. rw_mutex 는 1로 초기화된다.
Reader
: read_count와 rw_mutex, shared data에 접근할 때는 모두 semaphore mutex로 보호해야 한다. 코드의 첫 줄부터 설명하면, wait(mutex)를 통해 read_count를 보호하고 있다. 이후 reader가 mutex를 얻으면 read_count의 값을 증가시킨다. (하나의 reader가 데이터를 읽기 시작했기 때문이다.)
그리고 만약 read_count가 0이라면 즉, 첫번째 reader라면 rw_mutex를 가져간다. writer가 진입할 수 없도록 하기 위함이다. 이후 mutex를 통해 버퍼에 접근하여 데이터를 읽고 데이터를 다 읽은 후에는 read_count를 1 감소시킨다.
read_count == 0이라면 즉, 자신이 마지막 reader였다면 rw_mutex를 반납함으로써, writer가 접근할 수 있도록 한다.
writer
: writer의 코드 구성은 매우 간단하다. rw_mutex 자원이 없다면 대기하고 자원이 있다면 가져와 데이터에 접근할 수 있다.
readers - writers problem에서 설명했던 두 가지의 문제를 해결하는 방법은 아니다. 또한 readers - writers problem은 두 가지의 문제를 야기할 수 있다. 첫 번째 경우에는 새로운 reader가 계속 접근한다면 writer는 데이터에 접근하지 못하는 wirter starve 현상이 발생할 수 있다. 두 번째는 반대로 writer가 계속 대기 중이라면 reader들이 데이터에 계속 접근하지 못하는 reader starve가 발생할 수 있다.
Dining - Philosophers Problem
N명의 철학자들이 둥그런 테이블의 가운데에 밥(공유 자원)을 놓고 둘러 앉아 있다. 철학자들은 thinking과 eating의 두 가지 상태를 가질 수 있다. 그들은 절대 이웃한 철학자와 상호 작용을 하지 않는다.
thinking
: eating을 하지 않는 상태로써, 자원을 이용하지 않는 상태를 의미한다.
eating
: 자원을 이용하는 상태를 의미한다.
: 철학자는 자신의 양옆에 놓인 젓가락을 이용하여 밥을 먹을 수 있다. 반드시 한번에 두 개의 젓가락을 가지고 있어야 밥을 먹을 수 있다.
while (true){
wait (chopstick[i]);
wait (chopstick[(i + 1) % 5]);
/* eat for awhile */
signal (chopstick[i]);
signal (chopstick[(i + 1) % 5]);
/* think for awhile */
}: 매우 단순한 형태로 젓가락을 사용할 수 있도록 구성한 코드이다. 하지만 이 경우에는 철학자 모두가 자신의 왼쪽 젓가락에 먼저 접근한다면 5명의 철학자가 모두 오른쪽 젓가락을 잡지 못한 채 고착 상태에 빠지게 된다. 후에 포스팅하겠지만 이런 경우를 deadlock 이라고 한다.
[(i + 1) % 5] 는 자신의 오른쪽(왼쪽) 젓가락을 의미한다. 예를 들어 Philosoper[1] 에게 왼쪽(오른쪽) 젓가락이 1이라면, 오른쪽(왼쪽) 젓가락은 [(1 + 1) % 5] = 2가 되는 것이다.
monitor DiningPhilosophers{
enum{THINKING, HUNGRY, EATING} state[5];
conditionself[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 left and right neighbors
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();
}
}코드에 대해서 간단히 설명하자면 철학자는 젓가락을 들기 위해 pickup 함수에서 자신의 상태를 HUNGRY로 바꾼다.
이후 젓가락을 들 수 있는지 테스트를 하게 되는데 test 함수에서는 양 옆의 철학자가 EATING 상태가 아니며, 자신이 HUNGRY 상태인지 판별한다. 조건이 모두 맞다면 자신의 상태를 EATING으로 바꾸고, 자신을 깨움으로써 test 함수는 종료된다.
test 함수의 마지막에서 자신을 깨우는 이유는 putdown 함수에서 설명하겠다.
다시 pickup 함수로 돌아가보면 EATING에 실패한 경우 자신을 wait하게 된다.
putdown 함수는 EATING을 마친 철학자가 젓가락을 내려 놓는 함수이다. 자신의 상태를 THINKING으로 바꾸고, 양옆의 철학자들에 대해서 test 함수를 실행한다. 이유는 자신이 EATING 상태였기 때문에 자신의 옆 철학자가 pickup을 시도했다면, EATING에 실패하고 잠들어 있기 때문이다. 즉, test 함수의 마지막에서 호출하는 signal(i)를 통해 잠들어 있는 옆의 철학자를 깨우는 것이다.
Monitor를 통해 구현한 N Philosopher Solution 에서는 deadlock은 발생하지 않지만, starvation이 발생할 수는 있다.
