Modellieren mit Zustandsautomaten (Teil 4): Darstellung als Tabelle

In den ersten Teilen unserer Serie "Modellieren mit Zustandsautomaten" haben wir uns die Grundlagen von Zustandsautomaten und der graphischer Modellierung (lest hier Teil 1 und Teil 2) angesehen sowie die Realisierung mit Hilfe einer Switch-Anweisung kennengelernt.

Ein weiterer Ansatz, der in der Automatentheorie gern verwendet wird und den wir uns in diesem Teil anschauen möchten, sind Zustandsübergangstabellen (State transition tables) zur Spezifikation von Zustandsautomaten. Ausgangs- und Zielzustände sowie die Events, die zu einer Transition vom Ausgangs- zu einem Zielzustand führen, sind in einer Tabelle gelistet, die die Implementierung wiederholt konsultiert.

Eindimensionale Zustandsübergangstabelle

Eine eindimensionale Zustandsübergangstabelle definiert pro Zeile einen Zustandsübergang. Im einfachsten Fall enthält die Tabelle zwei Spalten: Die eine umfasst alle Ausgangszustände, die andere die jeweils zugeordneten Folgezustände.

Für eine Verkehrsampel sieht das so aus:

Die Wirklichkeit ist natürlich komplexer. Eine Ampel soll ja nicht in Bruchteilen von Sekunden durch die Zustände hetzen, sondern eine gewisse Zeit im jeweils aktuellen Zustand verharren und erst danach in den nächsten Zustand wechseln.

Dieses Verhalten lässt sich durch einen langsamen Takt von, sagen wir, zehn Sekunden sehr grob annähern. Der Zustandsautomat schaut bei jedem Takt – also alle zehn Sekunden – in die Tabelle, prüft, was der aktuelle Zustand ist und wechselt abhängig davon in den Folgezustand.

Das Ergebnis wäre allerdings immer noch sehr unbefriedigend, weil die Gelbphasen auf diese Weise viel zu lang und die Rot- und Grünphasen viel zu kurz wären. Wir brauchen unterschiedliche Verweildauern in den einzelnen Phasen. Das lässt sich mit zeitgesteuerten Events erreichen, siehe Teil 2 dieser Serie.

Der Wechsel vom Zustand Rot zu Rot-Gelb beispielsweise erfolgt erst nach Eintritt des Ereignisses 20 s vergangen.

In eindimensionalen Zustandsübergangstabellen ist jedem Event üblicherweise eine eigene Tabellenspalte zugeordnet. Diejenigen Zustandsübergänge (= Tabellenzeilen), die nur dann stattfinden sollen, wenn dieses Event vorliegt, enthalten in der entsprechenden Zelle ein Häkchen, etwa so:

Die erste Zeile beschreibt den Zustandsübergang von Rot nach Rot-Gelb. Da in der Spalte 20 s vergangen in dieser Zeile ein Häkchen gesetzt ist, erfolgt die Transition erst, nachdem dieses Ereignis eingetroffen ist. Die Events 3 s vergangen und 30 s vergangen sind hier unerheblich, da das Häkchen dort fehlt.

Jalousie mit Zustandsübergangstabelle steuern

Ein weiteres Beispiel ist die Jalousiesteuerung. Deren Zustandsübergangstabelle sieht so aus:

Zustandsübergangstabelle im Quellcode

Diese Tabelle lässt sich recht einfach in den Quellcode der gewünschten Programmiersprache umsetzen. Beispiele in Java haben wir bereits gesehen, daher hier etwas für C-Programmierer:

#include <stdbool.h>
#include <stdio.h>

enum states {
    INITIAL, IDLE, MOVING_UP, MOVING_DOWN
};

enum columns {
    SOURCE_STATE,
    USER_UP, USER_DOWN, POSSENSOR_UPPER_POSITION, POSSENSOR_LOWER_POSITION,
    TARGET_STATE
};

#define ROWS 7
#define COLS 6
int state_table[ROWS][COLS] = {
/*        source,      up,    down,  upper, lower, target */
        { INITIAL,     false, false, false, false, IDLE },
        { IDLE,        true,  false, false, false, MOVING_UP },
        { IDLE,        false, true,  false, false, MOVING_DOWN },
        { MOVING_UP,   false, true,  false, false, IDLE },
        { MOVING_UP,   false, false, true,  false, IDLE },
        { MOVING_DOWN, true,  false, false, false, IDLE },
        { MOVING_DOWN, false, false, false, true,  IDLE }
};

Das Enum states enthält symbolische Bezeichnungen der Zustände, was das Erstellen der Tabelle state_table vereinfacht. Das Enum columns ordnet den Spaltennummern symbolische Bezeichnungen zu. So braucht das untenstehende Beispielprogramm die Spalten mit den Ausgangs- und Zielzuständen nicht mit ihren absoluten Indizes 0 und 5 anzusprechen, sondern verwendet die symbolischen Namen SOURCE_STATE und TARGET_STATE.

Die symbolischen Bezeichnungen der Events benötigt das Beispielprogramm zwar nicht, sie sind aber hilfreich für die manuelle Pflege der Zustandsübergangstabelle.

Die Tabelle state_table spezifiziert den Zustandsautomaten rein deklarativ. Ändert sich der Automat, sind nur Anpassungen an der Tabelle nötig. Diese bleibt übersichtlich, solange die Anzahl der Zustände und der Events klein ist. Wenn deren Anzahl steigt, bleiben Übersichtlichkeit und Wartbarkeit der Tabelle allerdings auf der Strecke.

Immerhin bleibt der eigentliche Programmcode unverändert – ein Vorteil, weil Änderungen einfacher und weniger fehlerträchtig sind.

Den ersten Teil der Beispielimplementierung in C haben wir bereits gesehen; gleich folgt die Funktion main, die sich unmittelbar daran anschließt. Das Programm fragt nach der Nummer des nächsten Events, die der Benutzer über die Standardeingabe eingibt. Die Event-Nummern entsprechen der Position des Events in columns, also USER_UP = 1, USER_DOWN = 2 und so weiter.

Daraufhin konsultiert der Automat die Tabelle. Findet er eine Transition, die das eingegebene Event auslöst, informiert das Programm den Benutzer über die betreffende Zeile und Spalte in der Tabelle und gibt die Nummer des neuen Zustands aus. Diese Nummern entsprechen der jeweiligen Position in der Enumeration states. Die Implementierung verwendet dabei keinen festen Takt, sondern arbeitet rein ereignisgesteuert.

int main(int argc, char** argv) {
    int activeState = INITIAL;
    int event = -1;
    while (true) {
        int row, col;
        bool checkRows = true, checkCols;
        printf("Active state: %d\n", activeState);
        printf("Event: %d\n", event);

        /* Look for a row with the active state in the SOURCE_STATE column: */
        for (row = 0; checkRows && row < ROWS; row++) {
            checkCols = true;
            if (activeState == state_table[row][SOURCE_STATE]) {
                /* Found a row matching the active state. */
                /* Now check the columns for events triggering this transition: */
                for (col = SOURCE_STATE + 1; checkCols && col < TARGET_STATE; col++) {
                    if (state_table[row][col]) {
                        /* Found one. The current event must match this column
                         * to trigger the transition. */
                        if (event == col) {
                            /* The event matches. Let's do the transition: */
                            printf("Active state and event matching row %d, column %d.\n", row, col);
                            printf("Transitioning to target state %d\n", activeState);
                            activeState = state_table[row][TARGET_STATE];
                            /* Stop checking any further rows and columns: */
                            checkRows = checkCols = false;
                        } else {
                            /* The event does not match, so this transitions won't be triggered.
                             * We do not need to check any remaining columns: */
                            checkCols = false;
                        }
                    }
                }
                if (checkCols) {
                    /* At this point, we have checked all columns, but none of them requires an event
                     * for this transition. So we can do the transition in any case: */
                    printf("Transitioning without any event to target state %d\n", activeState);
                    activeState = state_table[row][TARGET_STATE];
                    checkRows = false;
                }
            }
        }
        printf("Active state: %d\n\n", activeState);
        printf("Please enter event number!\n");
        scanf("%d", &event);
    }
}

Bedingungen und Aktionen

Anders als im Beispiel hängen Transitionen in der Regel neben Events auch von zusätzlichen Bedingungen (Guard Conditions) ab. Das heißt, eine Transition "zieht" nur dann, wenn nicht nur das richtige Event vorliegt, sondern zugleich auch die Guard Condition erfüllt ist. In der Implementierung gehört zu einer Transition dann eine Funktion, die die Bedingung prüft.

Die Zustandsübergangstabelle kodiert dann nicht mehr nur Wahrheitswerte, sondern Zeiger auf diese Auswertungsfunktionen. Bei objektorientierten Sprachen kann das auch ein Objekt sein, das die Auswertungsfunktion enthält.

Steht in einer Tabellenzelle der Wert null, entspricht das false, das heißt, es gibt keine Transition für diese Kombination aus Zustand und Ereignis. Enthält die Tabelle jedoch einen Wert ungleich null, handelt es sich um den Zeiger auf eine Auswertungsfunktion. Dies entspricht zunächst true; die Transition kommt also prinzipiell in Frage.

Die Implementierung ruft nun die Funktion auf. Diese prüft die Guard Condition und teilt über ihren Rückgabewert mit, ob der Automat die Transition tatsächlich durchführen soll oder nicht.

Mit Transitionen und Zuständen können Aktionen verknüpft sein. Wollen wir diese ebenfalls berücksichtigen, überlassen wir auch dies den Funktionen, auf die die Zustandsübergangstabelle verweist. Eine solche Funktion prüft dann nicht nur die Guard Condition, sondern aktiviert, falls die Bedingung erfüllt ist, selbst den Folgezustand.

Konzepte wie Orthogonalität, zusammengesetzte Zustände oder History States mit einer Tabelle umsetzen, ist schwierig. Von der Theorie her existiert zwar für jedes dieser Konstrukte eine äquivalente Darstellung als flacher Zustandsautomat, allerdings explodiert dann der Zustandsraum sehr schnell.

Um beispielsweise orthogonale Bereiche in einem flachen Zustandsautomaten abzubilden, muss es dort einen eigenen Zustand für jede Permutation der aktiven Zustände in den orthogonalen Bereichen geben. Die Anzahl dieser Zustände ergibt sich durch das Kreuzprodukt der Zustände in den orthogonalen Bereichen. Bei zwei orthogonalen Bereichen mit je drei Zuständen mögen neun flache Zustände noch erträglich sein, doch sind es bei zehn orthogonalen Bereichen mit je acht Zuständen bereits 810 flache Zustände. Das ist mehr als eine Milliarde.

Zweidimensionale Zustandsübergangstabelle

Zweidimensionale Transitionstabellen sind im Allgemeinen kompakter als eindimensionale, weil pro Ausgangszustand eine einzige Zeile reicht. In den Zellen, in denen sich Ausgangszustandszeilen mit Ereignisspalten schneiden, ist der jeweilige Zielzustand notiert. In der folgenden Tabelle führt im Zustand Idle (zweite Zeile, Überschrift zählt nicht mit) das Event User.down (dritte Spalte) zum Zielzustand Moving down.

Für die Implementierung gilt das zu eindimensionalen Tabellen Gesagte sinngemäß. Ein Wahrheitswert reicht für die Tabellenzellen nicht mehr aus, sondern es ist der jeweilige Zielzustand zu kodieren. Wollen wir die mit Transitionen verknüpften Guard Conditions und Aktionen berücksichtigen, brauchen wir einen Zeiger auf eine Funktion, die der Transition entspricht und den Folgezustand implizit enthält. Das sind in der Regel durchaus unterschiedliche Funktionen für denselben Folgezustand.

In den folgenden Teilen dieser Reihe werden wir nach Switch-Anweisung und Zustandsübergangstabellen noch das objektorientierte Software-Entwurfsmuster State Pattern kennenlernen. Wir werden die drei verschiedenen Implementierungsansätze miteinander vergleichen – und sehen, wie wir uns dank automatischer Codegenerierung mit YAKINDU Statechart Tools den gesamten Implementierungsaufwand einsparen können.

Übrigens: Wer alle Teile unserer Blogserie auf einen Blick haben möchte, kann sich hier unser kostenloses Whitepaper herunterladen.