Lottery scheduling is a
probabilistic scheduling algorithm
In computing, scheduling is the action of assigning ''resources'' to perform ''tasks''. The ''resources'' may be processors, network links or expansion cards. The ''tasks'' may be threads, processes or data flows.
The scheduling activity is ca ...
for
processes in an
operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems schedule tasks for efficient use of the system and may also i ...
. Processes are each assigned some number of
lottery ticket
A lottery is a form of gambling that involves the drawing of numbers at random for a prize. Some governments outlaw lotteries, while others endorse it to the extent of organizing a national or state lottery. It is common to find some degree of ...
s, 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
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
, such as
Shortest job next and
Fair-share scheduling Fair-share scheduling is a scheduling algorithm for computer operating systems in which the CPU usage is equally distributed among system users or groups, as opposed to equal distribution of resources among processes.
One common method of logical ...
.
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
Lottery Scheduling: Flexible Proportional-Share Resource Managementby Carl A. Waldspurger and William E. Weihl. The 1994 Operating Systems Design and Implementation conference (OSDI '94). November, 1994. Monterey, California.
Lottery and Stride Scheduling: Flexible Proportional-Share Resource Managementby Carl A. Waldspurger. Ph.D. dissertation, Massachusetts Institute of Technology. September 1995.
Operating Systems: Three Easy Piecesby Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant chapter
Proportional-Share Scheduling
Implementing Lottery Scheduling - Matching the Specialization in Traditional Schedulers- Paper by David Petrou et al.
Stochastic priority-based task Schedulerby Robert V. Welland and Walter R. Smith. United States Patent Number US 5247677 A
{{Processor scheduling
Processor scheduling algorithms