Jump to content

Lottery scheduling

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 136.152.170.206 (talk) at 14:49, 14 March 2006 (→Implementation). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Lottery Scheduling is a scheduling algorithm for processes in an operating system, and is a specialized implementation of priority scheduling.

Lottery scheduling solves the problem of starvation, so that all threads waiting on the queue can occupy some CPU time. The problem is solved by giving each process at least one lottery ticket, and holding a lottery whenever a context switch to another thread is needed. The lottery will select a ticket from among the pool of lottery tickets held by the threads.

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 tickets with each ticket corresponding to a thread would be highly inefficient.

See also

Retrieved from "https://en.wikipedia.org/w/index.php?title=Lottery_scheduling&oldid=43734659"