Mutual Exclusion:Primitives and Implementation Considerations1Too Much Milk: LessonsSoftware solution (Peterson’s algorithm) works, but it is unsatisfactory¾Solution is complicated; proving correctness is tricky even¾Solution is complicated; proving correctness is tricky even for the simple example¾ While thread is waiting, it is consuming CPU time¾ Asymmetric solution exists for 2 processes.How can we do better?¾Use hardware features to eliminate busy waiting2¾Use hardware features to eliminate busy waiting¾ Define higher-level programming abstractions to simplify concurrent programmingConcurrency QuizIf two threads execute this program concurrently, how many different final values of X are there?Initially, X == 0.void increment() {int temp = X;temp = temp + 1;X = temp;}void increment() {int temp = X;temp = temp + 1;X = temp;}Thread 1 Thread 23Answer:A. 0B. 1C. 2D. More than 2Schedules/InterleavingsModel of concurrent executionInterleave statements from each thread into a single threadIf any interleaving yields incorrect results, some synchronization is neededtmp1 = X;tmp1 = tmp1 + 1;X = tmp1;tmp2 = X;tmp2 = tmp2 + 1;X = tmp2; Thread 1Thread 2tmp1 = X;tmp2 = X;tmp2 = tmp2 + 1;tmp1 = tmp1 + 1;4pp;X = tmp1;X = tmp2;If X==0 initially, X == 1 at the end. WRONG result!Locks fix this with Mutual Exclusionvoid increment() {lock.acquire();int temp = X;temp=temp + 1;Mutual exclusion ensures only safe interleavings¾ When is mutual exclusion too safe?temp temp + 1;X = temp;lock.release();}5Introducing LocksLocks – implement mutual exclusion¾ Two methods Lock::Acquire() – wait until lock is free, then grab itLock::Release()release the lock waking up a waiter if anyLock::Release() –release the lock, waking up a waiter, if anyWith locks, too much milk problem is very easy!¾ Check and update happen as one unit (exclusive access)Lock.Acquire();if (noMilk) {buy milk;Lock.Acquire();if (noMilk) {buy milk;Lock.Acquire();x++;LockRelease();Lock.Acquire();x++;LockRelease();6buy milk;}Lock.Release();buy milk;}Lock.Release();How can we implement locks?Lock.Release();Lock.Release();How to think about synchronization codeEvery thread has the same pattern¾ Entry section: code to attempt entry to critical section¾ Critical section: code that requires isolation (e.g., with mutual exclusion)exclusion)¾ Exit section: cleanup code after execution of critical region¾ Non-critical section: everything elseThere can be multiple critical regions in a program¾ Only critical regions that access the same resource (e.g., data structure) need to synchronize with each otherwhile(1) {7Entry sectionCritical sectionExit sectionNon-critical section}The correctness conditionsSafety¾ Only one thread in the critical regionLiveness¾ Some thread that enters the entry section eventually enters the critical region ¾ Even if other thread takes forever in non-critical regionBounded waiting¾ A thread that enters the entry section enters the critical section within some bounded number of operations.Failure atomicity¾It is OK for a thread to die in the critical region8¾It is OK for a thread to die in the critical region¾ Many techniques do not provide failure atomicitywhile(1) {Entry sectionCritical sectionExit sectionNon-critical section}ReadModifyWrite (RMW)Implement locks using read-modify-write instructions¾ As an atomic and isolated action1. read a memory location into a register, AND2. write a new value to the location¾ Implementing RMW is tricky in multi-processorspg yp Requires cache coherence hardware. Caches snoop the memory bus.Examples:¾ Test&set instructions (most architectures) Reads a value from memory Write “1” back to memory location¾ Compare & swap (68000) Test the value against some constant9 If the test returns true, set value in memory to different value Report the result of the test in a flag if [addr] == r1 then [addr] = r2;¾ Exchange, locked increment, locked decrement (x86)¾ Load linked/store conditional (PowerPC,Alpha, MIPS)Implementing Locks with Test&setint lock_value = 0;int* lock = &lock_value;int lock_value = 0;int* lock = &lock_value;If lock is free (lock_value == 0), then test&set reads 0 and sets value to 1 Î lock is set to busy and Acquire completesIf lock is busy, the test&set reads 1 and sets value to 1 Î no change in lock’s status and Acquire loopsIf lock is free (lock_value == 0), then test&set reads 0 and sets value to 1 Î lock is set to busy and Acquire completesIf lock is busy, the test&set reads 1 and sets value to 1 Î no change in lock’s status and Acquire loopsLock::Acquire() {while (test&set(lock) == 1); //spin}Lock::Acquire() {while (test&set(lock) == 1); //spin}10lock s status and Acquire loopslock s status and Acquire loopsLock::Release() {*lock = 0;}Lock::Release() {*lock = 0;}Does this lock have bounded waiting?Does this lock have bounded waiting?Locks and Busy WaitingLock::Acquire() {while (test&set(lock) == 1); // spin}Lock::Acquire() {while (test&set(lock) == 1); // spin}Busy-waiting: ¾ Threads consume CPU cycles while waiting¾ Low latency to acquireLimitations¾ Occupies a CPU core¾ What happens if threads have different priorities?}}11 Busy-waiting thread remains runnable If the thread waiting for a lock has higher priority than the thread occupying the lock, then ? Ugh, I just wanted to lock a data structure, but now I’m involved with the scheduler!¾ What if programmer forgets to unlock?Remember to always release locksJava provides convenient mechanism.import java.util.concurrent.locks.ReentrantLock;java.util.concurrent.locks.ReentrantLock;public static final aLock = new ReentrantLock();aLock.lock();try {…12} finally {aLock.unlock();}return 0;Cheaper Locks with Cheaper busy waitingUsing Test&SetLock::Acquire() {Lock::Acquire() {Lock::Acquire() {while(1) {if (test&set(lock) == 0) break;else sleep(1);Lock::Acquire() {while(1) {if (test&set(lock) == 0) break;else sleep(1);Lock::Acquire() {while (test&set(lock) == 1);}Lock::Acquire() {while (test&set(lock) == 1);}Lock::Release() {Lock::Release() {With busy-waiting}}With voluntary yield of CPULock::Release() {Lock::Release() {13*lock = 0;}*lock = 0;}*lock = 0;}*lock = 0;}What is the problem with this?¾ A. CPU usage B. Memory usage C. Lock::Acquire() latency¾ D. Memory bus usage E. Messes up interrupt handlingTest & Set with Memory HierarchiesCPU ACPU BWhat happens to lock variable’s cache line when different cpu’s contend
View Full Document