Aufgabe: Multi-Level-Queue-Scheduler

Übersicht

Einleitung

Periodische und nicht-periodische Ereignisse

Wie in der Einleitung zu Aufgabe 3 bereits erwähnt, gibt es neben Ereignissen, die regelmäßig und periodisch bearbeitet werden, auch Ereignisse, bei denen eine solche Art und Weise der Behandlung nicht adäquat ist. Solche Ereignisse treten oft in unregelmäßigen Abständen auf, von ihnen ist in den meisten Fällen nur die minimale Zwischenankunftszeit bekannt, ein Muster der Auftreten kennt man aber so gut wie nie. Angezeigt werden diese Ereignisse oft durch asynchrone Unterbrechungen an die CPU. In der Ereignisbehandlung werden anschließend abhängig vom jeweiligen Ereignis gewisse Eingabedaten in Ausgabedaten transformiert. Auch die Änderung des Zustands des Systems ist denkbar, die aus Regelkreisläufen bekannte Rückkoppplung fehlt aber oft.

Beispiele für Systeme, die Ereignisse nach diesem Schema behandeln, sind eben Systeme, die vor allem auf Benutzereingaben reagieren, wie ein elektronischer Bremsassistent oder eine Airbag-Steuerung. Im Zusammenhang mit Aufgabe 3 wurde ebenfalls erwähnt, dass sich nicht-periodische Ereignisse nur schwer auf periodische Ablaufpläne abbilden lassen, weshalb man für solche Ereignisse oft auch ein anderes Behandlungsschema verwendet. Man spricht hier nicht mehr von einem zeitgesteuerten sondern von einem ereignisgesteuerten System. Das System pollt dabei keine Eregnisse mehr, sondern reagiert auf eintretende Ereignisse, selbstverständlich auch hier unter der Einhaltung von Zeitbeschränkungen.

Prioritätensteuerung

Die Ablaufplanung findet in ereignisgesteuerten Systemen im Gegensatz zu zeitgesteuerten Systemen typischerweise zur Laufzeit statt. Die verschiedenen Bestandteile der Ereignisbehandlungen (also Fäden etc.) werden auf Prioritäten abgebildet, anhand deren zur Laufzeit entschieden wird, welcher Faden als nächstes eingelastet wird.

Die Zuteilung der Prioritäten kann dabei statisch von der Laufzeit entkoppelt oder dynamisch zur Laufzeit erfolgen. Das hängt vom jeweils verwendeten Verfahren ab, das man für die Prioritätenzuteilung verwendet. Der EDF-Algorithmus (Earliest Deadline First) beispielsweise ordnet den Ereignisbehandlungen zur Laufzeit Prioritäten zu, während dies bei RMA bzw. DMA (Rate bzw. Deadline Monotonic Approach) statisch vor der Laufzeit geschieht.

Verdrängbarkeit

Ein wesentliches Merkmal eines solchen ereignisgesteuerten Schedulers ist Verdrängbarkeit. Unter Verdrängbarkeit versteht man wann und unter welchen Umständen dem gerade laufenden Faden der Prozessor entzogen werden kann. Hauptsächlich unterscheidet man hier zwischen voll präemptiven, präemptiven, nicht präemptiven und gemischt päemptiven Systemen. Bei voll präemptiven Systemen wird einem Faden der Prozessor entzogen, sobald ein anderer Faden mit einer höheren Priorität lauffähig wird, bei nicht präemptiven erfolgt ein solcher Kontextwechsel dagegen nur dann, wenn ein Faden explizit auf den Prozessor verzichtet (z.B. weil er sich beendet oder beim Belegen eines Mutex blockiert). Ein präemptives System liegt vor, wenn das Betriebssystem dem gegenwärtig laufenden Faden zwar den Prozessor entziehen kann, dies aber nicht unbedingt immer dann tut, wenn ein Faden mit höherer Priorität laufbereit wird. Präemptive Systeme bilden also Zwischenstufen zwischen voll präemptiven und nicht präemptiven Systemen. Von gemischt präemptiven System spricht man, wenn sowohl Fäden existieren, die sich präemptiv verhalten, als auch solche, die sich nicht präemptiv verhalten. Der in der obenstehenden Grafik abgebildetete Ablauf der verschiedenen Fäden kann z.B. von einem voll präemptiv oder einem gemischt präemptiv arbeitenden Scheduler erzeugt worden sein.

Vorteile

ereignisgesteuerter Systeme sind unter anderem

