Lottery scheduling is a

probabilistic Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...

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 carried out by ...

for processes in an

operating system An operating system (OS) is system software that manages computer hardware and software resources, and provides common daemon (computing), services for computer programs. Time-sharing operating systems scheduler (computing), schedule tasks for ...

. Processes are each assigned some number of

lottery ticket A lottery (or lotto) 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 som ...

s, and the

scheduler A schedule (, ) or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things ...

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 mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for per ...

, such as Shortest job next and Fair-share scheduling. Lottery scheduling solves the problem of

starvation Starvation is a severe deficiency in caloric energy intake, below the level needed to maintain an organism's life. It is the most extreme form of malnutrition. In humans, prolonged starvation can cause permanent organ damage and eventually, de ...

. 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 An array is a systematic arrangement of similar objects, usually in rows and columns. Things called an array include: {{TOC right Music * In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...

where each

index Index (: indexes or indices) may refer to: Arts, entertainment, and media Fictional entities * Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index'' * The Index, an item on the Halo Array in the ...

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 Management
by 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 Management
by Carl A. Waldspurger. Ph.D. dissertation, Massachusetts Institute of Technology. September 1995.
Operating Systems: Three Easy Pieces
by 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 Scheduler
by Robert V. Welland and Walter R. Smith. United States Patent Number US 5247677 A {{Processor scheduling Processor scheduling algorithms