Starvation and fairness

The problem it solves

A thread is waiting for a lock. The lock is released. Another thread takes it. The first thread is still waiting. The lock is released again, and another thread takes it again.

Nothing is broken. Every critical section is short, every acquisition is legitimate, the system is doing plenty of work, and one participant is getting none of it. That is starvation: not a failure of correctness but a failure of fairness, and it is invisible to almost every check you might run. Throughput looks fine. No thread is deadlocked. The only symptom is a latency distribution with a tail that nobody can explain, belonging to whichever request happened to be unlucky.

The reason it happens is that a plain mutex makes no promise about who gets in next. When it is released, whichever thread the scheduler runs may take it — including the thread that just let it go, which is often the one still running on a warm core with the cache line already in hand.

The mechanism

Most production mutexes are barging locks: a thread arriving at the moment of release can take the lock ahead of threads that have been queued for much longer. This is deliberate and it is a throughput optimisation. Handing the lock to a queued thread means waking it, which costs a context switch and a cold cache; letting the running thread take it costs nothing. On a lock acquired millions of times a second, that difference is large.

A fair lock maintains a queue and hands ownership to the longest waiter. It removes starvation by construction and costs real throughput — every handoff is now a wake-up, and the lock cannot be re-taken by the thread that would have been fastest. Java’s ReentrantLock(true) is fair and is measurably slower, sometimes by an order of magnitude, which is exactly why it is not the default.

The trade is genuine and there is no free option. What there is instead is a decision: do you care more about total work done or about the worst case for any one participant?

What the enumeration shows

The program is a greedy thread that acquires the lock three times in a loop, and one other thread that wants it once. The waiter counts how many acquisitions happened ahead of it.

One of four interleavings starves the waiter completely — the greedy thread gets in all three times before the waiter gets in at all. The other three interleavings serve it earlier. Nothing here is malfunctioning: each of those four orderings is a legal execution of a correct program.

The value of watching it is that it makes visible something normally hidden behind averages. The lock is never held for long. The waiter is never blocked for long at any one moment. It is simply always behind, and there is no instant at which anything looks wrong.

The numbers worth carrying

• Greedy loop against one waiter: 1 of 4 interleavings starves it entirely.
• A fair lock in Java is roughly an order of magnitude slower in throughput on a contended short critical section than the barging default. That number is why the default is what it is.
• Starvation shows up in the p99 and p999, never in the mean or median. If your average latency is flat and your tail is not, and the resource is contended, this is a candidate.
• The general shape: as contention rises, the number of acquisitions that jump the queue rises with it, so a lock that was fair enough at low load becomes visibly unfair at high load without anything changing.

Where it breaks down

Starvation is not livelock. In livelock nobody makes progress; here the system makes plenty and one participant is excluded. They get confused because both present as “a thread that never finishes”.

Fairness at the lock does not give fairness end to end. A fair mutex ensures the waiting is FIFO. It says nothing about the thread that never reaches the queue because it is blocked elsewhere, or about a request whose work is longer than everyone else’s.

Reader-writer locks starve writers specifically. Under continuous read traffic, a writer waiting for all readers to leave may never see a gap — see reader-writer locks. This is common enough that most implementations offer a writer-preference mode, which then starves readers instead.

Priority inversion is the related failure worth naming. A low-priority thread holds a lock a high-priority thread needs, and a medium-priority thread — needing no lock at all — preempts the low one, so the high-priority thread waits on the medium one indirectly. It famously nearly ended the Mars Pathfinder mission. The fix is priority inheritance: the lock holder temporarily inherits the priority of the highest waiter.

What people get wrong

“Locks are fair.” Almost none are by default, and for a good reason.

“It is a scheduler bug.” The scheduler is doing what it is designed to do: run whichever thread is ready and cheapest. The lock chose not to impose an order on top of that.

“Fair locks are strictly better.” They are slower, often dramatically, and starvation may be entirely acceptable for your workload. The right question is whether any participant has a latency requirement, not whether unfairness is distasteful.

“We do not see it in testing.” Testing measures averages under uniform load. Starvation is a tail phenomenon under skewed load, which is what production is.

In production

The knobs, when you need them: new ReentrantLock(true) and new ReentrantReadWriteLock(true) in Java; parking_lot in Rust implements eventual fairness, handing the lock to a queued waiter periodically rather than always, which recovers most of the throughput while bounding the worst case. Go’s sync.Mutex does the same thing under a different name — a waiter that has been queued longer than 1ms switches the mutex into “starvation mode”, where ownership is handed directly to the head of the queue until the backlog clears. That hybrid is the state of the art and worth knowing about: it is neither policy, chosen dynamically.

The diagnosis, when you suspect it: look at the distribution of wait times for the resource rather than the mean, and look at whether a particular thread or request class is consistently in the tail. If one participant’s p99 is orders of magnitude above everyone else’s on a resource that is never held for long, you are looking at barging.

And the design that avoids the question: reduce contention rather than arbitrate it. A lock that nobody waits for cannot starve anybody — see lock granularity and work stealing for the two standard ways of getting there.

The follow-up questions

“Is a mutex fair?” — No, by default, and say why: handing off costs a context switch, barging does not.

“How would you make it fair, and what does it cost?” — A queued lock. An order of magnitude of throughput on a hot short critical section.

“A thread never gets the lock. Is that a bug?” — Not in the correctness sense. Whether it is acceptable depends on whether that thread has a latency requirement.

“What is priority inversion, and how is it fixed?” — The Mars Pathfinder story, and priority inheritance. A good signal if it comes up unprompted.