14_Condition_Variables

1 .Lecture 14 – Condition Variables Distinguish between events and conditions Describe the function of a condition variable and how it can be used to implement events and conditions Describe the issue of spurious wakeups , and how we can deal with them for events and conditions Use condition variables to solve a synchronization task, both within a single process and between multiple processes Learning Goals © Paul Davies, C. Antonio Sanchez. Not to be copied, used, or revised without explicit written permission from the copyright owner.

2 .Interthread/process Synchronization So far we have seen: thread/process joining – wait for each thread/process to finish mutex – wait until a single resource or critical section becomes free semaphores – wait until one of a countable number of resources is free Condition Variables 2 In concurrent systems, if two threads/processes are dependent , we often need to wait until some task is complete before we can continue. Conditions: wait until a condition is set by some other thread/process

3 .Traffic Light Control System Condition Variables 3 Pedestrians wait for walk light Cars wait for traffic light How would you do it?

4 .Events and Conditions Used to wait until something happens to trigger threads to continue. Condition Variables 4 Event : an instantaneously pulsed occurrence. When triggered, causes one or all waiting threads to wake up and continue. Future threads attempting to wait will block until the next trigger. Think: start gun of a race. Condition : an occurrence with a persisted state. When triggered, causes all waiting threads to wake up and continue. Future threads attempting to wait will continue without blocking until the condition is manually reset. Think: doorway or gate

5 .Traffic Light Control System Condition Variables 5 Cars wait until light turns green, future cars continue if still green Pedestrains wait until walk sign turns on, future pedestrians continue if still on Pedestrian light waits until button pressed, future light changes will wait until button pressed again.

6 .Condition Variable Condition Variables 6 Condition variables allow us to implement both events and conditions. They rely on data shared between threads, and consist of: A synchronization primitive that supports wait() , notify_one() and notify_all() An optional predicate to determine if the thread should continue (thread will wait until predicate evaluates to true ) When waiting on a condition variable, the current thread will block. When the condition variable is notified , either one or all waiting threads are awoken, ready to check any shared data to see if the thread should continue waiting.

7 .Condition Variable Condition Variables 7 A B C D Condition Variable N wait() notify_one() notify_all()

8 .Condition Variable with Predicate Condition Variables 8 A B C D Condition Variable N wait() notify_one() notify_all() predicate(): false true Predicate still false, so will again block Still waiting to be notified of predicate change

9 .Condition Variable When should we use a condition variable? Condition Variables 9 Events: Let through a group at a time Any stragglers must wait for the next event Condition: Let through a group at a time Any stragglers will still be allowed through until we close the gate In general, when we are interested in non-counting synchronization, letting one or all waiting threads/processes through.

10 .C++11 Condition Variables Condition Variables 10 http://en.cppreference.com/w/cpp/thread/condition_variable

