PHASE 13Advanced ~14 min· topic 9 of 11

Topic 13.9

Deadlock, Livelock and Starvation

In one line

A deadlock is threads waiting for each other forever, usually because they take the same locks in different orders. Livelock is threads busily reacting to each other without progress, and starvation is a thread that never gets a turn. Lock ordering, timeouts and fewer shared locks prevent them.

Think of it like this

Two cars meet on a narrow bridge from opposite ends, and neither will reverse. Both wait forever: deadlock. Two people in a corridor both step left, then both step right, again and again, never passing: livelock. At a busy counter, one shy customer keeps getting pushed back by louder ones and is never served: starvation.

Words you'll meet

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Deadlock: Two or more threads each waiting for a lock the other holds, so none can ever continue.
Circular wait: A chain of threads where each waits for the next, and the last waits for the first.
Lock ordering: Always taking several locks in the same agreed order, which makes deadlock impossible.
Livelock: Threads keep changing state in response to each other but never make progress.
Starvation: A thread that is ready to run never gets the lock or CPU it needs.
Thread dump: A snapshot of every thread's state and stack, used to diagnose hangs.
Jitter: A small random delay added to retries so threads don't retry in lockstep.

Step by step

01How the deadlock forms

Thread 1 holds A and wants B. Thread 2 holds B and wants A. Neither releases what it has, so the wait never ends.

It may only happen when the two transfers overlap at exactly the wrong moment, which is why deadlocks show up rarely and under load.

Deadlock.javawhole filejava

void transfer(Account from, Account to, int amount) {
    synchronized (from) {             // thread 1 locks a, thread 2 locks b
        synchronized (to) {           // each now waits for the other: deadlock
            from.balance -= amount;
            to.balance += amount;
        }
    }
}

How the deadlock formsdiagram

Rendering diagram…

02Break the cycle with a global order

Decide an order every thread follows, such as "lower account id first". Both transfer(a, b) and transfer(b, a) then lock a before b, so whoever gets a first also gets b, and the other waits without holding anything.

For objects without a natural id, System.identityHashCode can order them, with a tie-breaker lock for the rare equal hashes.

03Back off with tryLock

With ReentrantLock.tryLock(50, MILLISECONDS), a thread that can't get the second lock releases the first and retries later. Add a random delay before retrying so two threads don't keep colliding (livelock).

04Reading a deadlock in a thread dump

The JVM detects monitor and ReentrantLock cycles when you take a thread dump. It prints which thread holds which lock and which it's waiting for, plus each thread's stack, pointing straight at the two lines that lock in opposite orders.

terminal

$ jstack 12345

── expected output ──

Found one Java-level deadlock:

=============================

"t2":

waiting to lock monitor 0x00007f3a1c003a80 (object 0x0000000711e1a2b8, a Main$Account),

which is held by "t1"

"t1":

waiting to lock monitor 0x00007f3a1c006c30 (object 0x0000000711e1a2d0, a Main$Account),

which is held by "t2"

05Designs that avoid the problem

Hold at most one lock at a time where possible. Don't call methods you don't control (listeners, overridable methods) while holding a lock: they might take other locks. Prefer higher-level tools (concurrent collections, queues, immutable data) that don't need nested locks.

Try it yourself

1
Swap the order
In "Lock ordering makes transfers deadlock-free", change transfer to lock from then to directly. Run it on your own JDK several times: sometimes it hangs. Take a thread dump with jstack while it hangs and find the deadlock report.
2
Remove the jitter
In the tryLock example, replace the random sleep with Thread.sleep(1). It still finishes, but on a multi-core JDK you may see it take longer as the two threads keep colliding in step.

Code & diagrams

Lock ordering makes transfers deadlock-free New tab

With the naive version (lock `from` then `to`), this program can hang forever on a multi-core JDK.

Expected output

a=1000 b=1000 total=2000

Backing off with tryLock Java 5+ New tab

done[0]++ is safe here because it only runs while holding both locks.

Expected output

operations completed: 400

Detecting a deadlock from code (run on your own JDK)java

ThreadMXBean bean = ManagementFactory.getThreadMXBean();
long[] ids = bean.findDeadlockedThreads();          // null when there is none
if (ids != null) {
    for (ThreadInfo info : bean.getThreadInfo(ids)) {
        System.out.println(info.getThreadName() + " waits for " + info.getLockName()
                + " held by " + info.getLockOwnerName());
    }
}

