Lottery scheduling
Lottery scheduling is a probabilistic scheduling algorithm for processes in an operating system. Processes are each assigned some number of lottery tickets, and the scheduler draws a random ticket to select the next process. The distribution of tickets need not be uniform; granting a process more tickets provides it a relative higher chance of selection. This technique can be used to approximate other scheduling algorithms, such as
Shortest job next and Fair-share scheduling.
Lottery scheduling solves the problem of starvation. Giving each process at least one lottery ticket guarantees that it has non-zero probability of being selected at each scheduling operation.
Implementation
Implementations of lottery scheduling should take into consideration that there could be billions of tickets distributed among a large pool of threads. To have an array where each index represents a ticket, and each location contains the thread corresponding to that ticket, may be highly inefficient. Lottery scheduling can be preemptive or non-preemptive.
External links
- [https://www.usenix.org/legacy/publications/library/proceedings/osdi/full_papers/waldspurger.pdf Lottery Scheduling: Flexible Proportional-Share Resource Management] by Carl A. Waldspurger and William E. Weihl. The 1994 Operating Systems Design and Implementation conference (OSDI '94). November, 1994. Monterey, California.
- [http://www.waldspurger.org/carl/papers/phd-mit-tr667.pdf Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management] by Carl A. Waldspurger. Ph.D. dissertation, Massachusetts Institute of Technology. September 1995.
- [http://www.cs.wisc.edu/~remzi/OSTEP Operating Systems: Three Easy Pieces] by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant chapter: [http://www.cs.wisc.edu/~remzi/OSTEP/cpu-sched-lottery.pdf Proportional-Share Scheduling].
- [http://www.usenix.org/events/usenix99/full_papers/petrou/petrou.pdf Implementing Lottery Scheduling - Matching the Specialization in Traditional Schedulers] - Paper by David Petrou et al.
- [https://patents.google.com/patent/US5247677 Stochastic priority-based task Scheduler] by Robert V. Welland and Walter R. Smith. United States Patent Number US 5247677 A
{{Processor scheduling}}