Starvation
Starvation is the condition where a selection algorithm ignores one or more runnable tasks so they are never executed, despite being eligible to run (Buhr §7.2.2).
Why is this a separate failure mode from deadlock?
A starving task is not blocked, it is ready (or oscillating between active/ready/blocked). The scheduler just keeps skipping it. From outside it looks alive, it consumes CPU through the ready queue, but makes no forward progress. Deadlock is the blocked-forever cousin; starvation is the ignored-forever cousin.
The “no-progress failure” family:
| failure | state | CPU use |
|---|---|---|
| Deadlock | blocked forever | no |
| Livelock | actively changing state, no work | yes |
| Starvation | ready, never selected | yes (at least briefly) |
Long-term vs short-term
Infinite starvation is rare in practice. The real enemy is short-term starvation: bounded but arbitrarily long delays. A task that eventually runs but after N unrelated tasks have passed it is still “starved” in any fairness sense that matters.
Rule 5 and where starvation comes from
Buhr’s 5 rules for a mutual-exclusion solution, rule 5:
After a thread starts entry to the critical section, it must eventually enter.
Breaking rule 5 is starvation. Most of the classical solutions break it:
- set, swap, plain fetch-inc spin-locks, no ordering on who wins the next race, a fast thread can keep winning forever
- Spin locks break rule 5 in general, “most spin-lock implementations break rule 5, ⇒ possible starvation” (Buhr §6.2)
- Plain mutex with barging, released task uses
while(!avail), infinite bargers can overtake it unboundedly - Weak semaphore (no FIFO on the blocked queue), same overtaking story
- Priority-based scheduling without aging, a low-priority task behind an endless stream of higher-priority ones never runs
- Reader-writer lock, Solution 1, continuous stream of readers prevents writers from ever entering (Buhr §6.4.4.1)
- Reader-writer lock, Solution 2, writer priority, continuous writers starve readers (§6.4.4.2)
Examples from CS343
- Readers and Writers, the canonical starvation playground, every one of the 7 solutions is in part a different starvation-avoidance policy
- Dekker has unbounded overtaking but is not starving, the race loser retracts intent so the winner cannot exclude itself on reentry (Buhr §5.18.7)
- Arbiter cycles through waiting clients in a circular search,
do { i = (i+1) % N; } while (!intents[i]);, guaranteeing no starvation - Bakery gives FIFO service, 2N+1 tickets suffice so overflow is not a starvation risk
How to prevent starvation
- FIFO the waiting queue, strong semaphore, fair lock, bakery tickets
- Barging prevention, releaser passes the lock (baton) directly to the unblocked task rather than re-racing (see Mutex Lock three regimes and Baton Passing)
- Bounded overtaking, a weaker but often sufficient property, any thread can be overtaken at most K times before it enters
- Priority aging, gradually raise a waiting task’s priority so it eventually outranks new arrivals, standard in general-purpose schedulers (see CFS)
- Cycling selection (arbiter pattern), scheduler advances through waiters rather than picking arbitrarily
"No starvation" is not "fair"
A policy can be starvation-free (every task eventually runs) while still being wildly unfair (some tasks run 1000x more often). Starvation is the weakest liveness property, fairness is stronger and usually what you actually want.