1Synchronization: Going DeeperSynchronization: Going DeeperSharedLockSharedLock: Reader/Writer Lock: Reader/Writer LockA reader/write lock or SharedLock is a new kind of “lock” that is similar to our old definition:• supports Acquire and Release primitives• guarantees mutual exclusion when a writer is presentBut: a SharedLock provides better concurrency for readers when no writer is present.class SharedLock {AcquireRead(); /* shared mode */AcquireWrite(); /* exclusive mode */ReleaseRead();ReleaseWrite();}often used in database systemseasy to implement using mutexesand condition variablesa classic synchronization problemReader/Writer Lock IllustratedReader/Writer Lock IllustratedArMultiple readers may holdthe lock concurrently in shared mode.Writers always hold the lock in exclusive mode, and must wait for all readers or writer to exit.mode read write max allowedshared yes no manyexclusive yes yes onenot holder no no manyArRrRrRwAwIf each thread acquires the lock in exclusive (*write) mode, SharedLock functions exactly as an ordinarymutex.Reader/Writer Lock: First CutReader/Writer Lock: First Cutint i; /* # active readers, or -1 if writer */Lock rwMx ;Condition rwCv ;SharedLock::AcquireWrite() {rwMx.Acquire();while (i != 0)rwCv.Wait(&rwMx);i = -1;rwMx.Release();}SharedLock::AcquireRead() {rwMx.Acquire();while (i < 0)rwCv.Wait(&rwMx);i += 1;rwMx.Release();}SharedLock::ReleaseWrite() {rwMx.Acquire();i = 0;rwCv.Broadcast();rwMx.Release();}SharedLock::ReleaseRead() {rwMx.Acquire();i -= 1;if (i == 0)rwCv.Signal();rwMx.Release();}The LittleThe Little MutexMutexInsideInside SharedLockSharedLockArArRrRrRwArAwRrLimitations of theLimitations of the SharedLockSharedLockImplementationImplementationThis implementation has weaknesses discussed in [Birrell89].• spurious lock conflicts (on a multiprocessor): multiple waiters contend for the mutex after a signal or broadcast.Solution: drop themutex before signaling.(If the signal primitive permits it.)• spurious wakeupsReleaseWrite awakens writers as well as readers.Solution: add a separate condition variable for writers.• starvationHow can we be sure that a waiting writer will everpass its acquire if faced with a continuous stream of arriving readers?2Reader/Writer Lock: Second TryReader/Writer Lock: Second TrySharedLock::AcquireWrite() {rwMx.Acquire();while (i != 0)wCv.Wait(&rwMx);i = -1;rwMx.Release();}SharedLock::AcquireRead() {rwMx.Acquire();while (i < 0) ...rCv.Wait(&rwMx);...i += 1;rwMx.Release();}SharedLock::ReleaseWrite() {rwMx.Acquire();i = 0;if (readersWaiting)rCv.Broadcast();elsewcv.Signal();rwMx.Release();}SharedLock::ReleaseRead() {rwMx.Acquire();i -= 1;if (i == 0)wCv.Signal();rwMx.Release();}Guidelines for Condition VariablesGuidelines for Condition Variables1. Understand/document the condition(s) associated with each CV.What are the waiters waiting for?When can a waiter expect a signal?2. Always check the condition to detect spurious wakeups after returning from a wait: “loop before you leap”!Another thread may beat you to the mutex.The signaler may be careless.A single condition variable may have multiple conditions.3. Don’t forget: signals on condition variables do not stack!A signal will be lost if nobody is waiting: always check the wait condition before calling wait.StarvationStarvationThe reader/writer lock example illustrates starvation: under load, a writer will be stalled forever by a stream of readers.• Example: a one-lane bridge or tunnel.Wait for oncoming car to exit the bridge before entering.Repeat as necessary.• Problem: a “writer” may never be able to cross if faced with a continuous stream of oncoming “readers”.• Solution: some reader must politely stop before entering, even though it is not forced to wait by oncoming traffic.Use extra synchronization to control the lock scheduling policy.Complicates the implementation: optimize only if necessary.DeadlockDeadlockDeadlock is closely related to starvation.• Processes wait forever for each other to wake up and/or release resources.• Example: traffic gridlock .The difference between deadlock and starvation is subtle.• With starvation, there always exists a schedule that feeds the starving party.The situation may resolve itself…if you’re lucky.• Once deadlock occurs, it cannot be resolved by any possible future schedule.…though there may exist schedules that avoiddeadlock.Dining PhilosophersDining Philosophers• N processes share N resources• resource requests occur in pairs• random think times• hungry philosopher grabs a fork• ...and doesn’t let go• ...until the other fork is free• ...and the linguine is eatenwhile(true) {Think();AcquireForks();Eat();ReleaseForks();}D BAC1234Four Preconditions for DeadlockFour Preconditions for DeadlockFour conditions must be present for deadlock to occur: 1. Non-preemptability. Resource ownership (e.g., by threads) is non-preemptable.Resources are never taken away from the holder.2. Exclusion. Some thread cannot acquire a resource that is held by another thread.3. Hold-and-wait. Holder blocks awaiting another resource.4. Circular waiting. Threads acquire resources out of order.3Resource GraphsResource GraphsGiven the four preconditions, some schedules may lead to circular waits.• Deadlock is easily seen with a resource graph or wait-for graph.The graph hasa vertex for each process and each resource.If process A holds resource R, add an arcfrom R to A.If process A is waiting for resource R, add an arc from A to R.The system is deadlocked iff the wait-for graph has at least one cycle.21BAA grabs fork 1 andwaitsfor fork 2.B grabs fork 2 andwaitsfor fork 1.SnassignrequestNot All Schedules Lead to CollisionsNot All Schedules Lead to CollisionsThe scheduler chooses a path of the executions of the threads/processes competing for resources.Synchronization constrains the schedule to avoid illegal states.Some paths “just happen” to dodge dangerous states as well.What is the probability that philosophers will deadlock?• How does the probability change as:think times increase?number of philosophers increases?12YA1 A2 R2 R1A2A1R1R2RTG for Two PhilosophersRTG for Two Philosophers12XSnSmSnSm(There are really only 9 states wecare about: the important transitionsare allocate and release events.)12YXA1 A2 R2 R1A2A1R1R2Two Philosophers Living DangerouslyTwo Philosophers Living Dangerously???12YXA1 A2 R2 R1A2A1R1R2The Inevitable ResultThe Inevitable Resultno legal