How can a runtime detect a true deadlock automatically, and how do you tell a deadlock apart from a livelock or from threads merely waiting on a slow remote call?

## What makes a deadlock detectable A deadlock is a cycle of threads each waiting for a resource held by the next. Formally it needs the four Coffman conditions to hold simultaneously: mutual exclusion (the resource cannot be shared), hold-and-wait (a holder requests more while keeping what it has), no preemption (nothing can be forcibly taken back) and circular wait (a cycle in the wait-for relation). That last one is the algorithmic handle. Build a directed **wait-for graph**: a node per thread, an edge from thread A to thread B when A is blocked acquiring a lock that B owns. Deadlock exists exactly when the graph contains a cycle, so detection is cycle detection. A managed runtime can construct that graph for locks it mediates, which is why some runtimes report deadlocks explicitly, naming the participating threads and the locks. Databases do the same for row locks and resolve it by choosing a victim transaction to abort — a policy option the runtime lacks, since it cannot safely roll a thread back. ## What automatic detection misses The detector only sees the resources the runtime mediates. Real hangs frequently sit outside that view: - **Counting semaphores, latches, futures, condition variables** — no single "owner", so no edge to draw. - **Locks in other systems** — database row locks, distributed locks, file locks, a lock held across services. - **Starvation deadlock in thread pools** — every worker is occupied waiting for a result that could only be produced by a task queued on the *same* pool. No lock cycle exists, yet the system is permanently stuck. This is one of the most common production hangs and no detector reports it. - **Cross-layer cycles** — thread A holds a connection and waits on a lock; thread B holds the lock and waits for a free connection. So: a deadlock report is strong evidence, but its absence proves nothing. ## Telling the three apart in practice Gather the same three signals in every case: processor usage, several thread dumps spaced seconds apart, and a progress metric (completed requests/tasks). **Deadlock** - Progress: zero, permanently, and it never recovers on its own. - Processor: near zero — blocked threads consume none. - Dumps: identical stacks in every snapshot; blocked entries name lock owners; following them closes a cycle. - Scope: usually only the threads in the cycle plus everyone queued behind them. **Livelock** - Progress: zero, but the system is furiously active — threads keep responding to each other and undoing work. Classic sources: two components retrying in lockstep, optimistic retry loops that always collide, back-off-and-retry with no randomised jitter, or a lock-free compare-and-swap loop that never wins. - Processor: high. - Dumps: stacks change between snapshots, typically cycling through the same few frames (retry, back-off, attempt). - Recovery: sometimes spontaneous when load drops — which makes it look intermittent. **Slow or hung remote dependency** - Progress: degraded or zero, but the *shape* is saturation, not a cycle. - Processor: low. - Dumps: many threads in socket-read frames of a client library; no lock ownership cycle. - Corroborating evidence: downstream latency and error rates rise, connection-pool waits increase, and threads eventually free up when a timeout fires — if there is a timeout at all. Without one it is indistinguishable from a hang until you look at the stacks. A fourth case worth naming: **starvation** — some threads progress while a specific class never does, for example a writer perpetually pushed back by a stream of readers, or a low-priority task never scheduled. Progress is non-zero overall, which is what separates it from the three above; the tell is a per-class latency metric with an unbounded tail. ## From diagnosis to remedy - **Deadlock**: impose a global lock ordering, or acquire with a timeout and back off; shrink critical sections; never call out to another component while holding a lock. Prevention beats detection, since recovery from a real deadlock usually means restarting. - **Livelock**: add randomised jitter and bounded retries, introduce backoff asymmetry so contenders stop moving in lockstep, and cap the total retry budget. - **Slow dependency**: mandatory timeouts, bulkheads separating dependencies, circuit breaking, and load shedding. ## Detection you can build yourself Because the runtime's view is partial, production systems benefit from an application-level watchdog: a periodic task that checks a liveness heartbeat per pool and, if a pool has made no progress for N intervals, records a thread dump plus queue depths automatically. That converts "we restarted it and never found out why" into evidence, and it catches the pool-starvation class that no built-in detector reports.