Synchronization: Condition Variables(1)

Intro to Condition Variables

Warm up

다음 특성들의 이름을 생각해봅시다.

1.한 번에 오직 하나의 프로세스만이 Critical section에 진입할 수 있습니다.

2. 만약 대기중이라면, 다른 프로세스는 한정된 숫자의 횟수만큼 진입할 수 있습니다.(독점해서 다른 프로세스가 staving하는 것을 방지)

3. 만약 다른 프로세스가 CS안에 존재하지 않는다면 바로 CS에 진입합니다.

정답은 The Critical section problem에 존재합니다.

What are condition variables? How do you use them? What is Spurious Wakeup?

• Condition variable은 thread들의 집합을 tickle되기 전까지 sleep시킵니다. tickle할 때에는 sleep중인 모든 스레드를 할 수도 있고 하나의 스레드만 할 수도 있습니다. 만약 하나의 스레드만 깨우면 OS는 어떤 스레드를 깨울 것인지 정합니다. 스레드를 직접 깨우지 않고 대신 condition variable에 signal을 보냅니다. 이렇게 함으로써 condition variable안의 하나 또는 모든 스레드가 깨어나게 됩니다.
• Condition variable들은 mutex와 loop랑 같이 사용됩니다.(condition을 체크하기 위해)
• 때때로 waiting thread는 이유 없이 깨어나는 것처럼 보입니다.(Spurious wake) 계속 진행하기 위해 조건이 True임을 확인하는 loop안에서 항상 wait을 사용하기 때문에 이것들은 문제가 되지 않습니다.
• condition variable 안에 sleeping중인 스레드들은 pthread_cond_broadcast(wake up all)이나 pthread_cond_signal(wake up one)을 통해 깨워질 수 있습니다. (주의 : 이름은 signal이 있지만, POSIX의 signal들과는 전혀 연관이 없습니다!)

What does pthread_cond_wait do?

pthread_cond_wait을 호출하면 3가지 동작을 수행합니다.

1. unlock the mutex

2.waits(같은 condition variable의 pthread_cond_signal이 호출될때까지 sleep). 1과 2는 atomic하게 동작합니다.

3.return하기 전에, mutex를 lock합니다.

(Advanced topic) Why do Condition Variables also need a mutex?

condition variable은 3가지 이유로 mutex가 필요합니다. 

이해하기 가장 단순한 것은 early wakeup message(signal이나 broadcast function)가 분실되는 것을 방지하기 위해서입니다. 아래와 같은 순서의 이벤트가 순차적으로 일어난다고 가정해봤을 때, pthread_cond_wait이 호출되기 바로 전에 조건을 만족한다고 생각해봅시다. 이 경우 wake-up signal이 분실됩니다.

Thread 1	Thread 2
while (answer < 42) {
	answer++
	p_cond_signal(cv)
p_cond_wait(cv, m)

만약 두 스레드가 mutex를 잠근 경우, signal은 pthread_cond_wait(cv,m)이 호출(그러면 내부적으로 mutex를 unlock)되기 전까지 보내지지 않을 것입니다.

두 번째 일반적인 이유는 program state(answer variable)를 업데이트하는 데 일반적으로 mutual exclusion이 필요하기 때문입니다. 예를 들어 multiple threads는 answer의 value를 update할 수 있습니다.

세 번째는 real-time scheduling을 만족시키는 것은 다음과 같은 문제들이 있습니다: time critical application에서 높은 우선순위의 waiting 스레드는 먼저 continue됩니다. 이러한 조건을 만족시키기 위해서는 mutex는 pthread_cond_signal 또는 pthread_cond_broadcast를 호출하기 전에 lock되어야 합니다.  

이것에 대해 더 궁금하다면,

https://groups.google.com/forum/?hl=ky#!msg/comp.programming.threads/wEUgPq541v8/ZByyyS8acqMJ

를 살펴보세요.

Why do spurious wakes exist?

효율을 위해서입니다. Multi-CPU system에서는 race condition이 wake-up signal 요청을 알아채지 못하게 할 수도 있습니다. 커널은 wake up call이 사라진 것을 알아채지 못하고 발생할 것 같은 시기를 감지할 수 있습니다. 이러한 lost signal을 방지하기 위해서 스레드는 깨워지게 되고, 프로그램 코드는 컨디션을 다시 체크하게 됩니다.

Example

condition variable은 항상 mutex lock과 같이 사용됩니다.

wait을 호출하기 전에, mutex lock은 반드시 locked되어야 하고 wait은 loop로 둘러싸여 있어야 합니다.

pthread_cond_t cv;
pthread_mutex_t m;
int count;

// Initialize
pthread_cond_init(&cv, NULL);
pthread_mutex_init(&m, NULL);
count = 0;

pthread_mutex_lock(&m);
while (count < 10) {
    pthread_cond_wait(&cv, &m); 
    /* Remember that cond_wait unlocks the mutex before blocking (waiting)! */
    /* After unlocking, other threads can claim the mutex. */
    /* When this thread is later woken it will */
    /* re-lock the mutex before returning */
}
pthread_mutex_unlock(&m);

// later clean up with pthread_cond_destroy(&cv); and mutex_destroy 


// In another thread increment count:
while (1) {
    pthread_mutex_lock(&m);
    count++;
    pthread_cond_signal(&cv);
    /* Even though the other thread is woken up it cannot not return */
    /* from pthread_cond_wait until we have unlocked the mutex. This is */
    /* a good thing! In fact, it is usually the best practice to call */
    /* cond_signal or cond_broadcast before unlocking the mutex */
    pthread_mutex_unlock(&m);
}