Big idea
Earlier schedulers optimize turnaround or response time. Proportional-share scheduling aims at fairness — each job gets a share of the CPU matching its allocation.
Lottery scheduling
Jobs hold tickets. The scheduler draws a winning number; more tickets → higher chance to run. Over a long enough run, shares approach the ticket proportions.
Example: A has tickets 0–74 (75 tickets), B has 75–99 (25 tickets).
Ticket mechanisms
- Ticket currency / conversion — a process can hand tickets to its own children in a local currency that converts to a global share. Example from notes: OS gives A and B 100 tickets each (200 total). A splits 500/500 to two jobs locally → each child is 50 global; B’s one job keeps 100 global.
- Transfer — pass tickets to another process (e.g. client → server so the server answers faster).
- Inflation — processes raise or lower their own ticket counts. Only safe when processes trust each other.
Unfairness metric
Unfairness near 1.0 is most fair. Example: A finishes at 10, B at 20 → U = 10/20. Unfairness tends to drop as jobs run longer (law of large numbers).
Stride scheduling (deterministic)
Lottery is probabilistic and can look skewed in short windows. Stride is a deterministic alternative.
Example: tickets A=100, B=50, C=250. Pick a large constant (e.g. 10,000). Stride = constant / tickets → A:100, B:200, C:40.
Always run the process with the lowest pass value, then add its stride. Whoever is lowest next runs, and so on.