11 .C++11 Condition Variables Condition Variables 11 { // wait for event notification std :: unique_lock < decltype (mutex)> lock(mutex); cv.wait(lock); } // wake up all waiting threads cv.notify_all(); { // wait for condition notification std :: unique_lock < decltype (mutex)> lock(mutex); // only wait if condition not set while (!ready) { cv.wait(lock); } } { // modify condition state std :: lock_guard < decltype (mutex)> guard(mutex); ready = true ; } // notify waiting threads of change cv.notify_all(); Event Condition wait notify std :: mutex mutex; std :: condition_variable cv; bool ready = false ;

12 .C++11 Condition Variables Condition Variables 12 // wait for condition notification { std :: unique_lock < decltype (mutex)> lock{mutex}; // lock is acquired, all shared data is protected // in critical section // check on shared data while (!ready) { // internally releases lock and goes to sleep cv.wait(lock); // lock re-acquired } } // lock released Must use same mutex Must use unique_lock Lock is re-acquired after wait one awoken thread exits at a time

13 .C++11 Condition Variables Condition Variables 13 The while() loop pattern is so common that in C++ they built it in to the condition variable allowing you to specify a “predicate” function: { std :: unique_lock < decltype (mutex)> lock{mutex}; while (!ready) { cv.wait(lock); } } { std :: unique_lock < decltype (mutex)> lock{mutex}; cv.wait(lock, [&](){ return ready; } ); } Predicates are anything that can be evaluated as a boolean expression: bool predicate() . They are most often implemented using in-line lambdas: auto predicate = [&](){ return ready; } capture (& by reference) arguments expression

14 .Condition Variables: Typical Usage CVs are usually used as “conditions” that depend on shared data . The typical usage-pattern is as follows. Condition Variables 14 Notifying Thread: lock mutex modify shared data unlock mutex notify CV (one or all) Waiting Thread: lock mutex loop until shared data satisfies predicate wait unlock mutex

15 .Condition Variable When should we use a condition variable? Condition Variables 15 Events: Let through a group at a time Any stragglers must wait for the next event Condition: Let through a group at a time Any stragglers will still be allowed through until we close the gate In general, when we are interested in non-counting synchronization, letting one or all waiting threads/processes through.

16 .Spurious Wakeups Condition Variables 16 Sometimes threads are woken by the OS without having received a proper notification from the condition variable. E.g. after your process receives an interrupt signal. We call these spurious wake-ups, and are considered to be rare events. However, it breaks the standard “event” implementation. Q: Why don’t spurious wakeups affect the “condition” implementation? { std :: unique_lock < decltype (mutex)> lock(mutex); cv.wait(lock); // could wake up “spuriously” }

17 .Spurious Wakeups Sometimes these rare spurious wake-ups can be harmless. E.g. triggering a pedestrian crossing. Other times we may need to fix them. Observation: Events are like Conditions, except they get “reset” immediately after threads awoken Condition Variables 17 { std :: unique_lock < decltype (mutex)> lock{mutex}; while (!ready) { cv.wait(lock); } ready = false; // reset condition state } { // modify condition state std :: lock_guard < decltype (mutex)> guard(mutex); ready = true ; } // notify waiting threads of change cv.notify_all(); Failed Attempt #1:

18 .Condition Variables 18 A B C D Condition Variable N wait() notify_one() notify_all() ready: false true C & D wake up but see ready as false, so go back to sleep { std :: unique_lock < decltype (mutex)> lock{mutex}; while (!ready) { cv.wait(lock); } ready = false; // reset condition state } Spurious Wakeups

19 .Spurious Wakeups We need to wait until all desired threads (one or all) have passed condition barrier before resetting condition. Condition Variables 19 void release_one() { { // wait for condition notification std :: lock_guard < std :: mutex > lock(mutex); release = 1 ; // release one } cv.notify_one(); } void release_all() { { // wait for condition notification std :: lock_guard < std :: mutex > lock(mutex); release = waiting; // release all } cv.notify_all(); } void wait() { std :: unique_lock < std :: mutex > lock(mutex); ++waiting; // track # threads waiting // wait until release while (release == 0 ) { cv.wait(lock); } --release; // one thread was released --waiting; // one less thread waiting } Failed Attempt #2:

20 .Spurious Wakeups Condition Variables 20 A B C D Condition Variable N wait() notify_one() notify_all() waiting: 0 release: 0 C woke up but left waiting because D took his spot void wait() { std :: unique_lock < std :: mutex > lock(mutex); ++waiting; // track # threads waiting while (release == 0 ) { cv.wait(lock); } --release; // one thread was released --waiting; // one less thread waiting } 1 1 2 2 3 release one release all

21 .Spurious Wakeups Issues when trying to release all waiting threads and a new thread comes along and calls wait() between the start of the release operation and the time the last originally waiting thread resets release to zero. This is a race condition , could lead to issues if some important threads are left waiting forever. Solution: Stop new threads from calling wait() (requires an additional semaphore) Let new threads through – they are essentially arriving near the same time as the release call anyways (requires a boolean) Condition Variables 21

22 .Spurious Wakeups Condition Variables 22 void release_one() { { // wait for condition notification std :: lock_guard < std :: mutex > lock(mutex); release = 1 ; // release one } cv.notify_one(); } void release_all() { { // wait for condition notification std :: lock_guard < std :: mutex > lock(mutex); release = waiting; // release all all = true ; // releasing all } cv.notify_all(); } void wait() { std :: unique_lock < std :: mutex > lock(mutex); ++waiting; // track # threads waiting // arrived while still releasing all if (all) { ++release; // release me too } // wait until notification signals some to release while (release == 0 ) { cv.wait(lock); } --release; // one thread was released if (release == 0 ) { // cause future threads will wait all = false ; } --waiting; // one less thread waiting } Attempt #3:

23 .Condition Variables 23 A B C D Condition Variable N wait() notify_one() notify_all() waiting: 0 all: false release: 0 void wait() { std :: unique_lock < std :: mutex > lock(mutex); ++waiting; if (all) { ++release; } cv.wait(lock, [&](){ return release != 0 ;} ); --release; if (release == 0 ) { all = false ; } --waiting; } 1 1 2 2 3 release one release all 3 true Spurious Wakeups

24 .Spurious Wakeups We solved the spurious wake-up problem by “holding the door open” until the last waiting thread has passed through. This should work well in most cases, since the time taken to release all threads is typically very short. If a new thread arrives at the event during this time, we are essentially pretending it has arrived a few milliseconds earlier and assuming this precise timing is of no importance . This is not a true event behaviour, however. To truly fix this, we need to introduce a second condition variable to block new threads while the other condition is open. This doubles the synchronization overhead . Condition Variables 24

25 .Interprocess Condition Variables The standard C++11 std::condition_variable only works between threads within a single process . To create a condition variable for interpress synchronization, we can use the CPEN333 course library. Condition Variables 25 class condition_variable : public virtual named_resource { public : condition_variable( const std::string &name); // constructor void wait(std::unique_lock<cpen333::process::mutex>& lock); // waits to be notified // continues to wait until the predicate is true and cv is notified template < typename Predicate> void wait(std::unique_lock<cpen333::process::mutex>& lock, Predicate pred); void notify_one(); // awakes one waiting thread void notify_all(); // awakes all waiting threads bool unlink(); // unlinks name from condition variable (POSIX) }; Unlike std::condition_variable , these do not suffer from spurious wakes.

26 .Condition Variables 26 int main() { cpen333 :: process :: mutex mutex( "traffic_mutex" ); cpen333 :: process :: condition_variable cv( "traffic_cv" ); cpen333 :: process :: shared_object < TrafficLightInfo > light( "traffic_light" ); // initialize to green light std :: unique_lock < decltype (mutex)> lock(mutex); light -> green = true ; light -> walk = false ; lock.unlock(); while ( true ) { // flip lights lock.lock(); light -> green = !light -> green ; light -> walk = !l ight -> walk ; lock.unlock(); cv.notify_all(); // notify threads of change std :: this_thread ::sleep_for( std :: chrono :: seconds ( 60 )); } return 0 ; } int main() { cpen333 :: process :: mutex mutex( "traffic_mutex" ); cpen333 :: process :: condition_variable cv( "traffic_cv" ); cpen333 :: process :: shared_object < TrafficLightInfo > light( "traffic_light" ); // wait for green light std :: unique_lock < decltype (mutex)> lock(mutex); cv.wait(lock, [&](){ return light -> green ; }); std ::cout << "Driving through" << std ::endl; return 0 ; } int main() { // start with traffic light off cpen333 :: process :: mutex mutex( "traffic_mutex" ); cpen333 :: process :: condition_variable cv( "traffic_cv" ); cpen333 :: process :: shared_object < TrafficLightInfo > light( "traffic_light" ); // wait for walk light std :: unique_lock < decltype (mutex)> lock(mutex); cv.wait(lock, [&](){ return light -> walk ; }); std ::cout << "Walking through" << std ::endl; return 0 ; } Traffic Light Controller Car Pedestrian

27 .Homework Use Case Diagrams 27 https://www.youtube.com/watch?v=18_kVlQMavE Go through the tutorial on Sequence Diagrams in Visual Paradigm Go through the course library examples in: examples/q9_condition examples/q10_condition_variable examples/q11_event examples/q12_rendezvous Quiz 5 next week on UML