이화여자대학교 반효경 교수님의 2014년 Operating System 강의를 시청한 후 정리한 내용이다.
http://kocw.net/home/cview.do?cid=3646706b4347ef09
Race Condition
위 두 개의 코드는 각각 Producer와 Consumer로, count 변수의 값을 증가 또는 감소하는 역할을 한다. 만약 Producer와 Consumer가 둘 다 실행되어 동일한 count 변수를 바꾼다고 할 때, 아래와 같은 문제가 발생할 수 있다.
count의 초기 값은 5라고 가정할 때, 이상적인 결과는 5 + 1 - 1인 5이다. 하지만 Producer가 증가한 값 6을 count 변수에 쓰기 전에, Consumer가 초기 값인 5를 읽어 감소 연산을 한다. 따라서 Producer가 뒤늦게 6을 count 변수에 쓰지만, 이미 감소 연산을 끝낸 Consumer는 그의 연산 결과인 4을 count에 쓰면서, 결국 count는 5가 아닌 4가 된다. 이 문제 원인은 Producer가 값을 쓰기 전에 Consumer가 count에 접근하여 발생한 것인데, 이러한 상황을 Race Condition이라 한다. 따라서 이 문제가 발생하지 않도록 프로세스 간의 동기화가 필수불가결하다.
Concurrency Control: 병행 제어, Process Synchronization
Race Condition in OS
OS에서 Race Condition이 발생할 수 있는 경우는 다음과 같다.
- 프로세스가 System Call을 수행하여 Kernel Mode에서 동작 중, Context Switch 발생: context switch 또한 커널에서 코드로 동작하므로 커널 내부의 공유 변수가 변경될 수 있는데, 이는 문맥 교환 전에 kernel mode에서 동작했던 커널 코드에 영향을 줄 수 있다. 이 문제는 kernel model에서 time quantum이 지나도 CPU를 다른 프로세스에게 넘기기 위해 preempt를 하지 않도록 하는 것이 방법이다.
- Kernel Mode에서 동작 중, Interrupt가 발생: 첫 번째 경우와 같이 interrupt도 커널 내부 코드에서 handling되므로, kernel mode에서 동작하던 코드에 영향을 줄 수 있다. 이 문제는 kernel mode에서 동작하는 동안 interrupt를 pending하여 나중에 처리함으로써 해결할 수 있다.
- Multiprocessor System에서 Shared Memory에 접근: 여러 프로세서가 공유 데이터에 접근하여 조작하면 race condition이 발생할 수 있다. 이 문제는 커널에 접근하는 processor를 1개로 제한하거나, 특정 공유 데이터를 접근할 때 lock/unlock을 이용하여 해결할 수 있다.
Critical Section
특정 코드에서 Race Condition을 일으키는 코드를 Critical Section이라 한다. 특정 프로세스의 코드가 Critical Section을 실행 중이라면, 다른 프로세스는 동일한 공유 데이터에 접근하는 Critical Section에 진입할 수 없어야 한다.
따라서 Critical Section에 들어가기 전과 후에, 다른 프로세스가 해당 Critical Section에 접근하는 것을 막고 허용하는 코드를 삽입해야 한다.
Condition for Programatic Problem Solving of Race Condition
- Mutual Exclusion(상호 배제): 하나의 프로세스가 Critical Section에 접근할 때는 다른 프로세스들은 접근하지 못하도록 해야 한다.
- Progress: 어느 프로세스도 Critical Section에 접근하지 않을 때는 1개의 임의의 프로세스가 접근할 수 있어야 한다.
- Bounded Waiting: 임의의 프로세스가 Critical Section에 접근 요청을 한 후, 해당 프로세스에 Starvation이 일어나지 않도록 다른 프로세스들의 접근 횟수가 유한해야 한다.
Problem Solving Algorithms
Solving Algorithm #1
do{
while(turn != 0); /* My turn? */
//critical section
turn = 1; /* Now it's your turn */
//remainder section
} while(1);turn을 사용하여 자신의 차례인지 구별한 후 실행하며 turn을 다시 상대로 전환하는 코드다. 그러나 이 코드에서는, 하나의 프로세스가 연속적으로 critical section에 접근할 수 없는 문제가 있다. 즉 critical section에 다시 접근하기 위해서는 반드시 상대 프로세스가 해당 코드를 실행하여 turn을 넘겨야 한다. 따라서 이 알고리즘은 mutual exclusion을 만족하지만, progress를 만족하지 않는다.
Solving Algorithm #2
do{
flag[i] = true; /* Pretend I am in */
while(flag[j]); /*Is he also in? then wait */
//critical section
flag[i] = false; /* I am out now */
//remainder section
}while(1);flag 배열을 이용하여 상대의 진입 여부를 확인한다. 만약 상대가 진입한 상태가 아니라면 언제든지 Critical Section에 진입 가능하다. 하지만 2행(flag[i] = true)를 실행하고 context switch가 발생한다면, 상대 프로세스 또한 flag를 true로 바꾸고, 서로 계속 양보하는 문제가 발생할 수 있다. 그러므로 이 알고리즘 또한 mutual exclusion을 만족하나 progress를 만족하지 않는다.
Solving Algorithm #3: Peterson's Solution
do{
flag[i] = true; /* My intention is to enter ... */
turn = j; /* Set to his turn */
while (flag[j] && turn == j); /* wait only if ... */
//critical section
flag[i] = false;
//remainder section
}while(1);이 알고리즘은 진입 의사를 나타내는 flag배열과 차례를 나타내는 turn을 사용한다. 먼저 flag를 true로 바꾸고, 상대에게 turn을 준 다음 상대 flag가 true인지 확인하여 기다린 후 진입한다. 위 코드는 어느 부분에서든 context switch가 발생해도 3가지 조건을 만족하는, 순서가 잘 짜여진 알고리즘이다. 그러나 상대 프로세서의 차례이자 그의 flag가 true라면, while에서 계속 기다리다가 CPU를 빼앗기는 것을 반복하는 Busy Waiting(Spin Lock)이 발생한다. 이는 의미없이 while을 돌며 순서를 기다리면서 CPU와 Memory 자원을 소모하므로 비효율적이다.
Synchronization Hardware
위 코드가 길고 복잡하며 순서가 중요한 이유는, 고급 언어의 코드 한 줄이 여러 개의 CPU instruction으로 구성되기 때문인데, 이는 코드 하나가 동작하는 도중에 Interrupt가 발생하지 않음을 보장하지 못한다. 따라서 하드웨어 상 코드 실행 도중 Interrupt가 발생하지 않도록 명령을 지원하는 경우가 존재하는데, 이것이 Test_and_set()이다.
Test_and_set()은 인자로 넘겨진 변수를 읽고 True로 set하는 연산을 한 번에 수행하는 명령으로, atomic하게 수행된다(원자성을 만족한다). 이 명령을 통해 코드를 아래와 같이 더욱 간결하게 작성할 수 있다.
/* Synchronization variable */
boolean lock = false;
/* Process Pi */
do{
while(Test_and_Set(lock);
//critical section
lock = false;
//remainder section
}Semaphore
앞서 기술한 방식들을 특정 연산을 통해 구현할 수 있는 추상 자료형(ADT)이 Semaphore인데, 이것이 지원하는 각 연산들은 원자성을 만족한다. Semaphore 자료형 S 변수를 선언했을 때 사용 가능한 연산은 아래와 같다.
- P(S): while(S <= 0) do no-op; S--; //Possibility of Busy-Wait
- V(S): S++;
P(S)는 S가 0 이하면 wait하고, 그렇지 않으면 S를 감소한다. 이는 자원 접근 횟수가 유효한지 파악하고, 접근 가능하면 접근 횟수를 줄이는 동작이다. V(S)는 S를 증가하는 연산인데, 이는 자원을 반납하면서 접근 횟수를 증가하여 다른 프로세스가 해당 자원을 접근할 수 있도록 한다. 이 연산들을 이용하여 위 알고리즘들을 간하게 구현할 수 있다.
semaphore mutex; /* initially 1 */
do{
P(mutex);
//critical section
V(mutex);
//remainder section
}while(1);해당 코드는 Binary Semaphore으로, Mutex라고 부르기도 한다.
Block & Wakeup Implementation
위에 소개된 Semaphore 연산에서 P()는 Busy-Wait(Spin Lock) 문제를 야기할 수 있는데, Block & Wakeup 구현으로 이를 해결할 수 있다. linux kernel 내 /include/linux/semaphore.h 에서 정의된 semaphore 구조체를 보자.
위 구조체에서 count 변수는 semaphore 자원의 접근 가능 횟수이다. 만약 count가 0 이하의 값으로 set되어 특정 프로세스가 wait하는 상황이 발생하면, 해당 프로세스에서 block을 호출하며 kernel에서 프로세스를 suspend시키고, queue 자료구조인 wait_list에 그 프로세스의 PCB를 추가한다. 자원을 반납하고 wakeup()연산을 하면, block된 프로세스가 있을 경우 wakeup하고, 그 프로세스를 ready queue로 옮긴다. 이 구현으로 P(), V()연산을 아래와 같이 설명할 수 있다.
- P(S):
S.count--;
if (S.count < 0){
add this process to S.wait_list;
block();
} - V(S):
S.count++;
if (S.count <= 0){
remove a process P from S.wait_list;
wakeup(P);
}
V(S)에서 S.count <= 0을 검사하는 코드는, 현재 프로세스가 자원을 반납했을 때 다른 프로세스가 이 자원을 기다리고 있는지를 검사하는 코드로 이해할 수 있다. 즉, 자신이 자원을 반납했음에도 count가 0 이하라면, 다른 프로세스에서 count를 감소하고 block 상태에 있는 것이다.
Busy-Wait vs. Block & Wakeup
둘 중에 무엇이 더 효율적인지는 Critical Section의 길이에 따라 달라진다. 만약 Critical Section이 매우 짧다면 자원에 접근하기 위해 wait하는 시간이 짧아지므로 전자가 효율적이고, 오히려 후자의 경우 오버헤드가 커질 수 있다. 그러나 일반적으로 후자가 더욱 효율적이다.
Two Types of Semaphores
- Binary Semaphore(Mutex): 0, 1의 값을 가지며, 주로 lock/unlock의 mutual exclusion에 사용된다.
- Counting Semaphore: 여러 개인 자원의 개수를 파악하는데 사용하며, 0 이상의 정수 값을 가진다.
Deadlock & Starvation
프로세스 P0와 P1이 있고, S와 Q가 각각 1로 초기화된 Semaphore라 하자.
P0와 P1은 한 번에 S와 Q를 모두 접근하려 한다. 이 코드에서 P0의 wait(S)==P(S)를 실행하고 context switch로 인해 P1의 wait(Q)를 실행했다면, P0는 S를 얻었으므로 P1의 wait(S)에서 P0가 signal(S)==V(S)을 실행할 때까지 기다린다. 마찬가지로 P0 또한 P1이 signal(Q)을 실행할 때까지 wait(Q)에서 계속 기다리게 된다. 이 상황은 서로 상대의 event 발생을 무한히 기다리는 Deadlock으로, 자원을 무한히 얻지 못하는 Starvation 현상이 발생한다. 이 문제는 서로 Semaphore을 획득하는 순서를 맞춤으로써 해결할 수 있는데, P1에서 wait(S), wait(Q) 순으로 호출하면 Deadlock 현상은 발생하지 않는다.
Classical Problem of Synchronizations
Bound-Buffer Problem
위 그림은 유한한 크기의 버퍼에 다수의 Producer, Consumer 프로세스들이 데이터를 넣고 꺼내는 상황을 나타낸 것이다. 이 상황은 synchronization에 문제가 있음을 보이는데, 예를 들어 두 개 이상의 Producer 혹은 Consumer 프로세스가 하나의 비어 있거나 차 있는 버퍼 영역을 확인하고 동시에 데이터를 쓰거나 빼는 경우가 있다. 또한 버퍼가 비어있거나 가득 찬 경우, Producer와 Consumer은 각각 쓸 공간이 없거나 가져갈 데이터가 없는 문제가 발생한다. 따라서 이 문제는 크게 2가지로 나누어 해결할 수 있다.
- 하나의 프로세스가 버퍼에 접근하면 다른 프로세스가 접근하지 못하도록 Lock을 건다. (mutual exclusion)
- 버퍼가 가득 차 있으면 Producer가, 비어 있으면 Consumer가 wait 하도록 한다. 이때 각 프로세스는 각자의 자원의 개수를 고려하여 판단한다. 예를 들어, Producer는 비어 있는 버퍼의 수를 세고, Consumer는 가득 차 있는 버퍼의 수를 센다.
위의 해결 방법은 Semaphore를 이용하여 구현이 가능하다. lock/unlock을 위한 mutex, Producer의 자원 수를 나타내는 empty와 Consumer의 자원 수를 나타내는 full 세마포어를 이용하면 된다.
이 코드는 Producer 프로세스의 코드로, empty 세마포어가 0이 아닐 때까지(빈 버퍼가 존재할 때까지) 기다리고, mutex 세마포어를 통해 다른 프로세스가 버퍼에서 일을 다 마칠때까지(mutual exclusion 만족) 기다린다. 그리고 empty 감소 및 데이터 삽입 후, mutex 세마포어를 올려서 자원을 반환하고, full 세마포어 값을 올려서 값이 Consumer의 자원이 증가했음을 명시한다.
반면에 이 코드는 Consumer 프로세스 코드로, 해당 프로세스의 자원이 존재할 때까지 full 세마포어를 이용하여 기다린다. 그리고 full 감소 및 데이터 추출 후, 버퍼 자원을 반납하기 위해 mutex 세마포어를 올리고, empty 값을 증가시켜서 Producer의 자원이 증가했을을 명시한다.
Readers-Writers Problem
Readers-Writers Problem은 다수의 Reader와 Writer 프로세스가 DB에 접근하여 데이터를 읽고 쓸 때 발생하는 문제다. 그러나 이 문제는 Bounded-Buffer Problem과 다르게, 무조건 프로세스 하나만 접근하도록 구현할 필요할 없다. 그 이유는 Reader 프로세스가 데이터를 읽는 동작은 데이터 변경의 우려가 없기 때문이다. 따라서 동시에 많은 Reader 프로세스가 DB에 접근하는 것은 문제가 되지 않는다. 반대로 Writer 프로세스는 데이터를 변경하므로, 다른 프로세스가 동시에 DB로 접근하지 못하도록 lock을 해야 한다. 이때 Writer에게 DB 접근을 부여할 때, DB에 접근한 Reader 프로세스의 수를 확인해야 한다.
- Writer 프로세스가 DB 접근 허가를 얻기 전에는 모든 Reader 프로세스의 DB 접근을 수락한다.
- Writer 프로세스는 DB 접근 요청을 대기하는 Reader 프로세스가 없을 경우 접근 가능하도록 구현한다.
- Writer 프로세스가 DB에 접근했으면, Reader 프로세스의 DB 접근을 금지한다.
이 문제 또한 세마포어로 해결 가능하다.
세마포어 rw_mutex는 Writer, Reader 프로세스에 대한 mutual exclusion이고, 세마포어 mutex는 Reader 프로세스들이 공유하는 공유변수 read_count의 접근 제어를 하는 mutual exclusion이다. 그리고 read_count는 DB에서 읽는 동작을 하는 Reader 프로세스의 수이다.
Reader 프로세스를 구현할 때는, 먼저 read_count를 증가시키기 위해 mutex 세마포어를 기다리고, 자신의 차례가 오면 mutex를 감소시키며 read_count를 증가시킨다. 이때 자신이 DB에 접근한 최초의 Reader 프로세스라면 rw_mutex 세마포어를 통해 writer가 DB에 접근해 있을 경우를 기다리고 DB에 lock을 걸어 Writer 프로세스가 접근하지 못하도록 한다. 그러나 DB에 접근한 최초의 Reader 프로세스가 아니라면 이미 lock이 되어 있으므로 rw_mutex를 감소할 필요가 없다. 이 작업 이후 mutex를 다시 증가시킨다.
읽기 작업 후, read_count를 감소시키기 위해 mutex 세마포어를 기다리다가 read_count를 감소시킨다. 만약 자신이 DB 접근 권한을 마지막으로 반납하는 Reader 프로세스라면 rw_mutex를 증가시켜 DB를 unlock하여 Writer 프로세스가 접근할 수 있도록 한다.
위의 Reader 코드는 한 번 Reader 프로세스를 위한 DB Lock이 걸리면, DB에 요청하는 Reader 프로세스들이 없을 때까지 Writer를 위해 DB Unlock을 수행하지 않는다. 따라서 수많은 Reader 프로세스들이 DB에 계속 접근을 요청하면, Writer 프로세스는 계속 DB 접근을 할 수 없는 Starvation 상태를 맞이한다. 즉, Bounded-Waiting을 만족하지 않는다.
Starvation 문제는 Writer 프로세스가 DB 접근 요청을 한 시점에서, 남아 있는 Reader 프로세스의 접근 요청의 일부만 받아들이는 방식으로 해결할 수 있다.
Writer 프로세스의 구현은 mutex 변수를 사용할 필요가 없으므로 더욱 간결하다. rw_mutex를 통해 현재 DB가 lock된 상태인지 확인하고, unlock 상태일 경우 rw_mutex를 감소시키고 쓰기 작업을 수행한다. 그리고 DB를 다시 unlock하여 Reader 프로세스가 접근할 수 있도록 한다.
Dining-Philosophers Problem
서로 생각하며 식사하는 주기가 다른 5명의 철학자들이, 식탁에서 모여 생각하다가 배고파지면 식사를 하는데, 이때 철학자들 사이에 놓인 젓가락 5개 중 인접한 젓가락 2개를 이용하여 식사한다. 따라서 한 명의 철학자가 밥을 먹기 위해서는 양 옆의 젓가락을 들고 밥을 먹어야 한다. 그런데 이 상황에서는 총 두 가지 문제가 발생하는데, 첫째는 B와 D가 식사를 하기 위해 양 옆의 젓가락을 이용하면 C가 식사를 못하는 Starvation이 발생한다. 둘째는 모든 철학자들이 오른쪽의 젓가락을 들면 왼쪽의 젓가락을 갖지 못해 식사를 하지 못하는 Deadlock이 발생한다. 이러한 문제는 5명 중 4명까지만 식사를 하도록 하거나, 양쪽 젓가락을 모두 얻지 못할 경우 식사를 하지 않도록 하여 해결할 수 있다. 짝수 번째의 철학자가 왼쪽 젓가락을, 홀수 번째의 철학자가 오른쪽 젓가락을 집도록 하는 방법도 있다.
enum {thinking, hungry, eating} state[5];
semaphore self[5] = 0;
semaphore mutex = 1;
//Philosopher i
do
{
pickup(i);
eat();
putdown(i);
thinking();
}while(1);state는 철학자의 상태를, self 세마포어는 젓가락 2개 획득 가능 여부를, mutex는 공유 변수 state에 접근할 때 사용하는 mutual exclusion이다.
위 코드에서 semaphore self[5] = 0은 Semaphore의 철학에 맞지 않는 코드이다. 원래 Semaphore는 가능한 자원 접근 횟수로 초기화하지만, 이 경우는 처음부터 0으로 초기화되었기 때문이다.
void test(int i){
if(state[(i + 4) % 5] != eating && state[i] == hungry && state[(i + 1) % 5] != eating){
state[i] = eating;
V(self[i]);
}
}test()함수는 철학자 i가 젓가락 2개를 얻을 수 있는지를 확인하는 함수인데, i의 양 옆 철학자가 식사 중이지 않고 철학자 i가 배고프다면 그의 상태를 식사 중으로 바꾼다. 또한 다른 프로세스가 필요한 경우 해당 철학자의 식사 가능 여부를 바꿀 수 있도록 unlock한다. 따라서 self[i]가 1로 증가함에 따라 철학자 i는 2개의 젓가락을 얻을 수 있다.
void pickup(int i){
P(mutex);
state[i] = hungry;
test(i);
V(mutex);
P(self[i]);
}pickup()함수는 철학자 i가 젓가락을 들도록 동작하는 함수로, mutex를 통해 state에 접근하고, 철학자 i의 상태를 배고픔으로 변경한다. 그리고 test함수를 통해 젓가락 2개를 얻을 수 있는지 확인하는데, 젓가락 2개을 얻었다면 P(self[i])를 통해 test에서 증가시켰던 self[i] 세마포어 값을 다시 감소시킨다. 그러나 젓가락 2개를 얻는 것이 불가능하다면 test()함수에서 V(self[i])를 호출하지 않았으므로, 해당 프로세스는 P(self[i])에서 self[i]가 1이 될 때까지 waiting한다. self[i]가 1로 바뀌는 경우는, 다른 철학자의 putdown()을 통해 양 옆의 철학자에 대한 test()를 하는 경우다.
void putdown(int i){
P(mutex);
state[i] = thinking;
test((i + 4) % 5);
test((i + 1) % 5);
V(mutex);
}putdown()함수는 철학자 i가 식사를 마치고 젓가락을 내려놓도록 하는 함수다. mutex로 state에 접근하여 철학자 i의 상태를 생각 중으로 변경하고, test()를 통해 양 옆의 철학자들에게 필요한 경우 젓가락을 준다.
Monitor
Semaphore을 이용하여 코딩을 하다보면, 개발자의 실수로 V, P 연산을 잘못 사용하여 Mutual Exclusion이 지켜지지 않거나 Deadlock이 발생하는 경우가 생긴다. 위 코드와 같이 한 번 실수를 하면 데이터를 공유하는 다른 프로세스에게도 영향을 줄 수 있을 뿐더러, 이런 문제가 발생할 경우 버그를 찾기가 어렵다. 따라서 개발자가 사용 규칙을 잘 지키면 문제가 없겠지만, 결국에는 사람이 직접 두 연산을 이용하여 순서에 맞게 제어해야 하므로 정확할 수가 없으며 코딩하기도 힘들다.
이러한 Semaphore의 단점을 해결해 주는 것이 Monitor인데, 이는 고급 프로그래밍 언어에서 지원하는 Synchronization construct로, 공유 데이터와 연산 프로시저를 Monitor 내에 정의하여, 해당 데이터를 내부의 프로시저로만 다룰 수 있도록 한다(ADT의 안전한 공유 보장). 또한 Monitor는 기본적으로 동시 접근이 불가하므로, 개발자가 직접 Lock, Unlock을 할 필요가 없다. 아래 두 번째 그림을 보면, entry queue에 프로세스(사각형)이 연결되어 있는데, 이는 접근을 위한 queue를 표현한 것으로 동시 접근을 하지 않도록 관리하는 것을 볼 수 있다.
그러나 프로세스가 Monitor 내부의 공유 자원에 접근을 요청한 시점에서 해당 자원이 없다면, 접근 권한을 얻을 때까지 wait할 수 있는 연산이 Condition Variable을 통해 제공된다. 우선 자원의 존재 조건을 나타내는 condition 변수 x, y로 선언하고, x.wait(), y.wait()를 호출하면 자원의 접근 권한을 얻기 위한 대기 큐에 프로세스가 push되고, 그 프로세스는 signal() 호출 전까지 suspend된다(Bound-Buffer Problem을 Monitor로 구현 부분 참고). 아래 그림에서 프로세스(사각형)이 공유 자원을 기다리기 위해 queue에 매달린 것을 볼 수 있다. 그리고 x.signal(), y.signal()을 호출하여, 그 자원을 기다리기 위해 suspend한 프로세스를 resume한다. 만약 suspend된 프로세스가 존재하지 않는다면 아무 일도 일어나지 않는다.
Semaphore는 프로그래머로 하여금 직접 Lock, Unlock을 하도록 하여 값을 증감하지만, Monitor의 condition variable은 값을 가지지 않는다는 점에서 차이가 있다. 또한 Monitor은 동시 접근을 알아서 막아주지만, Semaphore는 연산을 적절히 사용하여 프로그래머에게 동시 접근 제어를 맏긴다.
Monitor with Bounded-Buffer Problem
monitor bounded_buffer{
int buffer[N];
condition full, empty;
/* condition variable은 값을 가지지 않고 자신의 큐에 프로세스를 push하여 sleep하거나
pop하여 깨우는 역할만 함*/
void produce(int x){
if there is no empty buffer
empty.wait();
//add x to an empty buffer
full.signal;
}
void consume(int *x){
if there is no full buffer
full.wait();
//remove an item from buffer and strore it to *x
empty.signal();
}
}앞에 소개했던 Bound-Buffer Problem을 Monitor로 구현한 것이다. 이 코드에서 는 produce와 consume 프로시저가 존재하는데, 각각 자원이 없는 경우 contidion variable의 wait() 연산을 사용하며, 프로시저 종료 전에는 signal()을 호출한다. 위 코드에서 확인할 수 있는 사실은, condition variable은 값 그 자체를 갖는 것이 아닌, 자원을 기다리는 프로세스에게 대기 큐를 제공하고 자원이 반납되면 기다리던 프로세스에게 제공하는 연산을 한다.
Monitor with Dining Philosophers Problem
monitor dining_philosopher{
enum {thinking, hungry, 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 left and right neighbors */
test((i + 4) % 5);
test((i + 1) % 5);
}
void tset(int i){
if((state[(i + 4) % 5] != eating) && (state[i] == hungry) && (state[(i + 1) % 5] != eating)){
state[i] = eating;
self[i].signal();
}
}
void init(){
for(int i = 0; i < 5; i++)
state[i] = thinking;
}
}
Each Philosopher:
{
pickup(i);
eat();
putdown(i);
thinking();
}while(1);위 코드의 state는 다른 프로세스들이 바꿀 수 있는 공유변수이므로 Monitor 내부에 선언한다. 그리고 젓가락을 2개 집을 수 있는지에 대한 여부는 condition variable인 self로 확인하며, 젓가락 2개를 얻지 못하면 self의 wait()을, 인접한 철학자들이 식사를 마쳤으면 self의 signal()을 호출한다. 코드의 전체적인 맥락은 Semaphore로 구현했을 때와 동일하다.
