1 COS 318: Operating Systems Mutex Implementation (http://www.cs.princeton.edu/courses/cos318/) 2 Today’s Topics  Disabling Interrupts for mutual exclusion  Hardware support for mutual exclusion  Competitive spinning 3 The Big Picture OS codes and concurrent applications High-Level Atomic API Mutex Semaphores Monitors Send/Recv Low-Level Atomic Ops Load/store Interrupt disable/enable Test&Set Other atomic instructions Interrupts (I/O, timer) Multiprocessors CPU scheduling 4 Revisit 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/threads Acquire(lock); if (noMilk) buy milk; Release(lock); Critical section2 5 Mutual Exclusion via Disabling Interrupts  Use interrupts  Implement preemptive CPU scheduling  Provide mutual exclusion by preventing context switch between acquire and release  Two types of events can cause switches: • Internal events to relinquish the CPU • External events to reschedule the CPU  Disable interrupts to prevent external events  Introduce uninterruptible code regions  Think sequentially most of the time  Delay handling of external events CPU Memory Interrupt DisableInt() . . . EnableInt() Uninterruptible region 6 A Simple Way to Use Disabling Interrupts  Issues with this approach? Acquire() { disable interrupts; } Release() { enable interrupts; } Acquire() critical section? Release() 7 Another Try  Issues with this approach?  Why disable interrupts at all? Acquire(lock) { disable interrupts; while (lock.value != FREE) ; lock.value = BUSY; enable interrupts; } Release(lock) { disable interrupts; lock.value = FREE; enable interrupts; }  Use a lock variable 8 Another 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; }  Use a lock variable, and impose mutual exclusion via interrupts only on testing and setting that variable3 9 Once more, with queuing …  What’s going on here?  When should acquirer re-enable interrupts?  Just before enqueue?  Just after enqueue and before Yield()? 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; } 10 Atomic Read-Modify-Write Instructions  Test&Set  Read location, set its value to 1, return value read  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 linked and conditional store  Read value in one instruction (load linked)  Do some operations;  When store, check if value has been modified since load linked. If not, ok; otherwise, jump back to start 11 A 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) == 1) ; } Release(lock) { lock.value = 0; } 12 What About This Solution?  How long does the “busy wait” take? Acquire(lock) { while (TAS(lock.guard) == 1) ; if (lock.value) { enqueue the thread; block and lock.guard = 0; } else { lock.value = 1; lock.guard = 0; } } Release(lock) { while (TAS(lock.guard)==1) ; if (anyone in queue) { dequeue a thread; make it ready; } else lock.value = 0; lock.guard = 0; }4 13 Example: 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 call Acquire(lock) count++; Release(lock) 14 Available Primitives and Operations  Test-and-set  Works at either user or kernel level  System calls for block/unblock  Block takes some token and goes to sleep  Unblock “wakes up” a waiter on token 15 Block and Unblock System Calls Block( lock )  Spin on lock.guard  Save the context to TCB  Enqueue TCB to lock.q  Clear lock.guard  Call scheduler Unblock( lock )  Spin on lock.guard  Dequeue a TCB from lock.q  Put TCB in ready queue  Clear lock.guard Always Block  What are the issues with this approach? Acquire(lock) { while (TAS(lock.value) == 1) Block( lock ); } Release(lock) { lock.value = 0; Unblock( lock ); }5 17 Always Spin  Two spinning loops in Acquire()? Acquire(lock) { while (TAS(lock.value)==1) while (lock.value) ; } Release(lock) { lock.value = 0; } CPU CPU L1 $ L1 $ L2 $ Multicore CPU L1 $ L2 $ CPU L1 $ L2 $ … … Memory SMP TAS TAS 18 Optimal 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 algorithms 19 Competitive 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 σ  We want have c to be as small as possible  Deterministic and randomized