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.