Beispiel für Periodische Ereignisse mit RM

Als erstes Beispiel betrachten wir nur endliche periodische Ereignismengen E, die mittels der Rate Monotonic [RM] Regel geplant werden sollen. Daraus ergibt sich, dass alle Prioritäten statisch sind, d.h. vorab einmalig berechnet und zugeteilt werden können.

Die Grundidee ist dann wie folgt:

Auf dem Leseband kann in jeder Zelle die Menge der Ereignisse stehen, die maximal zu einem Zeitpunkt auftreten können. Diese Ereignisse bilden eine Zeichenkette $\sigma \in \Sigma^{*}$ der Art $\langle e_{1}, e_{2}, \cdots, e_{n}\rangle$, wobei ein $e_{i}$ ein Dezimalzahl sein soll, die ein Ereignis eindeutig kennzeichnet. Die Ereignisse sind auf dem Band schon nach ihrer nominalen Priorität $\pi_{i}$ angeordnet; höchste Priorität 'links'.

Für den geplanten Kellerautomaten definieren wir eine spezielle Variante mit drei Stacks. Im Gegensatz zum normalen Kellerautomaten, bei dem der Stack unbegrenzt ist, sind die Stacks dieses Kellerautomaten alle endlich. Ihre tatsächliche Größe ergibt sich aus der Endlichkeit der vorausgesetzten Ereignismenge [E]. Diese umfasst nur endlich viele [n] Ereignisse $e_{i} \in E$ mit $\vert E\vert = n$. Bei den drei verschiedenen Stapelspeichern ('stacks') handelt es sich um einen Ereignis-Lese-Stack $S^{e}$, um einen Task-Stack $S^{t}$ und einen Kopier-Stack $S^{c}$. Ferner nehmen wir an, dass der Automat über drei Zustände verfügt $q_{read}, q_{ord}, q_{exec}$.

