Fairness and starvation in your scheduler

“The runtime is fair” is not a law of nature. It is a policy, it lives in about four lines of your executor, and changing it changes observable behaviour.

impl ReadyQueue { pub fn push(&mut self, id: usize); pub fn pop(&mut self) -> Option<usize>; }
pub fn schedule(counts: Vec<u32>, policy: String) -> Vec<usize>

Same tasks as your executor test — task i logs i and yields, counts[i] times — run under two queue disciplines:

• "fifo" — a queue. push_back, pop_front. Waking a task puts it at the back.
• "lifo" — a stack. push_front, pop_front. Waking a task puts it at the front.

schedule([3,2,1], "fifo")  ==  [0, 1, 2, 0, 1, 0]
schedule([3,2,1], "lifo")  ==  [2, 1, 1, 0, 0, 0]

FIFO gives every task a turn before any task gets a second. LIFO runs the most recently woken task to exhaustion first, and task 0 does not log a single entry until tasks 2 and 1 have completely finished.

Why anyone would want LIFO

It looks obviously worse and it is not. When a task wakes another task, the data that task needs is usually the data that was just written — still in L1, still in registers, still hot. Running the newly woken task immediately rather than at the back of a queue of a thousand can be a large throughput win, and it lowers latency for the common ping-pong pattern where two tasks hand work back and forth.

The trade is throughput and cache locality against fairness and tail latency. A task at the back of a LIFO queue may wait an unbounded time. Production schedulers therefore do not pick one: the general design is a small LIFO slot per worker for the just-woken task, with a cap on how many times in a row that slot may win, after which the worker goes back to the fair queue. tokio uses this idea; the specific numbers change between releases, so learn the shape rather than the constant.

The starvation you cannot see here

Every task in this problem does a bounded amount of work and then finishes, so both policies terminate. That is a property of the test, not of LIFO.

Give a pure-LIFO scheduler a task that wakes itself on every poll and never completes — a busy poller, a retry loop, an unbounded stream — and it goes to the front of the queue every single time. Nothing else ever runs. Not slowly: never. That is unbounded starvation, and it is the reason the LIFO slot in real schedulers is capped rather than trusted.

What “fair” actually means

FIFO here gives round-robin fairness: each runnable task is polled once per round. It says nothing about how much work a task does per poll — a task that runs for a millisecond between yields still hogs the thread, and no queue discipline can fix that. Item 16.22 is about that half of the problem.

There is also nothing here about priority. Every task is equal. Adding priorities means multiple queues and a policy for choosing between them, which is where scheduler design starts to get genuinely difficult and where the literature on priority inversion begins.