Conditional Variables

Condition Variables

 

There are many cases where a thread wishes to check whether a condition is true

before a continuing its execution.

 

예를 들어서 부모 쓰레드가 자식 쓰레드가 완료되었는지 아닌지에 대한 점검하는 것으로

이를 보통 join() 이라고 부른다.

 

다음 코드를 보도록 하자.

 

#include <stdio.h>
#include <assert.h>
#include <pthread.h>
#include <stdlib.h>

void *child(void *arg) {
    printf("child\n");
    return NULL;
}

int main(int argc, char *argv[]){

    printf("parent : begin\n");
    pthread_t c;
    pthread_create(&c, NULL, child, NULL);
    printf("parent: end\n");

    return 0;
}

 

 

사실 우리가 원하는 결과는 begin, end 사이에 "child" 문구가 떠야 한다.

그러나 자식 쓰레드를 만들기 위해 함수를 호출했으나 부모 쓰레드에서 자식 쓰레드를 기다리지 않고

parent: end 문구를 띄우고 return를 해버리기 때문에 그렇지 못한다.

 

부모 쓰레드가 자식 쓰레드를 기다릴 수 있도록 하는 수정된 코드를 보도록 하자.

 

#include <stdio.h>
#include <assert.h>
#include <pthread.h>
#include <stdlib.h>

static volatile int done;

void *child(void *arg) {
    printf("child\n");
    done = 1;
    return NULL;
}

int main(int argc, char *argv[]){

    printf("parent : begin\n");
    pthread_t c;
    pthread_create(&c, NULL, child, NULL);
    while(done == 0) ;
    printf("parent: end\n");

    return 0;
}

 

 

드디어 원하는 결과가 떳다.

그러나 while - loop 를 돌면서 static 변수 done를 설정하여 자식 쓰레드에서 해당 변수를 1로 설정할 때까지

부모 쓰레드는 계속 해서 spin 하는 상태이다.

즉, 이렇게 짠 코드는 부모 쓰레드가 자식 쓰레드가 종료할 때까지 계속해서 loop를 돌기 때문에 CPU time을 

많이 잡아먹기 때문에 비효율적이라고 볼 수 있다.

 

 

How to wait for a condition

 

Condition variable 이 어떤 것인지 알아보도록 한다.

(1) thread들이 담겨져 있는 Queue 이다.

(2) 특정 쓰레드가 조건(condition)을 만족하지 못 할 경우에 Waiting 한다. (state : blocked)

       즉, Queue에 조건을 만족하지 못한 쓰레드들이 존재하는 상태라고 볼 수 있다.

(3) 특정 쓰레드가 조건(condition)이 만족하기를 기다리는 상태로 Signaling 이라 한다.

       즉, blocked 인 상태의 쓰레드 중에 어떠한 쓰레드가 조건을 만족할 경우 해당 쓰레드를 

       ready state로 변경시켜서 Ready Queue에 insert 하도록 한다.

       이 때, OS Scheduler가 time quantum이 지나서 context switch를 할 때, running state로 

       변경하게 된다. 

 

Three in a package

   => condition variable c, state variable m, lock L

         Lock L은 state variable을 보호하기 위한 용도로 쓰인다.

 

pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
pthread_cond_signal(pthread_cond_t *c);

 

wait() 함수는 추가로 mutex parameter를 받아오는 것을 알 수 있다.

wait() 함수는 lock을 풀어주고 해당 쓰레드를 blocked 상태로 변경시켜주고

signal() 함수는 condition Queue에 존재하는 쓰레드를 깨우도록 signal을 보낸다.

이때 해당 쓰레드가 깨어날 경우 풀었던 lock을 다시 걸어주도록 하는 것을 잊지 말자.

 

 

Parent waiting for Child: Use a condition variable

 

#include <stdio.h>
#include <assert.h>
#include <pthread.h>
#include <stdlib.h>

int done;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;