Output

t2 waits for Main$Account@1b6d3586 held by t1
t1 waits for Main$Account@4554617c held by t2

Break it on purpose

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

Break #1

Calling a listener while holding a lock

Inside synchronized (this), call listener.onChange(), where the listener locks another object that another thread holds while calling into this one.

terminal

$ jstack <pid>

── what you'll see ──

Found one Java-level deadlock: ... waiting to lock <...> (a Model) which is held by "ui"

Myth vs fact

Myth

The JVM detects deadlocks and breaks them.

Fact

It only reports them in thread dumps and via ThreadMXBean. Deadlocked threads stay stuck until the JVM exits.

Myth

Deadlocks need many threads.

Fact

Two threads and two locks are enough.

Myth

Adding more locks makes code safer.

Fact

More locks taken together means more chances for a cycle. Fewer, coarser or ordered locks are safer.

Pro corner

Extra depth for experienced readers. New to this? Skip it for now and come back later.

▸
Database deadlocks follow the same rules: rows locked in different orders by two transactions. Databases detect them and abort one transaction; Java doesn't, so your code must prevent them.
▸
ThreadMXBean.findDeadlockedThreads() also finds cycles involving ReentrantLock and other ownable synchronizers, while the older findMonitorDeadlockedThreads() sees only synchronized monitors.
▸
Lock-ordering bugs are a good target for static analysis and for tests that run conflicting operations in tight loops on many cores; jcstress (the OpenJDK concurrency stress harness) helps exercise rare interleavings.

Remember this

1
A deadlock needs four conditions at once (the Coffman conditions): mutual exclusion (a lock is held by one thread), hold and wait (a thread holds one lock while waiting for another), no preemption (locks can't be taken away), and circular wait (thread A waits for B's lock while B waits for A's). Break any one and deadlock is impossible.
2
The classic case: thread 1 runs transfer(a, b) and locks a then b; thread 2 runs transfer(b, a) and locks b then a. Each gets its first lock and waits for the other's. Both are BLOCKED forever and the JVM does nothing about it.
3
Fix 1, lock ordering: always acquire multiple locks in one global order (for example by account id). Then a circular wait can't form. Fix 2, timeouts: tryLock(timeout) gives up and backs off instead of waiting forever. Fix 3, fewer locks: hold one lock at a time, keep critical sections short, never call unknown code (callbacks, listeners) while holding a lock.
4
Finding deadlocks: a thread dump (jstack <pid>, jcmd <pid> Thread.print, or kill -3) prints Found one Java-level deadlock: with the threads and locks involved (Topic 14.5). In code, ThreadMXBean.findDeadlockedThreads() reports them for monitoring.
5
Livelock often comes from "polite" retry logic: both threads detect a conflict, back off, and retry at the same moment, forever. Add random jitter to retry delays. Starvation comes from unfair scheduling or a thread holding a lock too long; fair locks or shorter critical sections help.

Explain it without notes

What four conditions must hold for a deadlock, and how does lock ordering prevent it?

How would you find the cause of a hung Java service?

What is livelock and how does jitter help?

Practice

Explain how you'd make a transfer between two Accounts deadlock-free when accounts have no id field.

Trade-offs

↔
Lock ordering prevents deadlock with no runtime cost but needs every developer to follow the rule; tryLock with back-off is self-contained but adds retries and complexity.
↔
Coarse locks avoid deadlocks but reduce parallelism; fine-grained locks scale but must be carefully ordered.

Done when you can

Done when you can name the four deadlock conditions and the classic two-lock example.
Done when you can prevent deadlock with lock ordering and with tryLock and back-off.
Done when you can find a deadlock in a thread dump.
Done when you can explain livelock and starvation and how to avoid them.

Command Palette

Words you'll meet

Step by step

01How the deadlock forms

02Break the cycle with a global order

03Back off with tryLock

04Reading a deadlock in a thread dump

05Designs that avoid the problem

Try it yourself

Swap the order

Remove the jitter

Code & diagrams

Break it on purpose

Calling a listener while holding a lock

Myth vs fact

Pro corner

Remember this

Explain it without notes

Practice

Trade-offs

Done when you can