Starvation and Fairness in Locks and CPU Scheduling

Starvation is the quiet relative of deadlock. In a deadlock, nothing moves. In starvation, the system looks busy and healthy, throughput graphs are fine, and one task or one class of tasks simply never gets its turn. A writer that can’t get past a stream of readers, a low-priority batch job that hasn’t run since Tuesday, a free-tier customer whose requests always lose to paid ones. Interviewers ask about it because the fixes involve a real trade-off between doing the most work and treating everyone acceptably.

A writer that never gets in

Reader-writer locks are the cleanest example. Many readers can hold the lock together; a writer needs it alone. The simplest design lets a new reader in whenever no writer is active, which is good for read throughput. But if readers overlap so that at least one is always inside, a waiting writer never sees the reader count reach zero.

Here’s that lock, with a flag to switch to writer preference, where a waiting writer also blocks new readers:

import threading

class RWLock:
    def __init__(self, writer_priority):
        self.cond = threading.Condition()
        self.readers = 0              # readers inside
        self.writer = False           # a writer inside
        self.writers_waiting = 0
        self.writer_priority = writer_priority
    def acquire_read(self):
        with self.cond:
            # reader preference: only an active writer blocks readers
            # writer preference: a waiting writer also blocks new readers
            self.cond.wait_for(lambda: not self.writer and
                               not (self.writer_priority and self.writers_waiting))
            self.readers += 1
    def release_read(self):
        with self.cond:
            self.readers -= 1
            if self.readers == 0: self.cond.notify_all()
    def acquire_write(self):
        with self.cond:
            self.writers_waiting += 1
            self.cond.wait_for(lambda: not self.writer and self.readers == 0)
            self.writers_waiting -= 1
            self.writer = True
    def release_write(self):
        with self.cond:
            self.writer = False
            self.cond.notify_all()

The test runs four reader threads for two seconds, each repeatedly holding a read lock for 10 ms, started 2.5 ms apart so their reads overlap. At 0.1 seconds a writer asks for the lock. Two runs on Python 3.14:

reader preference: writer got the lock after 1891 ms; readers completed 605 reads
writer preference: writer got the lock after 10 ms; readers completed 588 reads
reader preference: writer got the lock after 1903 ms; readers completed 591 reads
writer preference: writer got the lock after 14 ms; readers completed 603 reads

With reader preference, the writer got in after about 1.9 seconds, which is exactly when the readers hit their two-second deadline and stopped. It wasn’t slow; it was starved, and it would have waited as long as readers kept arriving. With writer preference it waited 10 to 14 ms, about one read’s length, and the readers lost almost nothing. Writer preference can starve readers instead if writes are constant, so production locks usually alternate or queue arrivals in order.

Note the difference from deadlock. Here nobody is stuck in a cycle. Readers complete hundreds of operations; the system as a whole is making progress. One participant is just being postponed indefinitely by a policy that keeps choosing someone else.

Where starvation comes from

The pattern is always the same: a policy picks the “best” candidate every time, and some candidate is never the best. Some places it shows up:

• Strict priority scheduling. If high-priority work keeps the CPU busy, low-priority work never runs.
• Shortest job first. It minimises average waiting time, which is why it’s attractive, and a long job can wait forever behind a steady stream of short ones.
• Unfair locks. When a lock is released, a thread that’s already running can often grab it again before the waiter it woke gets scheduled. That barging is good for throughput and bad for the waiter. Apple named its lightweight lock os_unfair_lock to say so up front.
• Disk and request schedulers that always serve the nearest or cheapest request can leave requests at the far end waiting.

Fairness has a price

Fair policies hand the resource over in arrival order, which means more context switches and less cache warmth. You can measure the trade on a lock. This FIFO ticket lock serves threads strictly in the order they asked:

class TicketLock:
    """FIFO lock: threads are served in the order they asked."""
    def __init__(self):
        self._cond = threading.Condition()
        self._next_ticket = 0
        self._now_serving = 0
    def __enter__(self):
        with self._cond:
            my = self._next_ticket; self._next_ticket += 1
            self._cond.wait_for(lambda: self._now_serving == my)
    def __exit__(self, *exc):
        with self._cond:
            self._now_serving += 1
            self._cond.notify_all()

