COS 318: Operating SystemsMutex Implementation(http://www.cs.princeton.edu/courses/cos318/)2Today’s Topics!Disabling Interrupts for mutual exclusion!Hardware support for mutual exclusion!Competitive spinning3Revisit Mutual Exclusion (Mutex)!Critical section!Conditions of a good solution"Only one process/thread inside a critical section"No assumption about CPU speeds"A process/thread inside a critical section should not be blocked by any processes/threads outside the critical section"No one waits forever"Works for multiprocessors"Same code for all processes/threadsAcquire(lock);if (noMilk) buy milk;Release(lock);Critical section4Use and Disable Interrupts!Use interrupts"Implement preemptive CPU scheduling"Internal events to relinquish the CPU"External events to reschedule the CPU!Disable interrupts"Introduce uninterruptible code regions"Think sequentially most of the time"Delay handling of external eventsCPUMemoryInterruptDisableInt()...EnableInt()Uninterruptibleregion5A Simple Way to Use Disabling Interrupts!Issues with this approach?Acquire() { disable interrupts;}Release() { enable interrupts;}Acquire() critical section?Release()6One More Try!Issues with this approach?Acquire(lock) { disable interrupts; while (lock.value != FREE) ; lock.value = BUSY; enable interrupts;}Release(lock) { disable interrupts; lock.value = FREE; enable interrupts;}7Another Try!Does this fix the “wait forever” problem? Acquire(lock) { disable interrupts; while (lock.value != FREE){ enable interrupts; disable interrupts; } lock.value = BUSY; enable interrupts;}Release(lock) { disable interrupts; lock.value = FREE; enable interrupts;}8Yet Another Try!Any issues with this approach?Acquire(lock) { disable interrupts; while (lock.value == BUSY) { enqueue me for lock; Yield(); } lock.value = BUSY; enable interrupts;}Release(lock) { disable interrupts; if (anyone in queue) { dequeue a thread; make it ready; } lock.value = FREE; enable interrupts;}9Atomic Memory Load and Store!Assumed in in textbook (e.g. Peterson’s solution)!A multiprocessor spin solution Acquire(lock) { while (!lock.value) { ; lock.value = i; if (lock.value == i) break; Yield() } }!L. Lamport, “A Fast Mutual Exclusion Algorithm,” ACM Trans. on Computer Systems, 5(1):1-11, Feb 1987."5 writes and 2 readsRelease(lock.value) { lock.value = 0;}10Atomic Read-Modify-Write Instructions!LOCK prefix in x86"Make a specific set instructions atomic"Together with BTS to implement Test&Set!Exchange (xchg, x86 architecture)"Swap register and memory"Atomic (even without LOCK)!Fetch&Add or Fetch&Op"Atomic instructions for large shared memory multiprocessor systems!Load link and conditional store "Read value in one instruction (load link)"Do some operations;"When store, check if value has been modified. If not, ok; otherwise, jump back to start11A Simple Solution with Test&Set!Define TAS(lock)"If successfully set, return 1;"Otherwise, return 0;!Any issues with the following solution?Acquire(lock) { while (!TAS(lock.value)) ;}Release(lock.value) { lock = 0;}12What About This Solution?!How long does the “busy wait” take?Acquire(lock) { while (!TAS(lock.guard)) ; if (lock.value) { enqueue the thread; block and lock.guard = 0; } else { lock.value = 1; lock.guard = 0; }}Release(lock) { while (!TAS(lock.guard)) ; if (anyone in queue) { dequeue a thread; make it ready; } else lock.value = 0; lock.guard = 0;}13Example: Protect a Shared Variable!Acquire(mutex) system call"Pushing parameter, sys call # onto stack"Generating trap/interrupt to enter kernel"Jump to appropriate function in kernel"Verify process passed in valid pointer to mutex"Minimal spinning"Block and unblock process if needed"Get the lock!Executing “count++;”!Release(mutex) system callAcquire(lock)count++;Release(lock)14Available Primitives and Operations!Test-and-set"Works at either user or kernel!System calls for block/unblock"Block takes some token and goes to sleep"Unblock “wakes up” a waiter on token15Block and Unblock System CallsBlock( lock )"Spin on lock.guard"Save the context to TCB"Enqueue TCB to lock.q"Clear lock.guard"Call scheduler!Questions"Do they work?"Can we get rid of the spin lock?Unblock( lock )"Spin on lock.guard"Dequeue a TCB from lock.q"Put TCB in ready queue"Clear lock.guardAlways Block!What are the issues with this approach?Acquire(lock) { while (!TAS(lock.value)) Block( lock );}Release(lock) { lock.value = 0; Unblock( lock );}17Always Spin!Two spinning loops in Acquire()?Acquire(lock) { while (!TAS(lock.value)) while (lock.value) ;}Release(lock) { lock.value = 0;}CPU CPUL1 $ L1 $L2 $MulticoreCPUL1 $L2 $CPUL1 $L2 $……MemorySMPTASTAS18Optimal Algorithms!What is the optimal solution to spin vs. block?"Know the future"Exactly when to spin and when to block!But, we don’t know the future"There is no online optimal algorithm!Offline optimal algorithm"Afterwards, derive exactly when to block or spin (“what if”)"Useful to compare against online algorithms19Competitive Algorithms!An algorithm is c-competitive if for every input sequence ! CA(!) ! c " Copt(!) + k"c is a constant"CA(!) is the cost incurred by algorithm A in processing !"Copt(!) is the cost incurred by the optimal algorithm in processing !!What we want is to have c as small as possible"Deterministic"RandomizedConstant Competitive Algorithms!Spin up to N times if the lock is held by another thread!If the lock is still held after spinning N times, block!If spinning N times is equal to the context-switch time, what is the competitive factor of the algorithm?Acquire(lock, N) { int i; while (!TAS(lock.value)) { i = N; while (!lock.value && i) i--; if (!i) Block(lock); }}21Approximate Optimal Online Algorithms!Main idea"Use past to predict future!Approach"Random walk• Decrement N by a unit if the last Acquire() blocked• Increment N by a unit if the last Acquire() didn’t block"Recompute N each time for each Acquire() based on some lock-waiting distribution for each lock!Theoretical resultsE CA(! (P)) ! (e/(e-1)) " E Copt(!(P)) The competitive factor is about 1.58.22Empirical ResultsA. Karlin, K. Li, M. Manasse, and S. Owicki, “Empirical Studies of Competitive Spinning for a Shared-Memory Multiprocessor,” Proceedings of the 13th ACM Symposium on Operating Systems Principle, 1991.23The Big PictureOS