Scheduling: Difference between revisions
(Lottery 1) |
(lottery 2) |
||
| Line 10: | Line 10: | ||
[[Image:Scheduling_1.png|thumb|300px|right|Abbildung 1: Beispiellotterie]] |
[[Image:Scheduling_1.png|thumb|300px|right|Abbildung 1: Beispiellotterie]] |
||
Dieses Scheduling Verfahren wurde 1994 von Carl A. Waldspurger entwickelt. Ihm liegt ein zufallsbasierter Ressourcen-Verteilungs-Mechanismus zugrunde, der eine einfache und doch sehr flexible Kontrolle über die relativen Ausführungsraten ermöglicht, da der Zufall über längere Sicht ja keinesfalls zufällig sondern relativ genau ist. Zur Abstraktion |
Dieses Scheduling Verfahren wurde 1994 von Carl A. Waldspurger entwickelt. Ihm liegt ein zufallsbasierter Ressourcen-Verteilungs-Mechanismus zugrunde, der eine einfache und doch sehr flexible Kontrolle über die relativen Ausführungsraten ermöglicht, da der Zufall über längere Sicht ja keinesfalls zufällig sondern relativ genau ist. Zur Abstraktion wird eine Währung eingeführt, sogenannte Lotterie Tickets. Vor jeder Ressourcenzuteilung wird eine Lotterie durchgeführt, wobei der Prozess, der das Gewinnerticket besitzt, die Ressource für ein fest definiertes Zeitquantum nutzen darf. |
||
Zum visuellen Verständnis ist rechts eine Beispiellotterie angegeben, die den Ablauf verdeutlicht. |
Zum visuellen Verständnis ist rechts eine Beispiellotterie angegeben, die den Ablauf verdeutlicht. |
||
Die Ticket Abstraktion bietet einen besonderen Vorteil, das modulare Ressourcen-Management, welches durch 4 Methoden beschrieben wird: |
|||
===Ticket Transfer=== |
|||
Der Ticket Transfer ermöglicht es Prozessen Tickets an Prozesse, von denen sie abhängig sind, abzutreten. |
|||
Angenommen in der Beispiellotterie wäre Prozess1 von Prozess3 abhängig, dann würde Prozess3 mit einer relativen Wahrscheinlichkeit von 5/10=0,5 die Ressource zugeteilt bekommen (Prozess 1 nimmt ja nicht an der Lotterie teil). Durch den Ticket Transfer könnte Prozess1 seine 10 Tickets an Prozess3 abtreten, und würde dessen Wahrscheinlichkeit auf 15/20=0,75 erhöhen. |
|||
===Ticket Inflation=== |
|||
Die Ticket Inflation ermöglicht es einem Prozess selbstständig die Anzahl seiner Tickets zu erhöhen oder zu verringern. Diese Methode setzt vorraus, dass die Prozesse untereinander nicht konkurrieren, da ansonsten jeder Prozess unendlich viele Tickets generieren würde. |
|||
Im vorherigen Beispiel könnte so Prozess3 selbst die Anzahl seiner Tickets erhöhen, ohne dass dafür eine Kommunikation zum Ticket Transfer nötig wäre. |
|||
===Ausgleichstickets=== |
|||
===Ticket Währungen=== |
|||
== Clock interrupt rate tuning == |
== Clock interrupt rate tuning == |
||
Revision as of 10:46, 24 January 2007
Diese Seite ist Teil des Seminars Advanced Operating System Principles.
Einführung
Scheduling ist generell die Zuteilung begrenzter Ressourcen auf Prozesse. Im folgenden werden 2 jüngere Methoden zur Verbesserung des Scheduling näher betrachtet. Einmal das Verfahren Lottery Scheduling, sowie das Steigern der Clock Interupt Rate. Fachbegriffe in diesem Artikel werden wenn möglich sinnvoll übersetzt.
Lottery Scheduling
Dieses Scheduling Verfahren wurde 1994 von Carl A. Waldspurger entwickelt. Ihm liegt ein zufallsbasierter Ressourcen-Verteilungs-Mechanismus zugrunde, der eine einfache und doch sehr flexible Kontrolle über die relativen Ausführungsraten ermöglicht, da der Zufall über längere Sicht ja keinesfalls zufällig sondern relativ genau ist. Zur Abstraktion wird eine Währung eingeführt, sogenannte Lotterie Tickets. Vor jeder Ressourcenzuteilung wird eine Lotterie durchgeführt, wobei der Prozess, der das Gewinnerticket besitzt, die Ressource für ein fest definiertes Zeitquantum nutzen darf.
Zum visuellen Verständnis ist rechts eine Beispiellotterie angegeben, die den Ablauf verdeutlicht.
Die Ticket Abstraktion bietet einen besonderen Vorteil, das modulare Ressourcen-Management, welches durch 4 Methoden beschrieben wird:
Ticket Transfer
Der Ticket Transfer ermöglicht es Prozessen Tickets an Prozesse, von denen sie abhängig sind, abzutreten. Angenommen in der Beispiellotterie wäre Prozess1 von Prozess3 abhängig, dann würde Prozess3 mit einer relativen Wahrscheinlichkeit von 5/10=0,5 die Ressource zugeteilt bekommen (Prozess 1 nimmt ja nicht an der Lotterie teil). Durch den Ticket Transfer könnte Prozess1 seine 10 Tickets an Prozess3 abtreten, und würde dessen Wahrscheinlichkeit auf 15/20=0,75 erhöhen.
Ticket Inflation
Die Ticket Inflation ermöglicht es einem Prozess selbstständig die Anzahl seiner Tickets zu erhöhen oder zu verringern. Diese Methode setzt vorraus, dass die Prozesse untereinander nicht konkurrieren, da ansonsten jeder Prozess unendlich viele Tickets generieren würde. Im vorherigen Beispiel könnte so Prozess3 selbst die Anzahl seiner Tickets erhöhen, ohne dass dafür eine Kommunikation zum Ticket Transfer nötig wäre.
Ausgleichstickets
Ticket Währungen
Clock interrupt rate tuning
Quellen
- Carl A. Waldspurger and William E. Weihl. Lottery Scheduling: Flexible Proportional-Share ResourceManagement. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI), pages 1–11, November 14–17 1994.
- Etsion, Yoav; Tsafrir, Dan; Freitelson, Dror G. Effects of Clock Resolution on the Scheduling of Interactive and Soft Real-time Processes. In SIGMETRICS ’03 S. 172 - 183.
- Andi Drebes Schedulingalgorithmen und Rechenzeitverteilung auf Betriebssystemebene