Automat mit Ablaufdatum

Mit Zustandsautomaten erfolgreich Systeme modellieren
Kommentare

Die Welt ist voller Vorgänge, deren Verhalten in Modi eingeteilt werden können. Informatiker fassen auf diesem Pattern basierende Programme unter dem Begriff Zustandsautomaten oder Finite State Machines zusammen. In diesem Artikel stellen wir Ihnen Prinzip und Funktionsweise solcher Zustandsautomaten vor.

Es gibt kaum einen Programmierer, der im Rahmen seiner Tätigkeit noch nie Kontakt mit Finite State Machines (FSMs) hatte. Das Designpattern ist bei der Realisierung von Parsern, dem Bearbeiten von Netzwerkanfragen und dem Modellieren realer Systeme von gleichermaßen hoher Bedeutung. Aufgrund des vergleichsweise einfachen inneren Aufbaus bringt die Nutzung eines Zustandsautomaten wesentliche Vorteile. Programme lassen sich in einzelne Stufen unterteilen, jeder Zustand ist im Idealfall von seinen Kollegen unabhängig. Im Rahmen der Erstellung der Zustandstabelle ist eine gewisse Einarbeitung in die zu lösende Aufgabe notwendig: Wer den zu erledigenden Job nicht versteht, scheitert meist schon bei der Definition der Zustände. Zu guter Letzt ist die Implementierung alles andere als komplex – eine FSM stellt in vielen Fällen den kürzesten Weg zum funktionsfähigen Programm dar.

Eine Frage der Begrifflichkeiten

Systemtechnische Themen lassen sich oft am einfachsten verstehen, wenn man sich ihnen schrittweise nähert und sie anhand konkreter Beispiele illustriert. Wir wollen uns in den folgenden Schritten mit der Modellierung einer Kaffeemaschine auseinandersetzen, die zweistufigen Milchkaffee zusammenbaut. Die Definition des Begriffs Automat lässt sich aus der theoretischen Informatik übernehmen. Es handelt sich dabei um ein System, das auf eine Eingabefolge mit Zustandsänderungen reagiert. Die primäre Rolle des Automaten besteht darin, unter Berücksichtigung von Eingabe und Jetzt-Zustand in einen Folgezustand zu wechseln. Für die folgenden Schritte wollen wir einen Zustand als eine Art Betriebsmodus auffassen. Unsere Kaffeemaschine kann schlafen, Kaffee brauen, Milch schäumen und nach Fertigstellung des Getränks piepsen. Jeder dieser Modi bedingt seine ureigene Konfiguration der Hardware und der dazugehörenden Betriebssoftware.

Ereignisse lösen Zustandswechsel (engl. Transitions) aus. Im Fall unserer Kaffeemaschine wäre dies beispielsweise das Drücken des Einschaltknopfs, der das Gerät aus seinem Schlummer reißt und zum Anfertigen von Espresso animiert. Mit diesem Wissen können wir uns an die Realisierung des Zustandsdiagramms unserer Kaffeemaschine wagen (Abb. 1). Kreise beschreiben Zustände, während die Pfeile die dazugehörigen Transitionen festlegen.

Abb. 1: Eine Kaffeemaschine als Zustandsautomat

Abb. 1: Eine Kaffeemaschine als Zustandsautomat

In den USA werden Zustandsautomaten gern in Analogie zur objektorientierten Programmierung (OOP) gesetzt. Die Idee dahinter ist, dass ein auf den Prinzipien der OOP basierendes Softwareprodukt seine Komplexität durch die Aufteilung in Klassen reduziert.

Ein Zustandsautomat erreicht durch seine scharf voneinander abgegrenzten Zustände einen ähnlichen Effekt: Eine FSM muss sich nur mit jenen Eingaben befassen, die im momentanen Betriebszustand von Relevanz sind. Dies führt in vielen Situationen zu einer nicht unwesentlichen Reduktion des Gesamtaufwands. In unserem Fall könnte die Maschine das Abfragen des Startknopfs während des Brauprozesses einstellen.

Zustandsautomat, ganz easy

Wer das Internet nach Möglichkeiten zur Realisierung eines Zustandsautomaten durchforstet, findet eine Vielzahl von mehr oder weniger anspruchsvollen Designvorgaben. Bei kleineren Maschinen mit wenigen Zuständen ist es oft am einfachsten, auf ein Switch-Statement und eine globale Variable zurückzugreifen.

