Deadlock, Starvation, Livelock

Three distinct ways concurrent code can stop making progress — interviewers ask this specifically to check whether a candidate conflates them, since the symptoms ("it's stuck") look identical from the outside but the causes and fixes are completely different.

Deadlock: the four necessary conditions

A deadlock requires all four of these simultaneously — remove any one, and deadlock becomes impossible:

1. Mutual exclusion — a resource can only be held by one thread at a time (true of any lock).
2. Hold-and-wait — a thread holds one resource while waiting for another.
3. No preemption — a lock can't be forcibly taken away from the thread holding it.
4. Circular wait — a cycle exists: thread A waits for a resource thread B holds, and thread B waits for a resource thread A holds.

// Classic deadlock: two locks, acquired in opposite order on two threads
Object lockA = new Object();
Object lockB = new Object();

// Thread 1
synchronized (lockA) {
    Thread.sleep(10); // gives Thread 2 time to grab lockB
    synchronized (lockB) { /* ... */ }
}

// Thread 2
synchronized (lockB) {
    Thread.sleep(10);
    synchronized (lockA) { /* ... */ } // waits for lockA, which Thread 1 holds — deadlock
}

Thread 1 holds lockA, waiting for lockB. Thread 2 holds lockB, waiting for lockA. Circular wait, and neither will ever release what it's holding — permanent deadlock.

Detecting deadlock via thread dump

jstack <pid>

A genuine deadlock produces an unmistakable marker in the output:

Found one Java-level deadlock:
=============================
"Thread-1":
  waiting to lock monitor 0x... (object lockA),
  which is held by "Thread-0"
"Thread-0":
  waiting to lock monitor 0x... (object lockB),
  which is held by "Thread-1"

jstack (or a thread dump triggered via kill -3 on the JVM process, or a profiler) walks every thread's lock-wait graph and explicitly detects cycles — this is the standard first diagnostic step when a Java service appears hung: take a thread dump, search for "Found one Java-level deadlock."

Prevention: consistent lock ordering

The most reliable fix removes the circular wait condition by establishing a global, consistent order in which locks are acquired everywhere in the codebase:

// Fix: always acquire lockA before lockB, everywhere, no exceptions
synchronized (lockA) {
    synchronized (lockB) { /* ... */ }
}
// Even the thread that conceptually "wants B first" must still acquire A first

If every code path that needs both locks always takes them in the same order, a cycle can never form — one thread might have to wait, but it will always eventually get both locks once the thread ahead of it releases them, because no thread is ever waiting for a lock while holding one that would complete a cycle.

tryLock with timeout: deadlock avoidance instead of prevention

When consistent ordering isn't practical (e.g. locks acquired dynamically, in an order determined by runtime data), ReentrantLock.tryLock(timeout) offers a back-off strategy instead:

if (lockA.tryLock(100, TimeUnit.MILLISECONDS)) {
    try {
        if (lockB.tryLock(100, TimeUnit.MILLISECONDS)) {
            try { /* critical section */ }
            finally { lockB.unlock(); }
        } else {
            // couldn't get lockB — release lockA and retry later, breaking hold-and-wait
        }
    } finally { lockA.unlock(); }
}

This breaks the hold-and-wait condition instead of circular wait: rather than blocking indefinitely while holding one lock, a thread gives up and retries if it can't get everything it needs within a bounded time — trading a small chance of a wasted retry for the guarantee that no thread blocks forever.

Starvation: distinct from deadlock

Starvation is a scheduling fairness problem, not a circular-wait problem: a thread is perpetually ready to run but never gets CPU time or a lock, because other threads (often higher-priority ones, or ones favored by an unfair lock's internal ordering) keep winning the race. Nothing is circularly blocked — the starved thread could eventually run, it just never actually does under the specific scheduling pattern in play. The default (unfair) synchronized/ReentrantLock behavior can starve a thread under sustained contention from other threads that keep re-acquiring the lock first; a fair lock (new ReentrantLock(true)) trades some throughput for guaranteeing FIFO ordering, which eliminates this specific starvation risk.

Livelock: actively working, making zero progress

Livelock is the strangest of the three: threads are not blocked — they're actively executing, responding to each other in real time — but the net effect is no actual progress. The canonical analogy: two people in a hallway repeatedly stepping the same direction to "let the other pass," perfectly in sync, neither ever getting through.

// Simplified livelock shape: both threads politely back off and retry, forever, in lockstep
while (!tryAcquireBoth(lockA, lockB)) {
    releaseAnyHeld();
    Thread.sleep(RETRY_DELAY); // if both threads use the same delay, they retry in sync forever
}

If two threads keep detecting contention, backing off identically, and retrying at the same moment, they can repeat this forever without either succeeding — this is exactly the failure mode overly-naive tryLock-and-retry "deadlock avoidance" code can accidentally introduce if every thread's retry behavior is too uniform. The fix is usually adding randomized backoff (jittered retry delays) so competing threads desynchronize over time instead of retrying in lockstep.

Follow-up questions this topic invites — and their answers

Q: Can you have deadlock without any explicit locks, e.g. using only blocking queues? A: Yes — any resource with mutual exclusion and hold-and-wait semantics can deadlock, not just synchronized/Lock objects. Two threads each blocked in queue.put() waiting for the other to take() from a queue it's simultaneously waiting to fill can deadlock structurally, even with zero explicit lock objects involved.

Q: Does removing just one of the four deadlock conditions always fix it, or do you need to remove more than one? A: Removing exactly one is sufficient in principle — deadlock requires all four simultaneously by definition — but in practice, some conditions (like mutual exclusion) are usually inherent to the resource and can't be removed at all, which is why circular wait (via lock ordering) and hold-and-wait (via tryLock timeouts) are the two conditions realistically targeted.

Q: Is starvation always a bug? A: Not necessarily by design intent — some systems deliberately use priority-based scheduling where low-priority work is expected to yield to high-priority work indefinitely under load. It becomes a bug when starvation is unintentional and affects work that was supposed to complete in bounded time.

Q: How would you distinguish deadlock from livelock by just looking at CPU usage? A: A deadlocked JVM shows the deadlocked threads at near-zero CPU (they're blocked, not running) — a jstack dump confirms it directly. A livelocked JVM shows those threads actively consuming CPU (they're genuinely executing, just unproductively) with no blocked-state threads in the dump — the absence of a "Found one Java-level deadlock" marker despite the app being visibly stuck is itself a strong signal to look for livelock instead.