Somit kann eine Transition in einem Zustandsgraphen allgemein beschrieben werden: "Befindet sich ein Operand im Zustand z1 und sind die mit x beschriebenen Bedingungen erfüllt, so geht der Operand durch Ausführung der Operation y in den Zustand z2 über, wobei y auch die Änderung von Zustandswerten in großen oder unendlichen Zustandsgraphen des Operanden beinhalten kann". Diese Beschreibung impliziert die Idee, die Ausführung einer Transition durch ein spezielles Software-Werkzeug, den Zustandsgrapheninterpreter, zu realisieren.
Zustandsgrapheninterpreter sind bereits auf vielfältige Arten implementiert worden. HOLCOMBE beschreibt einen Interpreter für Automatengraphen zum Einsatz in Dialogprozessen, am Massachusettes Institut of Technology werden Zustandsgrapheninterpreter zur Emulation und Simulation von CAM-Software verwendet (BLOOME et.al.). CORDES zeigt die Anwendung eines Automatengrapheninterpreters für Maschinen- und Robotersteuerungen. Verschiedene Zustandsgrapheninterpreter werden in EWSTATIEWA analysiert.
| _______________ _______________ |
| | | | | |
| | Ermittlung d. | | Ausführung | |
|----->| akt. Zustands |---->| Transition |------>|
| |_______________| |_______________| |
/ \
___________________________/ \_____
/ \
/ \
| ________________ _________________ |
| | | | | |
|----->| Bedingungstest |---->| ELSE-Regel-Test |-------->|
| |________________| |_________________| |
| | ^ | | |
| | | | V |
| +--------+ | _________________ |
| | | | |
| +------>|Aktionsausführung|-------->|
| |_________________| |
| | |
| V |
| _________________ |
| | | |
| alle Kanten |Zustandsübergang |-------->|
| alternativ |_________________| |
| |
Prozeßstruktur für die Abarbeitung einer Transition
Dem Zustandsgrapheninterpreter müssen die Operanden und die ihnen zugeordneten Zustandsgraphen bekannt sein. Die Grundidee besteht darin, Operanden informationeller Natur mittels Datenstrukturen, die Verweise auf Zustandsgraphen enthalten, zu implementieren. Zustandsgraphen werden ebenfalls in der Form von Datenstrukturen implementiert, die Verweise auf bestimmte Funktionen enthalten. Diese Funktionen wiederum realisieren den Test der Bedingungen und die Ausführung der Aktionen.
SIRIUS 2.2 arbeitet mit definierten Datenstrukturen, bezeichnet als informationelle Operanden. Diese können im Sinn der objektorientierten Programmierung als Objekte angesehen werden. Jeder informationelle Operand gehört einer bestimmten Objektklasse an.
Welche Objektklassen in einer konkreten Basis (im Sinne der materiellen Umgebung eines informationsverarbeitenden Prozesses) existieren, muß beim logischen Entwurf der Software herausgearbeitet werden. Darauf soll an dieser Stelle noch nicht näher eingegangen werden.
Jeder informationelle Operand, den SIRIUS 2.2 hantiert, repräsentiert einen Prozeß der im Entwurf erarbeiteten Prozeßstruktur. Um Prozesse mit SIRIUS 2.2 bearbeiten zu können ist es notwendig, diese mit Hilfe von Zustandsgraphen und Datenstrukturen zu beschreiben. Jedem informationellen Operanden können gleichzeitig bis zu fünf Zustandsgraphen, ggf. dynamisch veränderbar, zugeordnet sein, die (logisch) parallel hantiert werden. Über die physische Reihenfolge der Bearbeitung der Zustandsgraphen eines informationellen Operanden entscheidet SIRIUS selbständig.
Wir unterscheiden zwei wesentliche Phasen des Software-Entwurfs für CAMARS-Software:
Der funktional-logische Entwurf enthält keine implementationsspezifischen Elemente, auch nicht solche, die vom später verwendeten Interpreter (also SIRIUS 2.2) abhängen. Die Datenstrukturen stellen hier noch Zuordnungen von Informationen oder Entitäten zu den Prozessen oder Entitäten dar.
Der Implementationsentwurf stellt die Überführung des funktional-logischen Entwurfs in eine Form, an die sich die Implementierung unmittelbar anschließen kann, dar. Er ist äußerlich dadurch gekennzeichnet, daß Mittel und Darstellungsarten von funktional-logischem Entwurf und programmierungstechnischer Realisierung gemischt auftreten. Dazu gehören z.B. die Definition der verwendeten Datenstrukturen, die Festlegung der Namen von Bedingungs- und Aktionsroutinen und deren programmtechnischer Entwurf.
Zu diesem Schritt gehört auch die Modifikation der funktional-logischen Zustandsgraphen. Dabei können Programmfehler abgefangen oder zusätzliche Transitionen (beispielsweise zur Übernahme von Informationen anderer Entitäten) oder neue Zustände, die nur für die Implementation eine Bedeutung erlangen (z.B. 'initialisierend'), eingeführt werden. Die modifizierten Zustandsgraphen dürfen nicht den funktional-logischen Zustandsgraphen widersprechen, insbesondere dürfen keine Transitionen oder Zustände gestrichen werden (vgl. auch Abschnitt 8.3.).
Die Beschreibung der Zustandsgraphen erfolgt in Textfiles. Ein Aufbereitungsprogramm GRAPH generiert aus diesen Beschreibungen die Datenstrukturen für die Zustandsgraphen. Die Vollendung der Zustandsgraphenbeschreibung, wird durch die Bedingungs- und Aktionsroutinen des Anwenders hergestellt.
Die Bedingungen und Aktionen der Zustandsgraphen können als elementare Funktionen implementiert werden, die damit einen äußerst einfachen Aufbau haben. Diese Übersichtlichkeit erlaubt auch die Anwendung programmierungstechnischer Tricks und Kniffe ("trickreiche" Programmierung). Diese muß jedoch bei größeren Funktionen unbedingt abgelehnt werden, da sie die Portabilität in jeder Weise (also nicht nur Portabilität auf andere Rechner oder Betriebssysteme, sondern auch die Portabilität auf andere Programmiersprachen oder Bearbeiter) negativ beeinflußt. Kleinere Funktionen, deren Aufgabe überschaubar ist, lassen sich schnell durch Funktionen mit "sauberem" Programmierstil ersetzen, wenn es nicht gelingt, verwendete Tricks nachzuvollziehen.
Nachdem derart alle Bedingungs- und Aktionsfunktionen implementiert sind und die Beschreibung der Zustandsgraphen an SIRIUS 2.2 übergeben wurde, kann mit dem Test des Software-Produkt begonnen werden.
Der Zustandsgrapheninterpreter SIRIUS 2.2 arbeitet ereignisorientiert, d.h., es werden zu einem Zeitpunkt nur die informationellen Operanden bearbeitet, für die ein relevantes Ereignis vorliegt. Für einen solchen informationellen Operanden versucht SIRIUS 2.2, in jedem ihm zugeordneten Zustandsgraphen maximal eine Transition auszuführen. Dazu werden die aus dem aktuellen Zustand führenden Bedingungen durch Aufruf der Bedingungsroutinen getestet und, falls eine von ihnen einen Rückkehrcode ungleich Null liefert, die entsprechende Aktion durch Aufruf der Aktionsroutine ausgeführt.
Das Ereignis, das die Behandlung eines informationellen Operanden auslöst, ist die Aktivierung. Diese wird durch die Funktionen activate bzw. priactivate ausgeführt. Vor einem Aufruf von SIRIUS muß immer mindestens eine Aktivierung erfolgen. SIRIUS arbeitet solange, bis kein informationeller Operand mehr aktiviert ist. Wenn es Prozesse gibt, die sich ständig selbst aktivieren, wird die Funktion sirius nie verlassen.
Existieren zu einem gegebenen Zeitpunkt mehrere aktivierte informationelle Operanden, so wird der mit der höchsten Priorität zuerst behandelt. Die Bearbeitung eines informationellen Operanden ist nicht unterbrechbar.
Eine ausführliche Beschreibung des Zustandsgrapheninterpreters SIRIUS 2.2 ist in DOETZKIES 1990 enthalten.
SIRIUS 2.2 stellt die rechentechnische Realisierung des Prozesses der Ausführung einer Transition in einem Zustandsgraphen eines informationellen Operanden dar. Informationeller Operand und Zustandsgraph sind somit die Operanden des Zustandsgrapheninterpreters.
Die Menge der informationellen Operanden ist dynamisch und wird durch die Interpreterfunktionen odin und odkill beeinflußt. Die Anzahl der gleichzeitig existenten informationellen Operanden kann beliebig groß sein und ist nur von den Hauptspeicher- bzw. Plattenkapazitäten des verwendeten Rechners abhängig. In der Systemkoordination des FMS 2500 können zeitweise über 2000 informationelle Operanden gleichzeitig existieren, d.h., 2000 Prozesse können quasiparallel bearbeitet werden.
Die Menge der Zustandsgraphen ist für ein gegebenes Programmsystem statisch und wird durch das Aufbereitungsprogramm bestimmt. Die Anzahl der Zustandsgraphen entspricht der Anzahl der unterschiedlichen Prozesse. Sie kann ebenfalls beliebig hoch sein.
Die Prozesse, die SIRIUS 2.2 an den informationellen Operanden und den Zustandsgraphen ausführen kann, können mit Hilfe von Zustandsgraphen beschrieben werden. In diesen Zustandsgraphen widerspiegeln sich die Hauptfunktionen des Zustandsgrapheninterpreters. Die Transitionen sind jedoch nicht wieder über einen Interpreter implementiert, obwohl dies bis zu einem gewissen Grade denkbar wäre, sondern in Form von Funktionen. Die Bedingung für einen Zustandsübergang ist damit der Aufruf einer oder mehrerer Funktionen, die Aktion und die Transition werden durch die Funktion ausgeführt.
Der Zustandsgraph der informationellen Operanden ähnelt in seinen Grundzügen dem Zustandsgraph einer Task in Multitasksystemen. Im Gegensatz zu einer Task in einem Echtzeitbetriebssystem, die durch einen Tasksteuerblock und ihrem zugeordneten Programm repräsentiert wird (und damit lediglich Prozeßeigenschaften auf weist), stellt ein informationeller Operand von SIRIUS 2.2 eine Einheit von Prozeß und Operand dar. Dies ermöglicht eine einfache Handhabung und ist Voraussetzung für die sehr hohe Zahl parallel ausführbarer Prozesse. Dabei liegt die Zeitdauer der Prozeßumschaltung, nach HARDT ein Gütemerkmal eines Echtzeitbetriebssystems, durchaus in einem vertretbaren Rahmen (ca. 1 ms. auf AC 7150 für SIRIUS 2.2 - max. 9 ms. für Real-Time UNIX (nach POMPE) - Echtzeitbetriebssystem durch Hardware realisiert 1 µs. für SAB 80199).
Ein informationeller Operand ist im Zustand 'existent' (Task: 'gestoppt'), wenn er durch den Interpreter hantiert werden kann. Wenn von SIRIUS 2.2 an einem Operanden Transitionen ausgeführt werden sollen, befindet er sich im Zustand 'aktiviert' (Task: 'bereit'). Dieser Zustand wird durch den Aufruf der Funktionen activate oder priactivate erreicht. SIRIUS 2.2 kann zu einem bestimmten Zeitpunkt nur einen Operanden aus der Menge der aktivierten informationellen Operanden bearbeiten. Dieser wird durch eine Auswahlstrategie (Priorität, dann FIFO) bestimmt und geht in den Zustand 'in Prozeß' (Task: 'aktiv') über. Wird die Bearbeitung des informationellen Operanden beendet, wird er wieder 'existent' oder, falls er sich selbst aktiviert hat 'aktiviert'. Die Kooperation von Zustandsgraphen wird durch ihre wechselseitige Aktivierung realisiert. Dazu ist in den auslösenden Transitionen eine Aktivierung der Prozesse vorzunehmen, auf die die Transition einwirken kann.
Weitere Zustände der informationellen Operanden sind 'ausgelagert' und 'gesichert'. In den Zustandsgraphen werden auch die Zustände 'vor Erzeugung' und 'nach Vernichtung' aufgenommen.
___________________
| |
| vor Erzeugung |
|___________________|
|
| x1
___________________ | ___________________
| | | | |
| gesichert |---+ | +-->| aktiviert |
|___________________| | | | |___________________|
^ x7 | | | x2 | ^
| x6 V V | | |
| ___________________ | |
+-------| | | x3 | x5
| existent | | |
+------>|___________________| | |
| x9 | | ^ | |
| | | | V |
___________________ x8 | | | x4 ___________________
| | | | | | |
| ausgelagert |<--+ | +---| in Prozeß |
|___________________| | |___________________|
| x10
|
V
___________________
| |
| nach Vernichtung |
|___________________|
Funktionen, die die Zustandsübergänge bewirken:
x1 - odin x6 - s22save / s22fsave
x2 - activate / priactivate x7 - unbedingte Transition
x3 - interne Funktion x8 - x6 und odfree
x4 - interne Funktion x9 - s22load / s22fload
x5 - x2 für sich selbst x10 - odkill
Zustandsgraph eines informationellen Operanden
Außer den informationellen Operanden hantiert SIRIUS 2.2 auch die diesen zugeordneten Zustandsgraphen. Damit ist eine dynamische Zuordnung von Zustandsgraphen zu den informationellen Operanden möglich. Ein informationeller Operand ist so in der Lage, einmal nach diesem, ein ander Mal nach jenem Zustandsgraphen zu arbeiten, was vorteilhaft für die Implementation hierarchischer Zustandsgraphen ist. Diese werden auch durch die Möglichkeit unterstützt, Transitionen in Zustandsgraphen zu verbieten bzw. wieder zu erlauben.
odin /
____________ odlink ____________ odlock ____________
| nicht |---------->| |---------->| |
| zugeordnet | | zugeordnet | | gesperrt |
|____________|<----------|____________|<----------|____________|
odunlink odunlock
Zustandsgraph eines Zustandsgraphen bezüglich eines
informationellen Operanden
| voriger Abschnitt | Inhalt der Dissertation |
|
<F>-soft Homepage |
nächster Abschnitt |
Original © 1990 by Dresden University
of Technology; Dept. of Information Science; Applied Computer Science