Deadlock, Livelock & Starvation

#Introduction

Locks fix race conditions but introduce a new class of failures: threads that stop making progress. The three liveness problems are deadlock (threads wait for each other forever), livelock (threads stay busy but achieve nothing) and starvation (a thread never gets the resource it needs).

#What Is a Deadlock?

A deadlock occurs when two or more threads each hold a lock and wait for a lock held by another, forming a cycle — so none of them can ever continue.

class Account {
    private int balance;

    void withdraw(int amount) { balance -= amount; }
    void deposit(int amount)  { balance += amount; }
}

void transfer(Account from, Account to, int amount) {
    synchronized (from) {
        synchronized (to) {
            from.withdraw(amount);
            to.deposit(amount);
        }
    }
}

// Thread 1
transfer(accountA, accountB, 100);

// Thread 2 — at the same time
transfer(accountB, accountA, 50);

Both threads are BLOCKED permanently. The JVM does not resolve Java-level deadlocks — the threads stay stuck until the process restarts.

#The Four Coffman Conditions

A deadlock can happen only if all four conditions hold at once:

#Strategies to Prevent Deadlock

1. Impose a Global Lock Order — Breaks Circular Wait

Always acquire multiple locks in the same order everywhere — for example, by a unique ID:

void transfer(Account from, Account to, int amount) {
    Account first  = from.getId() < to.getId() ? from : to;
    Account second = from.getId() < to.getId() ? to   : from;

    synchronized (first) {
        synchronized (second) {
            from.withdraw(amount);
            to.deposit(amount);
        }
    }
}

Both threads now lock the lower-ID account first, so no cycle can form. This is the most common and most reliable technique (a lock hierarchy).

2. Use tryLock with a Timeout — Breaks Hold and Wait

ReentrantLock.tryLock() lets a thread give up instead of waiting forever:

boolean transfer(Account from, Account to, int amount) throws InterruptedException {
    long deadline = System.nanoTime() + TimeUnit.SECONDS.toNanos(1);

    while (System.nanoTime() < deadline) {
        if (from.lock.tryLock()) {
            try {
                if (to.lock.tryLock()) {
                    try {
                        from.withdraw(amount);
                        to.deposit(amount);
                        return true;
                    } finally {
                        to.lock.unlock();
                    }
                }
            } finally {
                from.lock.unlock();     // release what we hold and retry
            }
        }
        Thread.sleep(ThreadLocalRandom.current().nextInt(1, 10));   // random back-off avoids livelock
    }
    return false;   // couldn't get both locks in time
}

If the second lock isn't available, the thread releases the first and retries, so it never holds one lock while waiting indefinitely for another.

3. Avoid Nested Locks

Design so that a thread needs only one lock at a time where possible. For example, update each account in its own transaction step, or route all changes to one account through a single owner thread or queue.

4. Keep Lock Hold Time Short

Never perform I/O, remote calls or long computations while holding a lock. The shorter locks are held, the smaller the window for contention and deadlock.

5. Don't Call Alien Methods While Holding a Lock

Calling listeners, callbacks or overridable methods inside synchronized code is dangerous — you don't know which locks they take. Copy the data you need, release the lock, then call out ("open calls").

6. Use Immutable Objects and Lock-Free Structures

Immutable objects need no locks at all, and concurrent collections and atomics (ConcurrentHashMap, AtomicReference) avoid holding multiple locks.

7. Use Higher-Level Concurrency Utilities

Well-tested tools — concurrent queues, executors, CompletableFuture — reduce hand-written locking and therefore deadlock opportunities.

8. Test, Analyse and Document

• Stress-test concurrent code under load to expose deadlocks before production.
• Document the lock-acquisition order and which lock guards which data, so other developers don't introduce inconsistent ordering.

#Detecting Deadlocks

Thread Dumps

jstack <pid>

Found one Java-level deadlock:
=============================
"Thread-1":
  waiting to lock monitor 0x000001 (object 0x7a1, a com.bank.Account),
  which is held by "Thread-0"
"Thread-0":
  waiting to lock monitor 0x000002 (object 0x7b2, a com.bank.Account),
  which is held by "Thread-1"

jcmd <pid> Thread.print, VisualVM, JConsole and Spring Boot Actuator's /actuator/threaddump endpoint show the same information.

Programmatically

ThreadMXBean bean = ManagementFactory.getThreadMXBean();
long[] ids = bean.findDeadlockedThreads();   // monitors and ownable synchronizers
if (ids != null) {
    for (ThreadInfo info : bean.getThreadInfo(ids, true, true)) {
        log.error("Deadlocked thread: {}", info);
    }
}

#Livelock

In a livelock, threads aren't blocked — they keep reacting to each other and retrying, but none makes progress. Like two people in a corridor who both step aside the same way, again and again.

// Both threads repeatedly back off and retry in lock-step
while (true) {
    if (lockA.tryLock()) {
        try {
            if (lockB.tryLock()) { /* ... */ }
        } finally {
            lockA.unlock();
        }
    }
    // ❌ immediate retry with no delay — both threads may collide forever
}

Fix: add randomized back-off (as in strategy 2), or establish a priority so one party always yields.

#Starvation

Starvation happens when a thread is perpetually denied a resource it needs, while other threads keep getting it:

Fixes: fair locks (new ReentrantLock(true)), short critical sections, separate thread pools for slow and fast work, and not relying on priorities.

#Deadlock vs Livelock vs Starvation

#Thread-Pool Deadlock

A sneaky variant: tasks in a bounded pool that wait for other tasks submitted to the same pool.

ExecutorService pool = Executors.newFixedThreadPool(2);

Future<String> outer = pool.submit(() -> {
    Future<String> inner = pool.submit(() -> "inner result");
    return inner.get();     // ❌ waits for a task that needs a free thread from the same pool
});

If every pool thread is running an outer task waiting on an inner task, the inner tasks never get a thread. Use separate pools for dependent tasks, or compose with CompletableFuture instead of blocking get() calls.

#Key Takeaways

• Deadlock needs mutual exclusion, hold-and-wait, no preemption and circular wait — break one to prevent it.
• Consistent lock ordering is the simplest and most reliable prevention.
• tryLock with timeout and back-off avoids indefinite waiting.
• Thread dumps reveal deadlocks; the JVM won't resolve them.
• Livelock is busy non-progress; starvation is one thread repeatedly losing out.