Give an example of a deadlock in which no participant holds a mutex, and explain what plays the role of the lock in it.

## Locks are a special case, not the phenomenon Deadlock is defined over resources, not over mutexes. Re-reading the Coffman conditions with that in mind: mutual exclusion means the resource cannot be shared while in use; hold and wait means you can be holding one while asking for another; no preemption means nobody can take it back. A mutex satisfies all three, but so do many things a typical service uses constantly. ## Pool exhaustion with nested acquisition A pool of N database connections. A request handler borrows a connection, starts work, and then calls a helper that borrows a *second* connection - perhaps to read from a different data source, perhaps because a library opens its own. Under light load nothing happens, because free connections are always available. Under enough concurrency, N handlers each hold exactly one connection and each waits for a second. None will release until it finishes; none can finish. The pool is the resource type, the permit is the exclusive holding, and the wait is permanent. The hallmark that makes this a deadlock rather than mere saturation is that **all capacity is held by parties that cannot progress**. Saturation drains when slow work completes; this never drains. ## Thread-pool starvation deadlock A bounded worker pool where a running task submits a subtask to the same pool and blocks waiting for the subtask's result. The subtask is queued behind the running task, which will not release its worker until the subtask finishes. With one worker this deadlocks on the first attempt; with W workers it deadlocks as soon as W tasks do this simultaneously. Here the scarce resource is a **worker slot**. The same shape appears whenever a task waits on something that needs the pool that the task is occupying - which includes recursive parallel decomposition, and calling a service backed by the same executor. ## Bounded queues between stages A pipeline where stage A pushes to queue Q1 consumed by B, and B pushes to queue Q2 consumed by A (a feedback loop, or an error path). If both queues fill, A blocks on the full Q1 while holding its consumer role for Q2, and B blocks on the full Q2 while holding its role for Q1. The scarce resource is a **queue slot**. Unbounded queues remove this deadlock and replace it with unbounded memory growth, so the choice is between two failure modes rather than a free fix. ## Synchronous message passing Even with no shared memory at all, two processes that each perform a blocking send or receive toward the other with no buffering are deadlocked: each waits for a rendezvous the other will never reach. Message-passing designs remove data races, but circular waits survive; they simply become circular waits on messages. This is why request-response between two single-threaded actors, where each blocks awaiting the other's reply, deadlocks exactly like two mutexes taken in opposite orders. ## Cross-system and transactional variants - **Database row or range locks** held across two transactions updating the same rows in opposite orders. The engine usually detects and aborts a victim. - **Distributed leases and semaphores** in a coordination service, where the holder crashes or waits on a peer. - **Service A calls B, B calls A**, each with a bounded connection pool: pools on both sides fill with in-flight calls waiting on the other side. ## Why these are harder to diagnose Runtime deadlock detectors track only lock types they own. Pool permits, queue slots, worker slots and remote leases carry no ownership metadata the runtime can walk, so the automatic report says nothing and the dump looks like ordinary contention: many threads parked in a borrow or a put. The evidence you actually need is capacity accounting - how many instances exist, who holds them, and whether every holder is itself blocked. That argues for making these resources observable up front: metrics for pool saturation, wait time, borrow depth (how many permits one task can hold at once), and queue fullness turn an invisible deadlock into a visible one. ## The generalized rule Whenever a unit of work can hold one instance of a bounded resource while requesting another instance of the same or another bounded resource, you have reconstructed hold-and-wait over that resource, and a cycle becomes possible. Recognising that pattern - **nested acquisition of bounded capacity** - is the transferable skill; the specific resource is incidental.