1Outline 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...Thread0 Thread1Data: xwhile(i<10){x=x+1;i++;}0while(j<10){x=x+1;j++;}00ijWhat 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 atomicoperations.• 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 thekernel• 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 atomicst (count+1) count+1end atomicswitchld (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 ProtectCritical 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 ProtectCritical 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(listmutex);Release(listmutex);Acquire(listmutex);Release(listmutex);Focus on the data!16Yet Another ExampleProblem: Given arrays C[0:x,0:y], A [0:x,0:y], and B [0:x,0:y]. Use n threads to update each element of C to the sum of A and B and then the last thread returns the average value of all C elements.17• Static partitioning of arraysfor (i = lowi; i < highi; i++)for (j = lowj; j < highj; j++){C[i,j] = A[i,j] + B[i,j];privatesum = privatesum + C[i,j]; }sum = sum + privatesum;• Static partitioning of arraysfor (i = lowi; i < highi; i++)for (j = lowj; j < highj; j++){C[i,j] = A[i,j] + B[i,j];sum = sum + C[i,j]; }Design AlternativessumClowi = 0highi = n/2-1lowj = 0highj = n/2-1lowi = n/2highi = n-1lowj = 0highj = n/2-1lowi = 0highi = n/2-1lowj = n/2highj = n-1lowi = n/2highi = n-1lowj = n/2highj = n-118• Dynamic partitioning of arrayswhile (elements_remain(&i,&j)){C[i,j] = A[i,j] + B[i,j];sum = sum + C[i,j]; }Design AlternativessumC19Implementation Options for Mutual Exclusion• Disable Interrupts• Use atomic operations (read-mod-write instr.) • Busywaiting solutions - spinlocks– execute a tight loop if critical section is busy– benefits from specialized atomic instructions• Blocking synchronization– sleep (enqueued on wait queue) while C.S. is busySynchronization primitives (abstractions, such as locks) which are provided by a system may be implemented with some combination of these techniques.20The Critical Section Problemwhile (1){ ...other stuff...critical section –anything that touches a particular set of shared data}enter_region( );exit_region( );21Critical Data• Goal in solving the critical section problem is to build synchronization so that the sequence of instructions that can cause a race condition are executed AS IF they were indivisible – “Other stuff” code that does not touch the critical data associated with a critical section can be interleaved with the critical section code.– Code from a critical section involving data x can be interleaved with code from a critical section associated with data