Concurrency & Deadlock theory

A race condition occurs when multiple concurrent threads access and manipulate shared data concurrently, and the final outcome depends on the non-deterministic order of execution. To prevent race conditions, access to shared data within critical sections must be synchronized. Edsger Dijkstra established that any valid critical section solution must satisfy three requirements: (1) Mutual Exclusion: only one thread can execute in its critical section at any time; (2) Progress: if no thread is in its critical section, only threads wishing to enter can participate in deciding who enters, and this cannot be delayed indefinitely; and (3) Bounded Waiting: there must be an upper bound on the number of times other threads enter their critical sections after a thread has requested entry, preventing starvation.

Formulated by Edward G. Coffman Jr. in 1971, the four Coffman conditions are: (1) Mutual Exclusion: at least one resource is non-shareable; (2) Hold and Wait: a thread holds at least one resource while waiting for another; (3) No Preemption: resources cannot be forcibly confiscated from holding threads; and (4) Circular Wait: a closed chain of threads exists where each waits for a resource held by the next. These conditions are fundamental because deadlock can occur IF AND ONLY IF all four hold simultaneously. Consequently, deadlocks can be mathematically eliminated by designing protocols that violate at least one condition.

The Dining Philosophers Problem (Dijkstra, 1965) models resource contention among N concurrent processes competing for N shared resources (forks) arranged in a ring. A philosopher needs both adjacent forks to eat. If all philosophers follow the symmetric rule of picking up their left fork first, and all become hungry simultaneously, every philosopher successfully acquires their left fork. Now, all N forks are held, each philosopher waits for their right fork (held by their neighbor), and no fork can be preempted. All four Coffman conditions are satisfied, producing complete system deadlock where all philosophers starve.

Dijkstra eliminated Circular Wait by imposing a global partial ordering on resources. Number all forks 0 to N-1. The rule dictates that every philosopher must always acquire their lower-numbered fork before attempting to acquire their higher-numbered fork. Philosophers 0 through N-2 acquire fork i then i+1. But Philosopher N-1 has forks N-1 and 0; because 0 < N-1, Philosopher N-1 must pick up fork 0 FIRST. This means Philosopher N-1 and Philosopher 0 contend for fork 0 immediately, preventing the full circular wait chain from forming. At least one philosopher is always guaranteed to acquire both forks, eat, and release them, ensuring deadlock-free progress.

A Resource Allocation Graph (RAG) is a directed bipartite graph with thread nodes and resource nodes. Request edges (T_i → R_j) indicate a thread is waiting for a resource; assignment edges (R_j → T_i) indicate a resource is held by a thread. For single-unit resources (where only 1 instance of each resource exists), a directed cycle in the RAG is both NECESSARY AND SUFFICIENT for deadlock. For multi-unit resources, a cycle is necessary but not sufficient: a cycle indicates potential deadlock, but if un-involved threads holding the same resource type release their instances, the cycle can resolve. Full multi-unit deadlock detection requires matrix reduction algorithms.

Dijkstra's Banker's Algorithm (1965) prevents deadlocks by dynamically testing whether granting a resource request will leave the system in a 'Safe State'. A state is safe if there exists at least one order (safe sequence) in which all processes can finish executing, even if each process immediately demands its declared maximum claim. When a thread requests resources, the algorithm simulates the allocation and runs the safety algorithm. If a safe sequence exists, the allocation is approved; if the allocation would leave the system in an unsafe state (where deadlock could occur if processes demand maximum claims), the requesting thread is forced to wait.

Priority Inversion is a concurrency bug where a high-priority thread is indirectly blocked by a low-priority thread. Suppose Low-priority thread L holds a shared mutex. High-priority thread H needs the mutex and blocks. If a Medium-priority thread M becomes ready, it preempts L (since priority of M > L). Now L cannot run to release the mutex, so H is indefinitely delayed by M, inverting task priorities (famously freezing NASA's Mars Pathfinder in 1997). The Priority Inheritance Protocol solves this: whenever H blocks on a mutex held by L, thread L temporarily inherits H's high priority until it releases the mutex, preventing medium-priority threads from preempting L.