Lotterie-Scheduling

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 Aufteilung der Lose muss nicht gleich sein. Wenn man einem Prozess mehr Lose zuweist, erhöht das seine relativen Chancen, ausgewählt zu werden. Diese Technik kann man benutzen, um sich anderen Scheduling-Verfahren, wie zum Beispiel dem Shortest-Job-Next-Verfahren und dem Fair-Share-Scheduling, anzunähern.

Lotterie-Scheduling löst das Problem des Verhungerns. Wenn man jedem Prozess mindestens ein Los gibt, garantiert dies, dass es eine Wahrscheinlichkeit von über 0 % gibt, dass dieser Prozess bei der jeweils nächsten Scheduling-Operation ausgewählt wird.

Implementierung

Bei Implementierungen des Lotterie-Schedulings sollte beachtet werden, dass Milliarden Lose unter vielen Threads verteilt werden. Es ist also sehr ineffizient, ein Array aller Lose zu besitzen, in dem jedes Los mit seinem Thread verknüpft wird. Lotterie-Scheduling kann sowohl präemptiv, als auch nicht präemptiv implementiert werden.

Weblinks

• Operating systems and systems programming - UC Berkeley OS Class
• Implementing Lottery Scheduling - Matching the Specialization in Traditional Schedulers - Paper by David Petrou et al. (PDF-Datei; 234 kB)