Friedrich-Alexander-Universität UnivisSuche FAU-Logo
Techn. Fakultät Willkommen am Department Informatik FAU-Logo
Logo I4
Lehrstuhl für Informatik 4
Echtzeitsysteme
 
  Vorlesungsüberblick
  Voraussetzungen
  Vorlesungsfolien
  Übungen
   Getting Started
   Docs
   Environment
   svn
   Gruppeneinteilung
  Schein, Prüfung
  Evaluation
Department Informatik  >  Informatik 4  >  Lehre  >  WS 2006/07  >  EZS  >  Übung  >  Aufgabe 6

Aufgabe: Deferrable Server

Übersicht

Einleitung
Was ist zu tun?
Hinweise

Einleitung

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 um Behandlung aperiodischer Ereignisse.

Pragmatische Ansätze

Background Execution

Eine einfach 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, 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 am 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. Insbesonderen kann man solche Server zusätzlich noch mit z.B. Background Execution und/oder Slack Stealing kombinieren.

Was ist zu tun?

In dieser Aufgabe soll ein Deferrable Server auf Basis des prioritätengesteuerter 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 seiner Wiederherstellungsperiode p, sowie durch folgende Regeln charakterisiert:

  • Konsumregel: Wenn der Server ausgeführt wird, verbraucht er eine Zeiteinhein seines Budget 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:

pics/deferrable_server.gif
  1. Die periodische Ereignisbehandlung T3 wird ausgelöst und ausgeführt.
  2. Die periodische Ereignisbehandlung T2 wird ausgelöst und ausgeführt.
  3. Ein aperiodisches Ereignis tritt ein und aktiviert den Deferrable Server T1.
  4. Das Ausführungsbudget des Deferrable Servers T1 wird wiederhergestellt.
  5. Das Ausführungsbudget des Deferrable Servers T1 ist verbraucht, die periodische Ereignisbehandlung T2 wird fortgesetzt.
  6. Die periodische Ereignisbehandlung T2 wird erneut ausgelöst und ausgeführt.
  7. Das Ausführungsbudget des Deferrable Servers T1 wird wiederhergestellt, folglich wird die Ereignisbehandlung T2 verdrängt und der Deferrable Servers T1 wird ausgeführt.
  8. Der Deferrable Servers T1 beendet seine Ausführung, und die periodische Ereignisbehandlung T3 wird ausgelöst. Die periodische Ereignisbehandlung T2 wird fortgesetzt.
  9. 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:

pics/classesAufgabe6.gif

Deferrable_Server

Ein Deferrable_Server ist ein Thread der neben einem eigenen Stack und einer Priorität über ein Ausführungsbudget und eine Widerherstellungsperiode verfügt, das Ausführungsbudget wird nach den obigen Regeln verbraucht bzw. aufgefrischt wird.

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.

Hinweise

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.

  Impressum   Datenschutz Stand: 2007-01-16 09:02   scheler