Condition Variables

Condition Variables

• There are many cases where a thread wishes to check whether a condition is true before continuing its execution.
• Example:
  • A parent thread might wish to check whether a child thread has completed.
  • This is often called a join().

---

How to wait for a condition

Condition variable

• Queue of threads
• Waiting on the condition
  • An explicit queue that threads can put themselves on when some state of execution is not as desired.
• Signaling on the condition
  • Some other thread, when it changes it state, can wake one of those waiting threads and allow them to continue.

기존에는 while문을 사용하여 해당 쓰레드가 실행되지 못하도록 구현하였는데 CPU의 소모가 매우 컸다. 따라서 thread를 block한 상태로 queue에 넣었다가 다른 thread가 signaling을 해주면 ready 상태가 되는 식으로 구현해줘야 한다.

---

Definition and Routines

---

Parent waiting for Child : Use a condition variable

done이라는 변수는 반드시 있어야 한다.

만약 done이 없다면 child가 즉시 실행될 경우 blocked 된 parent를 깨울 방법이 없다.

---

Parent wating for Child : Use a condition variable

Parent:

• Creates the child thread and continues running itself.
• Calls into thr_join() to wait for the child thread to complete.
  • Acquires the lock.
  • Checks if the child is done.
  • Puts itself to sleep by calling wait().
  • Releases the lock.

Child:

• Prints the message "child".
• Calls thr_exit() to wake up the parent thread.
  • Grabs the lock.
  • Sets the state variable done.
  • Signals the parent thus waking it.

---

Another poor implementation

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

void thr_join(){
	if(done==0)
    	Pthread_cond_wait(&c);
}

The issue here is a subtle race condition.

• The parent calls thr_join().
  • The parent checks the value of done.
  • It will see that it is 0 and try to go to sleep
  • Just before it calls wait to go to sleep, the parent is interrupted and the child runs.
• The child changes the state variable done to 1 and signals.
  • But no thread is wating and thus no thread is woken.
  • When the parents again, it sleeps forever.

---

The Producer / Consumer (Bound Buffer) Problem

Producer

• Produce data items
• Wish to place data items in a buffer

Consumer

• Grab data items out of the buffer consume them in some way

Example : Multi-threaded web server

• A producer puts HTTP requests in to a work queue
• Consumer threads take requests out of this queue and process them.

---

Producer/Consumer : Single CV and If Statement

void *producer(void *arg){
    int i;
    int loops = (int) arg;
    for(i = 0; i < loops; i++){
        Pthread_mutex_lock(&mutex);             // p1 lock을 건다.
        if(count == 1)                          // p2 buffer가 채워져 있는지 확인
            Pthread_cond_wait(&cond,&mutex);    // p3 buffer가 채워져 있다면 wait
        put(i);                                 // p4 buffer에 값을 넣는다
        Pthread_cond_signal(&cond);             // p5 signal을 보내 consumer를 깨운다.
        Pthread_mutex_unlock(&mutex);           // p6 lock 해제
    }
}

void *consumer(void *arg){
    int i;
    while(1){
        Pthread_mutex_lock(&mutex);             // c1 lock을 건다.
        if(count == 0)                          // c2 buffer가 비워져 있는지 확인
            Pthread_cond_wait(&cond,&mutex);    // c3 buffer가 비워져 있다면 wait
        int tmp = get();                        // c4 buffer값을 가져온다.
        Pthread_cond_signal(&cond);             // c5 signal을 보내 producer를 깨운다.
        Pthread_mutex_unlock(&mutex);           // c6 lock 해제
        printf("%d\n",tmp);
    }
}

• p1-p3 : A producer waits for the buffer to be empty.
• c1-c3 : A consumer waits for the buffer to be full.
• With just a single producer and a single consumer, the code works.

위의 코드는 consumer와 producer가 1개가 존재 할 때만 돌아가는 코드이다.

만약 각각이 2개 이상일 경우는 어떡할까?

위는 consumer가 2개이고 producer가 1개일 때 buffer를 읽는 것을 나타낸 것이다.

