Lebendigkeit von Ablaufdiagrammen

Eine Eigenschaft von Ablaufdiagrammen ist die Lebendigkeit. Sie beschreibt, ob alle Wege durch ein Ablaufdiagramm durchlaufen werden können und danach die Ausgangslage wieder erreicht werden kann. Sie ist somit Grundvoraussetzung, dass der gezeichnete Ablauf überhaupt funktioniert. In der Steuerungstechnik werden oft Ablaufdiagramme gezeichnet, die einige Schritte zur Initialisierung oder auch eine Abschaltesequenz enthalten. Da diese meist nur einmal durchlaufen werden, führen sie so­fort zu einem nicht lebendigen Ablaufdiagramm. Es ist somit angebracht, in einem Ablauf den leben­digen Teil auszuscheiden und diesen genau zu untersuchen.

 

Definition der Lebendigkeit: Ein Ablaufdiagramm ist für eine Startmarkierung lebendig, wenn die Startmarkierung wieder erreicht werden kann und alle Transitionen mindestens einmal geschaltet ha­ben.

Die Lebendigkeit kann mit Rechenoperationen in der Ablaufdiagramm-Tabelle ausgedrückt werden. Dazu ist es nötig zu verstehen, was eine Multiplikation einer Spalte mit einer ganzen Zahl oder die Addition zweier Spalten bedeutet. Wird die j-te Spalte mit einer ganzen Zahl nj multipliziert, so geben die Zahlen in der Spalte an, um wieviel sich die Anzahl der Markierungen in den Schritten ändert, wenn die Transition Tj genau nj mal schaltet. Zählt man zwei Spalten zeilenweise zusammen, so ent­hält die Resultatspalte wieder die Veränderung der Markierungen in den Schritten, wenn beide zu den Spalten gehörende Transitionen geschaltet werden. Simulieren wir nun einen Ablauf, so müssen wir Buch führen, wie oft jede Transition geschaltet hat. Multiplizieren wir nun jede Spalte mit der Anzahl Schaltungen der entsprechenden Transition und zählen diese zeilenweise zusammen, so erhalten wir eine Angabe, um wieviel sich die Anzahl Markierungen in den Schritten verändert hat. Aufgrund der Definition der Lebendigkeit ist darum derjenige Fall interessant, bei dem alle Spalten mit einer von Null verschiedenen positiven Zahl multipliziert werden, d.h. jede Transition mindestens einmal schaltet, und die resultierende Zeilensumme Null ist, d.h. die Anzahl Markierungen sich nicht verändert hat und damit die Ausgangslage wieder erreicht ist.

Es ist nun offensichtlich, wie Anhand der Tabelle die Lebendigkeit eines Ablaufdiagramms untersucht werden kann:

Ein Ablaufdiagramm ist lebendig, wenn es eine Kombination von ganzen positiven Zahlen gibt, mit der die Spalten der Tabelle so multipliziert werden, dass alle Zeilensummen gleich Null sind.

Für das Alarmbeispiel:

Faktor

1

1

1

 

Schritt\    Transition

T1

T2

T3

Summe

S1

-1

0

1

0

S2

1

-1

0

0

S3

0

1

-1

0

S4

-1

1

0

0

S5

1

-1

0

0

Tabelle 1: Tabellendarstellung des Alarmbeispiels

Die Faktoren geben an, wieviel mal eine Transition schalten muss, bis die Anfangsmarkierung wieder erreicht ist.


Das folgende Beispiel zeigt den lebendigen und nicht lebendigen Teil eines Ablaufs. Meistens kann durch Verbinden der Endteils mit dem Initialisierungsteil der ganze Ablauf lebendig gemacht werden.

Abbildung 1: Lebendige Teile eines Ablaufdiagramms

Dead-Lock

