Scheduling: Difference between revisions

From
Jump to navigation Jump to search
m (Rückreferenz)
(Lottery 1)
Line 3: Line 3:
== Einführung ==
== 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.
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 ==
== Lottery Scheduling ==


[[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 der Ressource 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.


== Clock interrupt rate tuning ==
== Clock interrupt rate tuning ==
Line 18: Line 22:
* Carl A. Waldspurger and William E. Weihl. [http://www.usenix.org/publications/library/proceedings/osdi/full_papers/waldspurger.pdf 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.
* Carl A. Waldspurger and William E. Weihl. [http://www.usenix.org/publications/library/proceedings/osdi/full_papers/waldspurger.pdf 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. [http://portal.acm.org/citation.cfm?doid=781027.781049 Effects of Clock Resolution on the Scheduling of Interactive and Soft Real-time Processes]. In SIGMETRICS ’03 S. 172 - 183.
* Etsion, Yoav; Tsafrir, Dan; Freitelson, Dror G. [http://portal.acm.org/citation.cfm?doid=781027.781049 Effects of Clock Resolution on the Scheduling of Interactive and Soft Real-time Processes]. In SIGMETRICS ’03 S. 172 - 183.
* [http://www.informatik.uni-hamburg.de/WSV/teaching/sonstiges/EwA-Folien/Drebes-Paper.pdf Andi Drebes: Schedulingalgorithmen und Rechenzeitverteilung auf Betriebssystemebene]
* Andi Drebes [http://www.informatik.uni-hamburg.de/WSV/teaching/sonstiges/EwA-Folien/Drebes-Paper.pdf Schedulingalgorithmen und Rechenzeitverteilung auf Betriebssystemebene]

Revision as of 08:03, 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

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 der Ressource 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.

Clock interrupt rate tuning

Quellen