§9.4–9.8An Example … Summary

Lottery is delightfully simple — but random. This half of the chapter asks how unfair randomness gets, then meets the deterministic alternatives: stride scheduling and the fair-share scheduler you’re probably running right now.

9.4 An Example (How Unfair Is Random?)

Two jobs, identical tickets (100 each), identical run time R. Ideally they finish together; randomness says otherwise. Define unfairness $U = \frac{T_{first}}{T_{second}}$ — the first finisher’s completion time over the second’s. Perfect fairness is $U = 1$.

9.5 How To Assign Tickets?

An open problem the chapter is honest about: system behavior depends strongly on allocation, and “let the users decide” is a non-solution — it doesn’t tell anyone what to do. Hold that thought; it returns in the summary.

9.6 Why Not Deterministic? (Stride Scheduling)

If short-run randomness bothers you, Waldspurger has the cure: stride scheduling stride scheduling Deterministic fair share — stride = bignum/tickets; run the job with the lowest pass value, then add its stride to its pass. defined in ch. 9 — open in glossary , deterministic fair share. Each job gets a stride — a big number divided by its tickets (10,000 → A:100, B:200, C:40) — and a pass counter. The rule:

curr = remove_min(queue);   // pick client with min pass
schedule(curr);             // run for quantum
curr->pass += curr->stride; // update pass using stride
insert(queue, curr);        // return curr to queue

Low pass runs; running costs you your stride; big ticket-holders pay tiny strides and therefore run often. Trace it:

Exact proportions at the end of every cycle — so why would anyone still use lottery? Global state. Suppose a new job arrives mid-cycle: what pass value should it get? Zero would let it monopolize the CPU while it “catches up.” Lottery needs no per-process bookkeeping at all — add the job, bump the global ticket count, done. New processes fold in gracefully.

9.7 The Linux Completely Fair Scheduler (CFS)

The fair-share scheduler in actual deployment on billions of machines is Linux’s Completely Fair Scheduler cfs Linux's Completely Fair Scheduler — pick the lowest vruntime; dynamic slices from sched_latency/min_granularity; nice-based weights; red-black tree of runnables. defined in ch. 9 — open in glossary — same goals, different machinery, ruthlessly focused on efficiency (scheduling burns ~5% of datacenter CPU even after aggressive optimization; Google measured it).

Basic operation. No fixed time slice. Each running process accumulates vruntime vruntime Virtual runtime a process accrues while running (scaled inversely by its weight); CFS always runs the minimum. defined in ch. 9 — open in glossary ; on a decision, CFS runs the process with the lowest vruntime. Switching often maximizes fairness but costs performance; the tension is managed by two parameters: sched_latency (~48 ms) — divide by the number of runnables n for the per-process slice — and min_granularity (~6 ms), a floor so that huge n can’t shrink slices into switch-storm territory. (A 1 ms periodic timer quantizes decisions; vruntime is tracked precisely, so imperfect multiples come out right over time.)

Weighting (niceness). Priority comes not from tickets but from the classic UNIX nice nice Classic UNIX priority knob, −20…+19 (default 0); CFS maps it to weights (1024 at 0) — positive = nicer = less CPU. defined in ch. 9 — open in glossary level, −20…+19 (default 0; positive = nicer = less CPU). CFS maps nice to weights:

static const int prio_to_weight[40] = {
    /* -20 */ 88761, 71755, 56483, 46273, 36291,
    /* -15 */ 29154, 23254, 18705, 14949, 11916,
    /* -10 */  9548,  7620,  6100,  4904,  3906,
    /*  -5 */  3121,  2501,  1991,  1586,  1277,
    /*   0 */  1024,   820,   655,   526,   423,
    /*   5 */   335,   272,   215,   172,   137,
    /*  10 */   110,    87,    70,    56,    45,
    /*  15 */    36,    29,    23,    18,    15,
};

The slice generalizes to

and vruntime accrues inversely to weight:

One elegant table property: only nice differences matter — A at −5 vs B at 0 schedules identically to A at 5 vs B at 10 (run the math and see).

Red-black trees. With thousands of processes, scanning a list every few milliseconds wastes cycles. CFS keeps runnable processes in a red-black tree red-black tree A balanced binary tree keeping operations O(log n); CFS stores runnable processes in one, ordered by vruntime. defined in ch. 9 — open in glossary ordered by vruntime — insert, delete, and find-min in O(log n):

Sleepers. A wrinkle: if B sleeps 10 seconds while A runs, B wakes 10 seconds behind in vruntime — and would monopolize the CPU while catching up, starving A. CFS’s fix: on wake, set the job’s vruntime to the tree’s minimum. Starvation avoided — at a cost: processes that sleep briefly but often never accumulate credit, and can fall short of their fair share.

9.8 Summary

Three fair-share schedulers: lottery (randomness → proportions in expectation, zero global state), stride (deterministic exactness, awkward newcomers), and CFS (a bit like weighted round-robin with dynamic time slices, built to scale — the most widely used fair-share scheduler in existence). Caveats for the family: I/O-heavy jobs can get shorted, and ticket/nice assignment remains unsolved — which is why general-purpose systems often lean on MLFQ-like schedulers instead. But where shares are the point — say, dividing a virtualized datacenter’s CPU one-quarter to the Windows VM, three-quarters to Linux — proportional share is simple and effective, and the idea extends to memory and beyond.