Part 4 of 8 · 2 min read
Fairness
In plain words: Starvation is not a lock cycle. The thread that starves could run if it were served, but the rules always favour somebody else. The classic causes are a scheduler that always prefers high priorities (Level 3, page 4), a reader-preference read-write lock (Level 4, page 7, where a writer waited the whole 3 s test), and a lock that lets the thread that just released it take it again.
Not every lock starves. To see how a normal mutex behaves under heavy use, four threads each took and released one mutex as fast as they could for 3 s, with a short loop inside the lock. The numbers of successful acquisitions were:
thread 0: 1,867,509 thread 1: 1,927,094
thread 2: 1,840,963 thread 3: 1,872,423
The spread was about 5 per cent from the lowest to the highest. No thread starved in this test, although the lock gives no promise of fairness. A different load or machine could give a different result, and the POSIX mutex makes no guarantee of order.
There are three standard cures:
- Aging. The longer a thread waits, the higher its priority grows. Level 3, page 4, used it in the multilevel feedback queue.
- Queued locks. Serve waiting threads in order of arrival. A ticket lock (Level 4, page 2) does this, at the cost of lower speed when threads outnumber processors.
- Bounded bypass. Let a new request overtake a waiting one at most a fixed number of times.
Compare the three problems: a deadlock never ends, a livelock ends only by luck, and starvation ends when the competing load ends. Starvation is the mildest of the three. The longest wait of any thread is what a fair system must limit.
Aging
Aging is a method that raises the priority of a thread the longer it waits, so that every thread is eventually served and starvation is prevented.
Example: a job that has waited 10 minutes gets one priority level more every minute, until it outranks the new arrivals.
Check yourself: 1. Why did no thread starve in the mutex test, and what does the test not prove? 2. Name two causes of starvation. 3. How does a ticket lock prevent starvation?