Lottery Scheduling (Los-Scheduling) ist ein proportional-faires Scheduling-Verfahren, das Ressourcenanteile über ein Losverfahren verteilt. Jeder Prozess erhält so viele Tickets, wie ihm CPU-Anteil zusteht – ein Prozess mit doppelt so vielen Tickets bekommt im Mittel doppelt so viel Rechenzeit. Entwickelt wurde es von Carl Waldspurger und William Weihl am MIT (1994). Es zählt zu den Scheduling-Policies für proportionale Ressourcenverteilung.
\nSo funktioniert es
\nBei jeder Scheduling-Entscheidung zieht der Scheduler zufällig ein Ticket aus allen ausgegebenen Tickets; der Besitzer des Tickets läuft als Nächstes. Kurzfristig ist die Zuteilung zufällig und ungenau, langfristig konvergiert sie gegen den gewünschten Anteil. Das Verfahren ist einfach, robust und unterstützt flexible Mechanismen: Per Ticket-Transfer kann ein Prozess seine Tickets einem anderen geben (etwa bei Client-Server-Kommunikation), per Ticket-Inflation kann ein Prozess seine Anteile selbst erhöhen.
\nEinordnung
\nLottery Scheduling ist ein dynamisches Verfahren wie das Deadline Scheduling mit EDF – nur dass die Auswahl per Zufall statt nach Fristen erfolgt. Die deterministische Alternative gleicher Autoren ist das Stride Scheduling, das ohne Zufall exakte Anteile garantiert. Moderne Linux-Scheduler wie CFS/EEVDF verwenden ähnliche Gewichtungsideen, aber kein Losverfahren; Lottery Scheduling blieb vor allem ein wichtiges Forschungsergebnis. Auf parallelen Systemen lässt sich die Ticket-Idee mit Verfahren kombinieren, die Thread-Gruppen gemeinsam einplanen – siehe Gang Scheduling.
\nVerwandte Grundlagen: Prioritätswarteschlange, Algorithmus.