a deadlock and the Coffman conditions
/ KOF-muhn /
Two cars meet on a one-lane bridge, each blocking the other and refusing to back up. Neither can move; both wait forever. That frozen standoff is a deadlock: a set of threads each waiting for a resource that another thread in the set is holding, so none of them can ever make progress. Classically, thread A holds lock 1 and wants lock 2, while thread B holds lock 2 and wants lock 1 — each is politely waiting for the other to let go, and neither ever will.
A deadlock can only happen when four conditions, named after E. G. Coffman, all hold at once. Mutual exclusion: at least one resource is held in a non-shareable way (a lock is held by one thread). Hold-and-wait: a thread keeps the resources it already holds while waiting to acquire more. No preemption: a resource cannot be forcibly taken from the thread holding it — it must be released voluntarily. Circular wait: there is a cycle of threads, each waiting for a resource the next one in the cycle holds. All four are necessary; break any single one and deadlock becomes impossible. You can detect a deadlock by modelling who-holds-what and who-waits-for-what as a graph (a resource-allocation or wait-for graph) and looking for a cycle in it; some runtimes and tools do exactly this.
Deadlock is one of the most feared concurrency bugs because it is often timing-dependent: the program runs fine a thousand times, then hangs forever the one time two threads happen to grab their two locks in opposite orders. It does not crash, it does not log — it simply stops, which is why it can be agony to diagnose. The good news is that the four conditions are also your toolkit: prevention strategies each target one of them, most commonly attacking circular wait by imposing a global lock-ordering rule (see deadlock prevention).
Thread A: lock(m1); lock(m2); ... Thread B: lock(m2); lock(m1); ... — if A holds m1 and B holds m2 at the same instant, each then blocks forever waiting for the lock the other holds. That is the circular wait.
Opposite lock orders create a cycle in the wait-for graph; all four Coffman conditions hold.
A deadlock does not crash or error — the threads simply stop forever, so it often looks like a 'hang'. A thread sanitizer or a thread dump (showing each thread blocked on a lock the others hold) is usually how you confirm it; staring at logs will not, because nothing is logged.