Deadlock, livelock, and starvation: when threads get in each other's way

← Back to the section

Threads in Java run in parallel, and most of the time that's good. But sometimes they start getting in each other's way: they wait, mark time in place, or one thread is left forever without work. Let's look at three main scenarios.

Deadlock — mutual blocking

Deadlock (mutual blocking) is a situation where two or more threads wait for each other and none can continue. The program doesn't crash with an exception — it simply hangs.

A classic example: thread A holds lock 1 and wants lock 2, thread B holds lock 2 and wants lock 1 — both wait forever. The program below arranges exactly that and asks the JVM what is going on: findDeadlockedThreads() returns the threads closed into a cycle.

live example

import java.lang.management.ManagementFactory;
import java.lang.management.ThreadMXBean;

public class DeadlockDemo {
    private static final Object lock1 = new Object();
    private static final Object lock2 = new Object();

    public static void main(String[] args) throws InterruptedException {
        Thread a = new Thread(() -> grabBoth(lock1, lock2, "A"));   // A: lock1 first
        Thread b = new Thread(() -> grabBoth(lock2, lock1, "B"));   // B: lock2 first
        a.setDaemon(true);
        b.setDaemon(true);
        a.start();
        b.start();
        Thread.sleep(500);

        ThreadMXBean threads = ManagementFactory.getThreadMXBean();
        long[] inCycle = threads.findDeadlockedThreads();
        System.out.println("A: " + a.getState() + ", B: " + b.getState());
        System.out.println(inCycle == null ? "no deadlock" : "deadlock, threads in the cycle: " + inCycle.length);
    }

