Outline for TodaySemaphoresSemaphore UsagePowerPoint PresentationProducer / ConsumerSlide 6Tweedledum and TweedledeeThe code shown above exhibits a well-known synchronization flaw. Outline a scenario in which this code would fail, and the outcome of that scenarioShow how to fix the problem by replacing the Sleep and Wakeup calls with semaphore P (down) and V (up) operations.Monitor AbstractionCondition VariablesNachos-style SynchronizationSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Classic Problems5 Dining PhilosophersTemplate for PhilosopherNaive SolutionSimplest Example of DeadlockConditions for DeadlockPhilosophy 101 (or why 5DP is interesting)Dealing with DeadlockSlide 27Hold and Wait Condition1Outline for Today•Objective: –To continue talking about the critical section problem and get more practice thinking about possible interleavings. –Start talking about synchronization primitives.–Introduce other “classic” concurrency problems•Administrative details: –Look on the web for TAs’ office hours or check newsgroup for UTAs’ office hours for assignment 1.–On collecting problem sets…2Semaphores•Well-known synchronization abstraction•Defined as a non-negative integer with two atomic operationsP(s) - [wait until s > 0; s--]V(s) - [s++]•The atomicity and the waiting can be implemented by either busywaiting or blocking solutions.Reminder: notation [ ] = atomic3Semaphore Usage•Binary semaphores can provide mutual exclusion (solution of critical section problem)•Counting semaphores can represent a resource with multiple instances (e.g. solving producer/consumer problem)•Signaling events (persistent events that stay relevant even if nobody listening right now)4while (1){ ...other stuff...critical section}The Critical Section ProblemP(mutex)V(mutex)Semaphore:mutex initially 1Fill in the boxes5Producer / ConsumerProducer:while(whatever){ locally generate itemfill empty buffer with item}Consumer:while(whatever){get item from full bufferuse item}6Producer / ConsumerProducer:while(whatever){ locally generate itemfill empty buffer with item}Consumer:while(whatever){get item from full bufferuse item}P(emptybuf);V(fullbuf);P(fullbuf);V(emptybuf);Semaphores: emptybuf initially N; fullbuf initially 0;7Tweedledum and Tweedledee•Separate threads executing their respective procedures. The idea to cause them to forever take turns exchanging insults through the shared variable X in strict alternation. •The Sleep() and Wakeup() routines operate as follows: –Sleep blocks the calling thread, – Wakeup unblocks a specific thread if that thread is blocked, otherwise its behavior is unpredictable8The code shown above exhibits a well-known synchronization flaw. Outline a scenario in which this code would fail, and the outcome of that scenariovoid Tweedledum() { while(1) { Sleep(); x = Quarrel(x); Wakeup(Tweedledee); } }void Tweedledee() { while(1) { x = Quarrel(x); Wakeup(Tweedledum); Sleep(); } }If dee goes first to sleep, the wakeup is lost (since dum isn’tsleeping yet). Both sleep forever.9Show how to fix the problem by replacing the Sleep and Wakeup calls with semaphore P (down) and V (up) operations. void Tweedledum() { while(1) { Sleep(); x = Quarrel(x); Wakeup(Tweedledee); } }void Tweedledee() { while(1) { x = Quarrel(x); Wakeup(Tweedledum); Sleep(); } }P(dum);V(dee);semaphore dee = 0;semaphore dum = 0;V(dum);P(dee):10Monitor Abstraction•Encapsulates shared data and operations with mutual exclusive use of the object (an associated lock).•Associated Condition Variables with operations of Wait and Signal.monitor_lockenQ deQinitshared dataentry queuenotEmptyconditions11Condition Variables•We build the monitor abstraction out of a lock (for the mutual exclusion) and a set of associated condition variables.•Wait on condition: releases lock held by caller, caller goes to sleep on condition’s queue. When awakened, it must reacquire lock.•Signal condition: wakes up one waiting thread. •Broadcast: wakes up all threads waiting on this condition.12Nachos-style Synchronizationsynch.h, cc•SemaphoresSemaphore::PSemaphore::V•Locks and condition variablesLock::AcquireLock::ReleaseCondition::Wait (conditionLock)Condition::Signal (conditionLock)Condition::Broadcast (conditionLock)13Monitor Abstractionmonitor_lockenQ deQinitshared dataentry queuenotEmptyconditionsEnQ:{Lock->Acquire ( );if (head == null){head = item;notEmpty->Signal (Lock);}else tail->next = item;tail = item; Lock->Release( );}deQ:{Lock->Acquire (lock);if (head == null)notEmpty->Wait (lock); item = head; if (tail == head) tail = null; head=item->next;Lock->Release( );}14Monitor Abstractionmonitor_lockenQ deQinitshared dataentry queuenotEmptyconditionsEnQ:{Lock->Acquire ( );if (head == null){head = item;notEmpty->Signal (Lock);}else tail->next = item;tail = item; Lock->Release( );}deQ:{Lock->Acquire (lock);if (head == null)notEmpty->Wait (lock); item = head; if (tail == head) tail = null; head=item->next;Lock->Release( );}15EnQ:{Lock->Acquire ( );if (head == null){head = item;notEmpty->Signal (Lock);}else tail->next = item;tail = item; Lock->Release( );}deQ:{Lock->Acquire (lock);if (head == null)notEmpty->Wait (lock); item = head; if (tail == head) tail = null; head=item->next;Lock->Release( );} Monitor Abstractionmonitor_lockenQ deQinitshared dataentry queuenotEmptyconditions16EnQ:{Lock->Acquire ( );if (head == null){head = item;notEmpty->Signal (Lock);}else tail->next = item;tail = item; Lock->Release( );}deQ:{Lock->Acquire (lock);if (head == null)notEmpty->Wait (lock); item = head; if (tail == head) tail = null; head=item->next;Lock->Release( );} Monitor Abstractionmonitor_lockenQ deQinitshared dataentry queuenotEmptyconditions17EnQ:{Lock->Acquire ( );if (head == null){head = item;notEmpty->Signal (Lock);}else tail->next = item;tail = item; Lock->Release( );}deQ:{Lock->Acquire (lock);if (head == null)notEmpty->Wait (lock); item = head; if (tail == head) tail = null; head=item->next;Lock->Release( );} Monitor Abstractionmonitor_lockenQ deQinitshared dataentry queuenotEmptyconditions18EnQ:{Lock->Acquire ( );if (head == null){head = item;notEmpty->Signal (Lock);}else tail->next = item;tail = item; Lock->Release( );}deQ:{Lock->Acquire (lock);if (head == null)notEmpty->Wait (lock); item = head; if (tail == head) tail = null;