Aufgabe: Offline-Scheduler
Übersicht
Einleitung
Was ist zu tun?
Hinweise
Ein ScheduleTable-Scheduler, wie er in der vorhergehenden Übungsaufgabe entwickelt wurde, arbeitet nur einen vorgegebenen Zeitplan ab, indem er an bestimmten Zeitpunkten bestimmte Threads startet, er besitzt jedoch kein Wissen darüber, wie ein solcher Zeitplan erzeugt wird. Meistens erzeugt man solche Zeitppläne mit Hilfe von externen Werkzeugen vor der Laufzeit der eigentlich Anwendung (offline-scheduling oder pre-runtime scheduling).
Aus der Analyse eines (zu steuernden) Systems ergeben sich verschiedene Aufgaben, die periodisch ausgeführt werden müssen. Diese Aufgaben dienen als Eingabe für den Offline-Scheduler, er erzeugt daraus eine Tabelle, die angibt, wann welche Aufgabe bearbeitet werden soll.
Einige Vorteile:
- Der eigentlich Ablaufplan muss nicht zur Laufzeit berechnet werden, der eigentliche Scheduler wird dadurch sehr einfach gehalten (s. Aufgabe ScheduleTable).
- Solche Systeme sind einfach analysierbar.
- Kein Synchronisationsaufwand, der Ablaufplan kann so konstruiert werden, dass in kritischen Abschnitten der gegenseite Ausschluß gewährleistet ist.
- Overhead durch Kommunikation und Kontextwechsel kann a priori minimiert werden.
- ...
Einige Nachteile:
- Nicht alle Aktivitäten in einem System sind wirklich periodisch, d.h. solche Aktivitäten können schwer effizient auf einen periodischen Ablaufplan abgebildet werden.
- Statisch vorberechnete Ablaufpläne eignen sich nur bedingt für dynamisch rekonfigurierbare Systeme.
- ...
In dieser Aufgabe soll ein Werkzeug entwickelt werden, das aus einer Menge von Aufgaben einen fertigen Ablaufplan erzeugt, der vom ScheduleTable-Scheduler abgearbeitet werden kann. Die Programmiersprache, die für die Erstellung des Programms verwendet wird, sollte C++, C, Java, Perl, Phyton oder Shell-Script sein. Das fertige Programm ist unter Linux lauffähig und gehorcht folgender Aufrufsyntax:
generate_schedule <name>.sched
Ergebnis des Programms ist eine Header-Datei <name>.h, die sich im selben Verzeichnis befindet, wie die Datei <name>.sched.
Aufbau der Datei <name>.sched
Die Datei <name>.sched enthält eine Beschreibung der Ablaufpläne in folgender Form:
SCHEDULE < schedule_1 > {
TASK < task1 > {
PHASE = < val_phase >;
PERIOD = < val_period >;
EXEC_TIME = < val_exec_time >;
DEADLINE = < val_deadline >;
};
TASK < task2 > {
...
};
};
SCHEDULE < schedule_2 > {
...
};
Schlüsselwort SCHEDULE
Aus einem mit dem Schlüsselwort SCHEDULE eingeleiteten Block wird eine ScheduleTable erzeugt, die die Aufgaben abarbeitet, die in diesem Block aufgelistet sind. < schedule_1 > ist der Bezeichner der ScheduleTable und ist ein in C gültiger Variablenname. Ein mit SCHEDULE eingeleiteter Block enthält eine oder mehrere Aufgaben. Eine <name>.sched-Datei enthält einen oder mehrere mit SCHEDULE eingeleitete Blöcke.
Schlüsselwort TASK
Ein mit dem Schlüsselwort TASK eingeleiteter Block beschreibt eine Aufgabe. < task1 > ist der Bezeichner der Aufgabe und ein in C gültiger Variablenname. Der Bezeichner einer Aufgabe entspricht direkt einem Thread-Objekt in der späteren Applikation, Aufgaben werden also eineindeutig auf Threads abgebildet. Eine Aufgabe darf nur innerhalb eines mit SCHEDULE eingeleiteten Blocks definiert werden. Ein mit SCHEDULE eingeleiteter Block darf nicht zwei oder mehr Aufgaben mit demselben Bezeichner enthalten. Verschiedene mit SCHEDULE eingeleitete Blöcke dürfen Aufgaben mit denselben Bezeichnern enthalten. Eine Aufgabe hat vier Attribute mit den folgenden Bedeutungen:
| Name |
Beschreibung |
Einheit |
PHASE |
Der Versatz der einzelnen Aufgaben untereinander |
Zeit in Mikrosekunden |
PERIOD |
Die Periode, mit der eine Aufgabe wiederholt ausgeführt wird |
Zeit in Mikrosekunden |
EXEC_TIME |
Die Worst-Case-Execution-Time (WCET), die benötigt wird, um die Aufgabe abzuarbeiten |
Zeit in Mikrosekunden |
DEADLINE |
Die Zeitschranke bis zu der die Aufgabe relativ zu ihrem Startzeitpunkt abgearbeitet sein muss |
Zeit in Mikrosekunden |
Aufbau der Datei <name>.h
Die erzeugte Datei ist eine gewöhnliche Header-Datei, die für jeden SCHEDULE-Block der Datei <name>.sched zwei Makro-Definition enthält:
| Makro-Name |
Beschreibung |
DECLARE_SCHEDULE_TABLE_<schedule_identifier>(TOS) |
Dieses Makro wird verwendet, um für die ScheduleTable mit dem Bezeichner <schedule_identifier> in C++ ein ScheduleTable-Objekt mit dem Bezeichner <schedule_identifier> zu deklarieren. Der Parameter TOS ist ein Zeiger auf den Stapel, der für diese ScheduleTable verwendet werden soll. |
INIT_SCHEDULE_TABLE_< schedule_identifier >() |
Dieses Makro wird verwendet, um die ScheduleTable in der Applikation zu initialisieren, d.h. um die Periode festzulegen, mit der die ScheduleTable periodisch ausgeführt werden soll, und um die Threads, die in der ScheduleTable abgearbeitet werden sollen, zur ScheduleTable hinzuzufügen. |
Wenn es nicht möglich ist zu einer Menge von TASKs (also eine SCHEDULE) eine gültige ScheduleTable zu finden, soll statt der beiden Makros eine #error-Direktive mit einer entsrpechenden Fehlermeldung generiert werden.
Algorithmus
Um die einzelnen Aufgaben in der ScheduleTable anzuordnen, wird die nicht-präemptive Variante des EDF-Algorithmus verwendet (EDF = Earliest Deadline First).
Für die Bearbeitung der Aufgabe ist es nützlich, das Programm in die folgenden drei Abschnitte zu gliedern:
- Eingabe (Datei
<name>.sched einlesen und parsen)
- Ausgabe (Datei
<name>.h schreiben)
- Scheduling