Entsteht in einem Ablauf eine Situation, in der keine Transition mehr schalten kann, so wird dies als 'Dead-Lock' bezeichnet. Dies ist der Alptraum jedes Programmierers. Umso mehr ist er an Methoden interessiert, welche ihm ein Testen auf Dead-Lock-Freiheit ermöglicht. Die vollständige Modellierung eines Prozesses in einem Ablaufdiagramm erlaubt es, mit Computern den ganzen Ereignisgraphen nach Dead-Lock Situationen zu durchsuchen. Es braucht aber schon einiges an Genialität, das System so vollständig zu modellieren, dass eine Dead-Lock wirklich ausgeschlossen werden kann.

Beispiel für ein Ablaufdiagramm mit Dead-Lock:

Abbildung 2: Beispiel Dead-Lock

Simulieren Sie den Automaten und zeichnen Sie die Markierung ein, in der ein Dead-Lock auftritt! Was wurde falsch gemacht?

 

Erreichbarkeit und Erreichbarkeitsgraph

Von einer Startmarkierung ausgehend heisst eine Ziel-Markierung erreichbar, wenn es eine Schaltfolge gibt, die die Startmarkierung in die gewünschte Ziel-Markierung überführt. Diese Eigenschaft ist bei mit Vernunft gezeichneten Ablaufdiagrammen kaum ein Problem.

Der Zusammenhang zwischen Transitionen und erzeugten Markierungen kann für ein Ablaufdia­gramm in einem Erreichbarkeitsgraphen dargestellt werden. Erreichbarkeitsgraphen sicherer Ablauf­diagramme sind nicht unendlich gross und können somit graphisch dargestellt werden.

Beispiel (ohne Initialisierungsschritt!):

Startmarkierung

 

 

 

 

 

 

 

 

 

 

Abbildung 6: Erreichbarkeitsgraph

Komplettieren Sie den Erreichbarkeitgraphen: Zeigen Sie mit Pfeilen, wie die aus der Markierung links die anderen Markierungen entstehen. Geben Sie zu jedem Pfeil an, welche Transition dabei schalten muss. Achten Sie darauf, dass von jeder Markierung für jede Transition, die enabled ist, ein Pfeil weg­führt.

Wie erzeugt man für einen beliebigen Graphen den Erreichbarkeitsgraphen? Geben Sie dazu einen Algorithmus an.

 

 

 

Der Zustand eines Ablaufdiagrammes

Verschiedentlich wurde der Begriff Zustand verwendet, ohne dass er definiert wurde. Wieso ist man überhaupt an einem Zustand interessiert? Wenn Sie ein Occasionsauto kaufen, dann möchten Sie doch, dass das Auto in einem guten Zustand ist. Nur so haben Sie die Gewähr, dass sie das Auto noch eine gewisse Zeit benutzen können. Der Zustand des Autos lässt sich durch eine Reihe von Zustandsvaria­blen charakterisieren, so z.B. den Kilometerstand, die Zylinderkompression, Anzahl Roststellen und vieles mehr. Der Zustand des Autos entstand durch den Gebrauch des Autos in der Vergangenheit. Aus­ser vielleicht für Detektive ist die Geschichte des Autos nicht mehr interessant, wenn man den Zu­stand des Autos genau kennt. Der Zustand ist also diejenige Information über ein System, die nötig ist, um dessen Verhalten für ausgewählte, zukünftige Ereignisse vorhersagen zu können, ohne dass man die Vergangenheit kennt.

Ueberträgt man dies auf ein Ablaufdiagramm, so stellt sich die Frage, was vom Ablaufdiagramm be­kannt sein muss, damit man das Verhalten vorhersagen kann, wenn eine Schaltbedingung wahr wird. Der im vorangehenden Abschnitt eingeführte Erreichbarkeitsgraph eines Ablaufdiagrammes zeigt die Lösung für dieses Problem. Der Erreichbarkeitsgraph ist also Zustandsdarstellung eines Ablaufdiagrammes. Jedes Muster von Markierung stellt einen Zustand des Ablaufdiagrammes dar.