Outline for TodayPowerPoint PresentationConcurrency from the Kernel PerspectiveThe Trouble with Concurrency in Threads...Range of AnswersReasoning about ConcurrencyThe Trouble with ConcurrencyDesired: Atomic Sequence of InstructionsUnprotected Shared DataSlide 10Slide 11Critical SectionsThe Critical Section ProblemTemptation to Protect Critical Sections (Badly)Slide 15Yet Another ExampleDesign AlternativesSlide 18Implementation Options for Mutual ExclusionSlide 20Critical DataSlide 22Slide 23Atomic Operations (Integer)Atomic Operations (Bitwise)Uses of Atomic OperationsSlide 27Slide 28Slide 29Pros and Cons of BusywaitingSpinlock SubtletiesPros and Cons of BlockingSemaphoresSlide 34Slide 35Semaphore UsageSlide 37Lock Granularity – how much should one lock protect?Slide 39Optimistic Locking – SeqlocksPeterson’s Algorithm for 2 Process Mutual ExclusionInterleaving of Execution of 2 Threads (blue and green)Slide 43Slide 44BarriersClassic 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 DeadlockSlide 59Hold and Wait ConditionStarvationReaders/Writers ProblemTemplate for Readers/WritersReader/Writer SpinlocksReader/Writer SemaphoresBirrell paper: SRC Thread PrimitivesMonitor AbstractionCondition VariablesSlide 75Slide 76Slide 77Slide 78Slide 79Slide 80P&V using Locks & CV (Monitor)Design Decisions / IssuesUsing Condition Variables5DP - Monitor StyleWhat about this?Slide 88R/W - Monitor StyleIssuesSpurious WakeupsTricks (mixed syntax)More TricksAlertsUsing AlertsWisdom1Outline for Today•Objectives: –To introduce the critical section problem.–To learn how to reason about the correctness of concurrent programs.–To present Linux kernel synchronization•Administrative details:2To capture naturally concurrent activities –Waiting for slow devices–Providing human users faster response.–Shared network servers multiplexing among client requests (each client served by its own server thread)To gain speedup by exploiting parallelism in hardware –Maintenance tasks performed “in the background”–Multiprocessors–Overlap the asynchronous and independent functioning of devices and usersWithin a single user thread – signal handlers cause asynchronous control flow.Reasons for Explicitly Programming with Threads(User-level Perspective – Birrell)3Concurrency from theKernel Perspective•Kernel preemption – scheduler can preempt task executing in kernel.•Interrupts occurring – asynchronously invoking handler that disrupts the execution flow.•Sleeping to wait for events.•Support for SMP multiprocessors – true concurrency of code executing on shared memory locations.4The Trouble with Concurrency in Threads...Thread0Thread1Data: xwhile(i<10){xx+1; i++;}0while(j<10) {xx+1; j++;}00i jWhat is the value of x when both threadsleave this while loop?5Range of AnswersProcess 0LD x // x currently 0Add 1ST x // x now 1, stored over 9Do 9 more full loops // leaving x at 10Process1LD x // x currently 0Add 1ST x // x now 1Do 8 more full loops // x = 9LD x // x now 1Add 1ST x // x = 2 stored over 106Reasoning about Concurrency•What unit of work can be performed without interruption? Indivisible or atomic operations.•Interleavings - possible execution sequences of operations drawn from all threads.•Race condition - final results depend on ordering and may not be “correct”.The Trouble with Concurrency•Two threads (T1,T2) in one address space or two processes in the kernel•One counter (shared)ld r2, countadd r1, r2, r3st count, r1Shared Datacountld r2, countadd r1, r2, r3st count, r1TimeT1 T2 countld (count)addswitchld (count)addst (count+1)count+1switchst (count+1) count+1AssumedatomicprivateDesired: Atomic Sequence of Instructions•Atomic Sequence–Appears to execute to completion without any intervening operationsTimeT1 T2 countbegin atomicld (count)addswitchbegin atomic st (count+1) count+1end atomicswitch ld (count+1)addst (count+2) count+2end atomicwait9Unprotected Shared Datavoid threadcode( ){int i;long key;for (i=0; i<20; i++){key = rand();SortedInsert (key);}for (i=0; i<20; i++){key = SortedRemove();print (key); }}What can happen here?private10 20 30nullhead10Unprotected Shared DataWhat can happen here?20 30nullhead•2 concurrent SortedInserts with keys 5 and 7.571011Unprotected Shared DataWhat can happen here?20 30nullhead•2 concurrent SortedInserts with keys 5 and 7.•2 concurrent SortedRemoves10localptrlocalptr12Critical Sections•If a sequence of non-atomic operations must be executed as if it were atomic in order to be correct, then we need to provide a way to constrain the possible interleavings –Critical sections are defined as code sequences that contribute to “bad” race conditions.–Synchronization is needed around such critical sections.•Mutual Exclusion - goal is to ensure that critical sections execute atomically w.r.t. related critical sections in other threads or processes.13The Critical Section ProblemEach process follows this template:while (1){ ...other stuff... //processes in here shouldn’t stop othersenter_region( );critical sectionexit_region( );}The problem is to implement enter_region and exit_region to ensure mutual exclusion with some degree of fairness.Problem with this definition:It focuses on code not shared data that needs protecting!14Temptation to Protect Critical Sections (Badly)void threadcode( ){int i;long key;for (i=0; i<20; i++){key = rand();SortedInsert (key);}for (i=0; i<20; i++){key = SortedRemove();print (key); }}10 20 30nullheadAcquire(insertmutex);Release(insertmutex);Acquire(removemutex);Release(removemutex);Focus on the data!15Temptation to Protect Critical Sections (Badly)void threadcode( ){int i;long key;for (i=0; i<20; i++){key = rand();SortedInsert (key);}for (i=0; i<20; i++){key = SortedRemove();print (key); }}10 20