Sometimes we want a thread to check if a condition is true before continuing execution.
You could just use a global variable and check that, but the spinning is expensive.
A condition variable is a queue that threads put themselves in when some condition is not satisfied. This is considered waiting. When some other thread changes the state, it will wake one or more of the threads in the queue. This is called signaling.
A condition variable (at least in POSIX C) has wait and signal operations.
wait will release the lock and put the calling thread to sleep atomically. When the thread wakes up (after being signaled), it will reacquire the lock before proceeding.
Below is a simple piece of code: The parent spawns a child, and waits for the child to exit before resuming.
int done = 0;
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 p;
Pthread_create(&p, NULL, child, NULL);
thr_join();
printf("parent: end\n");
return 0;
}
Note that we must have the global state done. Without it we’ll have a race condition.
It is good practice to always hold the lock when signaling. It is not always necessary, but just do it! It is necessary to hold the lock when waiting!
The Producer/Consumer Problem
The producer/consumer problem: One or more threads is producing items for consumption by one or more threads. We want to place the produced items somewhere (e.g. buffer), but:
- We must ensure we don’t try to put something in the buffer when it is full.
- We must ensure we don’t try to consume something when the buffer is empty.
Broken Solution
Here is one broken solution:
int loops; // must initialize somewhere...
cond_t cond;
mutex_t mutex;
void *producer(void *arg) {
int i;
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;
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);
}
}
The reason this is broken: What if we have more than one consumer thread? Suppose the first consumer thread goes to sleep (nothing in the buffer). Then the producer wakes and puts something in there. That wakes up the first consumer thread. But now another consumer thread can sneak in and consume the value. The first consumer thread will now try to consume something from an empty buffer.
How can the second consumer thread sneak in? The wake operation tries to acquire the lock, but another consumer can acquire it first!
If it’s not clear, signaling a thread only wakes it up. It wakes up because there was a change in the condition, but there is no guarantee that that condition has remained changed after it wakes up!
To solve this, replace the if with a while. This forces the consumer to check the condition again after waking up.
The moral: Always use while loops! Another reason is you can have spurious wakeups - wakeups even when there shouldn’t be one. A while loop will always check and go back to sleep.
But we still have a bug: We really should have two mutexes! Here’s a trace of what can go wrong: Assume two consumers are asleep, and nothing is in the buffer. The producer puts a value in the buffer and it’s full, and it goes to sleep. Now a consumer is woken and consumes it. This will cause another thread to wake up. That thread should be the producer, but it’s actually the other consumer. That other consumer sees nothing in the buffer and goes to sleep. Now there is nothing to trigger the producer to wake up!
Here is the real solution:
cond_t empty, fill;
mutex_t mutex;
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex);
while (count == 1)
Pthread_cond_wait(&empty, &mutex);
put(i);
Pthread_cond_signal(&fill);
Pthread_mutex_unlock(&mutex);
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex);
while (count == 0)
Pthread_cond_wait(&fill, &mutex);
int tmp = get();
Pthread_cond_signal(&empty);
Pthread_mutex_unlock(&mutex);
printf("%d\n", tmp);
}
}
Consumers should not wake other consumers!
All the above code is for a buffer that allows only one value. To generalize to any buffer size, make the buffer an array and sleep/wakeup only when the buffer is full/empty. You’ll need a global counter that keeps track of the contents of the buffer.
int buffer[MAX];
int fill_ptr = 0;
int use_ptr = 0;
int count = 0;
void put(int value) {
buffer[fill_ptr] = value;
fill_ptr = (fill_ptr + 1) % MAX;
count++;
}
int get() {
int tmp = buffer[use_ptr];
use_ptr = (use_ptr + 1) % MAX;
count--;
return tmp;
}
cond_t empty, fill;
mutex_t mutex;
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex);
while (count == MAX)
Pthread_cond_wait(&empty, &mutex); // p3
put(i);
Pthread_cond_signal(&fill);
Pthread_mutex_unlock(&mutex);
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock(&mutex);
while (count == 0)
Pthread_cond_wait(&fill, &mutex); // c3
int tmp = get();
Pthread_cond_signal(&empty);
Pthread_mutex_unlock(&mutex);
printf("%d\n", tmp);
}
}
Covering Conditions
Another common problem: You want to allocate a certain amount of memory, but that amount may not be currently free. So you sleep until it is.
Suppose one thread needs 100MB, and another needs 10MB. Now a thread releases 50 MB. You want the latter thread to wake up, but it could keep waking up threads that aren’t useful.
The solution is to instead of waking up one thread, broadcast this to all sleeping threads. All will wake up, and so one of them will get it.
This is an example of a covering condition. It is costly, but it works.
BTW, if you find your program works when you change from signals to broadcasts, you likely have a bug!