logo

Programming Languages - Synchronization

Key Concepts

  • Race Condition: system's behavior is dependent on the sequence or timing of other uncontrollable events. The values of variables may be unpredictable.
  • Critical Section: If one thread is in the critical section, it excludes the others from entering until it has completed the section.

Locks

Implementations: (need hardware support)

  • disable interrupts (does not work on multiprocessors)
  • test-and-set instruction (a.k.a. atomic exchange)
  • compare-and-swap (compare-and-exchange) instruction
  • fetch-and-add instruction

instead of spinning:

  • yield
  • sleep

Lock vs Mutex vs Semaphore vs Monitor

  • Lock: not shared with any other processes
    • Read/write lock: unlimited number of readers or 1 writer at any given time
  • Mutex (mutual exclusion): same as Lock but can be shared by multiple processes, or system wide
    • A mutex is meant to be taken and released by the task.
  • Semaphores: same as Mutex but allows X number of threads to enter. Can be used as both locks and condition variables.
    • a binary semaphore is similar to a mutex, however, a semaphore is for signaling from one task to another.
  • Monitor: can wait for a certain condition, e.g. when the lock is released

Monitor

Monitors provide a mechanism for threads to temporarily give up exclusive access in order to wait for some condition to be met, before regaining exclusive access and resuming their task.

Monitor = a mutex (lock) + condition variables

Condition Variable: a container of threads that are waiting on a certain condition.

In multi-threaded programs, it is often useful for a thread to wait for some condition to become true before proceeding.

Solutions:

  • spinning until the condition becomes true (inefficient)
  • by condition variables: A condition variable is an explicit queue that threads can put themselves on when waiting for a condition

Deadlock vs Starvation vs Livelock

  • deadlock: dining philosophers, bow
  • starvation,
  • livelock: two people attempting to pass each other in a corridor

Imagine a little dog snuck under Big Dog's cone of shame and covered the food with its own cone of shame, and it won't leave. That's deadlock. Imagine a stream of little dogs sneaking under Big Dog's cone so Big Dog nevers gets a bite. That's livelock.

Barrier vs Latch vs Count-down Latch

  • Barrier: any thread/process must stop at this point and cannot proceed until all other threads/processes reach this barrier.
  • Latch: a barrier that starts in the raised state and cannot be re-raised once it is in the lowered state.
  • Count-down Latch: a latch that is automatically lowered once a pre-determined number of threads/processes have arrived.

Atomic

Atomic operations should be avoided. It should only be used by experts on low-level data structures.