What does it mean for a thread to be starved, and which properties of a lock implementation or a scheduler make starvation possible? Give at least two concrete mechanisms.
answer
- Starvation = system progresses, one thread never does
- Enabler = unbounded overtaking
- Barging lock, LIFO wait set, strict priority, reader-preference
- Fix = FIFO/handoff, aging, bounded overtaking (k bypasses)
- Metric = max/age-of-oldest wait, not the average
basics
~20 sStarvation is when a runnable thread never gets the resource it needs, even though the system as a whole keeps making progress. It comes from unbounded overtaking: barging (non-queued) locks, LIFO or priority-ordered wait sets, strict priority scheduling with a busy high-priority class, and readers that keep a writer out.
solid answer
~1 min**Starvation** = an individual thread is perpetually denied a resource it is eligible for, while other threads keep completing. It is a liveness failure at the level of one participant, not of the whole system — that is what separates it from deadlock and livelock. The enabling property is always **unbounded overtaking**: nothing limits how many times a newcomer may be served ahead of a waiter. Concrete mechanisms: - **Barging locks.** On release, ownership goes to whichever thread happens to be spinning or freshly arriving rather than to the longest waiter. A just-woken waiter has to be rescheduled first (microseconds) and loses the race repeatedly. - **LIFO or unordered wait sets / condition-variable wakeups.** A stack-ordered queue can leave the bottom entry forever; a "wake one arbitrary waiter" primitive gives no guarantee to any particular waiter. - **Strict priority scheduling.** If the scheduler always runs the highest-priority runnable thread, a saturated high-priority class starves everything below it — unless the scheduler ages priorities upward over time. - **Reader-writer locks with reader preference.** A continuous stream of overlapping readers keeps the writer out indefinitely (and vice versa with writer preference). Fixes: fair/FIFO queueing, priority aging, bounded overtaking ("at most k bypasses"), lock handoff, or admission control that caps the arrival rate of the class doing the overtaking.
code
text · 3 linesowner releases lock -> waiter W is signalled (must be rescheduled: ~5us)
-> thread N, already on CPU, calls lock() and CASes it (~50ns)
N wins. W parks again. Repeat every release -> W starves.go deeper
Define it: one thread never gets its turn while others keep being served, and name one cause such as always serving the highest-priority thread.
Explain unbounded overtaking concretely — barging locks, LIFO wait sets, reader preference — and name the fixes (FIFO fairness, aging, bounded bypasses).
Bring in observation and operation: per-class wait histograms, age-of-oldest, why averages hide it, and when to trade throughput for a bounded tail.
Treat it as an isolation problem: guarantee shares per tenant or class, use proportional-share scheduling and separate pools, and set explicit tail-latency objectives that the fairness policy must satisfy.
## Definition A thread is **starved** when it is continuously eligible to run or to acquire a resource, yet is never selected, while other threads are selected repeatedly. The formal property being violated is usually one of: - **Starvation-freedom (lock-level)**: every thread that requests the lock eventually acquires it. - **Bounded waiting**: after a thread requests the lock, other threads may enter the critical section at most a bounded number of times before it does. - **Fairness (scheduler-level)**: every runnable thread eventually receives CPU time, often quantified as a share. Note the strength ordering. Deadlock-freedom only promises that *some* thread progresses. Starvation-freedom promises that *every* thread progresses. Bounded waiting is stronger still: it quantifies the delay. Many production locks deliberately provide only the weakest guarantee because it is the fastest. ## Mechanism 1: barging (non-queued) locks A typical fast mutex is a compare-and-swap on a word plus a queue of parked waiters. When the owner releases, it clears the word and wakes a waiter. But the woken waiter must be rescheduled onto a core — often several microseconds — during which any thread already running that calls `lock()` can win the compare-and-swap immediately. That is **barging**: the newcomer overtakes the queue. Barging is great for throughput (the lock never idles while a waiter is being scheduled, and the barging thread's data is already cache-hot) and terrible for the tail: under sustained contention a specific waiter can be overtaken thousands of times. This is exactly why lock libraries offer an optional *fair* mode and why it costs throughput. ## Mechanism 2: wait-set ordering If waiters are stored in a LIFO stack, the earliest arrival sits at the bottom and is served last — forever, if arrivals never stop. Similarly, primitives that "signal one waiter" without specifying which, or that wake all waiters into a re-race (thundering herd), give no per-thread guarantee. A FIFO queue with strict handoff removes the possibility but serialises the wake-up path. ## Mechanism 3: strict priority scheduling Under strict (fixed) priority, the scheduler always picks the highest-priority runnable thread. If that class is never empty, lower classes receive nothing. Real schedulers therefore add **aging**: a thread's effective priority rises with waiting time, guaranteeing it eventually reaches the top. Proportional-share schedulers (weighted fair queueing, lottery/stride scheduling, CFS-style virtual-time schedulers) sidestep the problem differently — every runnable thread has a positive share, so its virtual clock always advances toward the front. The lesson for interviews: strict priority is starvation-prone by construction, and every practical priority scheduler bolts on an anti-starvation mechanism. ## Mechanism 4: reader-writer asymmetry A reader-preferring reader-writer lock admits a new reader whenever any reader holds the lock. With overlapping readers arriving faster than they finish, the read side never drops to zero and a waiting writer starves. Writer preference flips the victim: a queue of writers can starve readers. The usual remedy is a **phase-fair** or queue-based policy that alternates: once a writer is waiting, new readers queue behind it, so each side is bounded. ## Mechanism 5: resource-shaped starvation Starvation is not only about locks and CPU. A thread pool where long tasks monopolise every worker starves short tasks; a connection pool grabbed by a batch job starves interactive queries; a scan-heavy workload starves buffer-cache residency for point lookups. Any shared, contended, non-preemptible resource can starve a class of work when allocation is demand-driven and unbounded. ## How to detect it The signature is **throughput fine, tail catastrophic**. Averages hide starvation completely, so look at p99/p999 latency and, better, the *maximum* wait time per class of work. Instrument lock-wait and queue-wait histograms per caller, or per tenant, and watch for a distribution with a long flat tail rather than a heavier peak. Age-of-oldest-waiting-item is the single most diagnostic metric for queues, because it goes to infinity under starvation while length may look normal. ## How to fix it 1. **Fair queueing / FIFO handoff** on the contended lock or queue — bounded waiting by construction, at a throughput cost. 2. **Bounded overtaking**: allow barging but only k times before forcing handoff. This retains most of the throughput and caps the tail — a common compromise inside modern lock implementations. 3. **Aging**: increase effective priority (or decrease virtual finish time) with waiting time. 4. **Proportional share instead of strict priority** so every class gets a guaranteed slice. 5. **Isolation**: separate pools or queues per class of work so a greedy class cannot consume the resource another class depends on. 6. **Admission control**: cap the arrival rate of the overtaking class so the resource is not permanently saturated — starvation requires sustained saturation, and removing saturation removes the symptom.
- How do you distinguish starvation from livelock when triaging?Check whether the system as a whole completes work. Under livelock aggregate throughput collapses to near zero while CPU stays high; under starvation throughput looks healthy and only a subset of work never finishes, which shows up in per-class tail latency or an ever-growing age-of-oldest-request. Also, livelock disappears if you reduce to one participant, whereas the starving thread was always runnable on its own.
- Why not make every lock fair by default?Fairness forces a handoff to the next queued thread, which means the lock sits idle while that thread is rescheduled, and the incoming thread's data is cold in cache. Under contention this can cut throughput by a large factor compared with barging. The usual engineering answer is to default to fast/unfair locks, keep critical sections short, and switch on fairness only where a bounded tail matters more than throughput.
- What single metric best reveals starvation in a work queue?The age of the oldest waiting item (or the maximum wait time per class), because it grows without bound when a waiter is perpetually overtaken while average latency and queue length can look completely normal. Percentiles help, but the maximum and the oldest-item age are what actually diverge.
A queue-less coffee bar where the barista serves whoever is closest. Regulars standing near the counter are served all morning; the polite person who stepped back never gets a coffee even though coffee keeps being made.
saying these in an interview costs you the question
- Calling starvation a form of deadlock — the starved thread is runnable and the rest of the system keeps completing work.
- Believing an unfair lock is broken; barging is a deliberate throughput optimisation with a tail-latency cost.
- Assuming thread priorities alone fix or cause nothing — strict priority without aging is a textbook starvation source.
- Diagnosing with average latency, which hides starvation entirely; the maximum wait or oldest-item age is the signal.
- Claiming a reader-writer lock is inherently fair; reader preference starves writers and writer preference starves readers unless the policy is phase-fair.