The 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: PerExample: Per--Thread Counts and TotalThread 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: PingA New Synchronization Problem: Ping--PongPongvoidPingPong() {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?PingPing--Pong with Sleep/Wakeup?Pong with Sleep/Wakeup?voidPingPong() {while(not done) {blue->Sleep();purple->Wakeup();}}voidPingPong() {while(not done) {blue->Wakeup();purple->Sleep();}}PingPing--Pong withPong withMutexesMutexes??voidPingPong() {while(not done) {Mx->Acquire();Mx->Release();}}MutexesMutexesDon’t Work for PingDon’t Work for Ping--PongPongPingPing--Pong Using Condition VariablesPong 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 mutexesand 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 reserved for it.Problems?Note: the current value of the semaphore is the number of resource instances free to allocate.But semaphores do not allow a thread to read this value directly. Why not?The Roots of Condition Variables: MonitorsThe Roots of Condition Variables: MonitorsA monitor is a module (a collection of procedures) in which execution is serialized.P1()P2()P3()P4()statereadyto enterblockedwait()At most one thread may be active in the monitor at a time.(exit)(enter)A thread may wait in the monitor, allowing another thread to enter.A thread in the monitor may signal a waiting thread, causing it to return from its wait and reenter the monitor.signal()CVs are easier to understand if we think about them in terms of the original monitor formulation.[Brinch Hansen 1973, C.A.R. Hoare 1974]Hoare SemanticsHoare SemanticsP1()P2()P3()P4()statereadyto enterwaitingwait()(exit)(enter)Hoare semantics: the signaled thread immediately takes over the monitor, and the signaler is suspended.signal()(Hoare)Hoare semantics allow the signaled thread