Livelock & Starvation

Language-specific mechanics: Concurrency Language Manual →

Three ways to stop making progress

Deadlock isn't the only liveness failure a concurrent system can suffer, and interviewers routinely probe whether you can tell the three apart precisely — not just recite fuzzy definitions:

Failure	Thread state	Is the CPU busy?	Root cause
Deadlock	Blocked, permanently	No — threads are asleep/parked	A cycle in the wait-for graph
Livelock	Runnable, actively executing	Yes — CPU is fully busy	Threads keep reacting to each other without ever converging
Starvation	Runnable, but never scheduled/granted	Yes, for other threads	Unfair scheduling or resource allocation policy

The one-line distinctions worth memorizing: deadlock threads are stuck and idle; livelock threads are stuck and busy; starved threads are not stuck at all — there genuinely exists a schedule under which they'd make progress, the system simply never takes it.

Livelock: busy, but going nowhere

Livelock happens when threads actively change state in response to one another, in a pattern that never breaks symmetry. The textbook example: two people approach each other in a narrow hallway, both politely step to the same side to let the other pass, both step back the other way at the same time, and repeat forever. Translated to code, this is what happens when a deadlock-avoidance mechanism is implemented too naively:

# Naive deadlock avoidance that can livelock:
loop:
    acquire(lockA)
    if tryAcquire(lockB) fails:
        release(lockA)
        continue                 # immediately retry
    else:
        do work
        release both
        break

If two threads run this exact logic against the same two locks and their timing stays synchronized — both grab lockA, both fail to get lockB, both release and immediately retry in lockstep — they can do this indefinitely. Note the irony: this pattern is often introduced specifically to avoid the plain deadlock from acquiring A then B unconditionally, and ends up trading a silent hang for a CPU-burning non-hang that's arguably harder to notice in production monitoring (the threads look "active").

The fix is to break the symmetry, typically with randomized backoff: instead of retrying immediately, each thread waits a random amount of time before its next attempt, so the probability of both threads staying in lockstep forever collapses exponentially. This is the same idea behind Ethernet's exponential backoff and TCP retransmission — jitter is a general-purpose tool for breaking livelock-style resonance between independent retrying actors.

Starvation: perpetually passed over

Starvation occurs when a thread is denied a resource it needs indefinitely, even though the resource isn't permanently unavailable — other threads keep getting it instead. Unlike deadlock, the system as a whole is making progress; unlike livelock, the starved thread isn't burning CPU on a doomed retry loop, it's simply never winning the race to be scheduled or granted the lock.

The most common cause is naive priority scheduling: if higher-priority threads keep arriving, a low-priority thread can wait forever even though the CPU is constantly busy doing other useful work. The standard fix is aging: gradually increase a waiting thread's effective priority the longer it waits, so that eventually even the lowest-priority thread's priority is boosted high enough to win.

A related and famous failure mode is priority inversion: a high-priority thread blocks on a lock held by a low-priority thread, and an unrelated medium-priority thread preempts the low-priority holder before it can finish and release the lock — so the high-priority thread is effectively starved by a thread with lower priority than itself. This isn't hypothetical: it caused watchdog resets on the 1997 Mars Pathfinder mission. The standard fixes are priority inheritance (temporarily boost the lock holder to the waiter's priority for as long as it holds the lock) and priority ceiling (statically assign every lock a priority equal to the highest-priority thread that could ever acquire it, so no in-between-priority thread can ever preempt the holder).

Starvation isn't unique to CPU scheduling — it applies to any contended resource. A semaphore or lock implementation that hands the resource to whichever waiter happens to retry fastest (rather than, say, a FIFO wait queue) can starve a "quieter" thread indefinitely even under otherwise fair-looking conditions.

The fairness connection back to bounded waiting

This whole topic traces back to a promise (or lack of one) from the Critical Sections topic: bounded waiting — the guarantee that once a thread requests entry to a critical section, there's a finite bound on how many times other threads can enter before it does. A lock or semaphore that provides bounded waiting (typically via a FIFO queue of waiters) is starvation-free by construction: every waiter's position in line only ever improves. A lock implementation that instead lets any waiter "race" for the resource whenever it's released (common in simple spinlock or naive synchronized-style implementations, for throughput reasons) trades away that guarantee — it's faster in the uncontended and lightly-contended case, but offers no bound on how long an unlucky thread might wait under sustained contention.

