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 der Art , wobei ein ein Dezimalzahl sein soll, die ein Ereignis eindeutig kennzeichnet. Die Ereignisse sind auf dem Band schon nach ihrer nominalen Priorität 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 mit . Bei den drei verschiedenen Stapelspeichern ('stacks') handelt es sich um einen Ereignis-Lese-Stack , um einen Task-Stack und einen Kopier-Stack . Ferner nehmen wir an, dass der Automat über drei Zustände verfügt .
(12.26) |
(12.27) | |||
(12.28) |
Im Lesezustand werden die aktuellen Ereignisse vom Eingabeband gelesen und in einen Ereignis-Lese-Stack kopiert und in das Taskformat übersetzt, und zwar entsprechend den Prioritäten, die im Input vorgegeben sind. Niedrigste Prioriät 'oben' ('links'). Da maximal nur Ereignisse auftreten können, ist der Ereignis-Lese-Stacl endlich begrenzt. Falls keine Ereingisse auftreten -angezeigt durch -, wird nichts nach kopiert. Dann enthält der Ereignis-Lese-Stack nur das leere Symbol . In beiden Fällen übergibt der Lesezustand weiter an den Ordnungszustand .
Die Übersetzung von Ereignisidentitäten in den zugehörigen Task in Form der elementaren Taskelemente geschieht anhand der Tabelle, die im Lesezustand abgelegt ist. Dabei bedeutet das Ereignis 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.
(12.29) | |||
(12.30) |
Im Ordnungszustand müssen die neuen Tasks aus dem Ereignis-Lese-Stack in den Task-Stack 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 aus drei Ausführungselementen besteht () und ein Task aus zwei Elementen (), und , dann würde der Task-Stack zu Beginn wie folgt aussehen: . Zur Abarbeitung würde dann immer das oberste Element (also von 'links') mittels 'put' entfernt.
Angenommen der Ereignis-Lese-Stack ist nicht leer, dann gibt es zwei Möglichkeiten: (i) enthält ein Task , der schon in vorkommt oder (ii) alle Tasks in sind verschieden von den Tasks in . Im Fall (i) wurde die Deadline 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 ist nicht leer sondern enthält den Task und es gelten die Prioritäten . Um nun eine korrekte Einfügung des Inhalts von nach vornehmen zu können, müssten alle Taskelemente aus , deren Priorität größer ist als die Priorität des aktuellen Tasks von nach kopiert werden, dann müsste der Task aus nach kopiert werden und der Inhalt von müsste nach zurückkopiert werden. Diese müsste sooft wiederholt werden, bis der Inhalt von vollständig abgearbeitet wäre.
Problem: Um zu wissen, an welcher Position im Task-Stack ein neuer Task einzufügen ist, muss der Automat über die Information verfügen, welche Priorität 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:
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 größer als jene des obersten Elementes von -kurz: -, dann könnte der Inhalt von einfach 'auf' 'aufgesetzt' werden. Bei Gleichheit könnte dies auch praktiziert werden. Im Falle einer kleineren ID müßte diejenige Position in gesucht werden, ab der die ID des obersten Elementes von wieder mindestens gleich groß wäre. Also solange kopiere oberstes Element von nach . Sobald kopiere oberstes Element von nach , dann wieder Inhalt von zurück kopieren nach . (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.
(12.31) |
Im Ausführungszustand nimmt der Automat das 'oberste' Element vom Task-Stack und führt es aus. Dazu wird ein entsprechendes Symbol 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 stattfinden soll, die von einer Uhr [CLCK] mit einer Ganggenauigkeit von nach Zeiteinheiten generiert wird, dann bedeutet dies, dass der Zeitbedarf des RTA-PDA für die Ausführung der Operationen einen bestimmten Schwellwert nicht überschreiten darf. Nennen wir diesen Zeitbedarf die Worst-Case Execution Management Time [WCEMT], dann gilt . 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') 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:
Gerd Doeben-Henisch 2013-01-16