Nachdem wir die Modellierung von Zustandsautomaten und ihre Realisierung mit Hilfe von Switch-Anweisung und Tabelle kennengelernt haben, schauen wir uns nun eine objektorientierte Implementierungsvariante an: das State Pattern. Anschließend vergleichen wir die drei Varianten.
Das Software-Entwurfsmuster State Pattern verwenden etwa Spring Statemachine, Boost Meta State Machine (MSM) oder das Qt State Machine Framework. Es zählt zu den Verhaltensmustern (behavioral design patterns) und kapselt das zustandsabhängige Verhalten eines Objekts nach außen hin. Jeder Zustand ist als eine eigene Klasse implementiert, die das Verhalten des Automaten in diesem Zustand definiert. Alle Zustandsklassen leiten sich von einem gemeinsamen Interface ab, so dass sich sämtliche Zustände einheitlich behandeln lassen.
Das Klassendiagramm der Jalousiesteuerung sieht so aus:
Das Interface State definiert diejenigen Methoden, deren Verhalten zustandsabhängig ist. Neben den mit raise… beginnenden Methode zum Auslösen eines Event gibt es hier die Methode getName, die den Name des Zustands zurückgibt.
Die Klasse StateMachine repräsentiert den Zustandsautomaten. Sie verwaltet die dem aktiven Zustand entsprechende Klasse und damit das zustandsspezifische Verhalten im Attribut activeState. Damit ähnelt das State Pattern dem Strategy Pattern, wobei ein Zustand einer Strategie entspricht, sprich: der Implementierung eines konkreten Verhaltens. Während die Strategie im Strategy Pattern aber von außen gesetzt wird, kümmern sich die Zustände im State Pattern selbst darum. Wenn man so will, ersetzt im State Pattern eine "Strategie" sich selbst durch eine andere, oder in der richtigen Nomenklatur: Ein Zustand aktiviert seinen Folgezustand selbst.
Schauen wir uns das am Beispiel näher an: Die Client-Anwendung sendet Nachrichten an den Zustandsautomaten, indem sie StateMachine-Methoden aufruft. Nehmen wir an, der Benutzer drückt die [↓]-Taste. Der Client informiert den Zustandsautomaten über diese Aktion durch Aufruf der Methode raiseUserDown. Die Reaktion des Automaten hängt vom aktiven Zustand ab:
public void raiseUserDown() {
activeState.raiseUserDown();
}
Was nun geschieht, entscheidet das Zustandsobjekt. Handelt es sich um ein Objekt der Klasse Idle, erfolgt ein Zustandsübergang zu Moving down. So sieht raiseUserDown in Idle aus:
public void raiseUserDown() {
stateMachine.activateState(new MovingDown(stateMachine));
}
Die Methode aktiviert den neuen Zustand durch Übergabe eines entsprechenden Zustandsobjekts an die StateMachine-Methode activateState, die es activeState zuweist.
Befindet sich der Automat hingegen im Zustand Moving down, soll beim Aufruf von raiseUserDown nichts geschehen. Die Klasse MovingDown implementiert diese Methode daher gar nicht. Es "zieht" vielmehr die raiseUserDown-Implementierung der Oberklasse AbstractState:
public void raiseUserDown() {
}
Diese Methode tut nichts und ignoriert somit das Ereignis – in unserem Fall ein sinnvolles Standardverhalten für alle Ereignisse, für die die jeweilige konkrete Zustandsklasse kein Verhalten implementiert.
Hier der Quellcode der Jalousiesteuerung in der Implementierung gemäß dem State Pattern. Der Zustandsautomat besteht aus sechs Klassen; hinzu kommt eine Client-Klasse, die den Automaten nutzt.
Das Interface State spezifiziert, was in der Beispielanwendung ein Zustand ist:
package de.itemis.state_machine.example.state_pattern;
public interface State {
public void raiseUserUp();
public void raiseUserDown();
public void raisePosSensorUpperPosition();
public void raisePosSensorLowerPosition();
public String getName();
}
Die abstrakte Klasse AbstractState implementiert den Bezug zur StateMachine und das Standardverhalten für Events, nämlich diese zu ignorieren:
package de.itemis.state_machine.example.state_pattern;
abstract public class AbstractState implements State {
protected StateMachine stateMachine;
public AbstractState(StateMachine stateMachine) {
this.stateMachine = stateMachine;
}
public void raiseUserUp() {
}
public void raiseUserDown() {
}
public void raisePosSensorUpperPosition() {
}
public void raisePosSensorLowerPosition() {
}
abstract public String getName();
}
Die Klassen Idle, MovingUp und MovingDown repräsentieren die drei konkreten Zustände:
package de.itemis.state_machine.example.state_pattern;
public class Idle extends AbstractState {
public Idle(StateMachine stateMachine) {
super(stateMachine);
}
@Override
public void raiseUserUp() {
stateMachine.activateState(new MovingUp(stateMachine));
}
@Override
public void raiseUserDown() {
stateMachine.activateState(new MovingDown(stateMachine));
}
@Override
public String getName() {
return "Idle";
}
}
package de.itemis.state_machine.example.state_pattern;
public class MovingUp extends AbstractState {
public MovingUp(StateMachine stateMachine) {
super(stateMachine);
}
@Override
public void raiseUserDown() {
stateMachine.activateState(new Idle(stateMachine));
}
@Override
public void raisePosSensorUpperPosition() {
stateMachine.activateState(new Idle(stateMachine));
}
@Override
public String getName() {
return "Moving up";
}
}
package de.itemis.state_machine.example.state_pattern;
public class MovingDown extends AbstractState {
public MovingDown(StateMachine stateMachine) {
super(stateMachine);
}
@Override
public void raiseUserUp() {
stateMachine.activateState(new Idle(stateMachine));
}
@Override
public void raisePosSensorLowerPosition() {
stateMachine.activateState(new Idle(stateMachine));
}
@Override
public String getName() {
return "Moving down";
}
}
package de.itemis.state_machine.example.state_pattern;
public class StateMachine {
public StateMachine() {
activateState(new Idle(this));
}
State activeState = null;
public void activateState(State state) {
activeState = state;
}
public State getActiveState() {
return activeState;
}
public void raiseUserUp() {
activeState.raiseUserUp();
}
public void raiseUserDown() {
activeState.raiseUserDown();
}
public void raisePosSensorUpperPosition() {
activeState.raisePosSensorUpperPosition();
}
public void raisePosSensorLowerPosition() {
activeState.raisePosSensorLowerPosition();
}
}
Und so wird der Zustandsautomat vom Anwendungscode aus genutzt:
package de.itemis.state_machine.example.state_pattern;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Example {
public static void main(String[] args) throws IOException {
StateMachine stateMachine = new StateMachine();
stateMachine.activateState(new Idle(stateMachine));
BufferedReader console = new BufferedReader(new InputStreamReader(System.in));
while (true) {
System.out.println("Active state: " + stateMachine.getActiveState().getName());
System.out.print("Please enter event number! ");
System.out.print("1: User.up, 2: User.down, 3: PosSensor.upperPosition, ");
System.out.println("4: PosSensor.lowerPosition");
String line = console.readLine();
int eventNr = -1;
try {
eventNr = Integer.parseInt(line);
} catch (NumberFormatException ex) {
eventNr = -1;
}
switch (eventNr) {
case 1:
stateMachine.raiseUserUp();
break;
case 2:
stateMachine.raiseUserDown();
break;
case 3:
stateMachine.raisePosSensorUpperPosition();
break;
case 4:
stateMachine.raisePosSensorLowerPosition();
break;
default:
System.out.println("Unknown event number: " + eventNr + ".");
break;
}
}
}
}
Übrigens ist für das State Pattern nicht zwingend eine objektorientierte Programmiersprache nötig. Es lässt sich auch mit einer imperativen Sprache umsetzen, sofern diese über Funktionszeiger verfügt, wie beispielsweise C. Der Wesenskern des State Patterns ist, dass der aktive Zustand auf Ereignisse reagiert und gegebenenfalls einen anderen Zustand aktiviert.
Bei einer C-Implementierung gehört zu jedem Zustand eine Funktion ("Zustandsfunktion"), die diese Aktionen implementiert. Der Zustandsautomat merkt sich den aktiven Zustand durch einen Zeiger auf dessen Zustandsfunktion. Diese liefert als Rückgabewert den Zeiger auf den nächsten Zustand, genau: auf dessen Zustandsfunktion.
Für "richtige" Computer wie Notebooks, Desktop-PCs oder Server fallen die Unterschiede zwischen den betrachteten Implementierungsansätzen nicht wirklich ins Gewicht. Anders sieht es bei eingebetteten Geräten (embedded devices) aus, die in puncto Speicherplatz oder CPU-Leistung typischerweise stark eingeschränkt sind. Hier lautet die klare Antwort: Es kommt darauf an.
Erfahrungsgemäß sind Zustandsautomaten sehr schnell. Bei einem Zustandsautomaten mit wenigen Zuständen und wenigen Events lohnen sich Optimierungsüberlegungen daher kaum. Anders sieht es bei einer hohen Anzahl von Zuständen oder Events aus. Es soll an dieser Stelle allerdings nicht darum gehen, was genau eine "hohe" Anzahl ist – 500?, 50.000?, 5 Millionen? –, sondern lediglich um einige grundsätzliche Überlegungen.
Eine hohe Anzahl von Zuständen bedeutet:
Ist die Zahl der Events hoch, heißt das:
In allen Implementierungsansätzen setzt sich die Ausführungszeit aus folgenden Elementen zusammen:
Für die Suche nach dem aktiven Zustand führt die Switch-Anweisung mindestens einen Vergleich aus, nämlich dann, wenn der erste Fall der Switch-Anweisung bereits der aktive Zustand ist. Schlimmstenfalls benötigt die Switch-Anweisung so viele Vergleiche wie es Zustände gibt, nämlich dann, wenn erst die letzte Case-Klausel den aktiven Zustand behandelt. Sind alle Zustände gleich häufig aktiv, führt die Switch-Anweisung im Mittel z/2 Vergleiche durch, wobei z die Anzahl der Zustände ist. Die Ausführungszeit liegt also in der Größenordnung O(z). Es folgt die Analyse, ob bestimmte Events vorliegen, die die entsprechenden Transitionen auszulösen. Die Ausführungszeit hierfür liegt – mit ähnlicher Überlegung wie bei den Zuständen – in der Größenordnung O(e), wobei e die Anzahl der Event-Typen ist.
Der Zeitbedarf für die Suche in einer eindimensionalen Zustandsübergangstabelle liegt ebenfalls bei O(z) + O(e). Der erste Term beschreibt die zeilenweisen Suche nach dem aktiven Zustand, der zweite Term steht für die Suche nach einem Event innerhalb der Zeile. Führen vom aktiven Zustand mehrere Transitionen zu unterschiedlichen Folgezuständen, so sind im Allgemeinen mehrere Zeilen zu durchsuchen. An der Größenordnung des Laufzeitbedarfs ändert das aber nichts.
Der objektorientierte Ansatz punktet mit einem Zeitbedarf, der von der Anzahl der Zustände unabhängig ist. Da der aktive Zustand bereits als Objekt vorliegt, liegt der Zeitbedarf für die "Suche" nach dem aktiven Zustand in der Größenordnung O(1). Der Aufruf der dem Event entsprechenden Methode kommt hinzu. Auf den ersten Blick mag das ebenfalls nach O(1) aussehen, doch dürfte der Aufwand abhängig von der jeweiligen Sprache und Laufzeitumgebung konservativ geschätzt eher bei O(e) liegen.
Switch-Anweisung wie Zustandsübergangstabelle müssen sämtliche Kombinationen aus Zustand und Event entweder im Programmcode der Switch-Anweisung oder in den Tabellendaten berücksichtigen. Der Speicherbedarf liegt daher in beiden Fällen in der Größenordnung O(z · e). Allerdings belegt die Tabelle davon immer den vollen Umfang, auch wenn sie nur spärlich besetzt ist. Die Switch-Anweisung hingegen braucht nur diejenigen Zustand-/Event-Kombinationen zu kodieren, bei denen ein Event zu einer Transaktion führt. Andererseits belegt ein Funktionszeiger in der Tabelle nur den Speicherplatz einer Adresse, was im Allgemeinen weniger sein dürfte, als der Code einer einzelnen Zustand-/Event-Kombination im Mittel belegt.
Im State Pattern enthält jede Zustandsklasse eine Methode für jedes Event, das der jeweilige Zustand berücksichtigt. Wir haben es also ebenfalls mit der Größenordnung O(z·e) zu tu n. Ähnlich wie bei der Switch-Anweisung brauchen aber nur diejenigen Event-Methoden kodiert zu werden, die etwas anderes bewirken sollen als das in der abstrakten Oberklasse implementierte allgemeine Verhalten für dieses Event. Nur diese Methoden benötigen Speicherplatz für den Programmcode.
Zu bedenken ist, auf welchen Geräten ein Zustandsautomat laufen soll. Objektorientierte Sprachen benötigen in der Regel eine umfangreiche Laufzeitumgebung und mehr RAM, was den Einsatz auf eingebetteten Geräten einschränken oder verhindern kann. Je mehr Programmteile in das unveränderliche ROM passen, desto besser. Ausführbarer Code wie in der Switch-Anweisung fällt in diese Kategorie, ebenso festkodierte Zustandsübergangstabellen. Bei einer objektorientierten Implementierung des State Patterns sollte man statische Zustandsobjekte wiederverwenden statt stets dynamisch neue Objekte im RAM zu erzeugen.
Wichtig ist auch, wie leicht sich eine Statechart-Anwendung während der Entwicklung debuggen lässt. Der Entwickler möchte an bestimmten Stellen seiner Anwendung gern Breakpoints setzen. Dort soll die Anwendung anhalten, damit er sie Schritt für Schritt ausführen und analysieren kann, warum sie sich nicht wie erwartet verhält. In einer State-Klasse ist das recht einfach. Auch Switch-Anweisungen eignen sich. Bei Tabellen kann der Entwickler zwar Breakpoints in den Funktionen setzen, auf die die Funktionsszeiger in der Tabelle verweisen. Aber wenn diese Zeiger in den falschen Zellen stehen, ist die Analyse knifflig.
Überhaupt ist der Code von Zustandsautomaten im Allgemeinen weder übersichtlich noch anschaulich oder verständlich. Am besten schneidet das State Pattern ab, denn es vermeidet eine unübersichtliche und schwer lesbare Switch-Anweisung. Solange ein Zustand nicht zu viele unterschiedliche Events behandeln muss, bleibt er überschaubar. Neue Zustände erfordern lediglich neue Zustandsklassen; eine Änderung des Verhaltens beschränkt sich auf eine Änderung der betroffenen Zustände. Insgesamt verringert sich der Wartungsaufwand.
Bei Automaten mit wenigen Zuständen hingegen lohnt sich der Aufwand einer objektorientierten Implementierung nicht unbedingt, weil die Switch-Anweisung in diesem Fall gar nicht so unübersichtlich wäre.
Falls ein State-Machine-Framework zur Verfügung steht und sich vom Ressourcenbedarf her für die Zielplattform eignet, sollte es zum Einsatz kommen. Verständlichkeit und Wartbarkeit kann das nur gut tun.
Alle vorgestellten Implementierungsvarianten kranken prinzipbedingt an einer Reihe von Nachteilen:
Implementierungsaufwand und -komplexität schreien geradezu nach Tool-Unterstützung, so dass sich der Entwickler im Idealfall nur noch um das graphische Statechart zu kümmern braucht. Das werden wir uns im folgenden Teil dieser Serie am Beispiel YAKINDU Statechart Tools näher anschauen.
Übrigens: Alle Blogartikel aus dieser Serie auf einen Blick gibt es mit unserem kostenlosen Whitepaper.