Part 3 of 7 · 2 min read
Lottery
In plain words: Hold a raffle at every turn. Each process holds tickets, and the number of tickets is its weight. The scheduler draws one ticket at random, and its owner runs for one quantum. A process with 25 per cent of the tickets wins about 25 per cent of the draws. The analogy stops in one place: a raffle has one winner per event, but a scheduler holds a draw again after each quantum, so luck evens out.
Lottery scheduling needs almost no memory: only the ticket counts. To draw, pick a random number from 0 to the total minus 1, and walk down the list of processes, subtracting each count until the number falls inside one process's range.
Here are results from a program with 100, 50 and 250 tickets (total 400, expected shares 25.0, 12.5 and 62.5 per cent), using a random number generator with a fixed seed:
| Draws | A (100) | B (50) | C (250) |
|---|---|---|---|
| 20 | 20.0 % | 15.0 % | 65.0 % |
| 200 | 21.5 % | 10.0 % | 68.5 % |
| 10,000 | 24.7 % | 12.7 % | 62.6 % |
With 20 draws, the shares are rough. With 10,000 they come close to the expected values. This is the law of large numbers: lottery scheduling is fair only in the long run, and in the short run luck can give a process less than its share. Another disadvantage is that nothing guarantees an upper bound on a wait.
Lottery scheduling
Lottery scheduling is a proportional-share policy in which each process holds tickets, and at every scheduling decision a ticket is drawn at random and its owner runs next, so that the chance of running equals the process's share of all tickets.
Example: a process with 50 of 400 tickets wins a draw with probability 12.5 per cent.
Check yourself: 1. What is the expected share of a process with 30 of 120 tickets? 2. Why are 20 draws not enough to see the expected shares? 3. What is the advantage of lottery scheduling in memory use?