Producer-Consumer Problem
생산자가 데이터를 생산하면 소비자는 그 데이터를 소비하는 형태의 문제입니다. 컴퓨터 환경에서 예를 들자면, 컴파일러 -> 어셈블러가 있습니다. 컴파일러에서 생성한 어셈블리어는 어셈블러에서 소비하여 기계어를 만듭니다.
생산자가 생성한 데이터는 생산자와 소비자 사이의 버퍼라는 메모리 공간에 저장되고 소비자는 여기에서 필요한 만큼 가져가 소비합니다.
버퍼의 크기는 유한합니다. 생산자는 버퍼가 가득차면 더 이상 데이터를 저장할 수 없습니다. 또한 소비자는 버퍼가 비어 있으면 데이터를 가져올 수 없습니다. 유한한 크기의 버퍼를 Bounded Buffer라고 합니다. 그래서 Bounded Buffer Problem이라고도 합니다.
만약 둘 이상의 생산자가 버퍼에 동시에 데이터를 넣거나 둘 이상의 소비자 동시에 동일한 버퍼의 데이터를 사용한다면 문제가 생길 수 있습니다. 동시에 버퍼에 접근할 수 없도록 락을 걸어야 합니다.
락을 걸고 푸는 용도와 자원의 개수를 카운팅 하는 용도로 세마포어 변수를 사용합니다.
semaphore full = 0; semaphore empty = n; semaphore mutex = 1;// Producer
do
{
// produce an item in x
P(empty);
P(mutex);
...
// add x to buffer
...
V(mutex);
V(full);
} while(true);// Consumer
do
{
P(full);
P(mutex);
...
// remove an item in x
...
V(mutex);
V(empty);
...
// consume the item in y
...
} while(true);Readers-Writers Problem
한 프로세스가 데이터를 수정하는 작업을 수행할 때 다른 프로세스가 접근하면 안 되고 읽는 작업은 여러 프로세스가 동시에 수행 가능하도록 하는 문제입니다.
만약 데이터에 대해 하나의 lock을 사용하게 되면 데이터의 일관성은 지킬 수 있지만 여러 프로세스가 동시에 읽음 수 있음에도 불구하고 한 프로세스만 읽도록 강제하게 되어서 비효율적입니다.
현재 수정하려고 하는 프로세스가 없다면 모든 대기중인 Reader들의 접근을 허용하고, Writer는 대기중인 Reader가 하나도 없을 때 접근가능합니다. 그리고 Writer가 접근 중이면 Reader는 접근할 수 없습니다.
semaphore readcount = 0; semaphore wrt = n; semaphore mutex = 1;// Writer Process
do
{
P(empty);
...
// writing is performed
...
V(full);
} while(true);// Reader Process
do
{
P(mutex);
readcount++;
if (readcount == 1) P(wrt);
V(mutex);
...
// reading is performed
...
P(mutex);
readcount--;
if (readcount == 0) V(wrt);
V(mutex)
} while(true);만약 n개의 reader가 대기하고 있다면 첫 reader만 wrt 세마포에 넣고 나머지 n-1개의 reader는 mutex 세마포어 큐에 넣어둠으로써 효율성을 높입니다.
이 문제의 해결책은 기아(Starvation)의 가능성이 있습니다. 계속해서 reader가 들어오거나 writer가 들어오는 경우 한 쪽이 수행되지 않을 수도 있습니다. 큐에 우선순위를 부여하거나 일정 시간이 지나면 자동으로 write or read가 되도록 하여 해결할 수 있습니다.
Dining-Philosophers Problem
5명의 철학자가 원탁에 둘러앉아있고 젓가락도 5개가 놓여있습니다. 철학자들은 식사를 하기 원하고, 철학자가 식사를 하기 위해서는 양쪽 젓가락을 모두 집어야 합니다.
do
{
P(chopstick[i]);
P(chopstick[(i+1)%5]);
...
// eat
...
V(chopstick[i]);
V(chopstick[(i+1)%5]);
...
} while(true);다음과 같이 구현하면 두 철학자가 동시에 먹는 경우가 없다는 것이 보장됩니다. 하지만 이 방식은 모든 철학자가 식사를 하기 위해서 각자의 왼쪽에 있는 젓가락을 들었다면 더 이상 아무런 작업도 수행할 수 없는 Deadlock 상태에 빠지게 됩니다.
Deadlock 상태를 방지하기 위한 여러 방법이 있습니다. 4명의 철학자만이 테이블에 앉도록 하거나, 젓가락을 두 개 집을 수 있을 때만 젓가락을 집도록 하는 방법, 짝수/홀수 철학자는 왼쪽/오른쪽 젓가락을 먼저 집도록 하는 방법 등이 있습니다.
젓가락을 두 개 집을 수 있을 때만 젓가락을 집도록 하는 방법
V(self[i]): 양쪽 젓가락을 들 수 있는 권한을 얻는 부분. 만약 얻지 못하면 P(self[i])에서 기다리게 됩니다. 양쪽 철학자가 다 먹은 경우에 대기가 끝나게 됩니다.
enum {thinking, hungry, eating} state[5];
semaphore self[5] = 0; semaphore mutex = 1;// philosopher i
do
{
pickup(i);
eat();
putdown(i);
} while(true);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]);
}
void test(int i)
{
if (state[(i+4)%5] != eating && state[i] == hungry && state[(i+1)%5] != eating)
{
state[i] = eating;
V(self[i]);
}
}