The question this answers
The system is progressing and one task never gets to run — what keeps taking its turn?
A reporting service where hundreds of short read queries hold a read/write lock on a cache, and one background writer needs the write lock to refresh it.
A shared cache guarded by a read/write lock. Readers may hold it concurrently; the writer needs exclusive access, so it can only proceed at a moment when zero readers hold the lock.
Every task that is ready to run eventually runs — bounded waiting, not merely eventual progress. Deadlock and livelock break the system-wide progress property; starvation leaves that property intact and breaks it for one participant. The cache stays correct, the readers stay fast, and the refresh never happens.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The writer that is always almost ready
A read-preferring read/write lock lets a new reader in whenever any reader currently holds the lock. That policy maximises read throughput, which is why it is often the default, and it has a consequence people do not connect to the policy: if reader arrivals overlap, the reader count never reaches zero, and the writer never gets in.
Nothing here is a bug in the ordinary sense. Each reader acquires legally, holds briefly, and releases. The writer's request is recorded and honoured — the moment the count hits zero. Under a Poisson arrival rate high enough that inter-arrival time is shorter than read hold time, that moment does not arrive. The waiting is unbounded even though every individual wait is short.
Watch the trace and note where the invariant dies. It is not any single step; it is step 8, where the reader count returns to a value it has already had while the writer is still queued. Starvation, like livelock, is detected by noticing a repetition rather than by catching an illegal action.
| # | Reader stream (hundreds/sec) | Cache refresh writer | Reader stream (overlapping) | State |
|---|---|---|---|---|
| 1 | read_lock() — acquired | · | · | readers=1 writer=none writer waited=0 s |
| 2 | · | write_lock() — queued (readers > 0) | · | readers=1 writer=waiting writer waited=0 s |
| 3 | · | · | read_lock() — acquired (read-preferring: admitted despite queued writer) | readers=2 writer=waiting writer waited=2 ms |
| 4 | read_unlock() | · | · | readers=1 writer=waiting writer waited=4 ms |
| 5 | read_lock() — a new reader arrives and is admitted | · | · | readers=2 writer=waiting writer waited=5 ms |
| 6 | · | · | read_unlock() | readers=1 writer=waiting writer waited=7 ms |
| 7 | · | · | read_lock() — admitted | readers=2 writer=waiting writer waited=8 ms |
| 8 | read_unlock(); another reader arrives | · | · | readers=2 writer=waiting writer waited=10 ms ✕ Bounded waiting: the reader count has returned to a state it already held while the writer remains queued. The pattern is stationary, so the writer's wait is bounded only by the end of the traffic — not by anything in the lock. |
| 9 | · | ... still queued after 660 000 reader acquisitions | · | readers=2 writer=waiting writer waited=11 min |
The lane that is always ready and never running
The same shape appears without any lock at all, whenever a scheduler picks by priority and higher-priority work never runs out. A strict-priority queue with a saturating high-priority stream will never dequeue the low-priority item, and the low-priority item does not know it — from its perspective it is simply ready.
This is the distinction worth internalising: a starved task is in the ready state, not blocked and not running. It is eligible. It is passed over. On the timeline below there is no blocked segment and no idle segment on the low-priority lane; there is an unbroken band of ready, which is a state that almost never appears in a dashboard.
Real schedulers avoid this with aging — increasing a task's effective priority the longer it waits, so that any sufficiently old task eventually outranks new arrivals. That is the general fix for every starvation instance, and it appears under many names: aging in OS schedulers (The Scheduling Problem), writer-preference in a read/write lock, FIFO handoff in a fair mutex, and deadline scheduling in a queue.
Where starvation comes from, and what each source costs to fix
Starvation is not one bug; it is a family, and the fix depends on the source. What unites them is that some admission rule is *state-dependent in a way that correlates with the arrival pattern* — the more contended the resource, the less likely the starved party is to win.
The matrix below is the diagnostic. Find the row that matches your admission rule, and the fix is in the third column. Notice how consistently the fix is "add a notion of waiting time or of turn", and how consistently the cost is throughput: fairness means sometimes running the older request instead of the cheaper one, and that is a real, measurable loss. Fairness takes up exactly this trade.
One row deserves particular attention because it is invisible in application code: barging mutexes. Most production mutexes are deliberately unfair — a thread that requests the lock while a woken waiter is still being scheduled may take it first, because handing off to the woken thread costs a context switch. That design makes the mutex fast and makes long waits possible, which is a trade almost nobody makes consciously.
| Source | Why one party never wins | Fix | What the fix costs |
|---|---|---|---|
| Read-preferring RW lock | Overlapping readers keep the count above zero, so the writer is never woken. | Writer preference: block new readers once a writer is queued. | Read throughput drops and read p99 rises, because readers now queue behind writers. See Read/Write Locks, Honestly. |
| Strict priority scheduling | A saturating high-priority stream means the low-priority task is never selected. | Aging: effective priority rises with time waited. | Priorities stop meaning what they say; a low-priority job can preempt a high-priority one, which is sometimes unacceptable in real-time systems. |
| Barging (unfair) mutex | A running thread takes the lock before a just-woken waiter can be scheduled. | FIFO / ticket lock, or a fair-mode mutex. | A context switch per handoff. Measurably lower throughput under contention — often 2× or worse on a hot lock. |
| Shortest-job-first dispatch | A long job is deferred whenever any short job is available, and short jobs keep arriving. | Deadline or age-based dispatch; reserve a fraction of capacity for old work. | Mean latency rises, because you stop optimising for the common case. See Queueing: Why Systems Get Slow Before They Get Broken. |
| Retry with random backoff | One participant loses repeatedly by chance; probability of a long losing streak is small but non-zero. | Queue-based handoff, or escalate to a blocking acquire after N failures. | Loses the lock-free property of the retry loop and reintroduces blocking. See Livelock. |
| Work stealing with a hot deque | One worker's queue is always stolen from first, so its own tail tasks never run locally. | Randomised victim selection and steal-half policies. | More cross-core traffic and less locality. See Work Stealing. |
Key points
- Starvation leaves system-wide progress intact and denies it to one participant — which is why aggregate metrics never show it.
- A starved task is in the
readystate: eligible, not blocked, and repeatedly passed over. - A read-preferring RW lock under overlapping readers gives the writer an unbounded wait; the symptom is stale data, not slow requests.
- Almost every fix adds a notion of waiting time (aging, FIFO, deadlines), and almost every fix costs throughput.
- Most production mutexes are deliberately unfair, because fairness costs a context switch per handoff.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • An admission rule decides who acquires next based on current state (reader count, priority, who is running) rather than on how long each candidate has waited.
- • The arrival pattern keeps that state in a region where the starved party is never selected.
- • Because each individual acquisition is legal and brief, no error, timeout or assertion fires.
- • The starved party's wait grows without bound while every aggregate metric — throughput, error rate, median latency — stays at target.
- • A fix introduces waiting time into the admission rule: aging, a queue position, a deadline, or a preference flip once a party has been queued.
- • Non-overlapping readers: R1 acquires and releases before R2 arrives, count hits zero, writer is woken. Correct, and the schedule every test produces.
- • Overlapping readers: R2 acquires before R1 releases, so the count never reaches zero and the writer's queue entry is never serviced. Unbounded wait with bounded individual waits.
- • Writer preference: writer queues, new readers are blocked at the door, existing readers drain, writer runs. The writer's wait is now bounded by the longest current read.
- • Barging mutex: T1 releases and wakes T2; T3, already running on another core, acquires before T2 is scheduled. Repeat, and T2 waits arbitrarily long while the lock is never idle.
- • Aging: the low-priority job's effective priority crosses job C's at t=5 and it runs. The high-priority stream is delayed by two quanta — the measurable price of the fix.
- • A mutex guarantees mutual exclusion. Unless documented otherwise it does *not* guarantee FIFO order or bounded waiting —
std::mutex,pthread_mutex_tin its default mode andjava.util.concurrent.ReentrantLockin default mode are all explicitly unfair. - • A read/write lock guarantees exclusivity for writers and sharing for readers. Its *preference policy* is a separate, usually undocumented property, and it determines whether starvation is possible.
- • A semaphore guarantees at most N permits are held. It does not guarantee that a specific waiter gets one — see Semaphores: Counting Permits as a Resource Limit.
- • A fair lock guarantees bounded waiting. It does not guarantee low latency; under contention it is usually slower than the unfair version it replaced.
- • No lock guarantees anything about *which* waiter benefits. If your system requires a particular task to proceed, that requirement must live in the scheduling policy, not in the lock.
- • Starvation only manifests under contention, and gets monotonically worse as contention rises — which means load tests at half the production rate will not reproduce it.
- • The starved party contributes almost nothing to contention itself; it is one waiter among thousands, so removing it changes no aggregate metric.
- • Fair handoff reduces the maximum wait and increases the mean, because each handoff costs a wakeup and a context switch instead of letting a running thread reuse a hot lock. See The Cost of a Context Switch.
- • Writer starvation on a cache-refresh lock has a second-order cost: the longer the writer waits, the staler the data every reader gets, so the readers' correctness degrades while their latency looks perfect.
- • Writer starvation under a read-preferring RW lock — stale caches, unapplied configuration, unwritten checkpoints.
- • Reader starvation under a writer-preferring lock, the exact mirror image, which appears the moment someone "fixes" the first one.
- • Priority starvation: a background job that never runs because foreground work is saturating.
- • Queue starvation: an old item behind a stream of newer, cheaper ones under a shortest-job-first or LIFO policy — LIFO queues starve the oldest item by construction. See Depth Is Not an Emergency; Age Is.
- • Connection-pool starvation: one caller with a large request never finds enough free connections while small callers keep succeeding.
- • Unfair admission is a deliberate and often correct optimisation: read-preference maximises read throughput, barging mutexes avoid a context switch, and shortest-job-first minimises mean latency.
- • Strict priority genuinely helps when the low-priority work is truly optional — a best-effort prefetch that is allowed to never run.
- • It helps when the arrival rate is known to be bursty rather than saturating, so the resource does go idle and the queue drains naturally.
- • Whenever the starved work has a correctness or freshness requirement: cache refreshes, checkpoint writes, config reloads, lease renewals. A starved lease renewal is an outage.
- • When the SLO is on the tail rather than the median, because starvation is invisible in p50 and dominates p99.9. See
tail-latency. - • When capacity planning was done on averages: a system sized for mean utilisation will have a saturating stream at peak, which is exactly when the starved task is needed.
- • Maximum wait time, not mean — a per-lock or per-queue histogram with a real tail, because starvation lives entirely in the tail.
percentilesandaverages-liein Observability & Performance are the companion reading. - • Age of the oldest waiting item, sampled continuously. This single gauge detects every starvation variant, and a queue whose oldest item keeps growing while throughput is flat is the definitive signal. See Hold Time, Wait Time, and the Ratio Between Them and
queue-age. - • Per-class metrics: aggregate throughput hides starvation by construction, so break latency down by priority class, by caller, or by reader/writer role.
- • Data staleness as a proxy: for the cache case, "seconds since last successful refresh" catches it faster than any lock metric.
- • Reader-count-at-zero frequency. If a read/write lock's reader count never reaches zero during peak, the writer cannot run and no further investigation is needed.
- • Fair alternatives require a queue, which means more state per lock and a wakeup path, and they change the performance profile of every acquisition — not only the starved one.
- • Aging requires a timestamp per waiter and a policy for how fast priority rises, which is a tuning parameter with no obvious value.
- • Preference flips introduce the mirror-image starvation, so systems that need both often end up with a bounded-batch policy ("let at most N readers in while a writer waits") — more code and another parameter.
- • Detecting starvation requires per-class instrumentation that most services do not have, and adding it means deciding what the classes are.
- • Remove the exclusivity: publish an immutable snapshot with a single atomic pointer swap, so the writer never needs to exclude readers at all. This eliminates writer starvation by construction. See Copy-on-Write as a Concurrency Strategy and Immutability as a Concurrency Strategy.
- • Give the starved work a dedicated resource — a reserved worker, a separate connection, its own lock — instead of making it compete.
- • Convert to a queue with explicit deadlines, where "oldest first past a threshold" is expressible policy rather than emergent behaviour.
- • Reduce hold time so the resource actually goes idle. Starvation on a read/write lock frequently disappears once reads stop holding the lock during I/O. See Lock Scope: What You Hold It Across.
What people believe, and what is true
If throughput is at target, nothing is starving.
Aggregate throughput is exactly the metric starvation preserves. The starved participant is one of thousands, and its absence moves no average. Only per-class tails and oldest-waiter age reveal it.
Starvation is a kind of deadlock.
A deadlocked system makes no progress at all; a starving system makes full progress for everyone except one participant. They need different diagnoses and different fixes.
Mutexes are FIFO.
Most are explicitly not. Barging is the default in std::mutex, pthread_mutex_t, Go and Java, because handing off to a woken waiter costs a context switch that reusing the lock on a running thread avoids.
Go deeper
Overview
One task is always ready and never picked. Everyone else is fine, so nothing alerts. The cache refresh has not run since 09:00.
Practical
Measure the age of the oldest waiter, per class. If that number grows while throughput is flat, something is starving. For read/write locks, check whether the reader count ever reaches zero at peak — if it does not, the writer cannot run.
Advanced
Starvation is what you get when an admission rule is state-dependent and the state correlates with load. Every fix injects waiting time into the decision, and every fix therefore costs throughput, because you stop always choosing the locally cheapest option. That trade-off is the subject of Fairness and it has no universally right answer.
Internals
Go's mutex is a good study: it barges by default, but a waiter that has waited over 1 ms flips the mutex into "starvation mode", where the lock is handed directly to the head of the queue and barging is disabled until the queue drains. That hybrid — fast and unfair normally, fair once a wait becomes pathological — bounds the worst case while keeping the common case cheap, and it is the design most fair-lock implementations converge on.