Outline for TodayClassic Synchronization ProblemsProducer / ConsumerProducer / Consumer (with Counting Semaphores*)What does it mean that Semaphores have persistence? Tweedledum and Tweedledee ProblemThe 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.5 Dining PhilosophersTemplate for PhilosopherNaive SolutionSimplest Example of DeadlockConditions for DeadlockPhilosophy 101 (or why 5DP is interesting)Dealing with DeadlockPowerPoint PresentationHold and Wait ConditionStarvationReaders/Writers ProblemTemplate for Readers/WritersReader/Writer SpinlocksReader/Writer SemaphoresBirrell paper: SRC Thread PrimitivesMonitor AbstractionCondition VariablesSlide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37P&V using Locks & CV (Monitor)Design Decisions / IssuesUsing Condition Variables5DP - Monitor StyleWhat about this?Slide 44R/W - Monitor StyleIssuesSpurious WakeupsTricks (mixed syntax)More TricksAlertsUsing AlertsWisdom1Outline for Today•Objectives: –Discuss “Classic” concurrency problems•Administrative details: –Schedule on webpage now includes readings from Tanenbaum (the recommended optional undergrad-level text).–Change in schedule for next reading assignment.2Classic Synchronization ProblemsThere are a number of “classic” problems that represent a class of synchronization situations•Critical Section problem•Producer/Consumer problem•Reader/Writer problem•5 Dining PhilosophersWhy? Once you know the “generic” solutions, you can recognize other special cases in which to apply them (e.g., this is just a version of the reader/writer problem)3Producer / ConsumerProducer:while(whatever){ locally generate itemfill empty buffer with item}Consumer:while(whatever){get item from full bufferuse item}4Producer / Consumer(with Counting Semaphores*)Producer: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;*not Linux syntax5What does it mean that Semaphores have persistence?Tweedledum and Tweedledee Problem•Separate threads executing their respective procedures. The code below is intended 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 unpredictable•Linux: wait_for_completion() and complete()6The 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(); } }Lost Wakeup:If dee goes first to sleep, the wakeup is lost (since dum isn’tsleeping yet). Both sleep forever.7Show 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):85 Dining PhilosophersPhilosopher 0Philosopher 1Philosopher 2Philosopher 3Philosopher 4while(food available){pick up 2 adj. forks; eat; put down forks; think awhile;}9Template for Philosopherwhile (food available){ /*pick up forks*/eat; /*put down forks*/think awhile;}10Naive Solutionwhile (food available){ /*pick up forks*/eat; /*put down forks*/think awhile;}P(fork[left(me)]);P(fork[right(me)]);V(fork[left(me)]);V(fork[right(me)]);Does this work?11Simplest Example of DeadlockThread 0P(R1)P(R2)V(R1)V(R2)Thread 1P(R2)P(R1)V(R2)V(R1)InterleavingP(R1)P(R2)P(R1) waitsP(R2) waitsR1 and R2 initially 1 (binary semaphore)12Conditions for Deadlock•Mutually exclusive use of resources–Binary semaphores R1 and R2•Circular waiting–Thread 0 waits for Thread 1 to V(R2) and Thread 1 waits for Thread 0 to V(R1)•Hold and wait –Holding either R1 or R2 while waiting on other •No pre-emption–Neither R1 nor R2 are removed from their respective holding Threads.13Philosophy 101(or why 5DP is interesting)•How to eat with your Fellows without causing D eadlock.–Circular arguments (the circular wait condition)–Not giving up on firmly held things (no preemption)–Infinite patience with Half-baked schemes (hold some & wait for more)•Why Starvation exists and what we can do about it.14Dealing with DeadlockIt can be prevented by breaking one of the prerequisite conditions:•Mutually exclusive use of resources–Example: Allowing shared access to read-only files (readers/writers problem)•circular waiting–Example: Define an ordering on resources and acquire them in order •hold and wait •no pre-emption15while (food available){ if (me 0) {P(fork[left(me)]); P(fork[right(me)]);} else {(P(fork[right(me)]); P(fork[left(me)]); }eat; V(fork[left(me)]); V(fork[right(me)]); think awhile;}Circular Wait Condition16Hold and Wait Conditionwhile (food available){ P(mutex); while (forks [me] != 2) {blocking[me] = true; V(mutex); P(sleepy[me]); P(mutex);}forks [leftneighbor(me)] --; forks [rightneighbor(me)]--;V(mutex):eat;P(mutex); forks [leftneighbor(me)] ++; forks [rightneighbor(me)]++;if (blocking[leftneighbor(me)]) {blocking [leftneighbor(me)] = false; V(sleepy[leftneighbor(me)]); }if (blocking[rightneighbor(me)]) {blocking[rightneighbor(me)] = false; V(sleepy[rightneighbor(me)]); } V(mutex); think awhile; }17StarvationThe difference between deadlock and starvation is subtle:–Once a set of processes are deadlocked, there is no future execution sequence that can get them out of it.–In starvation, there does exist some execution sequence that is favorable to the starving process although there is no guarantee it will ever occur.–Rollback and Retry solutions are prone to starvation.–Continuous arrival of higher priority processes is