Lottery scheduling

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.

gollark: They also can't use the full intensity of light around midday.
gollark: Efficiency: that's, if I remember right, input light to stored carbohydrate efficiency.
gollark: Reflecting input light: well, they're green and not black.
gollark: Yes.
gollark: They *do* self-replicate, but there are no good manuals and they're really hard to repair.

See also
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.