Proportional-Share Scheduling: Lottery and Stride
The
Multi-Level
Feedback Queue chases good turnaround and response, but it makes no promise about
how much CPU any particular job gets. Sometimes that is exactly what you need to control. A cloud
host renting out a physical machine wants tenant A to get 60\% of a core and
tenant B 40\%, guaranteed, no matter what else is running. That is a
proportional-share (or fair-share) goal, and it needs a different kind of
scheduler — one whose whole design centre is a promised fraction, not a metric like turnaround.
The mechanism is beautifully simple: hand out tickets. A job holding
t_i of the T = \sum_j t_j total tickets is entitled to
a CPU share of
\text{share}_i \;=\; \frac{t_i}{T}.
Two classic schedulers turn tickets into a schedule. Lottery scheduling (Waldspurger &
Weihl, 1994) does it with a coin: hold a random draw each quantum, and whoever's ticket is drawn runs.
Stride scheduling does it deterministically, with no randomness at all. We build both.
Lottery: fairness by the law of large numbers
Give job A 75 tickets and job B 25. Every quantum, draw a random number in
[0, 100); if it lands in [0,75) A runs, otherwise B.
Over one draw this is pure chance — B might win three times in a row. But over many draws the
realised shares converge, by the law of large numbers, to 75\% and
25\%. The elegance is that the scheduler holds almost no state: no
per-job history, no priority decay tables. Add a job, add its tickets to the total; remove a job, remove
them. There is nothing to rebalance.
The price is variance. Lottery's fairness is only probabilistic: over a short
window a job may get noticeably more or less than its share. The expected error shrinks like
1/\sqrt{n} in the number of allocations n, so it is
excellent for long-running jobs and shakier for short ones. This is the fundamental trade you accept for
statelessness.
Your share depends on everyone else
A subtle point: your share is not fixed by your ticket count alone — it is your tickets divided by
the total, so it falls whenever someone else joins with tickets of their own. Below, the horizontal
axis is job A's own ticket count and the curve is its guaranteed share
t_A/(t_A + t_B). Drag the competitor's tickets t_B and
watch the whole curve sag — the same A tickets now buy a smaller slice because the pool grew. This
"dilution" is why real systems group tickets into currencies (below) so a user's internal
split does not leak out and dilute everyone else.
Stride: fairness made deterministic
Stride scheduling removes the dice. Pick a big constant C (say
10000). Give each job a stride inversely proportional to its
tickets, and a running counter called its pass:
\text{stride}_i \;=\; \frac{C}{t_i}, \qquad \text{scheduler picks the job with the
\emph{lowest} pass, runs it, then } \text{pass}_i \mathrel{+{=}} \text{stride}_i.
A job with many tickets has a small stride, so its pass creeps up slowly and it is picked often; a
job with few tickets has a large stride, its pass leaps ahead, and it waits longer between turns.
Over any window the pass values stay locked together, so the realised shares match the ticket ratios
exactly — no variance at all. The cost is state: stride keeps a global pass counter per job and
must find the minimum each quantum (a priority queue, giving
O(\log n) per decision). Lottery trades that exactness for near-zero state.
- a job with tickets t_i is owed CPU share
t_i / T, where T = \sum_j t_j;
- lottery picks the winner of a random ticket draw each quantum — stateless,
fair only probabilistically (error \sim 1/\sqrt{n});
- stride gives each job \text{stride}_i = C/t_i, always runs
the lowest-pass job, then advances its pass by its stride — deterministic and
exactly fair;
- tickets can be transferred (to a job you are blocked on) and scoped by a
currency (a private denomination that converts to the global pool).
Watch both schedulers run
Below, three jobs hold 100, 50, and 50 tickets — a target split of
50\%, 25\%, 25\%. The code runs a seeded lottery and a stride scheduler for the
same number of quanta and prints how many each job actually won. Notice how stride hits the target
exactly while lottery lands close — the signature difference between them.
// Proportional-share: compare LOTTERY (randomised) with STRIDE (deterministic).
const names = ["A", "B", "C"];
const tickets = [100, 50, 50]; // target shares: 50%, 25%, 25%
const total = tickets.reduce((s, t) => s + t, 0);
const QUANTA = 40;
// --- Lottery: seeded PRNG so the run is reproducible here. ---
let seed = 12345;
const rand = () => (seed = (seed * 1103515245 + 12345) & 0x7fffffff) / 0x7fffffff;
const lotteryWins = [0, 0, 0];
for (let q = 0; q < QUANTA; q++) {
let draw = Math.floor(rand() * total);
let i = 0;
while (draw >= tickets[i]) { draw -= tickets[i]; i++; } // walk the ticket line
lotteryWins[i]++;
}
// --- Stride: C/tickets, always run the lowest pass, then advance it. ---
const C = 10000;
const stride = tickets.map((t) => C / t);
const pass = [0, 0, 0];
const strideWins = [0, 0, 0];
for (let q = 0; q < QUANTA; q++) {
let m = 0;
for (let i = 1; i < pass.length; i++) if (pass[i] < pass[m]) m = i;
strideWins[m]++;
pass[m] += stride[m];
}
console.log("job tickets target% lottery stride");
for (let i = 0; i < names.length; i++) {
const target = ((tickets[i] / total) * 100).toFixed(0);
console.log(`${names[i]} ${tickets[i]} ${target}% ` +
`${lotteryWins[i]}/${QUANTA} ${strideWins[i]}/${QUANTA}`);
}
Proportional share has a lovely answer to a real problem. Suppose a client thread is blocked waiting on a
server thread (say a display server) to do work on its behalf. If the server has few tickets it runs
rarely, so the client — which is really just waiting for the server — is throttled too, even though the
client has plenty of tickets. The fix is ticket transfer: the client temporarily
lends its tickets to the server, so the server runs with the combined weight and finishes the work
the client is waiting for, then hands the tickets back. This is a scheduling-world cousin of
priority inheritance, and it neatly turns "I am blocked on you" into "so take my CPU share until
you unblock me."
A frequent slip is to read "job A has 200 tickets" as "job A gets a lot of CPU." Tickets are meaningless in
isolation — only the ratio to the total matters. 200 tickets out of 400 is half the CPU; 200 out
of 20000 is one percent. This is also why ticket currencies exist. A user can mint tickets
in their own private currency and divide them among their own jobs however they like; that currency is then
converted, as a whole, into a fixed slice of the global pool. So a user reshuffling their own jobs'
shares can never accidentally dilute or inflate other users' shares — the local split is sealed off
from the global one.
Why this matters downstream
Stride scheduling's core idea — "give each entity a per-step increment inversely proportional to its
weight, and always advance the one that is furthest behind" — is exactly the skeleton of Linux's
Completely
Fair Scheduler. CFS renames "pass" to virtual runtime and "run the lowest pass" to
"run the task with the least virtual runtime," and stores the jobs in a balanced tree instead of scanning
for the minimum. If you understand stride, CFS will feel like an old friend wearing a Linux badge.