Starvation and Livelock

Starvation (also called indefinite postponement or lockout) occurs when a process that is ready to run, and requesting resources it is entitled to, is repeatedly denied service while other processes continue to be served. Formally, in a system that runs forever, a process $P$ starves if $P$ is enabled (able to make progress) infinitely often but executes its critical action only finitely many times, or never. The defining feature is that the system overall is live — global throughput is nonzero, other processes complete — but one participant is singled out and denied forever, or for an unbounded time.

Livelock is a special, more dramatic case of starvation: the affected processes are not idle or blocked, they are actively executing, but their execution consists only of reacting to each other without any of them completing useful work. A classic mental image is two people in a corridor, both stepping left, then both stepping right, in perfect mirrored deference, forever. In systems terms, livelock typically arises from symmetric conflict-avoidance protocols: each thread detects contention, backs off, and retries, but the retry decisions correlate (e.g., all threads use the same fixed delay) so the same collision repeats indefinitely. Unlike ordinary starvation, where the victim is merely unlucky, livelock can afflict all participants simultaneously — none of them make progress even though CPU cycles are being spent every instant. Both are cleanly distinguished from deadlock. Deadlock requires a set of processes each waiting for a resource held by another in the set, forming a cycle in the resource-allocation graph, so that no process in the cycle can ever proceed — the system is not just unfair, it is frozen for those processes. Starvation requires no such cycle; resources are being granted and released constantly, just never (or too rarely) to the starving process. The standard liveness property that rules starvation out by construction is bounded waiting: a mutual-exclusion protocol satisfies bounded waiting if there exists a constant $B$ such that once a process signals its intent to enter the critical section, no other process is allowed to enter more than $B$ times before it does. Any implementation that provably enforces bounded waiting is starvation-free by definition — this is why textbook proofs of correctness for entry protocols always include a bounded-waiting argument alongside mutual exclusion and progress.

The mechanics of starvation and livelock are best understood by first showing a natural but flawed policy, then the standard repair.

Where starvation creeps in — priority scheduling. A pure static-priority scheduler always dispatches the highest-priority ready process. If high-priority processes keep arriving, a low-priority process can wait forever even though the CPU is constantly busy running someone. This is exactly the "starving low-priority job" pattern that shows up in the readers–writers problem when writer-priority readers-writers policies let a continuous stream of writers block all readers indefinitely (or vice versa for reader-priority policies blocking writers) — a direct extension of The Readers-Writers Problem.

The remedy — aging. Aging tracks how long a process has waited and gradually increases its effective priority, guaranteeing that no process can wait longer than some bound before it becomes the highest-priority ready process and gets scheduled. ```pseudocode // Starvation-prone scheduler: pure static priority function SCHEDULE_NAIVE(ready_queue): loop forever: p = process in ready_queue with max(static_priority) // tie-break arbitrarily, e.g., first found dispatch(p) // p runs until it blocks or is preempted by a strictly higher-priority arrival // Problem: if arrivals of higher-priority processes never stop, // a lower-priority process can remain in ready_queue forever. // Starvation-free scheduler: aging added function SCHEDULE_WITH_AGING(ready_queue, AGE_RATE): loop forever: for each p in ready_queue: p.effective_priority = p.static_priority + AGE_RATE p.wait_time p = process in ready_queue with max(effective_priority) dispatch(p) p.wait_time = 0 // reset once served for each q in ready_queue, q != p: q.wait_time += quantum_length // everyone else keeps aging ``` Why aging bounds waiting:* fix a process $p$ with static priority $s_p$ and let $M$ be the maximum static priority of any process in the system. If $p$ waits for time $t$, its effective priority is $s_p + \alpha t$ for aging rate $\alpha > 0$. Once $t \geq (M - s_p)/\alpha$, $p$'s effective priority exceeds every possible competitor's static priority (before their own aging), so $p$ must eventually be selected. This gives an explicit bound $B = \lceil (M - s_p)/\alpha \rceil$ on the number of scheduling rounds $p$ can be passed over — a bounded-waiting guarantee constructed by design.

Where starvation creeps in — lock implementations. A spinlock built from a single shared flag using test-and-set gives no ordering guarantee: whichever thread's CPU next notices the flag is free wins the race, and under contention this can (in principle, and sometimes in practice on real hardware with unfair cache/interconnect behavior) let one thread win the race indefinitely while another thread is repeatedly denied. ```pseudocode // Unfair lock: no bound on how long a waiter can be overtaken function LOCK_NAIVE(flag): while TestAndSet(flag) == true: pass // busy-wait; any waiter can "win" the retry race function UNLOCK_NAIVE(flag): flag = false ```

