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:44, 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.

One way is to total up all the tickets in the system and assign a specific range of "winning numbers" to each thread. If you had threads A, B and C with 5, 10, 15 tickets respectively, then the total number of tickets in the system is 30. We could do a rand(30) and get a winning number. Let's say it was 7, then obviously B is the winner since A has numbers 0-4, B has numbers 5-13, and C had 14-29 etc.

See also

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