Skip to content
Tutorials Center
My learning

Topics

Lesson 129 of 201 ยท Concurrency

Deadlocks, Livelocks and Starvation

See a Java deadlock happen and time out safely with tryLock, detect deadlocks with ThreadMXBean, prevent them with lock ordering, and avoid livelock and starvation.

Locks fix race conditions, but they bring a new failure: threads waiting for each other forever. In a deadlock, thread A holds lock 1 and wants lock 2, while thread B holds lock 2 and wants lock 1. Neither can continue, neither will let go, and the program, or part of it, freezes. No exception is thrown, nothing is logged, the CPU sits idle. Requests pile up until someone restarts the server.

This lesson makes deadlocks happen on purpose, in ways that can't hang your program: first with locks that give up after a timeout, then with a built-in deadlock detector. Then it covers the techniques that prevent deadlocks in the first place, and two relatives: livelock (threads busy but making no progress) and starvation (one thread never getting its turn).

The four conditions

A deadlock can only happen when all four of these hold at once (the "Coffman conditions"):

  1. Mutual exclusion: a resource (a lock) can be held by only one thread.
  2. Hold and wait: a thread holds one lock while waiting for another.
  3. No preemption: a lock can't be taken away; only its holder releases it.
  4. Circular wait: there's a cycle, A waits for B, B waits for A (or A โ†’ B โ†’ C โ†’ A).

Every prevention technique breaks one of them. Remember the list; it turns "how do I avoid deadlocks?" into four concrete questions.

A deadlock that times out

The typical setting is a transfer between two bank accounts. Each transfer locks the source account, then the destination. Now run "Alice โ†’ Bob" and "Bob โ†’ Alice" at the same time: the first thread locks Alice and waits for Bob; the second locks Bob and waits for Alice. A cycle.

With synchronized, that wait would last forever. The ReentrantLock class, covered properly in Locks and Conditions, has a tryLock(timeout) method that gives up if it can't get the lock in time. That turns a frozen program into one that notices the problem:

Java Two transfers deadlock, then time out

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The CountDownLatch makes each thread wait until both hold their first lock, so the deadlock happens on every run instead of once in a thousand. (A latch is a one-time gate; see Synchronizers.) Then both tryLock calls time out. The two lines saying "gave up" can appear in either order, and occasionally one thread's timeout releases its lock just in time for the other to succeed. Either way the program ends, and no money moves unless a transfer completes.

A timeout is a safety net, not a fix: the transfers still failed. The caller has to retry, ideally after a random pause, or report an error. The real fix comes below.

Detecting a real deadlock

With synchronized, a deadlock is permanent. The JVM can still find it: the ThreadMXBean from java.lang.management reports threads that are deadlocked on monitors or java.util.concurrent locks. This demo creates a real, permanent deadlock with daemon threads (so the program can still exit) and then asks the JVM about it:

Java Detecting a deadlock with ThreadMXBean

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Both threads are BLOCKED and the detector names the cycle. Detection is a diagnostic, not a cure: you can't release another thread's monitor, and interrupting a BLOCKED thread does nothing (Thread Lifecycle). In production, monitoring tools call findDeadlockedThreads() periodically and raise an alarm. A thread dump (jcmd <pid> Thread.print or jstack <pid>) reports it too, at the end:

TEXT
Found one Java-level deadlock:
=============================
"restocker":
  waiting to lock monitor 0x00007f... (object 0x000000071a..., a java.lang.Object),
  which is held by "checkout"
"checkout":
  waiting to lock monitor 0x00007f... (object 0x000000071b..., a java.lang.Object),
  which is held by "restocker"

If your service suddenly stops responding while the CPU is idle, take a thread dump first.

Prevention 1: a global lock order

The most effective fix breaks circular wait: if every thread acquires locks in the same global order, a cycle is impossible. Nobody can hold a "later" lock while waiting for an "earlier" one.

For accounts, order by a unique, stable key such as the account ID, regardless of the transfer's direction:

Java Lock ordering prevents the deadlock

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Eighty thousand transfers in random directions, and the program always finishes with the total intact. Remove the ordering (lock from then to directly) and on a multi-core machine this program will very likely freeze.

Ordering tips:

  • Use a unique, immutable key: a database ID, an account number. System.identityHashCode can collide; if you use it, you need a tie-breaking lock for equal hashes.
  • Document the order ("always lock inventory before orders") right where the locks are declared.
  • The order must hold across methods and classes. A deadlock often involves two different code paths written by two different people.

Prevention 2: other techniques

Each of these breaks a different Coffman condition:

  • Hold one lock at a time (breaks hold and wait). Copy the data you need, release the lock, then take the next one. Often the simplest fix.
  • Don't call unknown code while holding a lock. Calling a listener, a callback, an overridable method or a method on another object while inside synchronized is the most common hidden cause: that code may take locks you know nothing about. Make "open calls" (calls made with no locks held).
  • Use tryLock with a timeout (breaks no preemption: you preempt yourself). Back off by releasing everything, wait a little, retry. You saw the timeout half above.
  • Use one coarser lock, or a lock-free design (immutable objects, atomic variables, concurrent collections). Fewer locks, fewer cycles.
  • Keep critical sections small and never block (I/O, sleep, waiting on a future) while holding a lock.
  • Don't wait for a task you submitted to the same small thread pool while occupying one of its threads: if all pool threads wait on tasks queued behind them, that's a deadlock without any explicit lock.

Databases have deadlocks too (two transactions locking rows in opposite order); most detect them and abort one transaction with an error, which your code should retry.

Livelock: busy, but going nowhere

In a livelock, threads aren't blocked; they keep reacting to each other, and their reactions keep cancelling out. Picture two people meeting in a hallway: both step left, both step right, both step left... Each is perfectly polite, and neither gets through.

In code, livelocks usually come from retry logic in which every thread backs off and retries at the same moment, for example two threads with tryLock that release and retry on identical schedules. This simulation makes the threads move in lockstep with a barrier (a point where both wait for each other each round), which is exactly the condition that causes livelock:

Java A livelock and the random back-off cure

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

When both always step aside, they swap lanes together forever (here, until the round limit). With a random decision, they soon end up in different lanes. That's the standard cure for livelock: add randomness (jitter) to retry delays, often with exponential back-off, so competitors fall out of step. Network protocols such as Ethernet do exactly this after collisions. (The fixed seeds only make the demo repeatable; real code uses unseeded randomness such as ThreadLocalRandom.)

Starvation: never getting a turn

Starvation means a thread is ready to run but rarely or never gets the resource it needs, because others keep taking it first. The program as a whole makes progress; one participant doesn't. Common causes:

  • Unfair locks. Intrinsic locks and the default ReentrantLock are unfair: when a lock is released, any thread may grab it, including one that just arrived or the one that just released it. That gives better throughput, but in theory a waiting thread can lose again and again. new ReentrantLock(true) creates a fair lock that hands over to the longest-waiting thread, at a noticeable throughput cost.
  • Greedy threads that hold a lock for long periods, or re-acquire it in a tight loop.
  • Thread priorities where the OS honors them, and high-priority threads never let low-priority ones run.
  • Readers starving writers in a read-write lock where new readers keep arriving (Locks and Conditions).
  • Thread pools clogged with long tasks while short, urgent tasks wait in the queue.
Java
ReentrantLock fairLock = new ReentrantLock(true);   // first come, first served

The usual remedies are short critical sections, fair locks where fairness genuinely matters, separate pools for slow and fast work, and timeouts so a starved thread at least reports the problem.

Summary table

Problem Threads are... Progress Typical fix
Deadlock blocked, waiting for each other in a cycle none, forever global lock order, one lock at a time, tryLock with timeout
Livelock running, reacting to each other none random back-off (jitter) on retries
Starvation some ready but never chosen others progress fair locks, short critical sections, separate pools

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Thread A locks X then tries to lock Y. Thread B locks Y then tries to lock X. Both use synchronized. What happens if they run at the same time?

    This is the circular wait. Intrinsic locks have no timeout and are never taken away, so if the timing lines up both threads block permanently, with no exception.
  2. 2. Which change reliably prevents the deadlock in a transfer(from, to) method that locks both accounts?

    A single global lock order makes a cycle impossible. Sleeping only changes timing, volatile doesn't affect locking and priorities are hints.
  3. 3. What does ThreadMXBean.findDeadlockedThreads() let you do about a deadlock between synchronized blocks?

    It is a diagnostic. Intrinsic locks can't be released by another thread, and BLOCKED threads ignore interrupts, so the cure is prevention.
  4. 4. Two threads use tryLock and, on failure, release everything and retry after exactly 10 ms. Sometimes both keep failing for a long time. What is this called, and what's the usual fix?

    The threads aren't blocked, they keep retrying in step and cancelling each other out. Randomized back-off breaks the symmetry.
  5. 5. Which is the most common HIDDEN cause of deadlocks in large programs?

    Code you call while holding a lock may acquire other locks in an order you don't control, creating a cycle across classes. Make such calls after releasing your lock.

Summary

  • A deadlock needs mutual exclusion, hold-and-wait, no preemption and a circular wait; break any one and deadlock is impossible.
  • Deadlocked threads are BLOCKED forever with no exception and an idle CPU; thread dumps and ThreadMXBean.findDeadlockedThreads() reveal them.
  • tryLock with a timeout turns a permanent deadlock into a failure you can handle (release, back off, retry).
  • The best prevention is a global lock order based on a unique, stable key; also hold one lock at a time and never call unknown code while holding a lock.
  • Livelock: threads stay busy reacting to each other without progress; fix it with random back-off.
  • Starvation: one thread never gets its turn; use short critical sections, fair locks where needed and separate pools.

Next: Locks and Conditions, where ReentrantLock, read-write locks and Condition give you more control than synchronized.