The remedy — ticket lock (bounded waiting by construction). A ticket lock assigns each arriving thread a strictly increasing ticket number, using an atomic fetch-and-increment, and serves threads in ticket order — this is FIFO fairness enforced structurally, not probabilistically. ```pseudocode // Ticket lock: FIFO order guarantees bounded waiting shared now_serving = 0 shared next_ticket = 0 function LOCK_TICKET(): my_ticket = FetchAndIncrement(next_ticket) // atomic while now_serving != my_ticket: pass // spin, but order is fixed // critical section function UNLOCK_TICKET(): now_serving = now_serving + 1 ``` Why this bounds waiting: the moment a thread draws ticket $k$, exactly $k$ other threads (those with earlier tickets) can enter before it, and no thread that arrives later can ever draw a ticket $< k$. So the number of processes that can overtake a waiter is bounded by the number already ahead of it at arrival time — a hard, countable bound, satisfying bounded waiting exactly.

Where livelock creeps in — symmetric backoff. Suppose two threads each try to acquire two locks in the same order but back off identically on conflict: ```pseudocode // Livelock-prone: deterministic, synchronized retry function POLITE_ACQUIRE(my_lock, other_lock): loop forever: acquire(my_lock) if try_acquire(other_lock): return // success, proceed else: release(my_lock) // be "polite", avoid deadlock sleep(FIXED_DELAY) // BUG: same delay for everyone // retry from top ``` If two threads run this symmetrically with the same `FIXED_DELAY` and near-simultaneous start times, they can release-and-retry in lockstep forever: each grabs `my_lock`, finds `other_lock` taken, releases, sleeps the same fixed interval, and collides again. No deadlock (locks are always eventually released), but no progress either — this is livelock.

The remedy — randomized exponential backoff. Breaking the symmetry with randomness (and increasing the delay range on repeated failure) makes simultaneous re-collision increasingly improbable. ```pseudocode function ROBUST_ACQUIRE(my_lock, other_lock): attempt = 0 loop forever: acquire(my_lock) if try_acquire(other_lock): return release(my_lock) attempt = attempt + 1 delay = random(0, min(MAX_DELAY, BASE * 2^attempt)) // randomized, growing sleep(delay) ``` Randomization destroys the deterministic symmetry that caused livelock: the probability that two (or $n$) threads choose colliding retry windows shrinks geometrically with each retry round, so with probability 1 some thread eventually wins a collision-free window and completes.

Aging scheduler. Recomputing effective priority for all $n$ ready processes each scheduling decision costs $O(n)$ time, and selecting the maximum costs $O(n)$ as well (or $O(\log n)$ with a priority-heap keyed on effective priority, at the cost of $O(\log n)$ updates per aging step). Space overhead is $O(1)$ per process (one wait-time counter). The correctness argument is the bound derived above: for any process $p$ with static priority $s_p$ and system-wide maximum static priority $M$, waiting time is capped at

scheduling rounds, after which $p$'s effective priority dominates every possible competitor. This is a genuine liveness proof, not a heuristic claim: it holds for any finite $M$ and any $\alpha > 0$, independent of the arrival pattern of other processes, because effective priority increases monotonically and unboundedly with wait time while true competitors' static components are fixed.

Ticket lock. `FetchAndIncrement` and the spin check are each $O(1)$ amortized per attempt (ignoring the spin itself, which is bounded by the time the $k$ ahead-of-you threads take in their critical sections). Space is $O(1)$ — two shared counters, regardless of the number of contending threads. Correctness has three parts, mirroring the classical three-part proof structure for mutual exclusion:

• Mutual exclusion: only the thread with `my_ticket == now_serving` proceeds, and `now_serving` increases by

exactly one per release, so at most one ticket value is "being served" at any time.

• Progress: `now_serving` always advances (assuming critical sections terminate), so eventually every ticket

value is reached — no process can be skipped and no ticket value is ever served twice.

• Bounded waiting: a thread with ticket $k$ waits behind exactly the threads with tickets $0, \dots, k-1$ that

