Operating Systems: Three Easy Pieces Ch. 28

Locks

• Lock variable
  • Calling lock → acquire the lock and enter the ciritical section
  • thre thread acquire the lock called the owner of the lock
  • Unlock → free the lock again
• Pthread locks
  • Mutex → mutual exclusion between threads
  • one thread is in the critical section, it excludes the others from entering until it has completed the section
  • we may be using different locks to protect different variables (fine-grained)
  • Mutual exclusion
  • Fairness
  • Performance
• Earliest solution → disable the interrupt
  • simple
  • need to perform a privileged operations
  • Monopolize processor
  • Different CPU → does not matter of disable interrupts, just go to other process
  • Inefficient
• Just using load and store
  • test flag is one and holds the lock
  • simply spin-wait
  • Problem
    • correctness
      • Both threads can be set to 1 and able to enter the ciritical section
    • performance
      • Spin-waiting waste the time
• Spin locks with Test and sets
  • test-and-set (or atomic exchange1) instruction
    • Dekker’s algorithm
    • Peterson’s algorithm
  • returns the old value pointed to by the old ptr, and simultaneously updates said value to new
  • Atomically operates
  • By making both the test (of the old lock value) and set (of the new value) a single atomic operation, we ensure that only one thread acquires the lock.
• Evaluating Spin Locks
  • Correctness → proved
  • Fairenss → no fairenss guarantee
  • Performance
    • Single CPU → performance overhead
    • Multiple CPUs → work well
• Compare-And-Swap
  • Or Compare-And-Exchange
  • The basic idea is for compare-and-swap to test whether the value at the address specified by ptr is equal to expected
  • simply checks if the flag is 0 and if so, atomically swaps in a 1 thus acquiring the lock
  • lock-free synchronization
• MIPS
  • load-linked and store-conditional instructions can be used in tandem to build locks and other concurrent structures
  • Load-linked
  • store-conditional, which only succeeds if no intervening store to the address taken the place

  

  • Fetch and add
    • ticket lock
    • uses a ticket and turn variable in combination to build a lock
    • does an atomic fetch-and-add on the ticket value
    • The globally shared lock->turn is then used to determine which thread’s turn it is
    • it ensures progress for all threads\
• Spinning
  • Waste of time slice doing nothing and check
  • Yield approach
    • we assume an operating system primitive yield()
    • thread can call when it wants to give up the CPU and let another thread run
    • move running to ready state → descheduling
    • But potential waste still
  • Sleeping instead of spinning
    • park() to put a calling thread to sleep
    • unpark(threadID) to wake a particular thread as designated by threadID
    • old test-and-set idea with an explicit queue of lock waiters
    • use a queue to help control who gets the lock next, thus avoiding starvation.
    • Add to queue that does not get the lock
      • calling the gettid() function
    • Release the guard after park()
      • flag does not get set back to 0 when another thread gets woken up
    • a thread will be about to park, assuming that it should sleep until the lock is no longer held
      • wakeup/waiting race
    • setpark(). By calling this routine, a thread can indicate it is about to park.
  • Priority inversion
    • If I/O keep occurs on no lock thread, just keep spinning and take the CPU cycle
    • a higher-priority thread waiting for a lower-priority thread → priority inheritance
• Different OS
  • futex
    • associated with it a specific physical memory location
    • futex_wait
    • futex_wake
• Two-Phase Lock
  • spinning can be useful, particularly if the lock is about to be released
  • Hybrid approach
    • First Spin phase → lock is not acquired → second phase: caller is put to sleep, wake when lock become frees -