The Synchronization ToolboxMutual ExclusionLocksExample: Per-Thread Counts and TotalUsing Locks: An ExampleReading Between the Lines of CPortrait of a Lock in MotionCondition VariablesA New Synchronization Problem: Ping-PongPing-Pong with Sleep/Wakeup?Ping-Pong with Mutexes?Mutexes Don’t Work for Ping-PongPing-Pong Using Condition VariablesBounded Resource with a Condition VariableSemaphores using Condition VariablesSemaphoresA Bounded Resource with a Counting SemaphoreThe Roots of Condition Variables: MonitorsHoare SemanticsMesa SemanticsFrom Monitors to Mx/Cv PairsMutual Exclusion in JavaWait/Notify in JavaWhat to Know about Sleep/WakeupSemaphores as MutexesSpin-Yield: Just Say NoThe “Magic” of Semaphores and CVsSemaphores vs. Condition VariablesGuidelines for Choosing Lock GranularityTricks of the Trade #1Things Your Mother Warned You About #1More Locking GuidelinesGuidelines for Condition VariablesStuff to KnowThe Synchronization ToolboxThe Synchronization ToolboxMutual ExclusionMutual ExclusionRace conditions can be avoiding by ensuring mutual exclusion in critical sections.•Critical sections are code sequences that are vulnerable to races.Every race (possible incorrect interleaving) involves two or more threads executing related critical sections concurrently.•To avoid races, we must serialize related critical sections.Never allow more than one thread in a critical section at a time.1. BAD2. interrupted critsec BAD3. GOODLocksLocksLocks can be used to ensure mutual exclusion in conflicting critical sections.•A lock is an object, a data item in memory.Methods: Lock::Acquire and Lock::Release.•Threads pair calls to Acquire and Release.•Acquire before entering a critical section.•Release after leaving a critical section.•Between Acquire/Release, the lock is held.•Acquire does not return until any previous holder releases.•Waiting locks can spin (a spinlock) or block (a mutex).AARR/* shared by all threads */int counters[N];int total;/* * Increment a counter by a specified value, and keep a running sum. * This is called repeatedly by each of N threads. * tid is an integer thread identifier for the current thread. * value is just some arbitrary number. */voidTouchCount(int tid, int value){counters[tid] += value;total += value;}Example: Per-Thread Counts and TotalExample: Per-Thread Counts and TotalUsing Locks: An ExampleUsing Locks: An Exampleint counters[N];int total;Lock *lock;/* * Increment a counter by a specified value, and keep a running sum. */voidTouchCount(int tid, int value){lock->Acquire();counters[tid] += value; /* critical section code is atomic...*/total += value; /* …as long as the lock is held */lock->Release();}Reading Between the Lines of CReading Between the Lines of C/* counters[tid] += value; total += value;*/load counters, R1 ; load counters baseload 8(SP), R2 ; load tid indexshl R2, #2, R2 ; index = index * sizeof(int)add R1, R2, R1 ; compute index to arrayload 4(SP), R3 ; load valueload (R1), R2 ; load counters[tid]add R2, R3, R2 ; counters[tid] += valuestore R2, (R1) ; store back to counters[tid]load total, R2 ; load totaladd R2, R3, R2 ; total += valuestore R2, total ; store totalvulnerable between load and store of counters[tid]...but it’s non-shared.vulnerable between load and store of total, which is shared.loadaddstoreloadaddstorePortrait of a Lock in MotionPortrait of a Lock in MotionAARRCondition VariablesCondition VariablesCondition variables allow explicit event notification.•much like a souped-up sleep/wakeup•associated with a mutex to avoid sleep/wakeup racesCondition::Wait(Lock*)Called with lock held: sleep, atomically releasing lock.Atomically reacquire lock before returning.Condition:: Signal(Lock*)Wake up one waiter, if any.Condition::Broadcast(Lock*)Wake up all waiters, if any.A New Synchronization Problem: Ping-PongA New Synchronization Problem: Ping-PongvoidPingPong() { while(not done) { if (blue) switch to purple;if (purple) switch to blue; }}How to do this correctly using sleep/wakeup?How to do it without using sleep/wakeup?Ping-Pong with Sleep/Wakeup?Ping-Pong with Sleep/Wakeup?voidPingPong() { while(not done) { blue->Sleep(); purple->Wakeup();}}voidPingPong() { while(not done) { blue->Wakeup(); purple->Sleep(); }}Ping-Pong with Mutexes?Ping-Pong with Mutexes?voidPingPong() { while(not done) { Mx->Acquire(); Mx->Release(); }}Mutexes Don’t Work for Ping-PongMutexes Don’t Work for Ping-PongPing-Pong Using Condition VariablesPing-Pong Using Condition VariablesvoidPingPong() { mx->Acquire(); while(not done) { cv->Signal(); cv->Wait(); } mx->Release();}See how the associated mutex avoids sleep/wakeup races?Bounded Resource with a Condition VariableBounded Resource with a Condition VariableMutex* mx;Condition *cv;int AllocateEntry() {int i;mx->Acquire();while(!FindFreeItem(&i))cv.Wait(mx);slot[i] = 1;mx->Release();return(i);}void ReleaseEntry(int i) {mx->Acquire();slot[i] = 0;cv->Signal();mx->Release();}“Loop before you leap.”Why is this Acquire needed?Semaphores using Condition VariablesSemaphores using Condition Variablesvoid Down() {mutex->Acquire();ASSERT(count >= 0);while(count == 0)condition->Wait(mutex);count = count - 1;mutex->Release();}void Up() {mutex->Acquire();count = count + 1;condition->Signal(mutex);mutex->Release();}This constitutes a proof that mutexes and condition variables are at least as powerful as semaphores.(Loop before you leap!)SemaphoresSemaphoresSemaphores handle all of your synchronization needs with one elegant but confusing abstraction.•controls allocation of a resource with multiple instances•a non-negative integer with special operations and propertiesinitialize to arbitrary value with Init operation“souped up” increment (Up or V) and decrement (Down or P)•atomic sleep/wakeup behavior implicit in P and VP does an atomic sleep, if the semaphore value is zero.P means “probe”; it cannot decrement until the semaphore is positive.V does an atomic wakeup.num(P) <= num(V) + initA Bounded Resource with a Counting SemaphoreA Bounded Resource with a Counting Semaphoresemaphore->Init(N);int AllocateEntry() {int i;semaphore->Down();ASSERT(FindFreeItem(&i));slot[i] = 1;return(i);}void ReleaseEntry(int i) {slot[i] = 0;semaphore->Up();}A semaphore for an N-way resourceis called a counting semaphore.A caller that gets past a Down is guaranteed that a resource instance is