![Operating Systems: Three Easy Pieces [Concurrency Ch.5: Condition Variables]](https://cdn.hashnode.com/res/hashnode/image/upload/v1634688244309/7IPM3diYp.jpeg?w=1600&h=840&fit=crop&crop=entropy&auto=compress,format&format=webp)
Condition variables
A condition variable is an explicit queue that threads can put themselves on when some state of execution (i.e., some condition) is not as desired (by waiting on the condition); some other thread, when it changes said state, can then wake one (or more) of those waiting threads and thus allow them to continue (by signaling on the condition).
A condition variable has two operations associated with it: wait() and signal(). The wait() call is executed when a thread wishes to put itself to sleep; the signal() call is executed when a thread has changed something in the program and thus wants to wake a sleeping thread waiting on this condition.
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;
}
There are two cases to consider. In the first, the parent creates the child thread but continues running itself (assume we have only a single processor) and thus immediately calls into thr join() to wait for the child thread to complete. In this case, it will acquire the lock, check if the child is done (it is not), and put itself to sleep by calling wait() (hence releasing the lock). The child will eventually run, print the message “child”, and call thr exit() to wake the parent thread; this code just grabs the lock, sets the state variable done, and signals the parent thus waking it. Finally, the parent will run (returning from wait() with the lock held), unlock the lock, and print the final message “parent: end”. In the second case, the child runs immediately upon creation, sets done to 1, calls signal to wake a sleeping thread (but there is none, so it just returns), and is done. The parent then runs, calls thr join(), sees that done is 1, and thus does not wait and returns. One last note: you might observe the parent uses a while loop instead of just an if statement when deciding whether to wait on the condition. While this does not seem strictly necessary per the logic of the program, it is always a good idea, as we will see below.
A wrong version that you might think thats right
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);
}
Imagine the case where the child runs immediately and calls thr exit() immediately; in this case, the child will signal, but there is no thread asleep on the condition. When the parent runs, it will simply call wait and be stuck; no thread will ever wake it, and thats why conditional variables are important
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. Specifically, if the parent calls thr join() and then checks the value of done, it will see that it is 0 and thus try to go to sleep. But 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 waiting and thus no thread is woken. When the parent runs again, it sleeps forever.
hold the lock when calling wait, is not just a tip, but rather mandated by the semantics of wait, because wait always
(a) assumes the lock is held when you call it
(b) releases said lock when putting the caller to sleep, and
(c) re-acquires the lock just before returning
however, there are some other cases where it is likely OK not to, but probably is something you should avoid.
The Producer/Consumer (Bounded Buffer) Problem
Imagine one or more producer threads and one or more consumer threads. Producers generate data items and place them in a buffer; consumers grab said items from the buffer and consume them in some way
This arrangement occurs in many real systems.. For example, in a multi-threaded web server, a producer puts HTTP requests into a work queue (i.e., the bounded buffer)
Because the bounded buffer is a shared resource, we must of course require synchronized access to it, or a race condition arise
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);
}
}
Let’s understand the first problem, which has to do with the if statement before the wait. Assume there are two consumers (Tc1 and Tc2) and one producer (Tp). First, a consumer (Tc1) runs; it acquires the lock (c1), checks if any buffers are ready for consumption (c2), and finding that none are, waits (c3) (which releases the lock). Then the producer (Tp) runs. It acquires the lock (p1), checks if all
buffers are full (p2), and finding that not to be the case, goes ahead and fills the buffer (p4). The producer then signals that a buffer has been filled (p5). Critically, this moves the first consumer (Tc1) from sleeping on a condition variable to the ready queue; Tc1 is now able to run (but not yet running). The producer then continues until realizing the buffer is full, at which point it sleeps (p6, p1–p3). Here is where the problem occurs: another consumer (Tc2) sneaks in and consumes the one existing value in the buffer (c1, c2, c4, c5, c6, skipping the wait at c3 because the buffer is full). Now assume Tc1 runs; just before returning from the wait, it re-acquires the lock and then returns. It then calls get() (c4), but there are no buffers to consume! An assertion triggers, and the code has not functioned as desired. Clearly, we should have somehow prevented Tc1 from trying to consume because Tc2 snuck in and consumed the one value in the buffer that had been produced.
this image shows the action each thread takes, as well as its scheduler state (Ready, Running, or Sleeping) over time.
While instead of if
change the if to a while. Think about why this works; now consumer Tc1 wakes up and (with the lock held) immediately re-checks the state of the shared variable (c2). If the buffer is empty at that point, the consumer simply goes back to sleep (c3). The corollary if is also changed to a while in the producer (p2).
Thanks to Mesa semantics, a simple rule to remember with condition variables is to always use while loops
However, this code still has a bug, the second of two problems mentioned above. Can you see it? It has something to do with the fact that there is only one condition variable. Try to figure out what the problem is, before reading ahead.
The problem occurs when two consumers run first (Tc1 and Tc2) and both go to sleep (c3). Then, the producer runs, puts a value in the buffer, and wakes one of the consumers (say Tc1). The producer then loops back (releasing and reacquiring the lock along the way) and tries to put more data in the buffer; because the buffer is full, the producer instead waits on the condition (thus sleeping). Now, one consumer is ready to run (Tc1), and two threads are sleeping on a condition (Tc2 and Tp). We are about to cause a problem: things are getting exciting! The consumer Tc1 then wakes by returning from wait() (c3), re-checks the condition (c2), and finding the buffer full, consumes the value (c4). This consumer then, critically, signals on the condition (c5), waking only one thread that is sleeping. However, which thread should it wake? Because the consumer has emptied the buffer, it clearly should wake the producer. However, if it wakes the consumer Tc2 (which is definitely possible, depending on how the wait queue is managed), we have a problem. Specifically, the consumer Tc2 will wake up and find the buffer empty (c2), and go back to sleep (c3)
The producer Tp, which has a value to put into the buffer, is left sleeping. The other consumer thread, Tc1, also goes back to sleep. All three threads are left sleeping, a clear bug
Signaling is clearly needed, but must be more directed. A consumer should not wake other consumers, only producers, and vice-versa.
Another solution to avoid
Bad solution can be pthread cond broadcast(), which wakes up all waiting threads. By doing so, we guarantee that any threads that should be woken are The downside, of course, can be a negative performance impact, as we might needlessly wake up many other waiting threads that shouldn’t (yet) be awake. Those threads will simply wake up, re-check the condition, and then go immediately back to sleep. This called covering condition, as it covers all the cases where a thread needs to wake up (conservatively
The Single Buffer Producer/Consumer Solution
The solution here is once again a small one: use two condition variables, instead of one, in order to properly signal which type of thread should wake up when the state of the system changes.
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);
}
}
Now lets take more step
We now have a working producer/consumer solution, but not a fully general one. The last change we make is to enable more concurrency and efficiency; specifically, we add more buffer slots, so that multiple values can be produced before sleeping, and similarly multiple values can be consumed before sleeping
The first change for this correct solution is within the buffer structure itself and the corresponding put() and get()
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--;
r
}
We also slightly change the conditions that producers and consumers check in order to determine whether to sleep or not. We also show the correct waiting and signaling logic
cond_t empty, fill;
mutex_t mutex;
void * producer(void * arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock( & mutex); // p1
while (count == MAX) // p2
Pthread_cond_wait( & empty, & mutex); // p3
put(i); // p4
Pthread_cond_signal( & fill); // p5
Pthread_mutex_unlock( & mutex); // p6
}
}
void * consumer(void * arg) {
int i;
for (i = 0; i < loops; i++) {
Pthread_mutex_lock( & mutex); // c1
while (count == 0) // c2
Pthread_cond_wait( & fill, & mutex); // c3
int tmp = get(); // c4
Pthread_cond_signal( & empty); // c5
Pthread_mutex_unlock( & mutex); // c6
printf("%d\n", tmp);
}
}
condition variables enable us to neatly solve a number of important synchronization problems, including the famous (and still important) producer/consumer problem. Hope you enjoyed reading this chapter.