Lottery scheduling

Lottery scheduling is a probabilistic scheduling method for processes in an operating system. Processes all get a certain number of lots allocated and the process scheduler draws a Zufallslos to select the next process. The division of a lot must not be the same. If you assign a process more lots, which increases its relative chances of being selected. This technique can use it to get other scheduling methods, such as the shortest - job - next- method and the Fair Share Scheduling to approach.

Lottery scheduling solves the problem of starvation. If you give each process at least one lot, this guarantees that there is a probability of more than 0%, that this process is at its following scheduling operation selected.

Implementation

In implementations of the lottery - scheduling should be noted that billions lots will be distributed among many threads. So it is very inefficient to have an array of all the lots in which each lot is linked to his thread. Lottery scheduling can be implemented both preemptive as well as non- preemptively.