- Lottery scheduling
Lottery Scheduling is a probabilistic scheduling algorithm for processes in an
operating system . Processes are each assigned some number oflottery 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 schedulingalgorithms , such asShortest job next andFair-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.
ee also
*
Scheduling (computing) External links
* [http://inst.eecs.berkeley.edu/~cs162/sp06/ Operating systems and systems programming] - UC Berkeley OS Class
* [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.
Wikimedia Foundation. 2010.