Skip to main content

Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 9, Arpaci-Dusseau & Arpaci-Dusseau

Scheduling: Proportional Share

Instead of optimizing turnaround or response time, a proportional-share (fair-share) scheduler tries to give each job a target fraction of the CPU.

Crux: how do we share the CPU proportionally — and how well do the mechanisms work?

Classic answers: lottery (random), stride (deterministic), and Linux CFS (vruntime + weights).

Tickets = your share​

If A has 75 tickets and B has 25, A should get ~75% of the CPU.

Lottery scheduling (Waldspurger & Weihl): every time slice, draw a winning ticket in [0, total). Whoever holds that ticket runs.

  • Probabilistically correct over long runs
  • Short runs can look unfair
  • Almost no state beyond ticket counts
Use randomness

Random decisions often avoid pathological corner cases, need little state, and are fast if RNG is cheap.

Ticket tricks​

MechanismIdea
CurrencyUser assigns tickets in a private currency; OS converts to global shares
TransferHand tickets to a server while it works for you, then take them back
InflationTemporarily raise your tickets — only safe among trusting processes

Implementation sketch​

Walk a process list, accumulate tickets until counter > winner. Sorting high-ticket jobs first is an optimization, not required for correctness.

Fairness study​

Two equal-ticket equal-length jobs: unfairness U = tfirst / tsecond (ideal U ≈ 1). For short R, lottery can be quite unfair; as jobs run longer, U approaches 1.

Open problem: how many tickets should each job get? Users/admins often decide — the “ticket assignment problem” remains hard.

Stride scheduling​

Deterministic fair share:

  1. stride ∝ 1 / tickets (e.g. 10000 / tickets)
  2. Each job has a pass value (global progress)
  3. Always run the job with minimum pass
  4. After a quantum: pass += stride

Exact proportions over a cycle. Downside vs lottery: global state — a new job with pass = 0 would monopolize; lottery just adds tickets and updates the total.

Quiz

Rank the sequence

1 / 1

Order the steps of stride scheduling, from setup to after a job runs.

OrderDrag the handle to rearrange — top should be first.

  1. 1Run the job whose pass value is currently the minimum
  2. 2Compute each job's stride as inversely proportional to its tickets
  3. 3After the job runs a quantum, add its stride to its pass value
  4. 4Give every job an initial pass value

Drag items into the correct order (or use ↑↓), then check.

Linux Completely Fair Scheduler (CFS)​

Widely deployed fair-share scheduler. Goal: divide the CPU evenly (or by weight) with low overhead (scheduling alone can be ~5% of datacenter CPU in studies).

Virtual runtime​

  • Each runnable job accumulates vruntime while it runs
  • Always pick the job with the lowest vruntime
  • Runnable jobs live in a red-black tree keyed by vruntime → (O(\log n))

Dynamic slice​

  • sched_latency (e.g. 48 ms) / (n) ≈ ideal slice so fairness holds over that window
  • min_granularity (e.g. 6 ms) floors the slice so too many jobs don’t thrash on context switches

Nice → weight​

nice from −20 (more CPU) to +19 (less). Weights scale both the effective slice and how fast vruntime grows (heavier weight → vruntime climbs slower → runs more). Constant nice differences preserve the same ratios.

Sleep / I/O​

A job that slept a long time would otherwise wake with tiny vruntime and hog the CPU catching up. CFS sets a waking job’s vruntime near the current tree minimum — avoids starvation of others (but short frequent sleepers may get less than “fair”).

Interactive: lottery · stride · CFS​

Check your understanding​

Quiz

Proportional-share scheduling

1 / 4

In lottery scheduling, a process with more tickets…

Pick an answer to see if you are right.

Coding challenges​

Python — same language as lottery.py.

Homework lab: lottery.py​

Use the OSTEP lottery simulator. Notes/screenshots stay in this browser.

Lab

Homework: lottery.py

0/5 started

Loading lab…

Summary​

ApproachHow share is enforcedTradeoff
LotteryRandom ticket drawSimple; approximate; easy joins
StrideMin pass += strideExact; awkward new-job state
CFSMin vruntime + nice weightsProduction Linux; RB-tree; I/O edge cases

Fair-share leaves ticket/nice assignment hard and can interact poorly with I/O. Still excellent when shares are clear (e.g. VMs in a cloud).

Next: Multiprocessor Scheduling — SQMS, MQMS, affinity, and work stealing.

Further Reading​