Lottery scheduling

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 24.196.83.146 (talk) at 02:00, 9 March 2014 (Added external link to original paper; added link to free online book with chapter on subject; removed link to UC Berkeley class which is not a stable source of information. Some debate about whether to remove Petrou paper as it is not well known.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

See also

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Lottery_scheduling&oldid=598781694"