Aufgabe: Deferrable Server
Übersicht
Einleitung
Was ist zu tun?
Hinweise
Obwohl in ereignisgesteuerten System eine reaktive Behandlung von
nicht-periodischen Ereignissen prinzipiell möglich ist, bleibt ihre
Behandlung dennoch problematisch. Es gilt auch hier einen Kompromiss zwischen
einer möglichst guten Antwortzeit für nicht-periodische
Ereignisbehandlungen und einer möglichst geringen Beinflussung
periodischer Ereignisbehandlungen zu finden. Während bei aperiodischen
Ereignissen meist keine oder allenfalls feste Zeitbedingungen einzuhalten
sind, sind diese bei sporadischen Ereignissen strikt, was einen
zusätzlichen Akzeptanztest erfordert. Der Einfachheit halber befassen
wir uns aber auch in dieser Aufgabe lediglich mit der Behandlung
aperiodischer Ereignisse.
Pragmatische Ansätze
Background Execution
Eine einfache Möglichkeit zur Behandlung aperiodischer Ereignisse
ist, sie in den Idle-Phasen des Systems, also im Hintergrund, abzuarbeiten,
wie dies auch in Aufgabe 3 getan
wurde. Der Vorteil dieses Verfahrens ist, dass periodische
Ereignisbehandlungen dadurch in keiner Weise beeinträchtigt werden. Der
Nachtteil ist, dass die Antwortzeiten für solche Ereignisbehandlungen
immer noch verbesserungswürdig sind.
Interrupt-Driven Execution
Bei der Interrupt-Driven Execution wird ein aperiodisches
Ereignis sofort zum Zeitpunkt seines Eintretens bevorzugt zu periodischen
Ereignissen behandelt. Die Antwortzeit ist bei diesem Verfahren sehr kurz,
jedoch können dadurch periodische Ereignisbehandlungen so weit
verzögert werden, dass sie ihre Zeitbedingungen nicht mehr einhalten
können.
Slack-Stealing
Slack-Stealing stellt eine Mischung aus Background und
Interrupt-Driven Execution dar. Prinzipiell werden aperiodische Ereignisse
sofort bei ihrem Auftreten behandelt, es wird jedoch gleichzeitig
sichergestellt, dass periodische Ereignisbehandlungen nicht so stark
verzögert werden, dass sie ihre Zeitbedingungen nicht mehr einhalten
können.
Polling Server
Ein Polling Server wird wie eine periodische Ereignisbehandlung
ins Gesamtsystem eingeplant, d.h. er wird periodisch mit einer gewissen
Periode von p
Einheiten aktiviert und er benötigt maximal
e
Einheiten Laufzeit. Wird der Server lauffähig,
überprüft er, ob ein aperiodisches Ereignis zur Behandlung ansteht
und behandelt dies gegebenenfalls. Gibt es kein solches Ereignis, beendet
sich der Server und wird nach p
Zeiteinheiten erneut aktiviert.
Die zur Verfügung stehende Laufzeit geht in diesem Fall für die
Behandlung aperiodischer Ereignisse verloren, es wird also Bandbreite
verschwendet. Während hier periodische Ereignisbehandlung nicht negativ
beeinflusst werden, ist die Antwortzeit für die Behandlung aperiodischer
Ereignisse in den meisten Fällen sehr schlecht.
Bandwidth Preserving Servers
Ein weiterer mit dem Polling Server verwandter Ansatz sind
sogenannte Bandwidth Preserving Servers. Der Unterschied bei diesen
beiden Typen von Servern ist, dass bei Bandwidth Preserving Servers die
Bandbreite erhalten bleibt, auch wenn gerade kein aperiodisches Ereignis zur
Behandlung ansteht. Charakteristisch für einen solchen Server ist sein
Ausführungsbudget und die Periode dessen Wiederherstellung.
Zusätzlich unterscheidet man noch verschiedene Typen von Bandwidth
Preserving Servers, die hinsichtlich der Regeln, wie ein Server sein Budget
aufbraucht und wie es wieder aufgefüllt wird, verschieden sind. Der
große Vorteil dieser Server ist, dass man die Antwortzeit
nicht-periodischer Ereignisbehandlungen weiter verbessern kann, während
man den Einfluß auf periodische Ereignisbehandlungen durch die Wahl
eines geeigneten Ausführungsbudgets und einer geeigneten
Wiederherstellungsperiode genau bestimmen kann. Insbesondere kann man solche
Server zusätzlich noch mit z.B. Background Execution und/oder Slack
Stealing kombinieren.
In dieser Aufgabe soll ein Deferrable Server auf Basis des
prioritätsgesteuertem Multi-Level-Queue-Schedulers aus Aufgabe 4 implementiert werden. Ein
Deferrable Server ist die einfachste Form eines Bandwidth Preserving Servers
und seine Funktionweise soll im Folgenden kurz beschrieben werden.
Deferrable Server
Ein Deferrable Server ist durch sein Ausführungsbudget e
und seine Wiederherstellungsperiode p
, sowie durch folgende
Regeln charakterisiert:
- Konsumregel: Wenn der Server ausgeführt wird,
verbraucht er eine Zeiteinheit seines Budgets für jede Zeiteinheit,
die er ausgeführt wird.
- Wiederherstellungsregel: Zu
den Zeitpunkten
kp
mit k
= 0,1,2,3,... wird das
Ausführungsbudget wieder komplett hergestellt.
Jedem Deferrable Server ist statisch eine Priorität zugeordnet.
Solange der Server über Auführungsbudget verfügt, wird er
bevorzugt zu periodischen Ereignisbehandlungen gleicher Priorität
ausgeführt. Hat der Server sein Ausführungsbudget verbraucht, wird
er suspendiert. In der EZStubs-Implementierung soll pro Priorität ein
Deferrable Server unterstützt werden, die einzelnen Primitive zur
Verwaltung von Deferrable Servern unterscheiden sich etwas von denen zur
Verwaltung von Fäden:
add |
Versetzt einen Deferrable Server in einen ausfürhungsbereiten
Zustand, der Server wird jedoch nur dann ausgeführt, wenn er
über ein entsprechendes Ausführungsbudget verfügt. |
exit |
Der Deferrable Server beendet die Ausführung, behält aber
sein Ausführungsbudget. |
kill |
Der Deferrable Server wird beendet, behält jedoch sein
Ausführungsbudget. |
yield |
Der Server verzichtet auf den Prozessor und verliert sein
übriges Ausführungsbudget. |
enlist |
Jeder Server muss sich beim Scheduler registrieren, um sein
Ausführungsbudget und seine Wiederherstellungsperiode
mitzuteilen. |
Beispiel
Gegeben seien ein Deferrable Server und zwei periodische
Ereignisbehandlungen:
Name |
Phase |
Periode |
WCET |
Priorität |
T1 (Deferrable Server) |
|
3 |
1 |
5 |
T2 |
2 |
3,5 |
1,5 |
3 |
T3 |
0 |
6,5 |
0,5 |
1 |
Dieses System führt konkret zu folgendem Ablauf:
- Die periodische Ereignisbehandlung
T3
wird ausgelöst
und ausgeführt.
- Die periodische Ereignisbehandlung
T2
wird ausgelöst
und ausgeführt.
- Ein aperiodisches Ereignis tritt ein und aktiviert den Deferrable
Server
T1
.
- Das Ausführungsbudget des Deferrable Servers
T1
wird
wiederhergestellt.
- Das Ausführungsbudget des Deferrable Servers
T1
ist
verbraucht, die periodische Ereignisbehandlung T2
wird
fortgesetzt.
- Die periodische Ereignisbehandlung
T2
wird
erneut ausgelöst und ausgeführt.
- Das Ausführungsbudget des Deferrable Servers
T1
wird
wiederhergestellt, folglich wird die Ereignisbehandlung T2
verdrängt und der Deferrable Servers T1
wird
ausgeführt.
- Der Deferrable Servers
T1
beendet seine
Ausführung, und die periodische Ereignisbehandlung T3
wird ausgelöst. Die periodische Ereignisbehandlung T2
wird fortgesetzt.
- Die periodische Ereignisbehandlung
T2
beendet die Ausführung und die periodische Ereignisbehandlung
T3
fortgesetzt.
Zur Bearbeitung dieser Aufgabe ist es notwendig die in folgendem
Klassendiagramm rot markierten Klassen zu implementieren bzw.
anzupassen:
Deferrable_Server
Ein Deferrable_Server
ist ein Thread
der neben
einem eigenen Stack und einer Priorität über ein
Ausführungsbudget und eine Wiederherstellungsperiode verfügt. Das
Ausführungsbudget wird nach den obigen Regeln verbraucht bzw.
aufgefrischt.
Multi_Level_Queue_Scheduler_Deferrable_Server< MAX_PRIO > und
Guarded_Multi_Level_Queue_Scheduler_Deferrable_Server
Die Klasse Multi_Level_Queue_Scheduler_Deferrable_Server
erweitert den herkömmlichen Multi_Level_Queue_Scheduler
, so
dass auch Deferrable Server verwaltet werden können. Hierfür bietet
diese Klasse die oben beschriebene Schnittstelle an, die dem Vorhandensein
von Deferrable Servern Rechnung trägt. Der Templateparameter gibt die
höchste für Deferrable Server verfügbare Priorität an.
Die Klasse Guarded_Multi_Level_Queue_Scheduler_Deferrable_Server
stellt eine gegen Unterbrechungen gesicherte Variante dieser Schnittstelle
zur Verfügung.
Bevor man in den Testfällen für Deferrable Server auf
Fehlersuche geht, sollte man sicherstellen, dass alle Testfälle für
den herkömmlichen Scheduler fehlerfrei funktionieren.