Thread Starvation and Deadlock

On this page 14

Part II — Concurrency · Interview reference

Liveness failures: the system is “running” but work does not make progress. Seniors must define deadlock vs livelock vs starvation, know Coffman conditions, and design prevention / detection strategies.

Definitions

Failure	Definition
Deadlock	Set of threads permanently blocked; each waits for a resource held by another in the set (cycle)
Livelock	Threads keep changing state in response to each other but make no useful progress
Starvation	A thread never gets resources / CPU because others are continually preferred
Priority inversion	Lower-priority holds lock needed by higher-priority; medium-priority preempts → high waits (classic RT issue)

Deadlock — Coffman conditions (all required)

Mutual exclusion — resource not shareable
Hold and wait — hold one resource while waiting for another
No preemption — cannot forcibly take resource away
Circular wait — cycle in wait-for graph

Break any one to prevent deadlock.

Wait-for graph mental model

T1 → T2 → T3 → T1   (cycle ⇒ deadlock)

Nodes = threads (or transactions); edges = “waits for resource held by.”

DB systems detect cycles in lock waits; app servers rely on dumps + careful design.

Common deadlock shapes in services

Shape	Example
Lock order inversion	T1: lock A then B; T2: lock B then A
Nested synchronized	Different call paths acquire monitors in different orders
Thread-pool deadlock	All pool threads blocked waiting for results that need the same pool
Connection pool + lock	Hold DB connection while waiting on another locked resource
Distributed deadlock	A waits on B’s RPC; B waits on A’s RPC (harder to see)

Classic interview scenario: submitting tasks to the same Executor from inside a task and then Future.get() — can deadlock a fixed pool.

Production case study (high volume)

Context: Order orchestration service: fixed pool of 32 workers; each task fans out to inventory + pricing CompletableFutures submitted to the same pool, then join(). Why seniors care: Pool-induced deadlock takes down checkout for everyone; looks like “hang” with healthy CPU; blast radius is the whole dependency graph sharing that executor. Failure / symptom: All threads WAITING on Future.get; queue depth grows; LB health fails; jstack shows classic cycle. Resolution: Separate pools for orchestration vs blocking work; supplyAsync on dedicated executor; avoid blocking worker on same-pool children; deadlock detection via ThreadMXBean in canaries. Seen at / similar to: Widespread Spring @Async misuse; Cassandra Java driver / Netty event-loop deadlocks as cousins; Amazon Builders’ Library “avoiding deadlock” themes.

Prevention strategies

Strategy	How
Lock ordering	Global total order; always acquire by order
Lock timeout / tryLock	Fail + retry / abort instead of infinite wait
Avoid hold-and-wait	Acquire all needed locks at once; or don’t hold while calling out
No locks / finer design	Immutability, concurrent structures, single-threaded ownership
Resource hierarchy	Document layers (e.g. never call into module B while holding module A’s lock)
Separate pools	Isolate “orchestration” threads from “blocking work” threads

Detection & recovery

Detection

Thread dumps (jstack, IDE, kill -3): look for BLOCKED cycles
JFR / lock profilers
DB: pg_locks, InnoDB status, deadlock logs
Timeouts as soft detection

Recovery

Abort one participant (DB does this); app may fail request and retry idempotently
Restart process (last resort; masks design bug)

Starvation

Causes

Unfair locks under continuous contention (writer starvation with some RW locks)
Scheduler / priority misuse
Tasks always jumping queue (poor queue policy)
Shared pool dominated by long CPU tasks → short tasks starve

Mitigations

Fair locks when necessary (throughput cost)
Separate queues / pools by workload class
Aging / priority boost
Bound retries and backoff (also helps livelock)

Livelock

Example: two threads continually yielding to each other; or endless retry storms without jitter.

Mitigations: randomized backoff, retry budgets, circuit breakers, idempotent reconcile loops with progress metrics.

Production case study (high volume)

Context: Multi-region banking ledger: service A waits on B’s RPC while holding a DB row lock; B calls back into A for enrichment (distributed deadlock). Separately, unfair ReadWriteLock starves writers refreshing FX rates. Why seniors care: Local Coffman thinking extends to RPC+DB; livelock from retry storms burns error budgets; writer starvation makes “eventually consistent” configs never converge. Failure / symptom: Lock wait timeouts in Postgres; paired services with elevated latency; FX rates stale for minutes under read floods. Resolution: Never hold DB locks across RPC; break cycles with async events/outbox; timeouts + idempotent retry with jitter; fair locks or separate read snapshots for config; dependency graphs in architecture review. Seen at / similar to: Stripe/bank core ledgers; Google Chubby/lock service lore; AWS “timeouts, retries, and backoff with jitter” classic.

Java under the hood — detection & locks

Tool / API	Role
`jstack` / `jcmd Thread.print` / kill -3	Thread dump: `BLOCKED` on monitors, lock owners
`ThreadMXBean.findDeadlockedThreads()`	Programmatic cycle detection (monitors + some ownable synchronizers)
JFR / async-profiler	Lock contention profiles
AQS fair vs unfair	Fair reduces starvation, lowers throughput; default locks often unfair
`tryLock(timeout)`	Break hold-and-wait / detect stuck acquisition
Same-pool `Future.get()`	Fixed `ThreadPoolExecutor`: all workers blocked waiting for tasks that need the same pool → deadlock

Classic fix patterns: run nested work on caller thread, use a separate pool, or async composition without blocking the worker.

What interviewers probe

Define deadlock and give Coffman conditions.
Draw a cycle for a two-lock example; fix with ordering.
Thread-pool deadlock with Future.get() — how to redesign (same-thread execution, separate pool, async composition).
How do you diagnose in production? (dumps, metrics: stuck threads, queue latency).
Starvation vs deadlock differences.
Distributed systems: RPC cycles / dependency cycles analogous to deadlock.
Production dumps — narrate finding a same-pool Future.get deadlock under peak traffic.

Senior-level expectation: Prevention by design; recognition of pool-induced deadlocks; operational diagnosis path.

Pitfalls

Logging + locking in inconsistent order across modules
Calling foreign/unknown code while holding locks (callbacks!)
One giant shared executor for mixed blocking workloads
Infinite retries without jitter → livelock-like outages
“Fixing” deadlock only with larger timeouts (hides, adds latency)
Holding row locks while calling sister services

Cross-references

Threads
Thread safety
Thread pools
Microservices rules — distributed deadlock analogues