void thr_exit() {
    pthread_mutex_lock(&m);
    done = 1;
    pthread_cond_signal(&c);
    pthread_mutex_unlock(&m);
}

void *child(void *arg) {
    printf("child\n");
    thr_exit();
    return NULL;
}

void thr_join() {
    pthread_mutex_lock(&m);
    while(done == 0)
        pthread_cond_wait(&c, &m);
    pthread_mutex_unlock(&m);
}

int main(int argc, char *argv[]){

    printf("parent : begin\n");
    pthread_t c;
    pthread_create(&c, NULL, child, NULL);
    thr_join();
    printf("parent: end\n");

    return 0;
}

 

 

많은 case가 있지만 모두 자식 쓰레드를 기다리고 있다.

context switch가 걸리지 않았다는 가정하에 프로그램의 flow를 알아보도록 한다.

 

부모 쓰레드를 t1, 자식 쓰레드를 t2라고 할 때

1. main 함수에서 t2를 만들고 thr_join() 으로 이동하여 lock을 하고 done 값이 0 이므로

    cond_wait() 함수를 호출함으로써 lock을 release 하고 blocked 상태로 변경된다.

2. t2는 child() 함수에서 thr_exit() 함수를 호출함으로써 lock을 걸고 done 값을 1로 변경하여

    cond_signal() 함수를 호출함으로써 cond 변수 c에 존재하는 t1을 꺼낸다.

    즉, blocked 상태의 t1을 Ready queue에 삽입함으로써 ready 상태로 변경하고 다시 돌아와서

    unlock을 함으로써 완전히 child() 함수를 종료하여 t2의 life time이 끝난다.

3. ready 상태였던 t1이 t2이 종료되고 context switch가 일어남으로써 t1이 running 상태로 변경된다.

    따라서 다시 while 조건을 거치면서 done 값이 1이므로 loop를 빠져나오고 unlock을 하여 

    최종적으로 t1 또한 종료되어 process가 종료된다.

 

 

The importance of the state variable done

 

void thr_exit() {
    pthread_mutex_lock(&m);
    pthread_cond_signal(&c);
    pthread_mutex_unlock(&m);
}

void thr_join() {
    pthread_mutex_lock(&m);
    pthread_cond_wait(&c, &m);
    pthread_mutex_unlock(&m);
}

 

해당 코드의 문제점은 context switch가 일어나서 자식 쓰레드가 thr_exit()를 호출하는 경우다.

결국 부모 쓰레드는 thr_join()를 호출할 때 cond 변수 c에 현재 쓰레드(부모 = main)를 삽입하고

blocked state가 됨으로써 결국 쓰레드가 절대로 깨어날 수 없는 상태가 벌어진다.

 

또 다음과 같은 구현 코드를 보도록 하자.

 

void thr_exit() {
    done = 1;
    pthread_cond_signal(&c);
}

void thr_join() {
    if(done == 0)
        pthread_cond_wait(&c, &m);
}

 

이 코드는 race condition을 유발하는 코드라고 볼 수 있다.

단순하게 자식 쓰레드가 먼저 실행된다고 할 때 큰 문제는 없어보인다.

반대로 부모 쓰레드가 먼저 실행된다면 done 값이 0임을 체크하여 wait() 을 호출하고 자식 쓰레드에서

done 값을 1로 변경하여 signal을 호출함으로써 부모 쓰레드가 깨어나 정상적으로 작동하는 것을 유추할 수 있다.

 

그러나, thr_join() 에서 done값이 0임을 체크한 후에 context switch가 일어나면 어떻게 될까?

자식 쓰레드로 변경이 되어 done 값을 1로 바꾸고 signal을 호출하는 건 좋다.

하지만 부모 쓰레드로 돌아오고 나서가 문제이다.

done 값이 0을 체크한 다음 라인의 코드 즉, wait 함수를 호출하려는데 결국 이는 무한 Sleep 상태로 빠지게 된다.

 

 

The Producer / Consumer (Bound Buffer) Problem

 

