A task running on a bounded worker pool submits a second task to that same pool and then blocks waiting for the second task's result. Explain why this arrangement can deadlock, and what determines whether it actually will.
answer
- parent holds a worker while waiting for a child
- hold-and-wait on non-preemptible threads
- N blocked parents = permanent stall
- never await a future from your own pool
- separate pool per dependency layer
basics
~20 sThe waiting parent still occupies a worker. If every worker is a blocked parent, no worker is left to run the queued children, so parents wait on children that can never start. It is a resource deadlock where the scarce resource is the worker thread.
solid answer
~60 sThreads are the resource being allocated. A parent that blocks on its child's result holds its worker while requesting another one - hold-and-wait. The child sits in the queue, which is non-preemptible: nothing can evict the blocked parent to run it. If all `N` workers happen to be blocked parents at the same moment, the wait cycle is closed and the pool is permanently stuck; it never recovers, even if load drops. Whether it happens is a probability question about concurrency, not a design property: with `N` workers it takes only `N` simultaneous parents, so a pool of 8 survives light traffic and deadlocks under a burst - which is why this bug ships. Depth of nesting makes it worse: `d` levels of blocking need more than `N` free slots per chain. Fixes: never block on a result produced by your own pool. Use a separate pool per dependency layer, compose asynchronously with callbacks or continuations so waiting consumes no thread, or run the child inline on the caller.
code
text · 8 linespool P: workers = 2, queue = []
t0 worker1 <- A1 worker2 <- A2
t1 A1 submits B1 -> queue=[B1]
A2 submits B2 -> queue=[B1,B2]
t2 A1 awaits B1 (worker1 held, blocked)
A2 awaits B2 (worker2 held, blocked)
t3 queue=[B1,B2] free workers = 0 -> forevergo deeper
Recall the core mechanic: the waiting task keeps its thread, so the task it is waiting for may never get one.
State it as hold-and-wait on non-preemptible thread resources, note that N simultaneous parents suffice, and give the rule 'never await a future from your own pool'.
Discuss why it is load-dependent and ships to production, how to detect it in a thread dump, and the layered-pool and continuation-based fixes.
Argue for a structural invariant enforced by design or tests - the wait-for graph across executors must be acyclic - and weigh async composition against the complexity it adds.
## The setup ``` task A (running on pool P): fut = P.submit(task B) result = fut.await() // blocks this worker use(result) ``` Nothing here looks wrong: A decomposes its work, hands a piece to the pool, and waits. On a laptop with a small load it works every time. ## Why it deadlocks Model the worker threads as a pool of `N` identical, non-preemptible resources. Running any task requires holding one. When A blocks on `fut.await()`, it does not give its worker back - it holds resource 1 while requesting resource 2 (for B). That is textbook hold-and-wait. Now suppose `N` copies of A start at once. All `N` workers are held by blocked parents. Every child B is in the queue, and the queue can only be drained by a worker. So: - each A waits for a B, - each B waits for a worker, - every worker is held by an A. The wait-for graph has a cycle, and all four Coffman conditions hold: mutual exclusion (one task per worker), hold-and-wait, no preemption (you cannot yank a task off a thread mid-block), circular wait. The pool never recovers - unlike saturation, which drains when load falls, this state is permanent until the process restarts. ## What determines whether it happens It is a race, not a certainty, which is exactly what makes it dangerous: - **Concurrency of parents.** You need `N` parents blocked simultaneously. A pool of 100 hides the bug for months; a traffic spike or a slow downstream that makes parents linger exposes it. - **Nesting depth.** With `d` levels of blocking dependency (A waits for B, B waits for C), a chain occupies `d` workers, and the pool must always keep a free slot for the next level. A safe rule for a strict tree of depth `d` with at most `k` concurrent roots is `N > k * d` - which is a promise you usually cannot keep as load varies. - **Queue policy.** An unbounded queue guarantees the children wait forever. A bounded queue can turn the deadlock into a rejection or into a blocked submitter, which is a different failure but not a fix. - **Partial versions.** Even one blocked parent per `N` is enough to reduce effective parallelism; you lose throughput long before you lose liveness. ## The fixes, in order of preference 1. **Do not block on your own pool.** Make it a rule with a test: the future you await must be produced by a *different* executor than the one you are running on. 2. **Separate pools per dependency layer.** Layer 1 tasks submit to pool 2, layer 2 to pool 3. The wait-for graph is then a DAG across pools, and a cycle is structurally impossible. This is the strongest guarantee and the reason 'isolate pools by layer' is standard advice. 3. **Do not block at all.** Compose asynchronously: instead of `await`, attach a continuation that runs when the child completes. The parent's worker is released immediately, so a blocked parent stops being a held resource. Continuation-based composition converts the deadlock into ordinary queueing. 4. **Run the child on the caller.** If the child is cheap and side-effect-free, execute it inline rather than submitting it - the caller-runs strategy. This removes the dependency entirely. 5. **Engines that help instead of block.** A work-stealing engine whose join operation makes the waiting thread execute pending subtasks converts waiting into useful work, so the thread is never idle-blocked. That guarantee holds only if tasks are non-blocking, purely computational, and wait solely on their own descendants - a task that blocks on a socket breaks it. Growing the pool 'to be safe' is not a fix, only a delay: any bounded pool has an `N`, and traffic eventually finds it.
- Would making the pool larger, or unbounded, remove the risk?A larger bounded pool only raises the number of simultaneous blocked parents needed, so it converts a certainty into a rare, load-dependent outage - typically the worst kind. An unbounded pool avoids the deadlock by always creating a new thread, but trades it for unbounded thread creation: memory per stack, scheduler overhead, and possible exhaustion of OS thread limits under the same burst. Neither addresses the structural hold-and-wait.
- Why does composing with callbacks or continuations instead of blocking eliminate the problem?Because the parent stops holding a worker while it waits. It registers what to do with the result and returns the thread to the pool immediately, so the child can be picked up by that very worker. The dependency still exists in the data flow, but it is no longer a resource dependency, and a cycle in the wait-for graph cannot form. The cost is that the code must be written in continuation style and that state must be carried explicitly rather than living on the stack.
A restaurant with four cooks where every cook, mid-dish, needs a sauce that only a cook can make. If all four are standing still waiting for sauce, nobody is free to make sauce, and the kitchen never moves again.
saying these in an interview costs you the question
- Saying a bigger pool makes it safe
- Believing the blocked parent releases its thread back to the pool
- Calling it starvation or saturation - it does not recover when load drops
- Assuming a bounded queue prevents it, when it only changes the failure mode
- Claiming timeouts on the await are a fix rather than a way to fail faster