Java: wait/notify, Deadlock and Liveness

Description

Threads often need to wait for each other. A consumer waits until there's work in a queue; a producer waits until there's room; a payment waits until two accounts are both available. Getting this coordination right is what separates concurrent code that runs for months from code that freezes at 3 a.m. with every thread asleep and nothing in the logs.

There are three ways threads get stuck: waiting for something that never comes, waiting for each other in a circle (deadlock), and staying busy without getting anywhere (livelock and starvation). This skill covers all three, plus Java's built-in tool for waiting: wait and notify. Interviews love this area ("implement a bounded blocking queue", "why does this transfer code hang?"), and so do production incidents.

Here's the path, from easiest to most technical:

1. Waiting for a condition: wait, notify and the guarded-block pattern.
2. Why it's while and not if, and why notifyAll is usually the safe choice.
3. wait versus sleep, and the higher-level tools to prefer.
4. Deadlock: how two threads freeze each other, and lock ordering.
5. Livelock and starvation.

Waiting for a condition

Say a consumer thread needs an item that a producer hasn't made yet. It could loop and check over and over, but that burns CPU. Instead, Java lets a thread wait until another thread tells it something changed. The tools are three methods every object has: wait(), notify() and notifyAll().

The rules:

• You must hold the object's lock (be inside synchronized (obj)) to call obj.wait() or obj.notify(). Otherwise you get an IllegalMonitorStateException.
• wait() releases the lock and puts the thread to sleep until it's notified (or interrupted). Before wait() returns, the thread takes the lock back.
• notify() wakes one waiting thread; notifyAll() wakes all of them, and they take turns getting the lock.

Every correct use follows one pattern, called a guarded block: wait in a loop while the condition you need isn't true yet.

synchronized (lock) {
    while (!condition) {      // while, never if
        lock.wait();
    }
    // here the condition is true, and we hold the lock
}

And whoever changes the condition notifies the waiters while holding the same lock:

synchronized (lock) {
    condition = true;
    lock.notifyAll();
}

Why while, and why notifyAll

Why while? Being woken up only means "something changed", not "your condition is true". By the time the woken thread gets the lock back, another thread may have taken the item it was waiting for. A thread can even wake up with no notification at all (a spurious wakeup, which the JVM specification allows). The loop rechecks the condition every time; an if would carry on as if it were true.

Why notifyAll? Here's a one-slot buffer that passes items from producers to consumers:

synchronized void put(int x) throws InterruptedException {
    while (item != null) wait();      // wait for an empty slot
    item = x;
    notify();
}
synchronized int take() throws InterruptedException {
    while (item == null) wait();      // wait for an item
    int x = item;
    item = null;
    notify();
    return x;
}

It uses while loops and works with one producer and one consumer. With two of each, it hung in three test runs out of three, with every thread asleep in wait(). Producers and consumers wait on the same object, and notify() wakes just one waiter, chosen arbitrarily. A consumer that takes the item can wake another consumer instead of a producer. That consumer finds nothing, goes back to sleep, and now nobody is left to wake anyone. With notifyAll(), the same test finished every time.

So use notifyAll() unless every waiter waits for the same thing and any one of them can make progress.

wait versus sleep, and better tools

Thread.sleep() looks similar but behaves very differently inside a synchronized block: it keeps the lock for the whole sleep, so every other thread that needs the lock is stuck too. wait() releases it.

In everyday code you'll rarely write wait/notify yourself. java.util.concurrent has ready-made tools built on the same idea: a BlockingQueue (its put and take are exactly the producer/consumer code above, done right), CountDownLatch and Semaphore (the Concurrency module covers them). They're still worth understanding, because "implement a bounded blocking queue" is a classic interview question.

Deadlock

A bank transfer locks both accounts, so no other thread sees money in flight:

void transfer(Account from, Account to, long cents) {
    synchronized (from) {
        synchronized (to) {
            from.withdraw(cents);
            to.deposit(cents);
        }
    }
}
// thread 1: transfer(a, b, 100)        thread 2: transfer(b, a, 50)

If both transfers start at the same moment, this happens:

Each thread holds one lock and waits for the other's, forever. This is a deadlock: a cycle of threads each waiting for the next. Nothing crashes and nothing is logged; the threads just stop.

The standard fix is lock ordering: every thread takes locks in the same global order, so a cycle can't form. Here, always lock the account with the smaller id first:

Account first = from.id() < to.id() ? from : to;
Account second = (first == from) ? to : from;
synchronized (first) {
    synchronized (second) {
        from.withdraw(cents);
        to.deposit(cents);
    }
}

Two more habits help: don't call unknown code while holding a lock (a listener or callback might take locks of its own, in an order you don't control), and, with ReentrantLock, use tryLock with a timeout so a thread gives up instead of waiting forever.

When a service does freeze, a thread dump (jstack <pid>) finds the cycle for you: it ends with Found one Java-level deadlock: and names the threads and the locks each holds and wants.

Livelock and starvation

A deadlocked thread sits still. A livelocked thread keeps busy without getting anywhere. Two threads that each grab one lock, try the other with tryLock, fail, let go and retry immediately can collide in perfect step forever, like two people in a corridor who keep stepping aside the same way. A short random pause before retrying breaks the pattern.

Starvation is a thread that could run but never gets its turn. Java's built-in locks make no fairness promise, so under heavy contention one thread can keep losing the race for a lock. A thread that holds a lock for a long time starves everyone queued behind it. The fixes are shorter critical sections, a fair lock (new ReentrantLock(true), at some cost in speed), or a queue that serves waiters in order.

Common mistakes

Check yourself

Try to answer before opening each one. Recalling beats re-reading.

1. Why must wait() sit inside a while loop rather than an if?

2. What's the difference between wait() and sleep() inside a synchronized block?

3. A one-slot buffer with notify() works with one producer and one consumer but hangs with two of each. Why?

4. transfer(a, b) and transfer(b, a) each lock from and then to. How do you make deadlock impossible?

Key takeaways

• wait releases the lock and needs it to be called; sleep keeps it.
• Guarded blocks: while (!condition) wait();, and notifyAll() unless every waiter is interchangeable.
• In real code, prefer BlockingQueue, latches and semaphores.
• A deadlock is a cycle of waiting threads: order your locks and don't call unknown code while holding one.
• Livelock needs a random backoff; starvation needs shorter or fairer locking.