Lottery scheduling

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.

ee also

*Scheduling (computing)

External links

* [http://inst.eecs.berkeley.edu/~cs162/sp06/ Operating systems and systems programming] - UC Berkeley OS Class
* [http://www.usenix.org/events/usenix99/full_papers/petrou/petrou.pdf Implementing Lottery Scheduling - Matching the Specialization in Traditional Schedulers] - Paper by David Petrou et al.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Scheduling algorithm — In computer science, a scheduling algorithm is the method by which threads, processes or data flows are given access to system resources (e.g. processor time, communications bandwidth). This is usually done to load balance a system effectively or …   Wikipedia

  • Lotterie-Scheduling — ist ein Wahrscheinlichkeits Scheduling Verfahren für Prozesse in einem Betriebssystem. Prozesse bekommen alle eine bestimmte Anzahl von Losen zugewiesen und der Prozess Scheduler zieht ein Zufallslos, um den nächsten Prozess auszuwählen. Die… …   Deutsch Wikipedia

  • Multilevel feedback queue — In computer science, a multilevel feedback queue is a scheduling algorithm. It is intended to meet the following design requirements for multimode systems: Give preference to short jobs. Give preference to I/O bound processes. Separate processes… …   Wikipedia

  • WWE Raw — Format Sports entertainment Professional wrestling Created by Vince McMahon …   Wikipedia

  • Deal or No Deal (U.S. game show) — This article is about the American primetime version on NBC. For the American daily syndicated version, see Deal or No Deal (U.S. syndicated game show). Deal or No Deal Logo Created by Dick de Rijk …   Wikipedia

  • H-B Woodlawn — The H B Woodlawn Alternative Program, commonly referred to as H B, is an alternative all county public school located in Arlington County, Virginia, United States based on the liberal educational movements of the 1960s and 1970s. The school,… …   Wikipedia

  • WHDH (TV) — WHDH TV redirects here. For the first incarnation of WHDH TV on channel 5 in Boston (1957 1972), see WHDH TV (defunct). WHDH Boston, Massachusetts Branding …   Wikipedia

  • Charter school — Charter schools are primary or secondary schools that receive public money (and like other schools, may also receive private donations) but are not subject to some of the rules, regulations, and statutes that apply to other public schools in… …   Wikipedia

  • Department for Culture, Media and Sport — Department overview Formed 1997 Preceding Department Department for National Heritage Jurisdiction England (culture, sport) …   Wikipedia

  • Problem gambling — Classification and external resources ICD 10 F63.0 ICD 9 312.31 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”