• adäquate Unterstützung nicht periodischer Ereignisse
• kommen oft ohne a-priori Wissen über die Anwendung aus
• kommen oft ohne Polling aus
• flexibel
• "einfacher" zu programmieren??? (aus Sicht des Anwendungsentewicklers)
• ...

Nachteile

ereignisgesteuerter Systeme sind unter anderem

• komplexere Implementierung (aus Sicht des Systementewicklers)
• erhöhter Laufzeitbedarf, Einplanung erfolgt zur Laufzeit
• Fadensynchronisation notwendig
• ...

Was ist zu tun?

In dieser Aufgabe soll ein prioritätengesteuerter Scheduler implementiert werden, dieser Scheduler soll folgende Eigenschaften besitzen:

• der Scheduler verfügt über eine oder mehrere Prioritätsstufen
• die Prioritäten der Fäden wird a-priori statisch festgelegt
• der Scheduler kann mit mehreren Fäden umgehen, die die gleiche Priorität besitzen
• die Fäden sollen mehrmals aktivierbar sein
• der Scheduler arbeitet grundsätzlich voll präemptiv
• der Scheduler muss die Aktivierungsreihenfolge der Fäden nicht erhalten

Thread

Eine scheduler-spezifische Implementierung eines Threads.

Idle_Thread

Dieser Faden wird immer dann ausgeführt, wenn kein andere Faden aktiv ist. Die einzige Aktion dieses Fadens ist es, in einer Endlosschleife, die Kontrolle über den Prozessor abzugeben.

Thread_Queue< MAX_PRIO >

Diese Klasse ist für die Verwaltung der laufbereiten Fäden zuständig. Sie ist aus ähnlichen Gründen als C++-Template realisiert, wie die Klasse Schedule_Table< SIZE > in Aufgabe 2. Prinzipiell soll die Klasse Thread_Queue< MAX_PRIO > verschieden viele Prioritätsebenen unterstützen, in Ermanglung einer dynamischen Speicherverwaltung muss die Anzahl der Prioritätsebenen aber statisch bekannt gemacht werden. Die Implementierung der Thread_Queue ist vom eigentlichen Scheduler entkoppelt, weil z.B. für einen Scheduler, der nur einen Faden pro Priorität unterstützt, eine einfachere Thread_Queue ausreicht, soll der Scheduler zusätzlich die Reihenfolge der Fadenaktivierungen erhalten, ist wieder eine andere Thread_Queue notwendig. Im Idealfall muss nur noch die Implementierung der Thread_Queue ausgetauscht werden.

Multi_Level_Queue_Scheduler

Die Klasse Multi_Level_Queue_Scheduler implementiert den eigentlich Scheduler, der zur Verwaltung der laufbereiten Fäden auf die Klasse Thread_Queue< MAX_PRIO > zurückgreift. Im Gegensatz zur Aufgabe 2 entällt hier aber die Indirektionsstufe über eine abstrakte Klasse Abstract_Thread_Queue. Der Grund hierfür ist, dass eine Anwendung eine Menge von vorab bekannten Fäden umfasst, die alle vorab bestimmte, statische Prioritäten besitzen. Es existiert also einfach kein Grund die Anzahl der unterstützten Prioritäten zur Laufzeit ändern zu wollen.

Guarded_Multi_Level_Queue_Scheduler

Diese Klasse stellt die gegen Unterbrechungen geschützte Anwendungssschnittstelle für den Scheduler bereit.

Eine genauere Beschreibung der jeweiligen Klassen und der zu implementierenden Schnittstellen, findet man in der Doxygen-Dokumentation von EZ-Stubs.

Hinweise

Ähnlich wie mit Aufgabe 2 beginnt in dieser Aufgabe ein neuer Zweig im EZStubs-Repository. In dieser und den folgenden Aufgaben wird nämlich ein ereignisgesteuerte Variante des EZStubs-Betriebssystems entwickelt. Wir gehen dafür aber nicht vom aktuellen Zweig der Entwicklungs aus, sondern vom Stand der Aufgabe 1. Dafür geht man folgendermaßen vor:

1. Das Verzeichnis trunk des Repositories auschecken, darin sollte sich noch der Stand der Aufgabe 1 befinden.
2. Wie in Aufgabe 2 einen neuen Branch anlegen, der dieses Mal event_triggered heißen soll.
3. Auf diesen Branch wechseln.
4. Die Vorgabe in das Arbeitsverzeichnis kopieren und zum Repository hinzufügen.
5. Nicht vergessen, die Dateien guard_leave_no_scheduler.cc und main_no_scheduler.cc aus diesem Branch und entsprechende evtl. vorhandene Objektdateien aus der Bibliothek zu entfernen.