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.