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).

Left: a ticket line from 0 to 399 split into A 0 to 99, B 100 to 149 and C 150 to 399; a draw of 137 falls in B's range, so B runs. Right: three lanes with pass values A 100, B 200 and C 120; the smallest pass, A's, runs and grows by its stride of 100
Lottery picks a random ticket each tick; stride runs the job whose pass value is smallest, then adds its stride.

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).

LotteryStride
Picksa random ticketthe smallest pass
State per jobticketstickets, stride, pass
Shares over a short runnoisy (40 ticks: 5, 4, 31 instead of 10, 5, 25)exact (10, 5, 25)
A new job arrivesadd its tickets, nothing elsemust choose its starting pass
Two equal 10-tick jobsU = 0.60 with seed 1, 0.83 on averageU = 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.

Two Gantt strips of ticks 20 to 39. When C starts at pass 0, C runs ticks 20 to 29 alone, then A, B and C alternate. When C starts at pass 1000, the smallest pass, A, B and C alternate from tick 20
A late job that starts at pass 0 runs alone until it catches up; starting it at the smallest pass shares the CPU at once.

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 schedulingCFS
ticketsweight, from the nice value (nice 0 = 1024)
stride = 10000 / ticketsvruntime grows by time × 1024 / weight
passvruntime
run the smallest passrun the leftmost task in a red-black tree ordered by vruntime
a new job starts at the smallest passa 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

DemoResult
lottery, 100 : 50 : 25040 ticks: A 5, B 4, C 31 (fair 10, 5, 25)
stride, same ticketsA 10, B 5, C 25; every pass ends at 1000
lottery, two equal jobsB done at 12, A at 20; U = 0.60
stride, two equal jobsA done at 19, B at 20; U = 0.95
stride, late job at pass 0C runs ticks 20–29 alone; in 40 ticks A 14, B 13, C 13
stride, late job at the smallest passC starts at 1000; A 17, B 17, C 6
lottery, no transferA done at tick 35
lottery, ticket transferA 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.

On the mind map

Open the Operating Systems mind mapOperatingSystemsBoot and program start: from power on to main()Boot and program startProcesses and the kernel: how user code talks to the kernelProcesses and the kernelInterrupts and devices: hardware interrupts the CPUInterrupts and devicesScheduling and deadlock: who runs next, who gets whatScheduling and deadlockVirtual memory: every address is translatedVirtual memoryPhysical memory: who gets which bytes of RAMPhysical memoryFiles and storage: from open() down to the diskFiles and storageDisks and RAID: blocks down to platter or flashDisks and RAIDIsolation and security: limit what a process can doIsolation and securityContext switchContext switchswitch_mm loads CR3, switch_to swaps stacksCPU scheduling algorithmsCPU scheduling algorithmsFCFS, SJF, RR, CFS: compare waiting timeMultiprocessor SchedulingMultiprocessor SchedulingPer-CPU queues + stealing beat one lockMulti-Level Feedback QueueMulti-Level Feedback QueueUse your quantum, drop a levelLottery & strideTickets set shares; stride runs lowest passPreemptive vs cooperativePreemptive vs cooperativetimer forces a switch, or wait for yieldReal-time schedulingReal-time schedulingpriority inversion, fixed by inheritanceLoad averageLoad averagedamped count of R and D tasksBanker's algorithmBanker's algorithmgrant only if a safe order still existsDeadlock detectionDeadlock detectionFind the cycle, then kill a victimOpen the Operating Systems mind mapOperating Systemswho runs next, who gets whatScheduling and deadlockContext switchContext switchswitch_mm loads CR3, switch_to swaps stacksCPU scheduling algorithmsCPU scheduling algorithmsFCFS, SJF, RR, CFS: compare waiting timeMultiprocessor SchedulingMultiprocessor SchedulingPer-CPU queues + stealing beat one lockMulti-Level Feedback QueueMulti-Level Feedback QueueUse your quantum, drop a levelLottery & strideTickets set shares; stride runs lowest passPreemptive vs cooperativePreemptive vs cooperativetimer forces a switch, or wait for yieldReal-time schedulingReal-time schedulingpriority inversion, fixed by inheritanceLoad averageLoad averagedamped count of R and D tasksBanker's algorithmBanker's algorithmgrant only if a safe order still existsDeadlock detectionDeadlock detectionFind the cycle, then kill a victim
This page on the Operating Systems mind map · 64 pages in 9 branches · open it to see the whole map and test yourself in recall mode.