consumer1이 data를 읽으려 했지만 data가 없으므로 sleep이 되고 producer1이 buffer에 값을 넣어주고 consumer들을 깨웠다.

여기서 consumer2가 먼저 buffer값에 접근하여 값을 가져갔고, consumer1은 이미 if(count==0)을 지나온 상태이기 때문에 buffer가 비어있다는 조건을 지나친채 buffer에 접근하게 되고 에러가 나게 된다.

---

Thread Trace : Broken Solution (Version 1)

The problem arises for a simple reason:

• After the producer woke Tc1, but before Tc1 ever ran, the state of the bounded buffer changed by Tc2.
• There is no guarantee that when the woken thread runs, the state will still be as desired -> Mesa semantics
  • Virtually every system ever built employs Mesa semantics.

thread가 깨어났을 때, 상황이 thread가 signal을 받았을 때와 같을거라는 보장이 없다. 이를 Mesa semantics라고 한다.

 

Hoare semantics provides a stronger guarantee that the woken thared will run immediately upon being woken.

 

Hoare semantics는 thread가 일어났을 때와 실행될 때의 상황이 똑같게 보장해준다.

---

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 lock을 건다.
        while(count==1)                         // p2 buffer가 채워져 있는지 확인
            Pthread_cond_wait(&cond,&mutex);    // p3 buffer가 채워져 있다면 wait
        put(i);                                 // p4 buffer에 값을 넣는다
        Pthread_cond_signal(&cond);             // p5 signal을 보내 consumer를 깨운다.
        Pthread_mutex_unlock(&mutex);           // p6 lock 해제
    }
}

void *consumer(void *arg){
    int i;
    while(1){
        Pthread_mutex_lock(&mutex);             // c1 lock을 건다.
        while(count==0)                          // c2 buffer가 비워져 있는지 확인
            Pthread_cond_wait(&cond,&mutex);    // c3 buffer가 비워져 있다면 wait
        int tmp = get();                        // c4 buffer값을 가져온다.
        Pthread_cond_signal(&cond);             // c5 signal을 보내 producer를 깨운다.
        Pthread_mutex_unlock(&mutex);           // c6 lock 해제
        printf("%d\n",tmp);
    }
}

위 처럼 count의 값을 while문을 사용하여 다시 확인하게 한다면 아까와 같은 상황은 피할 수 있다.

하지만 여전히 완벽한 코드는 아니다.

Consumer가 다른 Consumer를 깨운 경우 Producer를 다시 깨울 방법이 없어 모든 thread가 잠드는 상황이 발생하게 된다. 

---

The single Buffer Producer/Consumer Solution

cond_t empty,fill;
mutex_t mutex;

void *producer(void *arg){
    int i;
    int loops = (int) arg;
    for(i = 0; i < loops; i++){
        Pthread_mutex_lock(&mutex);             // p1 lock을 건다.
        while(count==1)                         // p2 buffer가 채워져 있는지 확인
            Pthread_cond_wait(&empty,&mutex);   // p3 buffer가 채워져 있다면 wait
        put(i);                                 // p4 buffer에 값을 넣는다
        Pthread_cond_signal(&fill);             // p5 signal을 보내 consumer를 깨운다.
        Pthread_mutex_unlock(&mutex);           // p6 lock 해제
    }
}

void *consumer(void *arg){
    int i;
    while(1){
        Pthread_mutex_lock(&mutex);             // c1 lock을 건다.
        while(count==0)                         // c2 buffer가 비워져 있는지 확인
            Pthread_cond_wait(&fill,&mutex);    // c3 buffer가 비워져 있다면 wait
        int tmp = get();                        // c4 buffer값을 가져온다.
        Pthread_cond_signal(&empty);            // c5 signal을 보내 producer를 깨운다.
        Pthread_mutex_unlock(&mutex);           // c6 lock 해제
        printf("%d\n",tmp);
    }
}

 

condition variable를 두 개를 사용하여, consumer는 producer만을, producer는 consumer만을 깨우하면 된다.