Multimedia-Technik: Scheduling

(Prof. Dr. C. Vogt, Nachrichtentechnik, FH Köln - mit Dank an Daniel Steeg für die Erstellung dieser Visualisierung und an die Zentrale Arbeitsstelle Multimedia für die finanzielle Unterstützung)

Anleitung

Das erste hier gezeigte Java-Applet stellt zwei Prozesse mit periodischen Anforderungen (z.B. nach CPU-Zeit) dar und zeigt außerdem die dadurch verursachte Belastung des Systems an.
Periodische Anforderungen liegen bei vielen Multimedia-Anwendungen vor, wie z.B. bei der Bearbeitung eines Videostroms, dessen Frames in gleichmäßigen Abständen eintreffen. Die Kenntnis der Systemauslastung ist wichtig für die Berechnung und Durchsetzung von Dienstgüte-(Quality-of-Service-)Garantien.

Die Prozesse werden durch drei Parameter beschrieben:

Offset: Ist dieser Parameter ungleich Null, so beginnt ein Prozeß nicht mit Beginn der "Beobachtungszeit", sondern erst entsprechend später.
Man kann den Offset entweder direkt eingeben oder aber mit der Maus am Anfang (ca. die ersten 5 Pixel) des ersten Ausführungsblocks anfassen und bei gedrückter Maustaste den Block verschieben.
Breite: Dieser Parameter beschreibt die Zeitdauer, für ein einzelner Ausführungsblock Systemressourcen (z.B. Prozessorzeit) beansprucht.
Auch diesen Parameter kann man neben der direkten Eingabe auch mit der Maus verändern, indem man das Ende eines beliebigen Ausführungsblocks bei gedrückter Maustaste verschiebt.
Periode: Dies ist der zeitliche Abstand zwischen den Startzeitpunkten zweier aufeinanderfolgender Ausführungsblöcke.
Zum Verändern der Periode klickt man auf den Anfang eines beliebigen, jedoch nicht des ersten Ausführungsblocks.

Bei der direkten Eingabe der Parameterwerte in die Textfelder ist folgendes zu beachten: Die dargestellten Prozesse werden nicht direkt bei der Eingabe, sondern erst nach Betätigen der Return-Taste aktualisiert. Zudem dürfen aus Gründen der besseren Darstellung die Breite eines Ausführungsblocks und der Abstand zwischen zwei Blöcken den Wert 20 nicht unterschreiten.

Ratenmonotones Scheduling

Beim ratenmonotonen Scheduling hat jeweils der Prozeß mit der kürzeren Periode die höhere Priorität und wird somit bevorzugt behandelt.
Dabei unterscheidet man zwischen präemptivem und nicht-präemptivem Scheduling:

Beim präemptiven Scheduling wird ein laufender Prozeß unterbrochen, wenn ein Prozeß mit höherer Priorität Ressourcen beansprucht.
Beim nicht-präemptiven Scheduling muß ein Prozeß mit höherer Priorität warten, bis die gerade laufende Ausführung beendet worden ist.

Anhand des folgenden Applets kann man beobachten, welche Auswirkungen Änderungen der Prozeßparameter auf das Scheduling haben:

Man sieht insbesondere, daß bei steigender Systemauslastung die Wahrscheinlichkeit von Rückstaus steigt ("Rückstau" bedeutet, daß bei Ankunft eines Ausführungsblocks die Bearbeitung seines Vorgängers noch nicht abgeschlossen ist): Zum Beispiel werden bei Eingabe der Werte 0/20/120 für Prozeß A und 0/50/100 für Prozeß B alle Blöcke vor Ankunft ihrer Nachfolger fertig ausgefürt. Verkürzt man bei Prozeß A die Periode auf 40, so ist das nicht mehr der Fall. Bitte probieren!
Ein grundlegender Satz des Realzeit-Schedulings (Liu und Layland, 1973) besagt, daß unter präemptivem ratenmonotonem Scheduling die Systemauslastung höchstens ln(2) (also ca. 69%) betragen darf, um solche Rückstaus sicher ausschließen zu können.

Deadline-basiertes Scheduling

Beim Deadline-basierten Scheduling hat jeder Prozeß fest vorgegebene Zeitpunkte, die sogenannten "Deadlines", zu denen die Bearbeitungen seiner einzelnen Ausführungsblöcke jeweils abgeschlossen sein müssen. Bei bestimmten Anwendungen, insbesondere im Bereich Multimedia, ist das Ergebnis eines Prozesses möglicherweise nicht mehr zu gebrauchen, wenn es zu spät eintrifft. Das Scheduling muß darauf achten, daß keine Verletzung der Deadlines auftritt.

Das dritte Applet zeigt das präemptive Deadline-basierte Scheduling im direkten Vergleich mit dem ratenmonotonen Scheduling. Die Deadlines werden durch senkrechte Striche dargestellt, die man außer durch die direkte Eingabe auch durch Klicken und Ziehen mit der Maus an den kleinen Fähnchen verändern kann (Bei der direkten Eingabe werden keine Deadlines akzeptiert, die nach Ankunft des nächsten Blocks liegen):

Der oben erwähnte Satz von Liu und Layland besagt, daß bei nichtpräemptivem Deadline-basiertem Scheduling die Systemauslastung bis zu 100% betragen kann, ohne daß es zu Rückstaus kommt. Anders formuliert, werden unter dieser Bedingung Deadlines, die mit dem Ankunftszeitpunkt des nächsten Ausführungsblocks zusammenfallen, sicher eingehalten. In dieser Hinsicht ist also Deadline-basiertes Scheduling leistungsfähiger als ratenmonotones. Man sieht dies beispielsweise durch Eingabe der Werte 0/20/40/40 für Prozeß A und 0/50/100/100 für Prozeß B - bitte probieren!