Unformatted text preview:

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 itLock::Release()release the lock waking up a waiter if anyLock::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}ReadModifyWrite (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

UT CS 372 - Mutual Exclusion

Documents in this Course
MapReduce

MapReduce

17 pages

Processes

Processes

19 pages

MapReduce

MapReduce

17 pages

Load more
Download Mutual Exclusion
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Mutual Exclusion and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Mutual Exclusion 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?