Monitors
-
Semaphore의 가장 큰 문제는 결국 프로그래머의 실수로 귀결된다.
- 각 프로세스들이 wait->signal 순서를 지켜야 하는데, 이를 프로그래머가 실수 하면 바로 문제가 나타나고, 이는 Timing Error(Hiesenbugs)에 속하는 추적하기 어려운 버그다.
-
결론: 프로그래머에 synchronize를 모두 맡기기엔 불안하니, Language 자체에서 이를 보완해주는 기법을 만들겠다.
1. Monitors Concept
- Monitor라는 일종의 Data structure를 도입한다.(struct보단 class에 더 가까운 개념이다.)
- Monitor는 shared data와 procedure(method)로 구성된다.
- Monitor의 procedure는 복수의 task에서 작동하더라도 synchronized되는 것이 보장된다.
- 따라서 share하고 싶은 데이터를 monitor안에서 선언하고, 이를 handling하는 모든 함수들을 전부 procedure로서 작성하여 monitor안에 넣으면 이를 해결할 수 있다.
1-1. Condition Variables(CV)
- 간단히 말해서 shared data중에서 특정 task를 실행시킬지 말지 결정하는 data를 총칭하는 단어
- 이 data들의 상태에 따라서 task들은 continue할지 sleep할지 아니면 다른 task를 wake할지를 정하게 된다.
- Moitor의 특징 중 하나는, mutual exclusion을 지원하면서도, 동시에 monitor 내부에 언제나 단 한개의 task만이 존재하는 것은 아니라는 점이다.
- 특정 CV에 의해서 wait중인 task들은 monitor 밖으로 내쫒기는 것이 아니라 내부에서 CV마다 queue를 만들어서 이를 통해서 관리한다.
1-2. Monitor Structure
-
기본적으로 entry queue를 이용해서 monitor에 접근하고자 하는 task들의 출입을 제한한다.
- semaphore나 mutex와의 차이점은 어떤 task가 반드시 나가야만 monitor로 들어갈 수 있는 것은 아니다.
- 내부 task가 CV에 의해서 sleep 상태에 들어간 경우에도 task의 출입을 허용할 수 있다.
-
각 CV에 의해서 wait중인 task는 monitor 밖이 아니라 내부의 queue를 이용해서 관리한다.
-
그럼에도 불구하고 monitor 내부에서 procedure를 실질적으로 실행시키는 tasks는 한개로 유지함을 통해서 mutual exclusion을 보장한다.
1-3. CV API
- wait(c)
- monitor의 lock을 놓고 entry queu의 누군가가 moitor 내부로 들오도록 허가한다.
- 동시에 sleep 상태로 들어가며, CV의 waiting queue에 들어간다.
- 위의 2개의 작업은 반드시 atomic하게 이루어져야 한다!!!!!
- signal(c)
- waiting 중인 process를 하나 깨운다.(signal)
- waiting 중이든 아니든 일단 보낸다.
- signal 처럼 history가 존재하지 않는 system이다.(몇개가 도착하였든지간 한개만 처리가능하다.)
- broadcast(c)
- 대기중인 모든 process를 깨운다.(이러면 실질적으로 busy-waiting case로 돌입하는 셈이다.)
1-4. Example(Bounded Buffer)
Monitor bounded_buffer {
buffer resources[N]; // shared_data
condition not_full, not_empty; // CV - we set this CV as semaphore in prev
procedure add_entry(resource x) {
while (array “resources” is full)
wait(not_full);
add “x” to array “resources”;
signal(not_empty);
}
procedure remove_entry(resource *x) {
while (array “resources” is empty)
wait(not_empty);
*x = get resources from array “resources”
signal(not_full);
}
}2. Monitors Semantics
2-1. Hoare monitors
-signal()이 waiting thread를 깨우고 그 즉시 해당 thread로 context switch된다.
- Context switch 횟수가 크게 증가할 수도 있다.
- Condition이 반드시 만족됨을 보장한다.
if (notReady) // 한번만 체크해도 상관없다. wait가 끝났을 때
wait(c);2-2. Mesa monitors
signal()은 waiting thread의 상태를 ready queue에 넣어줄 뿐, 진행 자체는 해당 thread에서 계속된다.- Context switch 횟수를 줄일 수 있다.
broadcast()연산이 가능하다.- waiter가 호출되기 전까지 다른 thread condition이 변경될 수 도 있으므로 condition을 보장하지 못한다.
while (notReady) // wait가 끝나면 다시 한번 검사를 해야한다.(중간에 무슨일이 일어날지 모르므로)
wait(c);3. Monitors and Semaphores
3-1. Monitor Implementation with Semaphore
- Hoare monitors
Semaphore mutex = 1;
Semaphore next = 0;
int next_count = 0;
struct condition {
Semaphore sem;
int count;
} x = {0, 0};
procedure F() {
wait(mutex);
…
Body of F
…
if (next_count)
signal(next); // 다른 사람을 통해서 들어왔다면, 그 사람에게 넘긴다.
else
signal(mutex); // 없으면 lock을 풀어버려욧
}
procedure cond_wait(x) {
x.count++; // 대기 등록
if (next_count)
signal(next); // signal로 남에게 넘겨준 thread가 있으면 그 thread를 실행
else
signal(mutex); // 없으면 mutex 대기를 실행
wait(x.sem); // 이 thread는 잠들어야하고...
x.count--;
}
procedure cond_signal(x) {
if (x.count) { // waiting thread가 있음
next_count++; // 이 thread가 누군가를 깨웠음을 알림
signal(x.sem); // 대기중인 thread를 꺠운다.
wait(next); // 다음 thread에 넘기기 위해서 지금 실행중인 thread는 waiting으로 돌린다.
next_count--; // waiting에서 나오면 count를 한개 줄인다.
}
}- Mesa Monitors
3-2. Monitors vs Semaphores
-
Condition variables do not have any history, but semaphores do
-
On a condition variable signal(), if no one is waiting, the signal is a no-op
- If a thread then does wait() on the condition variable, it waits
-
On a semaphore signal(), if no one is waiting, the value of the semaphore is increased
- If a thread then does wait() on the semaphore, the value is decreased and the thread continues
물리와 컴퓨터