1. Bounded-Buffer Problem (Producer-Consumer Problem)
동그란 링 모양의 bounded buffer에 저장되어 있는 공유데이터에 producer와 consumer가 접근을 하는 경우에 해당한다. producer와 consumer가 수행하는 프로세스는 다음과 같다.
Producer
1. empty 버퍼가 있는지 확인한다. 없다면 기다린다.
2. 있다면 공유데이터(전체 버퍼)에 lock을 건다.
3. empty 버퍼에 데이털를 입력하고 버퍼를 조작한다.
4. lock을 푼다.
5. full buffer 개수를 하나 증가시킨다.
Consumer
1. full 버퍼가 있는지 확인한다. 없다면 기다린다.
2. 있다면 공유데이터(전체 버퍼)에 lock을 건다.
3. full 버퍼에서 데이터를 꺼내고 버퍼를 조작한다.
4. locker을 푼다.
5. empty 버퍼 개수를 하나 증가시킨다.
버퍼 자체 뿐만 아니라 버퍼를 조작하는 데에 사용하는 변수인 empty 버퍼와 full 버퍼의 시작 위치 등이 공유 데이터에 포함된다. 동기화에 사용하는 변수는 mutual exclusion을 위한 binary semaphore와 resource count를 위한 integer semaphore가 있다. semaphore에 대한 구체적인 설명은 여기서 확인할 수 있다.
semaphore를 이용해 구현한 코드는 다음과 같다.
semaphore full = 0, empty = n, mutex = 1;
//Producer
do {
P(empty); /*비어 있는 버퍼가 있는지 확인한다.*/
P(mutex);
//critical section : 데이터를 버퍼에 삽입
V(mutex);
V(full); /*full 버퍼 개수 증가시킨다.*/
} while (1);
//Consumer
do {
P(full) /*full 버퍼 있는지 확인.*/
P(mutex)
//critical section : 버퍼에서 데이터를 꺼냄
V(mutex)
V(empty) /*empty 버퍼 release*/
} while (1);
2. Readers-Writers Problem
한 프로세스가 db에 write 중일 때 다른 프로세스가 접근하면 안 되는 경우다. 다만 read의 경우에는 동시에 여러 프로세스가 수행할 수 있다.
db 접근 규칙
1. Writer가 db에 접근 허가를 얻지 못한 상태에서는 대기 중인 reader들이 모두 db에 접근하게 한다.
2. writer는 대기 중인 reader가 하나도 없을 때 db에 접근할 수 있도록 허용한다.
3. writer가 db에 접근 중이면 reader들은 접근을 금지시키고 writer가 db에서 빠져나가야만 reader이 접근할 수 있도록 한다.
db 자체와 현재 db에 접근 중인 reader의 수(readCount)를 공유 데이터로 두어야 하며, 동기화 변수로는 공유 변수인 readcount에 mutual exclusion하게 접근하도록 하는 mutex와 reader와 writer가 db 접근 규칙에 맞게 올바르게 접근하도록 하는 db 변수를 사용한다.
semaphore를 이용한 코드는 다음과 같다.
int readcount = 0;
semaphore mutex = 1, db = 1;
//Writer
P(db);
//critical section : db에 write//
V(db);
//Reader
P(mutex);
readcount++;
if(readcount == 1) P(db); /*db에 대한 semaphore를 하나만 걸기 위해서 readcount가 1 이상일 때가 아니라 1인 경우에만 실시*/
V(mutex);
//critical section : reading//
P(mutex);
readcount--;
if(readcount == 0) V(db); /*db에 접근하고 있는 reader가 없을 때, enable writer*/
V(mutex);
3. Dining-Philosophers Problem
위와 같이 생긴 탁자에 철학자들이 앉으며 철학자들은 자신이 앉은 의자 양 옆에 놓인 젓가락들을 모두 이용해야 식사를 할 수 있고, 식사를 하지 않을 때는 생각을 한다고 가정한다. 각각의 젓가락에 semaphore를 걸어서 하나의 젓가락에는 최대 한 명만 접근할 수 있도록 구현할 수 있다. 해당 코드는 다음과 같다.
semaphore chopsticks[5]; /*초기값은 모두 1*/
Philosopher i
do {
P(chopstick[i]);
P(chopstick[(i+1)%5]);
//critical section : eat
V(chopstick[i]);
V(chopstick[(i+1)%5]);
//think
} while(1);
그러나 이런 식의 구현은 deadlock 가능성이 있다. 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 모두 집어버린 경우에 서로가 놓기를 계속 기다리고만 있게 된다. 이를 해결하기 위해서는 다음과 같은 방법을 쓸 수 있다.
1. 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 제한한다.
2. 짝수 철학자는 왼쪽, 홀수 철학자는 오른쪽 젓가락부터 집도록 하는 식으로 비대칭적으로 구현한다.
3. 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다.
3번을 구현하기 위해서는 젓가락을 실제로 pickup하고 putdown하는 코드 외에 두 젓가락을 모두 집을 수 있는지 test하는 코드가 필요하다. 이를 구현한 코드는 다음과 같다.
enum {thinking, hungry, eating} state[5];
semaphore self[5]=0; /*자기 자신에 대한 semaphore*/
semaphore mutex=1; /*critical section에 한 프로세스씩만 들어가도록 제어*/
Philosopher i
do {
pickup(i);
eat();
putdown(i);
think();
} while(1);
void putdown(int i){
P(mutex);
state[i] = thinking; /*식사 끝*/
test((i+4)%5); /*옆 자리에 젓가락 넘겨주기*/
test((i+1)%5);
V(mutex);
}
void pickup(int i){
P(mutex);
state[i] = hungry;
test(i) /*식사 시도*/
V(mutex);
P(self[i]); /*test에서 if문 만족 안 한 경우에는 self[i]가 0이 되므로 프로세스 block됨.*/
}
void test(int i){
if(state[(i+4)%5]!=eating && state[i]==hungry && state[(i+1)%5]!=eating){
state[i]=eating;
V(self[i]); /*self[i]값이 0에서 1이 됨. 만약 eating하지 못한다면 0값으로 유지.*/
}
}