Producer, Consumer 에 대해 먼저 알아보도록 하자.

Producer는 data item들을 만들고 buffer에 data item들을 놓고 싶어한다.

Consumer는 buffer속 data item들을 꺼내오려고 한다.

추가로 bounded buffer는 pipe의 특성을 가지고 있는데 어떠한 프로그램의 output을 다른 프로그램으로

전달(pipe)하려고 할 때 사용되는 것이다.

 

예를 들어서 "grep foo file.txt | wc -l" 라는 명령어를 생각해보자.

이 때, "grep" 프로세스는 producer, "wc" 프로세스는 consumer 이라고 볼 수 있으며

두 프로세스 사이를 연결시켜주는 pipe 같은 존재 즉, kernel 내에서의 bounded buffer라고 볼 수 있다.

 

Bounded buffer is shared resource => Synchronized access is required.

 

 

The Put and Get Routines

 

int buffer;
int count = 0; // initially, empty

void put(int value) {
    assert(count == 0);
    count = 1;
    buffer = value;
}

int get() {
    asswer(count == 1);
    count = 0;
    return buffer;
}

 

단순한 코드이다.

먼저 assert 함수를 통해 put, get을 하려고 할 때 buffer가 비거나 꽉찬 경우 error를 탐지하도록 해준다.

그리고 error가 없을 경우에 buffer size를 늘리거나 줄인다.

 

 

Producer/Consumer Threads (Version 1)

 

void *producer(void *arg) {
    int i;
    int loops = (int) arg;
    for(i = 0; i < loops; i++)
        put(i);
}

void *consumer(void *arg) {
    int i;
    int loops = (int) arg;
    while(arg--) {
        int tmp = get();
        printf("%d\n", tmp);
    }
}

 

producer() : arg으로 받아온 buffer size만큼 loop를 돌려서 buffer에 정수값(i)을 put 한다.

consumer() : tmp 변수로 받아온 buffer의 정수값을 순서대로 출력한다.

 

 

Producer/Consumer: Single CV and If Statement

 

이번에는 cond 변수와 lock과 관련된 mutex를 덧붙여서 코드를 작성한다.

 

cond_t cond;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    int loops = (int) arg;
    for(i = 0; i < loops; i++) {
        pthread_mutex_lock(&mutex);            // p1
        if(count == 1)                         // p2
            pthread_cond_wait(&cond, &mutex);  // p3
        put(i);                                // p4
        pthread_cond_signal(&cond);            // p5
        pthread_mutex_unlock(&mutex);          // p6
    }
}

void *consumer(void *arg) {
    int i;
    int loops = (int) arg;
    for(i = 0; i < loops; i++) {
        pthread_mutex_lock(&mutex);            // c1
        if(count == 0)                         // c2
            pthread_cond_wait(&cond, &mutex);  // c3
        int tmp = get();                       // c4
        pthread_cond_signal(&cond);            // c5
        pthread_mutex_unlock(&mutex);          // c6
        printf("%d\n", tmp);                
    }
}

 

p2에서 count 값이 1일 경우 p3으로 넘어가는 경우는 buffer가 빌 때까지 기다리는 경우고

c2에서 count 값이 0일 경우 c3으로 넘어가는 경우는 buffer가 찰 때까지 기다리는 경우다.

이 코드는 single producer와 single consumer으로만 코드가 작동한다.

예를 들어서 buffer size가 5라고 할 때 다음과 같이 작동하는 것을 알 수 있다.

 

초기 상태가 위와 같을 때 다음과 같은 순서로 put, get을 반복하게 된다.

 

 

첫 번째로 producer에서 0을 buffer에 put 하고 2 번째 loop에서(i = 1) count가 1이므로 sleep 된다.

그래서 consumer에서 buffer에 담긴 0을 get 하고 2 번째 loop에서(i = 1) count가 0이므로 sleep 된다.

 

 