Folgendes Beispiel (Listing 1) stammt aus einem vom Unternehmen des Autors entwickelten Spiel (ein Klon von JezzBall) für Palm OS, bada und Symbian OS. Die Routine war im Laufe ihres Lebens auf tausenden von Telefonen im Einsatz, ohne je Probleme zu verursachen.

Listing 1

void setState(Boolean invoked_to_erase_lvls) 
{
  if(enginestate==STATE_MENU) 
  {
    paused=false;
    //To prevent game from freezing when entering this via the intersection menu
   textparams[0].active=true; 
   textparams[0].position.topLeft.x=20;
   textparams[0].position.topLeft.y=20;
   StrCopy(textparams[0].text,"New game");
    . . .
  }
  else if(enginestate==STATE_DIFF)
  {
    textparams[0].active=true; 
    . . . 
  }
}

setState() wird von der Spiellogik aufgerufen, wenn eine Änderung des Betriebszustands notwendig ist. Sie parametriert die diversen globalen Variablen neu, um die Grafik-Engine und die künstliche Intelligenz an die Bedürfnisse der aktuellen Spielsituation anzupassen.

Eine Frage des Typs

Systemtechniker unterteilen Zustandsautomaten in zwei nach ihren Erfindern als „Moore“ und „Mealy“ bezeichnete Klassen. Obwohl die Unterschiede in der Praxis von nicht allzu hoher Bedeutung sind, wollen wir uns die beiden Systeme zwecks Inspiration kurz ansehen.

Zustandsautomaten sind zum „Parsen“ von Texten geradezu ideal geeignet. Aus diesem Grund wollen wir eine Maschine betrachten, die bei der Eingabe von a b b mit 1 reagiert. Alle anderen Eingabefolgen sollen mit einer 0 quittiert werden. Abbildung 2 zeigt die Realisierung nach dem Moore-Schema, während Abbildung 3 eine nach dem Mealy-Schema aufgebaute FSM zeigt.

Abb. 2: Die Realisierung als Moore-Automat setzt vier Zustände voraus

Abb. 2: Die Realisierung als Moore-Automat setzt vier Zustände voraus

Abb. 3: Mealy-Automaten kommen oft mit weniger Arbeitsschritten aus

Abb. 3: Mealy-Automaten kommen oft mit weniger Arbeitsschritten aus

Betrachten Sie die in Dokumentenblau gehaltenen Ausgabewerte beider Maschinen. Bei der Moore-Maschine ist der Ausgabezustand nur vom erreichten Zustand abhängig. Dies wird dadurch ausgedrückt, dass der Ausgabewert in der „Blase“ des jeweiligen Zustands angegeben ist. Mealy-Maschinen unterscheiden sich, da die Ausgabewerte hier von der durchlaufenen Transition abhängig sind. Daraus folgt, dass ein Zustand mit mehreren verschiedenen Ausgabewerten einhergehen kann.

Moore- und Mealy-Automaten lassen sich ohne allzu großen Aufwand in die jeweils andere Form umrechnen. Leider führt die Transformation in Richtung des Moore-Automaten oft zu enorm komplexen Automaten, die sich – Stichwort UML-Tapete – nicht mehr ohne weiteres grafisch darstellen lassen.

Elektroniker kennen eine vereinfachte Form des Moore-Automaten, die nach seinem Erfinder Ju. T. Medwedew als Medwedew-Automat bezeichnet wird. Er unterscheidet sich vom Moore-Automaten insofern, als der gerade aktuelle Zustand gleichzeitig auch den Ausgabewert der FSM darstellt. Bei der Realisierung als digitaler Schaltkreis ergibt sich daraus eine mehr oder weniger signifikante Vereinfachung des Aufbaus.

Array-basierter Zustandsautomat

Unser weiter oben vorgestellter JezzBall-Klon hatte keine besonders komplexe innere Struktur. Bei größeren Maschinen führt die Realisierung auf Basis einer setState()-Funktion samt externer Verwaltungslogik schnell zu unübersichtlichem Code: Das gute Dutzend Zustandswechsel des Spiels namens BallZ war über acht verschiedene Codedateien verteilt.

Da die Änderungen von Zustand zu Zustand normalerweise einem festen Regelwerk folgen, bietet sich die Nutzung eines zu einer Art Lookup-Tabelle umfunktionierten zweidimensionalen Arrays an. Diese insbesondere in den vereinigten Staaten verbreitete Methode wirkt auf den ersten Blick erschlagend, weshalb wir sie anhand eines kleinen Beispiels (Listing 2) näher ansehen wollen.

Listing 2

