How can a well-intentioned fix for deadlock (releasing locks and retrying) actually cause livelock, and how do you prevent it?
answer
- tryLock + release-on-failure avoids deadlock but risks livelock
- Cause = symmetry: identical deterministic retry rhythm
- Fix 1: randomized (exponential) backoff to break symmetry
- Fix 2: global lock ordering removes the need to retry
- Fix 3: bound retries, fall back to serialized path
basics
~20 sIf a thread that can't get all its locks releases them and retries, and every competing thread does the same in lockstep, they keep releasing and retrying together and none ever finishes. Fix it by adding randomness or backing off for different amounts of time.
solid answer
~50 sA common deadlock avoidance pattern is: try to acquire all the locks you need; if you can't get one, release the ones you already hold and retry later (using tryLock with a timeout instead of a blocking lock). This prevents the circular wait that causes deadlock. But if two symmetric threads collide and both follow the exact same release-and-retry rhythm, they can keep stepping out of each other's way simultaneously — each releases, both retry, both collide again — making no progress. That's livelock. The cure is to break the symmetry: introduce randomness so threads back off for different, unpredictable durations (randomized exponential backoff), or impose a global lock-ordering so threads always acquire locks in the same order and never need to back off at all. Bounding the number of retries and falling back to a single-threaded path also prevents an unbounded livelock loop.
code
java · 24 lines// Try-and-back-off acquiring two locks. The RANDOMIZED backoff
// (not a fixed sleep) is what breaks the symmetry that causes livelock.
boolean transfer(ReentrantLock a, ReentrantLock b, int maxTries) throws InterruptedException {
Random rnd = new Random();
for (int attempt = 0; attempt < maxTries; attempt++) {
if (a.tryLock()) {
try {
if (b.tryLock()) {
try {
// ... critical section: both locks held ...
return true;
} finally {
b.unlock();
}
}
} finally {
a.unlock(); // release A so we never hold one while stuck on the other
}
}
// Randomized backoff: different threads wake at different times -> one wins.
Thread.sleep(rnd.nextInt(1 << Math.min(attempt, 6)));
}
return false; // bounded retries: give up instead of livelocking forever
}go deeper
Recognizes that retrying after failing to get a lock can loop forever, and that adding randomness helps.
Explains the tryLock/release-and-retry pattern, why symmetric threads livelock, and names randomized backoff and lock ordering as cures.
Compares trade-offs: lock ordering vs randomized exponential backoff vs bounded retries; reasons about throughput and the probabilistic guarantee randomness provides.
Designs the concurrency strategy for a subsystem — chooses between consistent ordering, lock-free structures, and queue/actor ownership; sets backoff/retry policy and considers fairness, tail latency, and failure escalation across the system.
## Setting the scene A **lock** is a token only one thread holds at a time, guarding shared data. A thread that needs **two** locks (say lock A and lock B) to do its work has two ways to ask for them: - **Blocking acquisition** (`synchronized`, `lock.lock()`): if the lock is taken, the thread waits indefinitely. Two threads that grab A and B in opposite orders can **deadlock** (a cycle of waiting). - **Non-blocking / timed acquisition** (`ReentrantLock.tryLock()`): the thread *attempts* to grab a lock and is told immediately (or after a timeout) whether it succeeded. This lets a thread give up gracefully instead of blocking forever. ## The well-intentioned deadlock fix To avoid deadlock, engineers often replace blocking acquisition with this **try-and-back-off** protocol: 1. `tryLock(A)`. If it fails, wait and retry the whole thing. 2. `tryLock(B)`. If it fails, **release A** (so you're not holding a lock while stuck), wait, and retry. 3. Once you hold both, do the work, then release both. Because a thread never *holds* one lock while *blocking* on another, the circular-wait condition for deadlock is broken. Good — no deadlock. ## How that creates livelock Now imagine two symmetric threads, T1 wanting (A then B) and T2 wanting (B then A), colliding at the same instant: - T1 grabs A; T2 grabs B. - T1 tries B → fails → releases A. T2 tries A → fails → releases B. - Both wait the **same** fixed amount, then retry **together**. - T1 grabs A again; T2 grabs B again. … and the pattern repeats forever. No thread is blocked — both are **actively running, acquiring and releasing**, changing state in response to each other — yet **no work is done**. That is **livelock**. The real-world analogy is two people in a hallway who keep mirroring each other's sidesteps. The root cause is **symmetry**: identical threads following an identical deterministic rhythm stay perfectly in step. ## How to prevent it **1. Break the symmetry with randomness (randomized backoff).** After a failed attempt, sleep for a *random* duration, ideally growing over successive failures (**randomized exponential backoff**: roughly `random(0 .. base * 2^attempt)`). Because the two threads now wait *different* amounts, one will wake first, grab both locks, finish, and release — letting the other proceed. Ethernet's CSMA/CD collision backoff uses exactly this idea. **2. Eliminate the need to back off — global lock ordering.** Assign every lock a total order (e.g. by an id) and require **every** thread to acquire locks in that ascending order. With a consistent order there is no cycle, so plain blocking acquisition can't deadlock and you never need the release-and-retry dance that risks livelock. This is usually the preferred design when the lock set is known. **3. Bound the retries.** Cap the number of attempts; on exhaustion, fall back to a serialized path, fail fast with an error, or escalate to a coarser single lock. This guarantees the loop is finite even if backoff doesn't separate the threads. **4. Use higher-level constructs.** A single coarser lock, a lock-free/`java.util.concurrent` structure, or an actor/queue that hands work to one owner sidesteps the multi-lock problem entirely. ## How to derive the answer under pressure Remember the causal chain: *blocking two locks → deadlock risk → switch to release-and-retry → symmetric threads stay in lockstep → livelock.* The fix is always to **break symmetry** (randomness), **remove the cause** (lock ordering), or **bound the loop** (retry cap).
- Why does randomized backoff work where a fixed delay fails?A fixed delay keeps symmetric threads in lockstep, so they keep colliding. Random delays make threads wake at different times, so one wins the locks and finishes while the others are still waiting, breaking the cycle probabilistically.
- If you adopt strict global lock ordering, do you still need the try-and-back-off protocol?No. A consistent acquisition order makes a circular wait impossible, so plain blocking acquisition can't deadlock — you can drop the release-and-retry dance and the livelock risk it carries.
saying these in an interview costs you the question
- Thinking the release-and-retry fix is always safe — it trades deadlock for possible livelock
- Using a fixed backoff delay for all threads (keeps them in lockstep)
- Believing more retries alone solves livelock — without breaking symmetry it loops forever
- Confusing lock ordering (a deadlock cure) with a livelock cure — note it ALSO removes the retry that causes livelock