    private static void grabBoth(Object first, Object second, String name) {
        synchronized (first) {
            try {
                Thread.sleep(100);              // let B grab its lock
                synchronized (second) {
                    System.out.println(name + " did the work");
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }
}

It prints A: BLOCKED, B: BLOCKED and deadlock, threads in the cycle: 2; "did the work" never appears. setDaemon(true) is here only so the program can finish: a normal thread stuck in a deadlock keeps the JVM alive.

The four Coffman conditions

A deadlock arises only when four conditions hold at the same time — conditions formulated by Edward Coffman in 1971:

1. Mutual exclusion — a resource can be held by only one thread at a time.
2. Hold and wait — a thread holds resources it has already acquired while waiting for new ones.
3. No preemption — a resource cannot be taken away from a thread by force; the thread must release it itself.
4. Circular wait — there is a chain of threads where each one waits for a resource held by the next.

To prevent a deadlock, it's enough to break at least one of the four.

How to avoid deadlock

Approach 1 — a fixed lock acquisition order

The simplest trick: always acquire multiple locks in the same order. If both threads take lock1 first and lock2 second, circular wait is impossible.

live example

public class LockOrderDemo {
    private static final Object lock1 = new Object();
    private static final Object lock2 = new Object();

    public static void main(String[] args) throws InterruptedException {
        Runnable job = () -> {
            synchronized (lock1) {          // always lock1 first
                synchronized (lock2) {      // then lock2
                    System.out.println(Thread.currentThread().getName() + " passed both locks");
                }
            }
        };
        Thread a = new Thread(job, "thread-A");
        Thread b = new Thread(job, "thread-B");
        a.start(); b.start();
        a.join(); b.join();
        System.out.println("both finished, no circular wait");
    }
}

Both lines print, the program exits. Reverse the order in the second thread and you get the first example back.

Approach 2 — tryLock with a timeout

ReentrantLock lets you attempt to acquire a lock and back off if you didn't succeed within the allotted time. This breaks the "hold and wait" condition: the thread releases what it holds and retries later.

live example

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;

public class TryLockDemo {
    private static final ReentrantLock lock1 = new ReentrantLock();
    private static final ReentrantLock lock2 = new ReentrantLock();

    public static void main(String[] args) throws InterruptedException {
        lock2.lock();                                  // held by the main thread
        Thread worker = new Thread(() -> {
            try {
                for (int attempt = 1; attempt <= 5; attempt++) {
                    lock1.lock();
                    try {
                        if (lock2.tryLock(100, TimeUnit.MILLISECONDS)) {
                            try {
                                System.out.println("attempt " + attempt + ": both locks are mine");
                                return;
                            } finally {
                                lock2.unlock();
                            }
                        }
                        System.out.println("attempt " + attempt + ": second lock is busy, releasing the first");
                    } finally {
                        lock1.unlock();                // released whatever the outcome
                    }
                    Thread.sleep(150);                 // only then try again
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });
        worker.start();
        Thread.sleep(400);
        lock2.unlock();                                // release while the worker still tries
        worker.join();
    }
}

The first two attempts print "second lock is busy", the third one prints "both locks are mine". What matters here is not tryLock so much as finally: the first lock is released whatever the outcome — otherwise a failed attempt leaves it held and turns the cure into the disease.

Diagnostics: thread dump

When an application hangs and you suspect a deadlock, take a thread dump (a snapshot of all threads' state). The JVM can produce one while the application runs.

jps -l          # find the PID of the Java process
jstack <PID>    # take a thread dump

In the jstack output, look for the block Found one Java-level deadlock: — the JVM detects circular waits itself and shows which thread holds what and waits for what. It is the same search findDeadlockedThreads() did above, only from outside the process, without touching the code.

Found one Java-level deadlock:
=============================
"Thread-0": waiting to lock monitor 0x... which is held by "Thread-1"
"Thread-1": waiting to lock monitor 0x... which is held by "Thread-0"

A thread dump also shows threads stuck in BLOCKED or WAITING longer than expected.

Livelock — marking time in place

Livelock is when threads are active and not blocked, yet they make no progress. They constantly react to each other and get in the way — like two people in a narrow hallway who politely step aside at the same moment and keep colliding anyway.

Example: two threads use tryLock and always back off at the same time — each sees the other is active and postpones its work again.

The cure is to add a random delay before retrying, so the threads spread out in time:

// A random pause before retrying
long pause = (long) (Math.random() * 50);   // 0–50 ms
Thread.sleep(pause);

The random addition to the pause is called jitter: it separates threads that would otherwise collide again at the same moment. Next to it one almost always finds exponential backoff: every next pause is longer than the previous one — 50 ms, 100, 200, 400. A growing delay plus a random spread is the usual retry recipe in network protocols and distributed systems.

Starvation — a starving thread

Starvation is when one or more threads persistently fail to get CPU time or access to a resource because other threads always turn out to be higher priority.

A typical cause: a low-priority thread, or a thread that forever loses the competition for a lock. It isn't technically blocked, but its task never gets done.

ReentrantLock lets you enable fair mode: the lock is granted to whoever has been waiting the longest.

// true = fair mode, threads get the lock in turn
ReentrantLock fairLock = new ReentrantLock(true);

Fair mode costs performance: tracking the queue is not free. Turn it on where starvation is a real problem, not an assumption.

How the three problems differ from each other

In short

• Deadlock — threads wait for each other in a cycle and don't move. It arises when the four Coffman conditions hold.
• The main defense against deadlock is a single lock acquisition order or tryLock with a timeout. Hold locks briefly and don't call foreign code inside synchronized.
• Livelock — threads are active but get in each other's way. Cured by a random pause before retrying.
• Starvation — one thread forever loses the competition for a resource. new ReentrantLock(true) evens the odds.
• Thread dump (jstack) is the main diagnostic tool: the JVM finds deadlocks itself and shows who holds what.

Further reading

• synchronized and monitor in Java — how the synchronized keyword works, the object monitor, the entry conditions for a deadlock.
• ReentrantLock and other locks — tryLock, lockInterruptibly, Condition, and when locks beat synchronized.
• Races in multithreaded programs — the other half of thread problems: corrupted data, not a hang.
• ExecutorService and the thread pool — how to manage the thread lifecycle and avoid creating them by hand.