6_Mutual_Exclusion

1 .Mutual Exclusion 1 Lecture 6: Mutual Exclusion Learning Goals Define mutual exclusion and describe its use Define and differentiate between an atomic operation and a critical section Create your own mutual exclusion class from scratch using atomic operations Create your own lock class that uses RAII principles to guarantee exception safety Use a mutex and lock to prevent inter-thread race conditions in a code example Use an inter-process mutex to prevent race conditions between multiple processes Identify critical sections in a provided task or code © Paul Davies, C. Antonio Sanchez. Not to be copied, used, or revised without explicit written permission from the copyright owner.

2 .Mutual Exclusion Mutual Exclusion 2 … neither can live while the other survives ~J.K. Rowling Mutual Exclusion: If any thread is accessing a resource, all others are excluded from doing so. Certain resources cannot be used simultaneously by two or more processes/threads without interfering with each other in a detrimental way We require a way to limit access, so that if one process/thread is using a resource, all others are forced to wait until the resource becomes available.

3 .Mutual Exclusion Mutual Exclusion 3 Hardware Resources Requiring Mutual Exclusion Printers. Memory I/O devices such as Graphics Displays Disk Files The OS takes care of the problem by using print spoolers , memory allocation algorithms and device drivers , windowing software (i.e. one window per process) built into the kernel to queue up accesses to the resource. Q: How do we implement this in our own software?

4 .Race Conditions Mutual Exclusion 4 void threadinc( size_t & counter) { for ( size_t i= 0 ; i< 5000000 ; ++i) { counter += 1 ; } } X 3 Reads the current value of counter Adds 1 to that value Stores the new value back to counter

5 .Race Conditions Mutual Exclusion 5 Miscellaneous Read value of a ( 0 ) Add 1 to value ( 1 ) Store back a ( 1 ) Miscellaneous Miscellaneous Read value ( 0 ) Add 1 to value ( 1 ) Store back ( 1 ) Miscellaneous CPU/Core P1 Miscellaneous Read value of a ( 0 ) Add 1 to value ( 1 ) Store back a ( 1 ) Miscellaneous Miscellaneous Read value ( 0 ) Add 1 to value ( 1 ) Store back ( 1 ) Miscellaneous CPU/Core P2 0 1 0 Actual ‘counter’ Error: ‘a’ has only been incremented once instead of twice Data Data Data Data

6 .Critical Section Mutual Exclusion 6 void threadinc( size_t & counter) { for ( size_t i= 0 ; i< 5000000 ; ++i) { counter += 1 ; } } Critical Section: a section of code in which it is critical that the instructions not be interrupted by another thread or process.

7 .Mutual Exclusion: How would you do it? Mutual Exclusion 7 void threadinc( size_t & counter) { for ( size_t i= 0 ; i< 5000000 ; ++i) { ... ? ... counter += 1 ; ... ? ... } }

