CSE Roadmap

Core tier · about 5 hours · 7 parts

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?