class: center, middle background-image: url(include/title-background.svg) # COMP35112 Chip Multiprocessors <br/> <br/> # .white[Synchronisation in Parallel Programming - Condition Variables] .white[Pierre Olivier] ??? - Hi everyone, we have seen previously two synchronisation mechanisms that are barriers and more importantly locks - In this video we will briefly talk about a third one, condition variables --- # Event Signalling - **Sleeping or busy-waiting for the buffer to be non-full/non-empty is suboptimal** - Example with thread trying to deposit in a full buffer: .leftcol[ ```c while(full) { pthread_mutex_unlock(&b->lock); usleep(100); pthread_mutex_lock(&b->lock); full = (b->count == b->max_elements); } ``` ] ??? - Recall our bounded buffer example from the lecture on locks - Threads may need to wait for the buffer to become non-full/non-empty - For example a thread attempting to extract from an empty buffer needs to wait for it to become non empty - Same thing for a thread attempting to deposit in a buffer that is full - There are two intuitive solutions to implement that wait - The one we saw previously involves sleeping in a loop until the condition we wait for becomes true, here it is the buffer becoming non-full -- .rightcol[ ```c while(full) { pthread_mutex_unlock(&b->lock); /* busy wait */ pthread_mutex_lock(&b->lock); full = (b->count == b->max_elements); } ``` ] ??? - Another approach is busy waiting: we get rid of the sleep and the thread will keep trying non-stop until the condition becomes true - Note that in that case we still need to unlock the buffer's lock to give a chance to other threads to access the queue and make the condition we wait for become true -- without this other threads will starve -- - With the `usleep` set to an arbitrary time, may sleep for a much longer time than needed - Without usleep, keep trying non-stop, monopolising the CPU and wasting cycles ??? - Both solutions are suboptimal - Sleeping for an arbitrary time may lead to long wakeup latencies - And busy waiting wastes a lot of CPU cycles because the threads keeps trying non-stop --- # Event Signalling - Sleeping or busy-waiting for the buffer to be non-full/non-empty is suboptimal - Example with thread trying to deposit in a full buffer: .leftcol[ ```c while(full) { pthread_mutex_unlock(&b->lock); usleep(100); pthread_mutex_lock(&b->lock); full = (b->count == b->max_elements); } ``` <div style="text-align:center"><img src="include/condvar-sleep.svg" width=400 /></div> ] .rightcol[ ```c while(full) { pthread_mutex_unlock(&b->lock); /* busy wait */ pthread_mutex_lock(&b->lock); full = (b->count == b->max_elements); } ``` <div style="text-align:center"><img src="include/condvar-spin.svg" width=400 /></div> ] ??? - This is illustrated on these two schemas - On the left we have the sleeping case - We have two threads, and the second one first access the buffer - Say it tries to deposit something but the buffer is full - So at regular intervals, here every 100 microseconds it's going to check if the buffer is still full and if so it will sleep for another 100 microseconds - The good thing here is that during all that time, something else can use that CPU core - Imaging now in the meantime another thread, thread 1, extracts something from the queue - Once its critical section is done, at the end of its red block on the schema, thread 2 could actually perform its deposit operation because the buffer is not full anymore - However thread 2 is in the middle of its 100 microseconds sleep so it will have to wait until the end of that sleep operation to be able to start making progress - This is why sleeping may lead to long wakeup delays - On the left we have a similar situation but this time with busy waiting - Because it keeps checking when the buffer becomes non-full, thread 2 has a much shorter wakeup delay compared to the sleeping solution - However, during the entire busy waiting period, thread 2 monopolises the CPU and nothing else can use that core --- # Condition Variables .leftcol[ - Used to signal threads waiting for a conjunction of: 1. **A lock becoming free** and 2. **An arbitrary event** (e.g. buffer becoming non-full) - Best of both worlds: thread wakes up right when needed, without monopolising the CPU by spinning ] ??? - So the condition variable is a synchronisation primitive that can address this problem - It is used for event signalling - More precisely, it allows to signal threads that sleep waiting for a conjunction of two events: a lock becoming free, and an arbitrary condition becoming true, for example the buffer becoming non-full or non-empty - You may ask yourself why is there the condition regarding the lock in addition to the arbitrary event - The reason is first that the implementation requires it, the condition variable need to be itself protected from concurrent accesses with the lock - And second, such a primitive is generally used to synchronise access to shared data structures which is something that itself requires a lock -- .rightcol[ <div style="text-align:center"><img src="include/condvar-full.svg" width=500 /></div> ] ??? - With condition variables you get the best of both worlds - As you can see on the bottom schema - Not only a waiting thread wakes up with a very low latency - But it also wait by sleeping so it does not hang the CPU --- # Applying Condition Variables to Our Example <div style="text-align:center"><img src="include/bb-condvar1.svg" width=700 /></div> ??? - So conceptually how would it work with our example - Assume a thread wants to deposit in a buffer that is full --- # Applying Condition Variables to Our Example <div style="text-align:center"><img src="include/bb-condvar2.svg" width=700 /></div> ??? - We want to use a condition variable to indicate when the buffer becomes non-full - With the buffer's lock held, the thread will call a function to sleep on that condition variable --- # Applying Condition Variables to Our Example <div style="text-align:center"><img src="include/bb-condvar3.svg" width=700 /></div> ??? - Later say another thread extracts an element from the buffer --- # Applying Condition Variables to Our Example <div style="text-align:center"><img src="include/bb-condvar4.svg" width=700 /></div> ??? - If the extracting thread realises it made the buffer non-full, it calls a function to signal that the condition relative to the condition variable has happened --- # Applying Condition Variables to Our Example <div style="text-align:center"><img src="include/bb-condvar5.svg" width=700 /></div> ??? - When the extracting thread releases the lock, that will trigger the awakening of the thread waiting, which will grab the lock and finally perform its deposit --- # Applying Condition Variables to Our Example <div style="text-align:center"><img src="include/bb-condvar6.svg" width=700 /></div> ??? - We similarly use a condition variable to represent the buffer becoming non-empty - When a thread attempts to deposit an element into an empty buffers it waits on that condition variable - Another thread depositing something and realising it makes the buffer non-empty will then signal that variable, waking up the deposit thread so it can perform its operation --- # Condition Variables .leftcol[ ```c void deposit(bounded_buffer *b, int message) { pthread_mutex_lock(&b->lock); int full = (b->count == b->max_elements); while(full) { // wait on condfull to be signalled // when the buffer becomes non-full // and the lock is free * pthread_cond_wait(&b->condfull, &b->lock); // we hold the lock here full = (b->count == b->max_elements); } b->buffer[b->in_index] = message; b->in_index = (b->in_index + 1) % b->max_elements; //signal condempty if buf. becomes non-empty * if(b->count++ == 0) * pthread_cond_signal(&b->condempty); pthread_mutex_unlock(&b->lock); } ``` ] .rightcol[ ```c int extract(bounded_buffer *b) { pthread_mutex_lock(&b->lock); int empty = !(b->count); while(empty) { // wait on condempty to be signalled when // the buffer becomes non-empty // and the lock is free * pthread_cond_wait(&b->condempty, &b->lock); empty = !(b->count); } int message = b->buffer[b->out_index]; b->out_index = (b->out_index + 1) % b->max_elements; //signal condfull if buf. becomes non-full * if(b->count-- == b->max_elements) * pthread_cond_signal(&b->condfull); pthread_mutex_unlock(&b->lock); return message; } ``` .codelink[<a href="src/condvar.c" download>`08b-condition-variables/condvar.c`</a> <a href="https://github.com/olivierpierre/comp35112-devcontainer" target="_blank" style="text-decoration: none"><img src="include/gh-logo.svg" style="height: 1em" ></a><a href="https://www.programiz.com/online-compiler/6yAJ6k6nYdhI4" target="_blank" style="text-decoration: none"><img src="include/programiz-logo.png" style="height: 1em"></a>] ] ??? - Now that's a lot of steps but the code is actually quite simple because the condition variable's implementation takes care of a lot of things for you - Here is just show you the updates to the deposit and extract functions, you can check the rest of the code to see how to initialise the condition variables it's pretty straightforward - A deposit thread realising the buffer is full waits on the corresponding condition variable with `pthread_cond_wait`, which takes a pointer to the condition variable data structure as well as a pointer to the buffer's lock as parameters - Notice that it needs to be called with the lock held - Under the hood `pthread_cond_wait` will release that lock and put the thread to sleep - On the other side, an extracting thread realising that the buffer becomes non-full will signal that condition variable with pthread_cond_signal to wake up a thread waiting on it - The waiting thread will then return from `pthread_cond_wait` - It holds the lock at that point, but still need to check the condition, because another thread may have been able to deposit an element in the meantime - If the buffer is still non-full it can proceed with the deposit - Things work similarly for the "buffer non-empty" condition variable - A thread attempting to extract from an empty buffer will wait on it - And a deposit thread that makes a buffer non-empty will signal that variable - This pattern of waiting and checking the condition in a loop is very common and you'll probably use something similar each time you need a condition variable --- # Summary - **Condition variables**: useful mechanism for event signalling - Avoid delayed wakeup resulting from arbitrary sleeps - Avoid wasting CPU cycle due to busy waiting - Next lecture: more about locks ??? - And that's it - We talked about condition variable, a synchronisation primitive used for event signalling - It avoid the wasting CPU cycles that comes with busy waiting, and also provides low wakeup latencies - In the next video we'll talk more about locks and the dangers of making mistakes when implementing your synchronisation strategy