Livelock and Starvation in Java

Deadlock isn't the only way threads can fail to make progress. In a livelock, threads are not blocked: they keep running and reacting to each other, but no real work gets done, like two people in a corridor who keep stepping aside in the same direction. In starvation, one thread never gets the resource it needs, because other threads keep taking it first. In this lesson, you will learn both problems, see examples, and learn how to avoid them.

Deadlock vs Livelock vs Starvation

Example: A Livelock and Its Fix

Let's see an example of two polite workers who want the same resource. In each round, a worker claims the resource, checks whether the other also claimed it, and if so, politely gives it up. A CyclicBarrier makes both workers move through each round in lockstep, which is exactly the situation that causes a livelock. In the second run, each worker may randomly sit out a round.

import java.util.Random;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.atomic.AtomicInteger;
 
public class Livelock {
    static final AtomicInteger claim = new AtomicInteger();
 
    static String worker(int me, boolean randomBackoff, long seed,
                         CyclicBarrier step) throws Exception {
        Random random = new Random(seed);
        String result = "gave up";
        boolean skip = false;
        for (int round = 1; round <= 5; round++) {
            boolean trying = !skip && result.equals("gave up");
            if (trying) {
                claim.updateAndGet(c -> c | me);
            }
            step.await();
            if (trying && claim.get() == me) {
                result = "won in round " + round;
            }
            step.await();
            if (trying) {
                claim.updateAndGet(c -> c & ~me);
            }
            step.await();
            skip = randomBackoff && random.nextBoolean();
        }
        return result;
    }
 
    static void run(String label, boolean randomBackoff) throws Exception {
        claim.set(0);
        CyclicBarrier step = new CyclicBarrier(2);
        String[] result = new String[2];
        Thread a = new Thread(() -> {
            try {
                result[0] = worker(1, randomBackoff, 1, step);
            } catch (Exception e) {
                result[0] = "error";
            }
        });
        Thread b = new Thread(() -> {
            try {
                result[1] = worker(2, randomBackoff, 3, step);
            } catch (Exception e) {
                result[1] = "error";
            }
        });
        a.start();
        b.start();
        a.join();
        b.join();
        System.out.println(label + "Navika " + result[0]
            + ", Srihitha " + result[1]);
    }
 
    public static void main(String[] args) throws Exception {
        run("Lockstep: ", false);
        run("Random:   ", true);
    }
}

Lockstep: Navika gave up, Srihitha gave up
Random:   Navika won in round 3, Srihitha won in round 4

Explanation: In the lockstep run, both workers claim in every round, both see the other's claim, and both back off, five times in a row. They were busy the whole time, but nobody ever got the resource: a livelock. In the random run, each worker flips a (seeded) coin after every round to decide whether to sit out the next one. In round 3, only Navika tried, so Navika got the resource; in round 4, only Srihitha tried. Breaking the lockstep let both make progress. (The barrier is only there to make the lockstep easy to see; real code would back off with random sleeps.)

Starvation

A thread starves when it is always passed over. Common causes:

• Unfair locks: synchronized makes no promise about which waiting thread goes next, so an unlucky thread can wait a very long time.
• Greedy threads: a thread that holds a lock for long periods, or re-takes it immediately.
• Priorities: on some systems, low-priority threads rarely run while high-priority ones are busy.

Common Mistakes

Retrying immediately in a loop after a conflict. Both threads retry in step; add a random back-off.

Holding a lock while doing long work. Other threads may starve.

Assuming synchronized is fair. It isn't.

Practice

1. Easy: Explain the difference between deadlock, livelock and starvation using the corridor example.
2. Harder: Write a program where one thread takes a lock in a tight loop and another thread tries to take it once, and measure how long the second thread waits. Then make the first thread pause briefly after each release.

Key Takeaways