8 .Mutual Exclusion: How would you do it? Mutual Exclusion 8 void threadinc( bool & usage_flag, size_t & counter) { // increment for ( size_t i= 0 ; i< 5000000 ; ++i) { // wait until not being used while (usage_flag == true ) {} usage_flag = true ; counter += 1 ; // let next thread use counter usage_flag = false ; } } Protect operation with a flag? Multiple steps: two threads can concurrently see flag as false, then set to true

9 .Mutual Exclusion: How would you do it? Mutual Exclusion 9 Read Write CPU 1 Address Bus R/W Signal Think Data Out 1 (Busy) Data In 0 (Free) 1 0 Read Write Address Bus R/W Signal Think Data Out 1 (Busy) Data In 0 (Free) 1 0 CPU 2 e.g. 10nS e.g. 10nS e.g. 10nS e.g. 10nS

10 .Mutual Exclusion: How would you do it? Mutual Exclusion 10 void threadinc( bool & usage_flag, size_t & counter) { // increment for ( size_t i= 0 ; i< 5000000 ; ++i) { // wait until not being used while (usage_flag == true ) {} usage_flag = true ; counter += 1 ; // let next thread use counter usage_flag = false ; } } We want this to be captured in a single, uninterrupted operation

11 .Mutual Exclusion: How would you do it? Mutual Exclusion 10 void threadinc( bool & usage_flag, size_t & counter) { // increment for ( size_t i= 0 ; i< 5000000 ; ++i) { // wait until not being used while (usage_flag == true ) {} usage_flag = true ; counter += 1 ; // let next thread use counter usage_flag = false ; } } We want this to be captured in a single, uninterrupted operation

12 .Atomic Operations in Assembly Mutual Exclusion 12 pushq % rbp movq % rsp, % rbp movb $ 120 , - 9 ( % rbp) movl $ 10 , - 8 ( % rbp) movl - 8 ( % rbp), % eax movl % eax, - 4 ( % rbp) addl $ 1 , - 4 ( % rbp) nop popq % rbp ret %rbp : 64-bit stack “base” pointer %rsp : 64-bit stack “top” pointer %eax : 32-bit general purpose %rax : 64-bit general purpose %rbx : 64-bit general purpose %rcx : 64-bit general purpose %rdx : 64-bit general purpose void is_this_atomic() { char x = x ; int y = 10 ; int z = y ; z += 1 ; }

13 .Atomic Operations in Assembly Mutual Exclusion 13 pushq % rbp movq % rsp, % rbp movq % rdi, - 24 ( % rbp) movq $ 0 , - 8 ( % rbp) .L36: cmpq $ 4999999 , - 8 ( % rbp) ja .L37 movq - 24 ( % rbp), % rax movq ( % rax), % rax leaq 1 ( % rax), % rdx movq - 24 ( % rbp), % rax movq % rdx, ( % rax) addq $ 1 , - 8 ( % rbp) jmp .L36 .L37: nop popq % rbp ret void threadinc(size_t& counter) { for (size_t i= 0 ; i<5000000; ++i) { counter += 1 ; } }

14 .Atomic Operations in Assembly Mutual Exclusion 14 .L37: movq - 24 ( % rbp), % rax movzbl ( % rax), % eax testb % al, % al je .L36 jmp .L37 .L36: movq - 24 ( % rbp), % rax movb $ 1 , ( % rax) while (usage_flag == true) {} usage_flag = true;

15 .Atomic Operations Mutual Exclusion 15 CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=295612 atomic: cannot be broken down into smaller parts We want some way to check that our flag has been cleared and if so, simultaneously set it. An atomic operation is a single operation which cannot be interrupted by the real-time clock interrupt (time-slicing), or by another thread (e.g. when accessing shared memory).

16 .Atomic Flags in C++11 Mutual Exclusion 16 http://en.cppreference.com/w/cpp/atomic/atomic_flag

17 .Atomic vs Critical Section Mutual Exclusion 17 void threadinc(std::atomic_flag& usage_flag, size_t& counter) { // increment for (size_t i= 0 ; i< 5000000 ; ++i) { // wait until not being used while (usage_flag.test_and_set() == true ) {} counter += 1 ; // clear to let others access counter usage_flag.clear(); } } atomic critical section

18 .Mutual Exclusion: How would you do it? Mutual Exclusion 18 void threadinc(std::atomic_flag& usage_flag, size_t& counter) { // increment for (size_t i= 0 ; i< 5000000 ; ++i) { // wait until not being used while (usage_flag.test_and_set() == true ) {} counter += 1 ; // clear to let others access counter usage_flag.clear(); } } lock: unlock:

19 .Spin-Lock Mutual Exclusion 19 // wait until not being used while (usage_flag.test_and_set() == true ) {} ... // clear to let others access counter usage_flag.clear(); lock: Notes: Atomic flag initialization std :: atomic_flag usage_flag = ATOMIC_FLAG_INIT ; Spin-wait should yield to other threads rather than loop indefinitely while (usage_flag.test_and_set() == true ) { std :: this_thread ::yield(); } unlock:

20 .(Mut)ual (Ex)clusion Mutual Exclusion 20 http://en.cppreference.com/w/cpp/thread/mutex

21 .Mutex Mutual Exclusion 21 void threadinc(std::mutex& mutex, size_t& counter) { // increment for (size_t i= 0 ; i< 5000000 ; ++i) { // wait until not being used mutex.lock() counter += 1 ; // clear to let others access counter mutex.unlock(); } } lock: unlock:

22 .Mutex Mutual Exclusion 22 Always remember to unlock, or you could lock everyone out of using a resource!!! void threadinc(std::mutex& mutex, size_t& counter) { // increment for (size_t i= 0 ; i< 5000000 ; ++i) { // wait until not being used mutex.lock() counter += 1 ; } } Only the thread who locks the mutex can unlock it!!!

23 .Mutex: Exception Safety Mutual Exclusion 23 #include <exception> struct TenMillionException : public std :: exception { const char * what() const noexcept { return "ten million exception" ; } }; // increments the counter by 1, throwing an // exception at 10 million void increment( size_t & counter) { if (counter == 10000000 ) { throw TenMillionException (); } ++counter; } // increments counter by 5 million in increments of 1 void threadinc( std :: mutex & mutex, size_t & counter) { for ( size_t i= 0 ; i< 5000000 ; ++i) { mutex.lock(); increment(counter); // might throw exception mutex.unlock(); } } // catches any exception to prevent program termination void threadcatch( std :: mutex & mutex, size_t & counter) { try { threadinc(mutex, counter); } catch ( std :: exception & ex) { std ::cout << "An exception was thrown: " << ex.what() << std ::endl; } }

24 .Mutex: Exception Safety Mutual Exclusion 24 Solution: use RAII principles, destructors guaranteed to be called!! #include <mutex> class lock { std::mutex& mutex_; // reference to a mutex public : lock(std::mutex& mutex) : mutex_(mutex) { mutex_.lock(); // lock in constructor } ~lock() { mutex_.unlock(); // unlock in destructor } }; void threadinc(std::mutex& mutex, size_t& counter) { for (size_t i= 0 ; i< 5000000 ; ++i) { { lock mylock(mutex); // locks mutex counter += 1 ; } // mutex guaranteed to be unlocked } }

25 .Locks Mutual Exclusion 25

26 .Locks Mutual Exclusion 26 void threadinc(std::mutex& mutex, size_t& counter) { for (size_t i= 0 ; i< 5000000 ; ++i) { { // locks mutex std::lock_guard<std::mutex> mylock(mutex); counter += 1 ; } // mutex guaranteed to be unlocked } } void threadinc(std::mutex& mutex, size_t& counter) { for (size_t i= 0 ; i< 25 00000 ; ++i) { { // locks mutex std::unique_lock<std::mutex> mylock(mutex); counter += 1 ; mylock.unlock(); // ... do other stuff mylock.lock(); counter += 1 ; } // mutex guaranteed to be unlocked } } lock_guard: unique_lock:

27 .Mutexes and Locks Between Processes Mutual Exclusion 27 The current std::atomic_flag and std::mutex only work between threads in the same process. To coordinate between separate processes , we need a mechanism to create a mutex that is accessible without needing to share the same virtual memory block. Most operating systems provide a mutex implementation that is accessible using a name or path . If a mutex with the given name doesn’t exist, the OS kernel will create one. If a mutex with the name does exist, the OS kernel will return it so the process can share access to it.

28 .Mutexes and Locks Between Processes Mutual Exclusion 28 https://msdn.microsoft.com/en-us/library/windows/desktop/ms682411(v=vs.85).aspx void threadinc( size_t & counter) { // connect to mutex named "windows_mutex" HANDLE mutex = CreateMutex ( NULL , FALSE , "windows_mutex" ); for ( int i= 0 ; i< 5000000 ; ++i) { WaitForSingleObject(mutex, INFINITE ); // lock ++counter; ReleaseMutex(mutex); // unlock } CloseHandle(mutex); } Windows:

29 .Mutexes and Locks Between Processes Mutual Exclusion 29 CPEN333 Library: #include <cpen333/process/mutex.h> void threadinc( size_t & counter) { // inter-process mutex cpen333 :: process :: mutex mutex( "process_mutex" ); // increment for ( size_t i= 0 ; i< 500000 ; ++i) { // locks std :: lock_guard < cpen333 :: process :: mutex > lock(mutex); counter += 1 ; } }