Home/Learn/Operating Systems/Livelock & Starvation

Livelock & Starvation

Intermediate

Deadlocks

Livelock occurs when processes keep changing state in response to each other but make no progress, while starvation occurs when a process is indefinitely denied the resources it needs.

Overview

Livelock is like two people walking toward each other in a corridor: each steps aside to let the other pass, but both step to the same side repeatedly — active, but going nowhere. Unlike deadlock (blocked), livelocked threads are running and consuming CPU. Starvation is different: a process is perpetually skipped in favour of higher-priority processes. Both are progress failures. Solutions include randomised backoff for livelock (breaking symmetry) and aging for starvation (gradually increasing priority of waiting processes). Java's fair locks (ReentrantLock with fairness=true) and the ForkJoinPool work-stealing scheduler are designed to avoid starvation.

Livelock Demo and Fix with Random Backoff

A livelock arises when two threads each detect a conflict and both back off simultaneously — then both retry simultaneously — forever. Breaking the symmetry with a random sleep duration prevents both threads from choosing the same backoff window.

Java — Livelock demo and random-backoff fix

import java.util.concurrent.atomic.AtomicBoolean;

// LIVELOCK: two "polite" threads each yield endlessly
AtomicBoolean resource = new AtomicBoolean(false); // false = available

Runnable politeThread = () -> {
    String name = Thread.currentThread().getName();
    int attempts = 0;
    while (!resource.compareAndSet(false, true)) {
        // Resource busy — politely back off
        System.out.println(name + ": resource busy, yielding...");
        Thread.yield(); // both threads yield forever — livelock!
        attempts++;
        if (attempts > 1000) {
            System.out.println(name + ": giving up after 1000 attempts (livelock)");
            return;
        }
    }
    System.out.println(name + ": acquired resource!");
    resource.set(false); // release
};

// FIX: randomised backoff breaks symmetry
Runnable fixedThread = () -> {
    String name = Thread.currentThread().getName();
    while (!resource.compareAndSet(false, true)) {
        try {
            // Random sleep: one thread will wait longer than the other
            long backoff = (long)(Math.random() * 50); // 0-50ms
            System.out.println(name + ": backing off for " + backoff + "ms");
            Thread.sleep(backoff);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            return;
        }
    }
    System.out.println(name + ": acquired resource!");
    resource.set(false);
};

Starvation and Aging with Fair Locks

Starvation occurs when low-priority threads are perpetually bypassed by high-priority ones. ReentrantLock(true) uses a fair FIFO queue, ensuring threads acquire the lock in the order they requested it — no thread waits forever. Without fairness, a high-throughput producer can monopolise the lock.

Java — Fair ReentrantLock and aging pattern

import java.util.concurrent.locks.ReentrantLock;

// Unfair lock (default) — high-priority threads can starve low-priority
ReentrantLock unfairLock = new ReentrantLock(false); // unfair

// Fair lock — threads acquire in FIFO order, prevents starvation
ReentrantLock fairLock = new ReentrantLock(true);    // fair

// Demonstrate starvation risk with priority
Runnable highPriority = () -> {
    for (int i = 0; i < 100; i++) {
        fairLock.lock();
        try {
            // high-priority work
        } finally {
            fairLock.unlock();
        }
    }
};

Runnable lowPriority = () -> {
    fairLock.lock();        // with fair=true: guaranteed to eventually acquire
    try {
        System.out.println("Low priority finally got the lock!");
    } finally {
        fairLock.unlock();
    }
};

// Aging concept (manual implementation):
class PrioritisedTask implements Comparable<PrioritisedTask> {
    int basePriority;
    long waitStart = System.currentTimeMillis();

    // Effective priority increases the longer it waits (aging)
    int effectivePriority() {
        long waited = System.currentTimeMillis() - waitStart;
        return basePriority + (int)(waited / 100); // +1 per 100ms waited
    }

    @Override
    public int compareTo(PrioritisedTask other) {
        return Integer.compare(other.effectivePriority(), this.effectivePriority());
    }
}

Key Points to Remember

1Livelock threads are active (not blocked) but make no progress — they consume CPU unlike deadlocked threads.
2Randomised backoff with exponential delay (like Ethernet's CSMA/CD) is the standard livelock remedy.
3Starvation occurs when scheduling policy indefinitely postpones a process — common with strict priority scheduling.
4Aging gradually increases a waiting process's priority to guarantee it eventually runs.
5ReentrantLock(true) enables fairness (FIFO ordering) at the cost of ~10-30% throughput reduction.
6Java's ForkJoinPool uses work-stealing: idle threads steal tasks from busy threads, preventing starvation of long-queued tasks.

Interview Questions

What is the difference between deadlock, livelock, and starvation?

EasyAmazon

How does randomised backoff prevent livelock? Why does a fixed backoff not work?

MediumGoogle

When would you use ReentrantLock(true) vs ReentrantLock(false), and what is the performance trade-off?

MediumAtlassian

Design a task scheduler that prevents starvation of low-priority tasks in a high-throughput system.

HardUber

Ask Aria about Livelock & Starvation

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Deadlock Detection & Recovery

CPU Scheduling in Java