arrived earlier; since `next_ticket` only increases, no later arrival can ever acquire a ticket smaller than $k$, so at most $k$ (a fixed, finite number determined at arrival time) threads can enter before it. This is bounded waiting by construction, hence starvation-free. The tradeoff: ticket locks impose strict FIFO order even when a different order might have higher throughput (e.g., a thread that just released the lock and still has the relevant cache lines hot might be a better next holder), so fairness here is bought at some potential cache-locality cost compared to unfair test-and-set locks.

Randomized backoff. Each retry round costs $O(1)$ expected work (attempt, sleep, retry). Correctness for livelock-freedom is probabilistic rather than a hard bound: if $n$ contending threads independently draw delays from a window that widens geometrically, the probability that thread $i$'s chosen window overlaps no competitor in round $t$ approaches 1 as $t$ grows (the window size, and hence the chance of a clean slot, grows exponentially while the number of competitors that remain unresolved shrinks in expectation). Formally, this is an argument of progress "with probability 1" (almost-sure termination) rather than a deterministic bound like the ticket lock's $B$ — an important honesty point: randomized backoff eliminates livelock almost surely, not by a hard worst-case guarantee, and adversarial scheduling can in principle still delay termination, though not indefinitely with probability 1.

Honest tradeoff summary. Deterministic fairness mechanisms (aging, ticket locks) give hard, provable bounds but add bookkeeping overhead and can reduce peak throughput or cache locality. Randomized mechanisms (backoff) are cheap and scale well under heavy contention but only guarantee progress probabilistically, and pathological adversarial timing (rare in practice, but not impossible in theory) could delay a particular thread arbitrarily long, though the expected wait remains bounded.

Trace a concrete readers–writers scenario with a naive writer-priority policy, then the aging fix, to see starvation appear and disappear.

Setup. Reader-priority variant: a writer may enter only when no reader is currently reading and none is waiting with higher priority; suppose writers are given strict priority so that any waiting writer is served before any newly arriving reader. Requests arrive in this order (time increases downward), each writer taking one time unit and finishing quickly, each reader wanting to read for one time unit:

In the naive column, as long as writers arrive faster than R2 can be squeezed in, R2 is a textbook starving reader: ready, never denied by any cycle (so not deadlock), yet never scheduled — an unbounded number of writers can overtake it. In the aging column, R2's `wait_time` grows every round it is passed over, so its `effective_priority` eventually exceeds any writer's static priority, forcing the scheduler to admit R2 no later than round $B = \lceil (M - s_{R2}) / \alpha \rceil$, giving a computable, finite guarantee instead of "eventually, we hope."

A livelock trace. Two threads $T_1, T_2$ each need locks $A$ and $B$, using the polite-release protocol with `FIXED_DELAY = 5ms` for both, started 1ms apart:

Because both threads use the identical fixed delay and their relative offset never changes, the pattern at $t=1, 6, 11, 16, \dots$ repeats exactly: this is livelock, not deadlock — locks are being acquired and released continuously — but neither thread ever holds both $A$ and $B$ simultaneously. Switching `sleep(5)` to `sleep(random(0, 2^attempt * BASE))` breaks the fixed 5ms offset: after a few rounds the random delays desynchronize enough that one thread's retry lands in a window where the other is not contending, and it acquires both locks.

Operating system schedulers (Linux's Completely Fair Scheduler, Windows' priority boosting for starved threads) build in explicit anti-starvation mechanisms because pure priority scheduling is known to starve low-priority work. Database engines use aging or wound-wait/wait-die schemes not just to avoid deadlock but to prevent transactions from being perpetually aborted and restarted by younger, more aggressive transactions. Network protocols — Ethernet's CSMA/CD, TCP's congestion-control backoff, wireless MAC layers — rely on randomized exponential backoff precisely to prevent livelock-like collision loops between competing senders. Concurrent data structure libraries (Java's `java.util.concurrent`, Linux kernel queued spinlocks) implement ticket and MCS locks specifically because naive spinlocks can be starvation-prone under real cache-coherence traffic patterns, even though they are deadlock-free on paper. Distributed consensus and leader-election protocols must guard against livelock when multiple nodes simultaneously detect a leaderless state and race to become leader, a scenario directly analogous to the two-thread polite-lock livelock traced above, usually resolved with randomized election timeouts (as in Raft).

Ask the tutor: How would you redesign a writer-priority readers-writers lock to guarantee bounded waiting for readers without sacrificing writer throughput too much?