Two threads competing for one second over a short critical section, first with threading.Lock, then with the ticket lock:

threading.Lock  acquisitions {'A': 13098, 'B': 13044}  worst wait ms {'A': 7.7, 'B': 7.7}
TicketLock      acquisitions {'A': 11971, 'B': 11781}  worst wait ms {'A': 0.6, 'B': 0.2}
threading.Lock  acquisitions {'A': 13699, 'B': 13024}  worst wait ms {'A': 7.7, 'B': 15.1}
TicketLock      acquisitions {'A': 12092, 'B': 11698}  worst wait ms {'A': 0.3, 'B': 0.2}

The ticket lock did 9 to 11% fewer acquisitions and cut the worst wait from 7.7 to 15 ms down to well under a millisecond. Python’s GIL shapes the exact numbers (by default it passes the interpreter between threads on a 5 ms switch interval), but the direction matches what Java documents for ReentrantLock: a fair lock gives lower overall throughput and more predictable waiting. Whether that’s worth it depends on whether you care about the average or the tail.

How schedulers bound the wait

Operating system schedulers can’t afford starvation, so they all build in a way to bound it.

Aging raises a task’s priority the longer it waits, so eventually it outranks everyone. The multi-level feedback queue described in OSTEP does a blunt version: every so often it moves all jobs back to the top queue, so a CPU-heavy job that sank to the bottom gets a turn regardless of what’s arriving.

Proportional share gives up on strict priority. Each task gets a share of the CPU in proportion to a weight. Lottery scheduling does this randomly, with tickets; stride scheduling does it deterministically. Linux’s CFS tracked each task’s virtual runtime, CPU time scaled by its weight, and always ran the task with the smallest. Since kernel 6.6 the default is EEVDF, which keeps weighted fairness and adds deadlines for latency-sensitive tasks. A nice value is a weight, not a strict rank: in CFS each nice step changes a task’s share by roughly 10%, so even a nice 19 task still gets some CPU next to a nice 0 one.

Real-time classes (SCHED_FIFO, SCHED_RR) are the exception. They’re strict priority on purpose, and a runaway SCHED_FIFO thread can starve everything below it. Linux reserves 5% of each second for normal tasks by default (sched_rt_runtime_us is 950,000 out of a 1,000,000 µs period) as a safety valve.

The textbook vocabulary for all this is bounded waiting: once a thread asks to enter a critical section, there’s a limit on how many times others can enter before it. Mutual exclusion and progress aren’t enough on their own; an algorithm that satisfies both can still starve someone.

Interview exercise: free-tier jobs that never run

A job platform has two classes of work: paid customers at high priority and free-tier at low priority, served by the same worker pool from a priority queue. During a big sale, paid jobs arrive continuously, and free-tier jobs don’t run at all for six hours. Product still wants paid jobs favoured. What would you change?

Answer and reasoning

The priority queue implements strict priority, so whenever any paid job is waiting it wins. During the sale, paid demand alone exceeded capacity, so free-tier jobs never reached the front. That’s starvation by policy, not a bug in the queue.

“Favoured” should become a share rather than a rank. One approach is weighted fair queuing between the classes, for example serving paid and free in a 4:1 ratio with weighted round robin or deficit round robin: when both queues have work, free-tier gets about 20% of dispatches; when free-tier is empty, paid gets everything, so no capacity is wasted. Another is aging: compute a job’s effective priority from its class plus time waited, so a free job waiting more than, say, 30 minutes outranks a fresh paid job. A third is reserving a small dedicated pool of workers for free-tier.

Whichever you pick, define the promise explicitly (“free-tier jobs start within 30 minutes”) and monitor it with the age of the oldest waiting job per class, not just throughput, because starvation is invisible in throughput graphs. If paid demand alone exceeds capacity, no scheduling policy creates more workers; you also need autoscaling or admission control.

More on scheduling

• Operating Systems interview questions
• Operating Systems MCQs
• Priority Inversion and Lock Ownership
• Deadlock Conditions and Lock Ordering
• OSTEP, Scheduling: Proportional Share, covering lottery, stride and the Linux CFS scheduler