Lottery scheduling

from Wikipedia, the free encyclopedia

Lottery scheduling is a probability - scheduling process for processes in an operating system . Processes are all assigned a certain number of lots and the process scheduler draws a random lot to select the next process. The division of the lots does not have to be the same. Assigning more lots to a process increases its relative chances of being selected. This technique can be used to approximate other scheduling methods, such as the shortest job next method and fair share scheduling .

Lottery scheduling solves the problem of starvation. Giving each process at least one lot guarantees that there is a greater than 0% probability that that process will be selected for the next scheduling operation.


When implementing lottery scheduling, it should be noted that billions of tickets are distributed among many threads. So it is very inefficient to have an array of all lots with each lot linked to its thread. Lottery scheduling can be implemented both preemptively and non-preemptively.

Web links