Concurrency, Synchronization & Deadlocks
Race conditions, lost updates, visibility, critical sections, mutexes, semaphores, atomics, and the four ingredients of a deadlock.
Concurrency bugs come in seven recognisable shapes — race, lost update, visibility/ordering, deadlock, livelock, starvation, priority inversion — each with a distinct mechanism and a distinct production symptom, and naming the shape is most of the diagnosis.
`counter++` is three instructions — load, add, store — and if two threads interleave between them one increment is lost; races are timing-dependent by nature, and the same read-then-act shape on the file system (TOCTOU) is a security bug rather than a counting bug.
A critical section is the stretch of code that touches shared state and must not interleave with another such stretch; synchronisation exists to enforce that, and its cost is decided by how much you put inside, how long you hold it, and how many threads want it — which Amdahl’s law turns into a hard ceiling on speedup.
A mutex is a lock with an owner: the thread that locks it must unlock it, a second thread that wants it waits — spinning briefly or sleeping in the kernel via a futex — and the uncontended path is a single atomic instruction that never enters the kernel.
A semaphore is a counter with blocking decrement and non-blocking increment and no notion of an owner — the right tool for "at most N at once" and for signalling between threads — while a mutex owns and a condition variable waits for a predicate; the three are different primitives, not interchangeable spellings.
CPUs provide indivisible read-modify-write instructions — fetch-and-add, compare-and-swap, load-linked/store-conditional — that make a lock-free counter possible and every lock implementable; the subtleties are the ABA problem and the memory-ordering flags that say what else becomes visible when an atomic does.
A deadlock needs four things at once — mutual exclusion, hold-and-wait, no preemption, circular wait — and the last is a cycle in the waits-for graph, which is why detection is depth-first search, prevention is imposing an order on the graph, and a database deadlock detector runs the same algorithm on transactions.