This is the practical reason "fairness" shows up as a real, named option on production lock APIs (e.g., a fair vs. non-fair reentrant lock): it's a direct dial between throughput and the bounded-waiting guarantee. Fair locks impose FIFO ordering (and therefore some overhead and reduced throughput under contention) specifically to make starvation structurally impossible; non-fair locks skip that bookkeeping and accept a (usually small, but theoretically unbounded) starvation risk in exchange for speed.

Putting the whole topic together

Deadlock: prevent it by breaking one of the four Coffman conditions (most practically, circular wait via global lock ordering), or avoid it dynamically with something like the Banker's Algorithm, or detect it after the fact via cycle detection in a wait-for graph.
Livelock: recognize it as "busy but not progressing," distinct from deadlock's "blocked and idle," and fix it by breaking retry symmetry (randomized backoff).
Starvation: recognize it as "some threads progress, this one doesn't," caused by unfair scheduling or allocation, and fix it with aging, priority inheritance/ceiling, or a fair (FIFO) lock/semaphore implementation that provides bounded waiting.

Pitfalls and interview gotchas

Calling livelock "a kind of deadlock." It isn't — the threads are demonstrably running, which immediately rules out every deadlock-detection technique that looks for blocked threads or wait-for cycles. Livelock requires watching for lack of progress, not lack of execution.
Assuming more concurrency primitives always mean more fairness. Compare-and-swap-based lock-free retry loops are a classic livelock risk under high contention for exactly the reason above: everyone's "busy," nobody's blocked, and without backoff nobody's guaranteed to win eventually either.
Treating starvation as purely a scheduling problem. It shows up anywhere there's contention and an unfair arbitration policy — lock acquisition order, connection-pool checkout, even naive load-balancer routing — not only in the OS's CPU scheduler.
Assuming deadlock prevention fixes starvation for free. A global lock-ordering rule (previous subtopic) eliminates deadlock but says nothing about who wins a given lock first among several waiters — those are orthogonal guarantees, and a system can be simultaneously deadlock-free and starvation-prone.

A naive "tryLock both, release-and-immediately-retry-on-failure" loop can livelock two threads in lockstep (see theory). Adding random jitter before retrying breaks the symmetry.

func withBothLocks(first, second *sync.Mutex, work func()) {
    for {
        if first.TryLock() { // Go 1.18+, immediate only
            if second.TryLock() {
                work()
                second.Unlock()
                first.Unlock()
                return
            }
            first.Unlock()
        }
        // Jittered backoff instead of immediate retry -- breaks lockstep livelock.
        time.Sleep(time.Duration(1+rand.Intn(19)) * time.Millisecond)
    }
}

TryLock is immediate and has no timeout overload. Without the random sleep, two goroutines can stay perfectly synchronized — both grab first, both fail on second, both unlock and retry together, forever. Mutex is still not reentrant: never Lock() a mutex you already hold inside work.

Everyone takes a numbered ticket on arrival and is served strictly in order — the same idea as a deli counter. This guarantees bounded waiting, so no waiter can be perpetually skipped the way it can with a naive "whoever notices first" lock.

type TicketLock struct {
    nextTicket atomic.Uint64
    nowServing atomic.Uint64
}

func (t *TicketLock) Lock() {
    my := t.nextTicket.Add(1) - 1 // take a place in line
    for t.nowServing.Load() != my {
        runtime.Gosched() // wait for our turn; yield so GOMAXPROCS=1 can't livelock
    }
}

func (t *TicketLock) Unlock() {
    t.nowServing.Add(1) // let the next ticket holder in
}

Ticket order is assigned once at arrival and never changes, so waiting is bounded. Spin without runtime.Gosched() and a GOMAXPROCS=1 program can livelock: the holder never gets scheduled to Unlock. For long waits, a sync.Cond (or a FIFO channel of tokens) sleeps instead of spinning — same fairness, cheaper.

Three ways to stop making progress

Livelock: busy, but going nowhere

Starvation: perpetually passed over

The fairness connection back to bounded waiting

Putting the whole topic together

Pitfalls and interview gotchas

Breaking Livelock with Jittered Backoff

A FIFO Ticket Lock (Bounded Waiting, Starvation-Free by Construction)

Further Resources (Optional)