$$X-zustand := \langle q_{X}, input, S^{e}, S^{t}, S^{c}, output, q_{X'}\rangle$$ (12.26)

1. $q_{X}$ definiert den aktuellen Zustand.
2. $input$ ist die Eingabezeichenkette $\sigma \in \Sigma^{*}$ mit den geordneten Ereignissen
3. $S^{e}$ Ereignis-Lese-Stack mit dem leeren Symbol $Z_{0}$ und wichtigstem Task $\tau_{i}$ 'unten' (d.h. 'rechts'). D.h. der Ereignis-Lese-Stack enthält eine Übersetzung der gelesenen Ereignisse in die erkannten Tasks.
4. $S^{t}$ Task-Stack mit dem leeren Symbol $Z_{0}$; enthält alle Tasks, die ausgeführt werden müssen, samt elementaren Ausführungskomponenten geordnet nach Prioritäten mit höchster Priorität 'oben' ('links').
5. $S^{c}$ Kopier-Stack mit dem leeren Symbol $Z_{0}$; dient als Zwischenspeicher, wenn die neuen Tasks in den Ordnungsstack eingefügt werden sollen.

$$Lesezustand := \langle q_{read}, \sigma, S^{e},no, no, no, q_{ord}\rangle$$ (12.27)

$$Lesezustand := \langle q_{read},\langle ..., e_{1},...\rangle,\langle ...,\tau_{i.1}, ..., \tau_{i.l}, ...\rangle ,no, no, no, q_{ord}\rangle$$ (12.28)

Im Lesezustand $q_{read}$ werden die aktuellen Ereignisse vom Eingabeband gelesen und in einen Ereignis-Lese-Stack $S^{e}$ kopiert und in das Taskformat übersetzt, und zwar entsprechend den Prioritäten, die im Input $\sigma$ vorgegeben sind. Niedrigste Prioriät 'oben' ('links'). Da maximal nur $n-viele$ Ereignisse auftreten können, ist der Ereignis-Lese-Stacl $S^{e}$ endlich begrenzt. Falls keine Ereingisse auftreten -angezeigt durch $\epsilon$-, wird nichts nach $S^{e}$ kopiert. Dann enthält der Ereignis-Lese-Stack nur das leere Symbol $Z_{0}$. In beiden Fällen übergibt der Lesezustand $q_{read}$ weiter an den Ordnungszustand $q_{ord}$.

Die Übersetzung von Ereignisidentitäten $e_{i}$ in den zugehörigen Task $\tau_{i}$ in Form der elementaren Taskelemente geschieht anhand der Tabelle, die im Lesezustand abgelegt ist. Dabei bedeutet $...,e_{i},...$ das Ereignis $e_{i}$ in einem Kontext, entsprechend die Notation für die Taskelemente.

Der 'Konstrukteur' eines RT-PDA muss also für ein bestimmtes Realzeitsystem die entsprechenden Informationen aus der technischen Tabelle geeignet in die Kodierung des Automaten 'einbauen'^12.2.

$$Ordnungszustand := \langle q_{ord}, no, S^{e}, S^{t}, S^{c}, no, q_{ord}\rangle$$ (12.29)

$$Ordnungszustand := \langle q_{ord}, no, Z_{0}, no, no, no, q_{exec}\rangle$$ (12.30)

Im Ordnungszustand $q_{ord}$ müssen die neuen Tasks aus dem Ereignis-Lese-Stack $S^{e}$ in den Task-Stack $S^{t}$ eingefügt werden. Dies muss so geschehen, dass die Ordnung nach der Priorität gewahrt bleibt. Nach Annahme befinden sich alle Tasks im Task-Stack geordnet nach Prioritäten und zerlegt in Ausführungseinheiten. Also wenn ein Task $\tau_{i} = \langle i_{1}, i_{2}, i_{3}\rangle$ aus drei Ausführungselementen besteht ($C_{i}=3$) und ein Task $\tau_{j} = \langle j_{1}, j_{2}\rangle$ aus zwei Elementen ($C_{j}=2$), und $\pi_{j} > \pi_{i}$, dann würde der Task-Stack zu Beginn wie folgt aussehen: $S^{t}=\langle j_{1}, j_{2},i_{1}, i_{2}, i_{3}, Z_{0}\rangle$. Zur Abarbeitung würde dann immer das oberste Element (also von 'links') mittels 'put' entfernt.

Angenommen der Ereignis-Lese-Stack $S^{e}$ ist nicht leer, dann gibt es zwei Möglichkeiten: (i) enthält ein Task $\tau_{i}$, der schon in $S^{t}$ vorkommt oder (ii) alle Tasks in $S^{e}$ sind verschieden von den Tasks in $S^{t}$. Im Fall (i) wurde die Deadline $D_{i}$ gebrochen, da ein Task neu auftritt, bevor sein vorhergehendes Auftreten vollständig abgearbeitet werden konnte. Im Fall (ii) liegt kein Bruch einer Deadline vor.

Angenommen der Ereignis-Lese-Stack $S^{e}$ ist nicht leer sondern enthält den Task $\tau_{k} = \langle k_{1}, k_{2}\rangle$ und es gelten die Prioritäten $\pi_{i} < \pi_{k} < \pi_{j}$. Um nun eine korrekte Einfügung des Inhalts von $S^{e}$ nach $S^{t}$ vornehmen zu können, müssten alle Taskelemente aus $S^{t}$, deren Priorität größer ist als die Priorität des aktuellen Tasks $\tau_{k} \in S_{t}$ von $S^{t}$ nach $S^{c}$ kopiert werden, dann müsste der Task aus $S^{e}$ nach $S^{t}$ kopiert werden und der Inhalt von $S^{c}$ müsste nach $S^{t}$ zurückkopiert werden. Diese müsste sooft wiederholt werden, bis der Inhalt von $S^{e}$ vollständig abgearbeitet wäre.

Problem: Um zu wissen, an welcher Position im Task-Stack $S^{t}$ ein neuer Task einzufügen ist, muss der Automat über die Information verfügen, welche Priorität $\pi_{i}$ ein Task jeweils hat. Die vorausgehende Beschreibung setzt voraus, dass dies der Fall ist. Aber dies ist bislang nur eine Annahme. Der bisherige Informationsstand ist wie folgt:

1. Zu Beginn ist $S^{t}$ leer.
2. Erste Informationen über Tasks kommen von $S^{e}$. Diese Tasks sind geordnet.
3. Die ersten Einträge in $S^{t}$ stammen von $S^{e}$ und sind daher auch geordnet.
4. Weitere Informationen können nur von $S^{e}$ kommen. Diese können nur Tasks enthalten, die aktuell noch nicht in $S^{t}$ enthalten sind (ansonsten Fehler).
5. Die Prioriät $\pi_{k}$ eines neuen Tasks $\tau_{k}$ aus $S^{e}$ kann kleiner, gleich oder größer sein wie die des obersten Tasks in $S^{t}$.
6. Der Ordnunszustand $_{ord}$ muss also über die Möglichkeit verfügen, $S^{t}$ elementweise zu durchlaufen und in jedem Fall berechnen können, wie sich die Priorität des aktuellen Elementes aus $S^{t}$ zur Priorität des aktuell obersten Tasks aus $S^{e}$ verhält.

Angenommen bei der Übersetzung der Ereignisse vom Eingabeband in das interne Taskformat würden die Prioritäten mitnotiert, indem z.B. die Task-IDs Zahlen wären, die die Prioritäten direkt repräsentieren würden, dann würde sich die Aufgabe dahingehend vereinfachen, die Task-IDs bzgl. ihrer Größe zu vergleichen. Wäre die Task-ID des obersten Elementes von $S^{e}$ größer als jene des obersten Elementes von $S^{t}$ -kurz: $ID_{e} > ID_{t}$-, dann könnte der Inhalt von $S^{e}$ einfach 'auf' $S^{t}$ 'aufgesetzt' werden. Bei Gleichheit könnte dies auch praktiziert werden. Im Falle einer kleineren ID müßte diejenige Position in $S^{t}$ gesucht werden, ab der die ID des obersten Elementes von $S^{e}$ wieder mindestens gleich groß wäre. Also solange $ID_{e} < ID_{t}$ kopiere oberstes Element von $S^{t}$ nach $S^{c}$. Sobald $ID_{e} \geq ID_{t}$ kopiere oberstes Element von $S^{e}$ nach $S^{t}$, dann wieder Inhalt von $S^{c}$ zurück kopieren nach $S^{t}$. (Dies muss noch genauer ausgearbeitet werden). Da alle beteiligten Mengen endlich sind, muss die Aufgabe berechenbar sein. Es frgat sich nur, ob und wieweit man über die Möglichkeiten eines Kellerautomaten hinausgehen muss.

$$Ausfuehrungszustand := \langle q_{exec}, no, no, S^{t}, no, \xi, q_{read}\rangle$$ (12.31)

Im Ausführungszustand $q_{exec}$ nimmt der Automat das 'oberste' Element vom Task-Stack $S^{t}$ und führt es aus. Dazu wird ein entsprechendes Symbol $\xi$ in den Output geschrieben. Dann kehrt der Automat in den Lesezustand zurück.

Geht man davon aus, dass das Lesen des Eingabefeldes jeweils nach einer vorgeschriebenen Zeiteinheit $\kappa$ stattfinden soll, die von einer Uhr [CLCK] mit einer Ganggenauigkeit von $X \%$ nach $m-viele$ Zeiteinheiten generiert wird, dann bedeutet dies, dass der Zeitbedarf des RTA-PDA für die Ausführung der Operationen $time(q_{read} \otimes q_{ord} \otimes q_{exec})$ einen bestimmten Schwellwert $\theta$ nicht überschreiten darf. Nennen wir diesen Zeitbedarf die Worst-Case Execution Management Time [WCEMT], dann gilt $WCEMT \leq \theta$. Dazu kommt dann noch die Taskbezogene Ausführungszeit. Um also vorgeschriebene Deadlines einhalten zu können muss das System sowohl die Taskausführungszeit ('execution time') $C_{i}$ der einzelnen Tasks beherrschen als auch gleichzeitig die zugehörige WCEMT. Mit Zunahme der Ereignismenge nimmt entsprechend der Zeitbedarf für die Übersetzung in das Taskformat, das Ordnen der Taskmenge, die Kontrolle auf Fehler, sowie die Task-Ausführungszeit zu.

Dieses erste Fallbeispiel legt die Vermutung nahe, dass der Ansatz mit einem Kellerautomaten für eine endliche periodische Taskmenge ohne kritische Ressourcen und der RM-Regel durchführbar ist. Folgende Übungen sollten versucht werden:

1. Wenigstens ein vollständiges Beispiel mit einer planbaren Taskmenge durchrechnen.
2. Wenigstens ein Beispiel mit einer nicht planbaren Taskmenge durchrechnen.
3. Anhand der Ausführungsgraphen überprüfen, inwieweit die Idee einer automatischen Verifikation anwendbar ist; falls nicht, was würde noch fehlen.
4. Vergleich eines deterministischen Kellerautomaten mit drei endlichen Stacks zu einem deterministischen Kellerautomaten mit einem unendlichen Stack.
5. Vergleich eines deterministischen Kellerautomaten mit drei endlichen Stacks zu einem nicht-deterministischen Kellerautomaten mit einem unendlichen Stack.
6. Überprüfen, inwieweit der aktuelle RTS-PDA nicht schon einem linear-gebundenen Automaten entspricht.