Livelock

When threads are too polite, resulting in an endless dance where nothing gets done.

The idea

A Deadlock is when two threads freeze because they are waiting for each other to release a lock. A Livelock is when two threads try to fix a deadlock by being overly polite. Imagine two people walking towards each other in a hallway. They both step to their left to get out of the way. Now they are still blocking each other. So they both step to their right. Blocked again! They are constantly moving (using CPU), not "dead", but making zero progress. This is a livelock.

Step 1: The Collision. Two threads need both Lock A and Lock B. Thread 1 grabs A, Thread 2 grabs B.

How it works (Randomized Backoff)

To avoid deadlocks, threads are often programmed to release their locks if they can't get all the locks they need. But if both threads release their locks and try again at the exact same time, they will collide again infinitely. To fix a livelock, you must introduce randomness into the system (often called "Jitter" or "Exponential Backoff").

// BAD: Livelock waiting to happen
while (true) {
    lock(A);
    if (tryLock(B)) { 
        doWork(); break; 
    } else {
        // "Oops, I'll be polite and release A"
        unlock(A);
        // Both threads do this instantly, and immediately restart the loop!
    }
}

// GOOD: Randomized Backoff (Jitter)
while (true) {
    lock(A);
    if (tryLock(B)) { 
        doWork(); break; 
    } else {
        unlock(A);
        // Wait a RANDOM amount of time before trying again. 
        // This breaks the symmetry!
        sleep(random(10, 100)); 
    }
}

Cost

Adding sleep/jitter slows down the optimal execution path slightly, because threads intentionally pause doing work. However, this microscopic cost in milliseconds prevents a catastrophic scenario where your server's CPU spikes to 100% while processing zero requests.

Watch out for