Lottery Scheduling: Flexible Proportional-Share Resource Management
Carl A. Waldspurger and William E. Weihl
I implemented lottery scheduling in my CS162 project. Lottery scheduling is a really simple and elegant idea. The ability to support a great deal of threads created a need for a better proportional-share/priority scheduling algorithm. Lottery scheduling works as follows: give each job some number of lottery tickets, on each time slice randomly pick a winning ticket, CPU time is proportional to number of tickets given to each job (on average). Lottery scheduling is probabilistically fair and behaves gracefully as load changes. Increasing the number of tickets also reduces the mean waiting times for each thread and gets closer to ideal fairness. There is even a form of priority donation that is accomplished by transferring a number of tickets to a client that that is blocking. The lottery scheduling mechanism achieves this fairness with relatively little overhead. A tree based lottery only needs to generate a random number and perform log(n) additions and comparisons to select a winner among n clients. Lotteries can also be used to manage many diverse resources: processor time, I/O bandwidth, and access locks. Lottery scheduling can even be used for scheduling communication resources.
Analysis: Lottery scheduling offers probabilistic guarantees for throughput and response time. This results in increased expected error (variability) in as the number of allocations increases. The Lottery Scheduling authors responded with Stride Scheduling to limit the variability and make the error independent of the number of allocations. Stride scheduling still uses tickets to determine proportional throughput among clients.