Livelock and starvation

Key points

• Deadlock is frozen. Livelock is busy: threads keep reacting to each other and none of them ever finishes.
• The classic cause is polite retry. Both threads take one lock, see the other taken, release and try again in step.
• Fix it by breaking the symmetry: random back-off, or one global lock order so retrying is not needed at all.
• Starvation is different. A thread is ready but never scheduled, because greedier threads keep winning the lock.
• A fair lock, new ReentrantLock(true), always hands off to the longest waiter. Slower, but nobody is left behind.
• Both look like a hang in production. A thread dump separates them: livelocked threads are RUNNABLE and burning CPU.

Example

import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;

public class Main {
    static final ReentrantLock left = new ReentrantLock();
    static final ReentrantLock right = new ReentrantLock();

    // Grab one lock, reach for the other, and step aside if it is taken.
    static boolean tryMeal(ReentrantLock first, ReentrantLock second) throws InterruptedException {
        if (!first.tryLock()) return false;
        try {
            Thread.sleep(5);                                    // holding one, reaching for two
            if (!second.tryLock(2, TimeUnit.MILLISECONDS)) return false;
            try { return true; } finally { second.unlock(); }
        } finally { first.unlock(); }
    }

    // Livelock: both threads stay busy being polite and neither one makes progress.
    static void dine(String who, ReentrantLock first, ReentrantLock second, AtomicInteger retries)
            throws InterruptedException {
        for (int meal = 1; meal <= 3; meal++) {
            boolean ate = false;
            for (int attempt = 0; attempt < 100 && !ate; attempt++) {
                ate = tryMeal(first, second);
                if (!ate) {
                    retries.incrementAndGet();
                    Thread.sleep(ThreadLocalRandom.current().nextInt(1, 6));   // random back-off
                }
            }
            if (!ate) { System.out.println(who + " gave up on meal " + meal); return; }
        }
        System.out.println(who + " ate 3 meals, " + retries.get() + " retries on the way");
    }

    public static void main(String[] args) throws InterruptedException {
        AtomicInteger a = new AtomicInteger();
        AtomicInteger b = new AtomicInteger();
        Thread t1 = new Thread(() -> run("alice", left, right, a));
        Thread t2 = new Thread(() -> run("bob  ", right, left, b));
        t1.start(); t2.start();
        t1.join();  t2.join();

        System.out.println("alice retries : " + a.get());
        System.out.println("bob retries   : " + b.get());
        System.out.println("no deadlock, but the retries are wasted work");
    }

    static void run(String who, ReentrantLock first, ReentrantLock second, AtomicInteger retries) {
        try { dine(who, first, second, retries); }
        catch (InterruptedException e) { Thread.currentThread().interrupt(); }
    }
}

Deadlock is frozen. Livelock is busy. Both mean no progress.