Locks and Synchronization
Stub. Locks and how they're built (from hardware primitives up to two-phase and OS-assisted locks), locked data structures (concurrent lists, queues, hash tables), condition variables for waiting on a predicate, semaphores as a single primitive that can implement both locks and condition variables, and a taxonomy of common concurrency bugs.
The core toolkit for correct shared-memory concurrency. Locks provide mutual exclusion, built up from hardware support (test-and-set, compare-and-swap) to practical two-phase locks that spin briefly then sleep; applying them to standard data structures (with an eye to granularity and performance) gives locked concurrent lists, queues, and hash tables. Condition variables add the ability to wait for a condition on shared state rather than just for exclusive access, and semaphores unify both concerns into a single counting primitive — general enough to implement locks and condition variables both. Closes with the standard taxonomy of concurrency bugs (deadlock, atomicity violations, order violations) and how to reason about avoiding them.
Outline (TODO — flesh out each)
- Locks — hardware primitives, two-phase locks
- Locked data structures — concurrent lists, queues, hash tables
- Condition variables
- Semaphores
- Concurrency bugs — deadlock, atomicity and order violations