Mutual Exclusion and Locks

Synchronization Problems

  • Shared state can be corrupted when multiple threads access and modify it concurrently.
  • Atomic Operation: An operation that runs to completion or not at all, indivisible and uninterruptible.

Too Much Milk Problem

  • Illustrates the complexities of synchronization.
  • Several solutions are explored:
    • Solution #2: Leaving labeled notes; doesn't work.
    • Solution #2.5: Reordered note leaving; doesn't work.
    • Solution #3: Two-note solution; complex but works by ensuring either the current thread can safely buy milk or another thread will.

Locks

  • Definition: A synchronization primitive that provides mutual exclusion.
  • Acquire: Wait until the lock is free, then grab it.
  • Release: Unlock, waking up anyone waiting.
  • Critical Section: Code between Acquire() and Release().

Multithreading

  • Enables resource sharing, modularity, and parallelism.
  • Threads may need to wait for results from other threads.

Implementing Locks

  • Involves waiting if the lock is already held.
  • Hardware Lock instructions can be used, but may increase complexity.

Naive Interrupt Enable/Disable

  • Disabling interrupts can prevent context switching on a uniprocessor.
  • Naive implementation: LockAcquire { disable ints; }, LockRelease { enable ints; }.

Problems with Naive Interrupt Enable/Disable

  • User code could disable interrupts indefinitely.
  • Real-time systems require guarantees on timing, which this violates.
  • Critical sections might be arbitrarily long.
  • Can interfere with I/O and other important events.

Better Implementation with Interrupts

  • Maintain a lock variable and impose mutual exclusion only during its access/update.
  • Example:
    • Acquire(): Disable interrupts, check if the lock is BUSY. If so, put the thread on a wait queue and sleep. Otherwise, set the lock to BUSY. Enable interrupts.
    • Release(): Disable interrupts, check for waiting threads. If any, move one to the ready queue. Otherwise, set the lock to FREE. Enable interrupts.

Interrupt Re-enable

  • Re-enable interrupts when going to sleep.
  • The next thread to run is responsible for re-enabling interrupts after sleep.

Atomic Read-Modify-Write Instructions

  • Alternative to disabling interrupts, works on multiprocessors.
  • Instructions read a value from memory and write a new value atomically.
  • Examples:
    • test&set(&address)
    • swap(&address, register)
    • compare&swap(&address, reg1, reg2)

Implementing Locks with test&set

  • Simple Solution:
    • Acquire(): while (test&set(value));
    • Release(): value = 0;

Busy-Waiting

  • Inefficient, consumes cycles while waiting.
  • Can lead to priority inversion.

Better Locks using test&set

  • Minimize busy-waiting by only busy-waiting to atomically check the lock value.
  • Use a guard variable to protect the lock.

Locks using test&set vs. Interrupts

  • Replace disable interrupts with while (test&set(guard));
  • Replace enable interrupts with guard = 0;

Summary

  • Hardware atomicity primitives: disabling interrupts, test&set, swap, compare&swap.
  • Careful construction of locks is crucial to avoid wasting resources.
  • Separate lock variable and use hardware mechanisms to protect modifications of that variable.