[Operating System] Condition Variable

상호배제의 문제는 lock을 통해서 해결했지만, lock은 쓰레드 간에 lock을 얻는 순서를 정해줄 수 있는 기능은 없다. 이와 같은 ordering의 문제는 CV와 semaphore를 통해서 해결할 수 있다.

 

CV란?

CV란 말 그대로 조건이 만족되기를 기다리는 공유 변수를 의미한다. 뒤에서 살펴 보겠지만 CV가 쓰레드 간에 공유되는 state라는 점은 꼭 명심해야할 부분이다.

 

Ex) 쓰레드에서 instruction 수행 이전에 컨디션이 만족 되었는지를 먼저 확인하고 싶은 경우가 존재한다. 예를 들어서 parent 쓰레드가 child 쓰레드가 완료되었는지(exit 했는지) 확인을 하고 싶은 경우에 join()을 사용한다.

 

CV의 특징

1. 쓰레드 간 공유되는 공유 변수이므로 상호 배제가 되어야 한다.

2. Blocking 매커니즘에 기반한다. cond_wait를 하면 해당 조건이 만족될 때까지 spinning을 하면서 기다리는 것이 아니라 sleep 상태(BLOCKED)가 된다. 다른 쓰레드에서 signal을 보내면 BLOCKED 상태에서 READY 상태가 되고 스케줄링 될 수 있다. 

3. 또 다른 공유 변수인 state variable을 while loop을 통해 체크하면서 CV를 사용하는 것이 좋다.

4. 쓰레드의 종류 별로 CV를 하나씩 두는 것이 좋다. (producer-consumer problem)

 

 

Condition Variable API

1. wait(cond_t *cv, mutex_t *lock)

• 만약 wait를 호출하면 일단 현재 쓰레드를 sleep 상태에 두고 mutex lock을 release한다. (atomic하게 이루어짐)
• 그리고 다른 쓰레드에서 signal을 보낼 때까지 sleep한다.
• pthread_mutex_t *m이 인자로 전달 되는 이유는 sleep을 할 때 mutex lock을 먼저 release하고 sleep 상태가 되어야하기 때문이다. mutex lock을 잡은 상태에서 sleep 해버리면 그 어떤 쓰레드도 lock을 잡고 진행할 수 없는 데드락 상태가 된다.

참고) Sleep 매커니즘

쓰레드 $T$가 wait를 호출하면 signal을 받을 때까지 block 상태가 된다. 이 때 쓰레드 $T$는 스스로를 block 상태로 만들기 이전에 mutex lock을 놓는다. 그래야 다른 쓰레드에서 lock을 잡고 진행을 할 수 있기 때문이다. 이후 다른 쓰레드에서 보낸 signal을 $T$가 받게 되면 다시 깨어나게 되고 이 때 mutex lock을 새로 잡는다. 다음은 실제 리눅스 시스템에서 동작하도록 간단히 sleep 함수를 구현한 것이다.

 

void sleep(void) {
    DEFINE_WAIT(wait_queue_entry);
    prepare_to_wait(&__wait_queue, &wait_queue_entry, TASK_INTERRUPTIBLE);
    mutex_unlock(&wait_mutex);
    schedule();
    mutex_lock(&wait_mutex);
    finish_wait(&__wait_queue, &wait_queue_entry);
}

1. 우선 현재 쓰레드를 wait queue에 넣어서 schedule 함수를 호출하여 스케줄링을 했을 때 BLOCK 상태가 될 수 있도록 한다.
2. 현재 쓰레드가 block된 이후에 다른 쓰레드에서 mutex lock을 잡고 진행할 수 있도록 lock을 release 한다.
3. 스케줄러를 호출하여 현재 쓰레드는 BLOCK 상태로 만들어 스케줄링이 되지 않도록 한다.
4. 시간이 흐른 뒤 다른 쓰레드에서 signal을 호출하면 wait queue에 있는 쓰레드 중 하나(또는 전부)가 wait queue에서 제거되고 run queue에 삽입되어 READY 상태가 된다.
5. 스케줄러의 선택을 받아 RUN 상태가 된(컨트롤을 받은) 쓰레드는 schudule(); 이후의 시점부터 재개한다.
6. 다시 mutex lock을 잡고 진행한다.

 

2. signal(cond_t *cv)

만약 cv 컨디션이 만족되길 기다리는 쓰레드가 있으면 그 쓰레드를 깨운다

• 1개만 깨우는 경우: 깨어난 쓰레드가 lock을 얻는다.
• 여러개를 깨우는 경우(broadcast): 여럿 중 하나만 lock을 얻음
• 기다리는 쓰레드가 없으면 그냥 리턴한다.

 

---

Condition Variable 예시 (1): Parent-Child Thread

