The idea: share the CPU by tickets
Most schedulers try to finish jobs fast or answer quickly. A proportional-share scheduler has a different goal: each job should get a fixed fraction of the CPU. You give each job a number of tickets, and a job with twice the tickets should get twice the CPU. Waldspurger and Weihl built two schedulers on this idea at MIT: lottery scheduling (1994) and stride scheduling (1995).
The page runs one CPU and up to three jobs, one tick per step; every tick is one quantum. Top left: each job's tickets, its share of the tickets in play right now, the CPU ticks it got and the fair amount it should have got. Top right: the lottery's ticket line, or stride's pass values. Below: a Gantt chart; a coloured cell means the job ran in that tick.
Lottery scheduling
Each tick, the scheduler adds up the tickets of the ready jobs (say 400), draws a random number from 0 to 399 and walks the job list: A holds tickets 0–99, B 100–149, C 150–399. The job whose range holds the number runs. A job with 250 of 400 tickets wins each draw with probability 250/400, so on average it gets 62.5% of the CPU.
- It needs almost no state: a ticket count per job and a random number generator. A new job just adds its tickets to the total.
- It is only fair on average. In 40 draws with seed 1, A (100 tickets) wins 5 times, B (50) 4 times and C (250) 31 times, against fair shares of 10, 5 and 25 (Demo: lottery, 100 : 50 : 250 tickets). The error grows like the square root of the number of draws, so it shrinks only relative to the total.
- The page draws from a small seeded generator (mulberry32), so a run is the same every time and Undo works. A real kernel would use a fast pseudo-random generator too.
Unfairness of short jobs
OSTEP measures this with the unfairness metric U: two jobs with the same tickets and the same length; U = the time the first one finishes divided by the time the second one finishes. A perfect scheduler gives U close to 1. With seed 1, B finishes at tick 12 and A at tick 20, so U = 12 / 20 = 0.60 (Demo: lottery, two equal jobs (unfairness)). Seeds 2 and 3 give 0.90 and 0.85. Over 2000 seeds the average U is 0.83 for 10-tick jobs and 0.94 for 100-tick jobs: lottery is fair for long jobs, not for short ones. Stride finishes them at ticks 19 and 20, U = 0.95 (Demo: stride, two equal jobs).
Stride scheduling
Stride scheduling gets the same shares with no randomness. Each job has a stride = a large constant / tickets (10000 here, as in OSTEP), so 100 tickets → stride 100, 50 → 200, 250 → 40. Each job also has a pass value, starting at 0. Every tick:
current = the ready job with the smallest pass (ties: list order) run current for one tick current.pass += current.stride
A job with a small stride falls behind slowly, so it is picked more often. With 100 : 50 : 250 tickets the 40 ticks go exactly 10, 5 and 25, and every pass ends at 1000 (Demo: stride, the same tickets, exact shares). After any tick, no job is more than about one tick away from its fair share (1.25 at most in this demo; the lottery run is 6 ticks off at the end).
| Lottery | Stride | |
|---|---|---|
| Picks | a random ticket | the smallest pass |
| State per job | tickets | tickets, stride, pass |
| Shares over a short run | noisy (40 ticks: 5, 4, 31 instead of 10, 5, 25) | exact (10, 5, 25) |
| A new job arrives | add its tickets, nothing else | must choose its starting pass |
| Two equal 10-tick jobs | U = 0.60 with seed 1, 0.83 on average | U = 0.95 |
A job that arrives late
Stride's pass values are global state, and that bites when a job joins. A and B have run 10 ticks each, so their passes are 1000. If C starts at pass 0, it is "owed" 1000 of pass, and it takes the CPU for 10 ticks in a row (ticks 20–29) while A and B get nothing (Demo: stride, a new job starts at pass 0). The fix is to start C at the smallest pass of the ready jobs, 1000. Then A, B and C take turns at once (Demo: stride, a new job starts at the smallest pass). The page uses the same rule when a job wakes up after waiting. Lottery has no such problem: C's tickets simply join the next draw.
Ticket transfer
Tickets can move. When client A sends a request to server S and blocks, its 100 tickets do nothing while it waits, and S has only 20 tickets against B's 100. S wins about one draw in six, and A is done at tick 35 (Demo: lottery, client waits on a server). With ticket transfer, A lends its tickets to S until the reply: S runs with 120 tickets, wins about one draw in two, and A is done at tick 15 (Demo: lottery, ticket transfer to the server). Under stride the same two runs end at ticks 26 and 13. The lottery paper also describes ticket currencies (a user splits its tickets among its own jobs in its own unit) and ticket inflation (a trusted job raises its own tickets when it needs more CPU).
Stride and CFS's vruntime
Linux's Completely Fair Scheduler, shown on CPU Scheduling, is stride scheduling with real time instead of whole ticks:
| Stride scheduling | CFS |
|---|---|
| tickets | weight, from the nice value (nice 0 = 1024) |
| stride = 10000 / tickets | vruntime grows by time × 1024 / weight |
| pass | vruntime |
| run the smallest pass | run the leftmost task in a red-black tree ordered by vruntime |
| a new job starts at the smallest pass | a new task starts near min_vruntime |
CFS does not use a lottery: like stride it is deterministic, and it keeps tasks in a tree so that picking the smallest vruntime is fast with thousands of tasks. Proportional share fits jobs that are all ready; for jobs that block and wake often, see the priority tricks of the multi-level feedback queue, and for strict deadlines real-time scheduling.
The demos in numbers
| Demo | Result |
|---|---|
| lottery, 100 : 50 : 250 | 40 ticks: A 5, B 4, C 31 (fair 10, 5, 25) |
| stride, same tickets | A 10, B 5, C 25; every pass ends at 1000 |
| lottery, two equal jobs | B done at 12, A at 20; U = 0.60 |
| stride, two equal jobs | A done at 19, B at 20; U = 0.95 |
| stride, late job at pass 0 | C runs ticks 20–29 alone; in 40 ticks A 14, B 13, C 13 |
| stride, late job at the smallest pass | C starts at 1000; A 17, B 17, C 6 |
| lottery, no transfer | A done at tick 35 |
| lottery, ticket transfer | A done at tick 15 |
What the page leaves out
- One CPU, whole ticks, and a job always runs its whole quantum. Real lottery and stride schedulers give a job that blocks early a compensation ticket (lottery) or a smaller pass increase (stride), so it does not lose its share.
- When tickets change, the stride paper adjusts the remaining pass of the job (and uses a global pass for joins). The page simply recomputes the stride and keeps the pass.
- No ticket currencies, no inflation, no hierarchical stride, no I/O except the one request to S, and no context-switch cost. Several CPUs are not shown either.