두 번째로 producer에서 0을 buffer에 put 하고 3 번째 loop에서(i = 2) count가 1이므로 sleep 된다.

그래서 consumer에서 buffer에 담긴 0을 get 하고 3 번째 loop에서(i = 2) count가 0이므로 sleep 된다.

 

 

반복하다 보면 결국 마지막에 4값을 get하고 producer는 이미 unlock 하여 종료된 상태라면 

consumer가 드디어 unlock 하고 종료하게 된다. 

 

만약에 여러개의 producer, consumer를 가지고 있다면 어떻게 될까?

 

 

Thread Trace : Broken Solution (Version 1)

 

이때 C1, C2를 consumer1, 2, P1를 producer1 라고 하자.

 

1. C1는 비어 있으므로 Sleep에 빠지게 된다.

 

 

2. P1은 buffer에 0을 넣고 2번째 loop에서(i = 1) buffer가 찼으므로 Sleep에 빠지게 된다.

 

 

3. C2는 buffer에 들어있는 0을 가져오고 cond_signal을 호출함으로써 cond Queue에 존재하던

     C1을 wake up 시킨다. 그 후에 unlock을 하고 Context switch가 일어나서 Ready state가 된다.

 

 

4. C1은 buffer에서 값을 가져오려고 했으나 현재 buffer는 비어있다. 

     따라서 이부분에서 Error가 일어나게 된다.

 

There is no guarantee that when the woken thread runs, the state will still be as desired

=> Mesa semantcis, virtually every system ever built employs Mesa semantics.

Hoare semantics provides a stronger guarantee that the woken thread will run 

immediately upon being woken.

 

 

Producer/Consumer: Single CV and While

 

cond_t cond;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    int loops = (int) arg;
    for(i = 0; i < loops; i++) {
        pthread_mutex_lock(&mutex);            // p1
        while(count == 1)                      // p2
            pthread_cond_wait(&cond, &mutex);  // p3
        put(i);                                // p4
        pthread_cond_signal(&cond);            // p5
        pthread_mutex_unlock(&mutex);          // p6
    }
}

void *consumer(void *arg) {
    int i;
    int loops = (int) arg;
    for(i = 0; i < loops; i++) {
        pthread_mutex_lock(&mutex);            // c1
        while(count == 0)                      // c2
            pthread_cond_wait(&cond, &mutex);  // c3
        int tmp = get();                       // c4
        pthread_cond_signal(&cond);            // c5
        pthread_mutex_unlock(&mutex);          // c6
        printf("%d\n", tmp);                
    }
}

 

여러 개의 consumer, producer가 작동시키기 위해 if에서 while문으로 변경시켰다.

그러나 이 또한 버그가 있다.

 

 

이때 C1, C2를 consumer1, 2, P1를 producer1 라고 하자.

 

1. C1은 buffer가 비어 있으므로 sleep 상태가 된다.

 

2. C2 또한 buffer가 비어 있으므로 sleep 상태가 된다.

 

3. P1는 buffer가 비어있으므로 정수값 0을 buffer에 넣고 cond Queue에서 C1을 깨움으로써 Ready 상태로

    변경시킨다.

    그 후에 2 번째 loop에서(i = 1) buffer가 가득 차있으므로 Sleep 상태가 되면서 Ready 상태에 있던

    C1이 Running 상태로 바뀌게 된다.

 

 

4. C1은 buffer에 있는 값 0을 가져오고 cond Queue에서 C2를 깨움으로써 Ready 상태로

    변경시킨다.

    그 후에 2 번째 loop에서(i = 1) buffer가 비어 있으므로 Sleep 상태가 되면서 Ready 상태에 있던

    C2이 Running 상태로 바뀌게 된다.

 

5. C2는 while-loop 에서 또 다시 조건을 검사하게 된다.

    이 때, 여전히 buffer가 비어있으므로 sleep 상태가 된다.

 

즉, 모두 Sleep 하게 되는 이상한 현상이 발생하게 된다.