//Zustände
#define STATE_SCHLAFE       0
#define STATE_KAFFEE        1
#define STATE_MILCH         2
#define STATE_TROETE        3
#define STATE_FEHLER        4
//Ereignisse
#define ERG_AUFWACHEN       0
#define ERG_KAFFEEFERTIG     1
#define ERG_MILCHFERTIG      2
#define ERG_TASSEWEG         3
int fsm[][]=
{
  //   SCHLAFE       KAFFEE        MILCH         TROETE
  {STATE_KAFFEE, STATE_FEHLER, STATE_FEHLER, STATE_FEHLER},
  {STATE_FEHLER, STATE_MILCH,  STATE_FEHLER, STATE_FEHLER},
  {STATE_FEHLER, STATE_FEHLER, STATE_TROETE, STATE_FEHLER},
  {STATE_FEHLER, STATE_FEHLER, STATE_FEHLER, STATE_SCHLAFE}
}

fsm wird hier mit einem Fehlerzustand ausgestattet, der bei ungültigen Ereignis-Zustands-Kombinationen zurückgegeben wird. Auf diese Art und Weise ist sichergestellt, dass eventuelle Fehler in der Tabelle zumindest bis zu einem gewissen Grad abgefangen werden.

Wenn unser Programm zwischen verschiedenen Zuständen wechseln möchte, wird das Array mit dem gerade aktuellen Zustand und dem aufgetretenen Ereignis versehen. Das Resultat ist der neue Zustand der Maschine: int newstate=fsm[zustand][event];

