Review II: done.

Link check Warning (ps)

Acronyme, Absätze und Wordanführungszeichen done.

Review Prof. Kosch eingearbeitet.

Formel done.

Unbekannte Characters ausgebessert.

Formeln inline gestellt.

Eine Fallstudie - IRS

1

Auto

• Integrated Real-Time Resource Scheduling (IRS445)
• Multimedia Applikation am Server
  • Besteht aus voneinander abhängigen Aufgaben
  • Jede Aufgabe ist an eine bestimmte Ressource gebunden
  • Aufgabensequenzen wiederholen sich während der Laufzeit der Applikation
  • Eine Applikation nimmt Zeit aus einer bestimmten Periode p

Auto PC

Auto PDA_Phone

2

Auto

Einleitung zu IRS445:

Auto PC

Auto PDA_Phone

Auto

Eine Multimedia Applikation auf einem Server besteht in der Regel aus verschiedenen voneinander abhängigen Aufgaben, wobei jede dieser Aufgaben an eine bestimmte Ressource gebunden ist. Gewisse Abfolgen solcher Aufgaben wiederholen sich während der Laufzeit einer Applikation am Server. Anhand der Abfolge der Aufgaben, welche jeweils eine bestimmte Periode p an Zeit benötigen, kann man einen Abhängigkeitsgraph dieser erstellen (siehe obige Abbildung). Aufgabe1 ist eine Leseoperation von der Platte, welche ein Videoframe aus der lokalen Festplatte ausliest. Dieses Frame wird dann am Bildschirm dargestellt (Aufgabe2) und über das Netzwerk zu einem Benutzer übertragen (Aufgabe3).

Um nun die Echtzeitbearbeitung von Applikationen, welche wie oben erklärt Zugang zu mehreren Ressourcen erfordern, garantieren zu können, wurde das Integrated Real-Time Resource Scheduling (IRS445) an der Stony Brook University in New York entwickelt. Die wichtigste Komponente von IRS445 ist ein neuer Multi-Ressource-Alloziierungs- und Deadline-Zuteilungs-Algorithmus, DSSCAN genannt.

Koordiniertes Scheduling mehrerer Ressourcen

1

Auto

• Der Anwendungsprogrammierer muss folgendes spezialisieren:
  • Anforderungen an jede Ressource
    • Anzahl an Bytes für Übertragung, Jitter für Berechnungen
  • Aufgaben-Prioritäts-Graph (TPG446)
• Unter diesen Bedingungen werden vom IRS445 Framework
  • Heterogene Ressourcen alloziiert
  • Das Verzögerungsbudget (Deadline pro Periode) für die Aufgaben berechnet
  • Zugangskontrolle wird durchgeführt
  • Wenn möglich, Lockerung des Verzögerungsbudgets um Ressourcennutzung auszugleichen
  • Erlaubt den lokalen Schedulern erwünschte Metriken zu definieren
    • Z.B. der Plattenscheduler kann Anfragen in SCAN-Ordnung vorziehen

2

Auto

Um das koordinierte Scheduling mehrerer Ressourcen in IRS445 zu ermöglichen, muss der Anwendungsprogrammierer die Anforderungen an jede Ressource (Anzahl der Bytes für Übertragung, etc.) spezifizieren und einen Aufgaben-Prioritäts-Graph (TPG446) erstellen. Ein TPG446 ist ein gerichteter azyklischer Graph zwischen den verschiedenen Aufgaben einer Applikation. Jede Aufgabe in diesem Graph steht in Beziehung zu einer speziellen Ressource, die Kanten des Graphen repräsentieren die Prioritätsordnung der verschiedenen Aufgaben.

Mithilfe dieser Angaben ist das IRS445 Framework in der Lage heterogene Ressourcen zu alloziieren und das Verzögerungsbudget (Deadline pro Periode) für jede Aufgabe zu berechnen. Sämtliche Aufgaben eines TPG446 müssen allerdings innerhalb einer Periode beendet werden. Auch die Zugangskontrolle, bei welcher überprüft wird ob die Anforderungen einer Applikation rechtzeitig befriedigt werden können und die Ressourcen reserviert werden, ist Aufgabe des IRS445-Frameworks.

Ist die gegenwärtige Verfügbarkeit der Ressourcen im System bekannt, so alloziiert IRS445 die ungenutzte Ressource-Kapazität für die Aufgaben des TPG446 und berechnet das minimale Verzögerungsbudget, das benötigt wird um jede Aufgabe fertig zu stellen. Diese minimalen Verzögerungsbudgets werden dann durch die Zuteilung der verfügbaren Flauten im Verzögerungsbudget des TGP der Auslastung der einzelnen Ressourcen entsprechend gelockert. Dieser Lockerungsprozess stoppt bei optimaler Ressourcen-Alloziierung, wobei der TGP in der Lage sein muss, seine periodischen Deadlines einzuhalten. Der Lockerungsalgorithmus hat, durch die Ausgleichung der Nutzung der verschiedenen Ressourcen den Zweck, dass langfristig mehr Echtzeit-Applikationen vom System zugelassen werden.

IRS445 unterstützt eine zwei-Level Echtzeit-Scheduler Architektur, welche sich aus einem globalen Scheduler und einer Anzahl von lokalen Schedulern, die sich jeweils auf eine bestimmte Ressource beziehen, zusammensetzt. Dem globalen Scheduler sind alle TPG446's und die Anforderungen an die Ressourcen bekannt. Er hat die Aufgabe sicherzustellen, dass alle Aufgaben befriedigt werden können, bevor er sie in den Anfrage-Queue der betreffenden Ressource platziert. Die lokalen Scheduler verwalten bestimmte Ressourcen und treffen ihre Scheduling-Entscheidungen anhand der Deadlines der Aufgaben und der Auslastung der Ressourcen. Welche Scheduling Strategie sie verwenden ist ihnen freigestellt. Der globale Scheduler fungiert mithilfe seines Wissens über die ganze Applikation somit als Verwaltungsstelle für die lokalen Scheduler.

Aufgaben-Deadline Definition

1

Auto

• Basisbegriffe
  • Aufwand (z.B. Mbit), Verzögerungsbudget (sec), Kapazität (Mb/s)
• Minimales Verzögerungsbudget () einer Aufgabe welche eine Resource pro Periode benutzt:
  • Benötigter Aufwand /verfügbare Kapazität der Ressource
    (= maximale Kapazität -benötigte Kapazitäten)
• Zugangskontrolle für eine Anwendung
  • LNi sind erfüllbar
• Lockerung der Deadlines um Ressourcenauslastung zu balancieren
• Wenn die Periode länger ist: freier Raum verfügbar
• Verteile die verbleibenden Ressource-Kapazitäten entweder
  • gleichmäßig, oder
  • Im Verhältnis zum erwarteten Bedarf

2

Auto

Grundlegende Begriffe des IRS445-Framework sind der Aufwand, das Verzögerungsbudget und die Kapazität. Der Aufwand, in Mbit gemessen, bezeichnet die Anforderung einer Aufgabe an eine bestimmte Ressource. Die Deadline einer Aufgabe für eine Periode in Sekunden wird als Verzögerungsbudget bezeichnet. Die Kapazität bezieht sich auf die Leistungsfähigkeit einer Ressource und wird in Mb/s angegeben.
Die Ende-zu-Ende Verzögerungsspezifikation des TPG446's einer Applikation wird bei IRS445 von einem Multi-Ressource Alloziierungs-Algorithmus in aufgabenspezifische Verzögerungsbudgets aufgeteilt. Jede Aufgabe im TPG446 erhält eine Auslastungsspezifikation (benötigter Aufwand) für eine Ressource . Das minimal mögliche Verzögerungsbudget wird wie folgt berechnet:

wobei R_Ni die verfügbare Kapazität der Ressource bezeichnet.
Wie schon vorhin erwähnt erfüllt IRS445 auch die Aufgabe der Zugangskontrolle. Eine Anwendung kann bearbeitet werden wenn alle minimalen Verzögerungsbudgets erfüllbar sind und die Summe dieser Verzögerungsbudgets nicht größer als die Periode der Anwendung N ist.
Mithilfe des Lockerungsalgorithmus, der in der vorhergehenden Folie bereits erklärt wurde, ist es möglich die Ressourcenauslastung möglichst optimal zu balancieren. Die verbleibenden Ressourcen-Kapazitäten können entweder gleichmäßig auf alle Aufgaben oder im Verhältnis zum erwarteten Bedarf verteilt werden.

Deadline sensibler SCAN (DSSCAN)

1

Auto

• Vereinigt SCAN und EDF439
• Zwei Queues
  1. Geordnet nach Start-Deadline
  2. Geordnet nach SCAN-Ordnung
• DSSCAN Algorithmus
  1. Wähle erste Anfrage aus der Start-Deadline Queue (EDF439 Queue)
  2. Wähle erste Anfrage aus der SCAN Queue
  3. Schedule den 2., außer die Deadline des 1. würde überschritten
  4. Rearrangiere die SCAN Queue wenn Queue 1. gewählt wurde
• Kann um eine 3. Queue für interaktive I/O erweitert werden
  • Wird schnell bedient (vor 2.), aber ohne die Deadline zu überschreiten

2

Auto

IRS445 zeichnet sich durch einen dynamischen Echtzeit-Scheduler, Deadline sensibler SCAN (DSSCAN), aus, welcher eine Vereinigung von SCAN und EDF439 darstellt. Er versucht, die Platten I/O-Anfragen in SCAN Ordnung zu erledigen, ohne allerdings die Deadlines dieser Anfragen zu überschreiten. DSSCAN kennt keinen fixen Service-Zyklus, somit ist mittels DSSCAN das Scheduling sowohl von periodischen und nicht-periodischen Echtzeit-Anfragen, als auch für Best-Effort Anfragen möglich.

Der Algorithmus arbeitet mit zwei Queues. Die erste ist nach der Start-Deadline geordnet, die zweite nach der SCAN-Ordnung. Die Start-Deadline stellt den spätesten Zeitpunkt dar, zu der eine Echtzeitanfrage eingeplant werden muss um die gesamte Deadline einer solchen Anfrage einzuhalten, selbst unter Annahme der Worst-case Servicezeit.

Der Algorithmus wählt jeweils die erste Anfrage aus der Start-Deadline Queue (EDF439 Queue) und der SCAN Queue. Wenn es sich hierbei um zwei verschiedene Anfragen handelt, so wird die Anfrage aus der SCAN Queue bearbeitet, sofern dadurch nicht die Deadline der Anfrage aus der EDF439-Queue überschritten wird. Nun wird die bearbeitete Anfrage aus allen Queues gelöscht, in der sie sich befunden hat, und die SCAN Queue wird, sofern notwendig, neu geordnet.

Dieser Algorithmus kann auch um eine dritte Queue erweitert werden, die interaktive I/O, also VCR-Kontrolloperationen, berücksichtigt. Wenn diese zusätzliche Queue existiert, so wird, sofern diese gefüllt ist, die Anfrage aus dieser Queue zuerst bedient. Das natürlich nur in dem Fall, dass dadurch die Deadline der Anfrage in der Start-Deadline Queue nicht überschritten wird.

IRS Implementations Architektur

1

Auto PC

Auto PDA_Phone

2

Auto PC

Auto PDA_Phone

Auto

Obige Abbildung zeigt die Software-Architektur von IRS445. Durch eine einmalige Zugangskontrolle werden die Ressourcen reserviert. Der Ressourcenbenützungsmonitor beobachtet und überwacht den Ressourcenkonsum der einzelnen Aufgaben. Es ist möglich, dass eine einfache lese/schreibe Aufgabe Anfragen zum Lesen und Schreiben an verschiedene Datenblöcke auf der Platte stellt. In traditionellen Betriebssystemen kann ein Prozess, der solche synchronen Plattenzugriffe erfordert, in jedem Durchlauf nur jeweils einen Plattenzugriff tätigen. Daraus ergeben sich signifikante Kontextwechsel- und Plattenscheduling-Überläufe. Für Echtzeit-Anfragen ist das allerdings unpassend. Um eine Optimierung zu erreichen, werden die Dateisystem lese/schreibe Routinen so modifiziert, dass sämtliche zusammengehörige lese/schreibe Operationen eines Prozesses als eine solche Operation durchgeführt werden, bevor dieser Prozess blockiert. Diese Optimierung ist allerdings nicht unbedingt notwendig, damit IRS445 funktioniert.

Der globale Scheduler hat Überblick über alle TGP's der bearbeiteten Applikationen und über die Kapazität der vorhandenen Ressourcen. Mit diesem Wissen ist er in der Lage, die darunterliegenden lokalen Scheduler für die einzelnen Ressourcen so anzuweisen, dass alle Aufgaben ohne Konflikte bearbeitet werden können.

Bibliographie

2

Auto

CG

CG02