• Parent thread는 thr_join 함수를 통해서 자식 쓰레드가 thr_exit을 통해 signal을 보내길 기다린다.
• Child thread는 자신이 할 일을 하고, thr_exit을 통해서 state variable을 세팅하고 parent 쓰레드에게 signal을 보낸다.

 

CV는 State Variable과 함께 사용해야 한다.

아래의 코드에 있는 thr_exit과 thr_join 함수를 사용해서 parent-child 쓰레드 프로그램을 실행한다고 해보자. 만약 parent에서 wait를 하기도 전에 child에서 signal을 해버리면 signal이 그냥 지나가게 되고 parent는 영영 깨어날 수 없는 상태가 된다.

 

void thr_exit() {
    Pthread_mutex_lock(&m);
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}

void thr_join() {
    Pthread_mutex_lock(&m);
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}

 

위와 같은 경우를 방지하기 위해서 다음과 같이 state variable을 사용해서 state check를 먼저 해주어야 한다.

 

void thr_exit() {
    Pthread_mutex_lock(&m);
    done = 1;
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}

void thr_join() {
    Pthread_mutex_lock(&m);
    while (done == 0)
        Pthread_cond_wait(&c);
    Pthread_mutex_unlock(&m);
}

 

이 때 꼭 명심해야 할 사항은 다음과 같다.

 

1. State variable도 쓰레드 간 공유되는 변수이므로 상호배제가 필요하다.
2. State variable을 통한 조건 체크는 반드시 while loop을 통해서 해야하며 if문을 사용하면 문제가 된다. 

위 조건을 만족하지 않으면 문제가 발생하는 이유를 생각해보자. 위의 코드에서 mutex lock과 unlock 하는 부분을 제거하고, while 대신에 if가 들어가면 다음과 같은 문제 상황이 발생할 수 있다.

 

• if (done == 0)과 Pthread_cond_wait(&c); 사이에서 interrupt가 걸려서 child로 컨트롤이 넘어간다.
• Child에서는 done을 1로 세팅하고 parent로 signal을 보낸다.
• Interrupt 이전에는 done이 0이어서 while loop body로 들어오게 되었고, Pthread_con_wait을 호출하게 된다.
• Parent가 wait하기도 전에 이미 child에서 signal을 보냈기 때문에 그 signal을 날아가 버렸고, parent는 영영 깨어나지 못하게 된다. 

 

 

Condition Variable 예시 (2): Producer-Consumer Problem

Producer-Consumer의 예시

1. Web server에서 client와 server 간의 통신

int buffer[MAX];
int fill = 0;	// put할 index
int use = 0;	// get할 index
int count = 0;	// buffer 내의 item 개수

void put(int value) {
    buffer[fill] = value;
    fill = (fill + 1) % MAX;
    count ++;
}

int get() {
    int tmp = buffer[use];
    use = (use + 1) % MAX;
    count--;
    return tmp;
}


// 2개의 CV를 사용하면 wake up all 할 필요 없다.
cond_t empty;	// producer의 조건 변수
cond_t fill;	// consumer의 조건 변수
mutex_t mutex;

void *producer(void *arg) {
   	for (int i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        while (count == MAX) {
            Pthread_cond_wait(&empty, &mutex);
        }
        put(i);
        Pthread_cond_signal(&fill);
        Pthread_mutex_unlock(&mutex);
    }
}

void *consumer(void *arg) {
    for (int i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        while (count == 0)
            Pthread_cond_wait(&fill, &mutex);
        int tmp = get(i);
        Pthread_cond_signal(&empty);
        Pthread_mutex_unlock(&mutex);
        printf("%d\n", tmp);
    }
}

위의 코드에서 주목할 부분은 다음과 같다.

 

• Producer를 위한 CV(empty)와 consumer를 위한 CV(fill) 2개를 사용하였다. 만약 2개의 CV를 사용하지 않고 1개만 사용을 한다면 다음과 같은 문제가 발생할 수 있다.
  1. Producer 쓰레드(P1) 1개와 Consumer 쓰레드(C1, C2) 2개가 있다고 하자. 이들은 모두 동일한 CV를 공유한다.
  2. C1이 get()을 한 뒤에 signal(CV)을 보낸다. 이 때 의도는 P1을 깨워서 새로운 item을 put()하게 만들려는 것이다.
  3. 하지만 C1, C2, P1이 동일한 CV를 공유하기 때문에 P1이 아니라 C2가 깨어난다.
  4. C2는 buffer의 count가 0인 것을 확인하고 wait(CV, mutex)를 한다.
  5. 모든 쓰레드가 잠든 상태가 되었다.
• 2개의 CV를 사용하지 않고서 위와 같은 문제를 해결하는 방법은 signal(CV)를 했을 때 모든 쓰레드를 깨우는 것이다. 하지만 모든 쓰레드를 깨우면 굳이 깨어날 필요가 없는 쓰레드까지 깨어나서 이들을 다시 sleep 시켜야 할 수도 있고, context switch overhead도 더 커진다.