Derartige Zustandsautomaten weisen zwei Schwachpunkte auf. Erstens ist es nicht möglich, auf Zustandsänderungen „direkt“ zu reagieren. Zweitens wird die Verwaltung der Arrays ab einem gewissen Komplexitätsgrad umständlich – wer kein spezielles Programm wie die von QuantumLeaps angebotenen Programme (siehe http://www.state-machine.com/) zur Generation des Feldes einsetzt, verbringt jede Menge Zeit mit Fehlersuche und Syntaxkorrektur.

Pointer und mehr

Ein erster Schritt zur Vereinfachung dieses Patterns bestünde darin, das Array mit Funktions-Pointern zu befüllen. Das Programm müsste im Rahmen einer Statusänderung den zurückgegebenen Pointer ausführen, der die eigentlichen Anpassungen vornimmt.

Der seinerzeit bei Conman Laboratories arbeitende Mark Grosberg schlug in einem Essay zum Thema effiziente Zustandsautomaten eine neue und vergleichsweise radikale Abart dieser Vorgehensweise vor. Er realisierte die bisher als Integer ausgelegte Zustandsvariable in Form eines Funktions-Pointers. Der gerade aktuelle Zustand wird somit in Form eines Zeigers auf eine Funktion dargestellt:

typedef struct StateMachine TStateMachine; 
typedef void (*StateProc)(TStateMachine *sm, EIndication input);

void Idle(TStateMachine      *sm,  EIndication input); 
. . .

Eingehende Ereignisse werden fortan durch einen Aufruf der gerade aktuellen Zustandsmethoode abgebildet. Der darin enthaltene Code hat die Aufgabe, die Events den notwendigen Zustandsänderungen zuzuordnen:

void Dial(TStateMachine *sm, EIndication input) 
{ 
  switch (input) 
  { 
    case DIGITS_IND:
      sm->curState = Alerting;
      break; 
      . . .

Aber bitte mit C++

Unter C++ arbeitende Entwickler bevorzugen normalerweise Implementierungen, die auf einer Klassenhierarchie basieren. Im State-Pattern werden normalerweise zwei Klassen spezifiziert, die auf die Namen State und Machine hören. Machine enthält dabei eine als changeState bezeichnete Methode, die einen Zeiger auf ein Statusobjekt entgegennimmt. Dieses wird in einer Member-Variable abgelegt, die den momentanen Betriebszustand des Systems beschreibt:

class Machine
{
  public:
      void setState(State* _aState);
      void handleAnEvent(int _anEvent);
  private:
      State myState;
}

Die eigentliche „Intelligenz“ des Systems wird in Klassen realisiert, die von einer abstrakten Klasse namens State abgeleitet sind. Sie implementieren die von den diversen Status ausgehenden Reaktionen:

class State
{
  public:
      void handleA();
      void handleB();
      void handleC();
}
class aState:public State
{
  public:
      void handleA();
      void handleB();
      void handleC();
}

State dient hierbei als eine Art abstrakte Klasse, die die für die diversen Ereignisse notwendigen Behandlungsmethoden deklariert. Die eigentlichen Zustände entstehen durch Ableitungen, die die eigentlichen Ereignis-Handler weiterleiten. Machine muss die eingehenden Ereignisse sodann an die Handler-Funktionen des gerade aktiven Zustands weiterleiten. Diese können mitunter einen Zeiger auf das Machine-Objekt bekommen, um so den aktuellen Zustand verändern zu können.

Wenn Ihr Projekt auf Basis der Boost-Bibliothek entsteht, können Sie auf die im Framework enthaltene Statechart-Funktionalität zurückgreifen. Sie bietet diverse Hilfsobjekte an, die die Realisierung eines Zustandsautomaten erleichtern. Leider ist sie aufgrund des streng objektorientierten Aufbaus alles andere als einfach zu bedienen – Interessierte finden in der Dokumentation weitere Informationen zum Thema.

Zustandsautomat trifft Stack

Im Bereich der Computerspiele trifft man immer wieder auf Situationen, die sich in einem einzelnen Zustandsautomaten nicht ohne Weiteres abbilden lassen. Als klassisches Beispiel dafür sei eine Spielfigur angeführt, die ihre Aufgaben sowohl mit als auch ohne Waffe erledigen kann. Daraus folgt – normalerweise – eine nur schwer überschaubare Anzahl von Zuständen. Die Einheit kann beim Springen oder beim Laufen feuern: Wenn es noch dazu mehrere Waffengattungen zu berücksichtigen gilt, so gerät die Anzahl der Zustände bald komplett außer Kontrolle.

Dieses Problem lässt sich durch verschachtelte Zustandsklassen lösen. Der Sprungzustand wäre vom Standzustand abgeleitet. Eingehende Ereignisse werden je nach Bedarf „lokal“ gelöst oder an die Mutterklasse weitergeleitet, wo sie von den dafür zuständigen Methoden entgegengenommen werden.

In der Literatur findet sich zudem der Begriff „Pushdown-Automaton“ oder „Kellerautomat“. Dabei handelt es sich um einen Zustandsautomaten, dessen aktueller Status in Form eines Stacks gespeichert wird. Das bedeutet, dass der Automat mehrere Zustände gleichzeitig einnehmen kann. Jeder Zustand entscheidet selbst, ob er beim Einstellen eines neuen Zustands über den alten State geschoben wird oder ob dieser restlos ersetzt werden soll.

Wir wollen auch dies kurz anhand der soeben vorgestellten Spielfigur besprechen. Wenn der Spieler während des Springens einen Schussbefehl gibt, so wird der Stack mit einer Instanz des „Feuern“-Zustands bevölkert. Dieser verschwindet nach dem Abfeuern der Kartusche, wodurch der Soldat wieder in den normalen Sprungzustand zurückkehrt. Nach der Landung ist eine etwas andere Transformation erforderlich. Der Sprungzustand wird vom Stack gezogen und durch den Standzustand ersetzt.

Deterministisch?

Wer sich tiefer mit Zustandsautomaten befasst, stolpert irgendwann über die Begriffe deterministisch und nicht deterministisch. Da beide Systeme normalerweise nur beim Parsing von Sprachen zum Einsatz kommen, wollen wir sie auf Basis dieses Einsatzfelds unterscheiden.

In deterministischen Automaten führt eine Eingabe stets zu einer bestimmten Reaktion – wenn der Automat in einem bestimmten Zustand mit einem gewissen Symbol gefüttert wird, reagiert er darauf immer mit einer vorgegebenen Ausgabe. Ein nichtdeterministischer Zustandsautomat zeigt bei ein- und demselben Eingabezeichen verschiedene Reaktionen. Die Maschine darf dabei aus mehreren verschiedenen Zuständen mehr oder weniger zufällig wählen.

Fazit

Es gibt kaum ein größeres Programm, das komplett ohne Zustandsautomaten auskommt. Diomidis Spinellis’ 2003 erschienener Klassiker zum Thema Code Reading widmete dem Thema einige Seiten, in denen diverse Beispiele aus verschiedenen Open-Source-Projekten vorkamen.

FSMs sind bei der Realisierung von Parsern und Lexern besonders wichtig. Wer sich näher mit Regular Expressions auseinandersetzt, stellt über kurz oder lang eine Art „Äquivalenz“ zwischen den beiden Darstellungsformen dar: Ein Zustandsautomat ist und bleibt der beste Weg zum Verarbeiten eines regulären Ausdrucks.

Aufmacherbild: security guard watching video monitoring surveillance security system von Shutterstock / Urheberrecht: Dmitry Kalinovsky

Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -