Modellieren mit Zustandsautomaten (Teil 1)

In der Informatik geht es darum, mit Hilfe von Computern oder computergesteuerten Anlagen bestimmte Aufgaben zu lösen. Beispiele dafür sind die Erstellung eines Eisenbahnfahrplans, die Visualisierung von Neutronenfluß und Leistungsverteilung in einem Kernreaktor, die Simulation physikalischer Vorgänge in Halbleiterbauelementen, die Implementierung einer Social-Media-App oder die Entwicklung von Maschinensteuerungen unterschiedlichster Art. Nicht zuletzt sind zahlreiche Steuerungsprogramme in Embedded Devices zu finden.

Bevor es ans Programmieren geht, sollte ein Modell dessen vorliegen, was man per Software in die Praxis umzusetzen gedenkt. Ein Modell ist eine vereinfachte Darstellung der Wirklichkeit und verzichtet auf alles, was für die zu lösende Aufgabe unerheblich ist. Bei einer Kaffeemaschinensteuerung ist beispielsweise der Füllstand der Bohnen wichtig, die Farbe der Kaffeetasse oder das Geschlecht des Bedieners sind es nicht.

Das Modell sollte übersichtlich und gut verständlich sein und durch sinnvolle Strukturierung auch komplexe Zusammenhänge gut in den Griff bekommen. Verständliche Modelle sind nicht nur für Software-Architekten und Entwickler wichtig, sondern genauso auch für deren Auftraggeber, also Fachabteilungen und Kunden. An einem für ihn nachvollziehbaren Modell erkennt der Auftraggeber, ob die ITler die Aufgabenstellung korrekt verstanden haben. Fehler und Mißverständnisse lassen sich klären, bevor Aufwände in die Implementierung einer falschen Lösung fließen.

Bestimmte Aufgabenstellungen lassen sich besonders gut mit Hilfe von Zustandsautomaten beschreiben. Informatikstudenten lernen Zustandsautomaten auch als deterministische Automaten, endliche Automaten, Finite State Machines, Moore-, Mealy-, Harel-Automaten oder dergleichen in der Theoretischen Informatik kennen – und nicht selten bleiben Fragezeichen in den Gesichtern zurück, weil nicht klar ist, was das denn eigentlich soll.

Keine bloße Theorie – Zustandsautomaten zeigen Systemverhalten praktisch und anschaulich

Abseits aller Theorie soll dieser Beitrag einen praxisorientierten Einstieg in Zustandsautomaten geben. Hierbei handelt es sich nämlich um weit mehr als um ein bloßes theoretisches Konstrukt – sie sind bei der praktischen Arbeit ausgesprochen nützlich.

Zustandsautomaten eignen sich zur Beschreibung sogenannter ereignisdiskreter Systeme. Die Idee dabei ist, daß sich ein System immer in genau einem von endlich vielen Zuständen befindet. Ein Lichtschalter befindet sich immer in genau einem der beiden Zustände »An« oder »Aus«. Zustandsübergänge definieren, aus welchem Zustand (State) heraus sich welche anderen Zustände erreichen lassen – und unter welchen Voraussetzungen welcher Zustandsübergang erfolgt.

Bevor es hier doch noch theoretisch wird, schauen wir uns lieber ein konkretes Beispiel an: eine Jalousiesteuerung. Im einfachsten Fall kennt die Jalousiesteuerung drei Zustände:

  • Die Jalousie wird nicht bewegt (Zustand Idle).
  • Die Jalousie wird nach oben gefahren (Zustand Moving up).
  • Die Jalousie wird nach unten gefahren (Zustand Moving down).

Im Zustandsdiagramm werden Zustände als Rechtecke (mit abgerundeten Ecken, wenn man es genau nimmt) und Zustandsübergänge als Pfeile dargestellt:

Der dicke Punkt links markiert den Initialzustand des Automaten, also Idle. Drückt der Benutzer die [↑]-Taste, tritt also das Ereignis (Event) up ein, wechselt der Automat in den Zustand Moving up, und die Jalousie fährt nach oben. Sobald sie die obere Position erreicht hat, erzeugt der Positionssensor das Ereignis upperPosition. Dies sorgt für den Zustandsübergang, die Transition, von Moving up zurück nach Idle. Das Herunterfahren der Jalousie funktioniert analog, wenn der Benutzer die [↓]-Taste drückt. Das Zustandsdiagramm macht das dynamische Verhalten des Systems anschaulich.

Unser Modell ist allerdings noch sehr unvollkommen. Wir wollen die Jalousie ja nicht nur ganz oben oder ganz unten haben, sondern gern auch nach Bedarf dazwischen. Zusätzlich soll die Jalousie bei starker Sonnenstrahlung automatisch verdunkeln. Der Benutzer kann das manuell sofort stoppen oder rückgängig machen.

Bei starkem Wind soll die Jalousie immer nach oben fahren, um Beschädigungen zu vermeiden. Darüber kann sich der Benutzer nicht hinwegsetzen. Die Jalousie läßt sich erst dann wieder nach unten fahren, wenn der Wind nachgelassen hat. Denkbar ist zudem, die Jalousie zeitgesteuert hoch- und herunterzufahren.

Toolgestützte Entwicklung am Beispiel einer Jalousiesteuerung

Einige dieser Funktionen wollen wir im folgenden mit Hilfe eines Zustandsautomaten modellieren, aber natürlich nicht wie oben mit Stift und Zettel beziehungsweise Whiteboard. Wir brauchen ein vernünftiges Modellierungswerkzeug. Ich verwende dazu die federführend von meinem Brötchengeber itemis AG entwickelte Anwendung YAKINDU Statechart Tools (SCT). SCT ist quelloffen, eclipsebasiert und unterstützt nicht nur die Modellierung selbst, sondern auch die dynamische Simulation des Modells sowie die Generierung des Zustandsautomaten als Quellcode in verschiedenen Programmiersprachen. Aber dazu später mehr.

Zunächst setzen wir das Whiteboard-Modell eins zu eins mit SCT um. Wer das selbst nachvollziehen möchte, kann die Software unter http://statecharts.org/ kostenfrei herunterladen und findet dort eine Installationsanleitung sowie ein Fünf-Minuten-Tutorium für den Schnelleinstieg.

Modelliert mit SCT sieht unser Jalousiebeispiel so aus:

Links hinzugekommen ist der sogenannte Definitionsbereich, der die Namen der Ereignisse festlegt.

Um die Jalousie auf dem Weg nach oben oder unten an der aktuellen Position anzuhalten, drückt der Benutzer diejenige Taste, die der jeweiligen Bewegung entgegenläuft, beispielsweise [↓], wenn die Jalousie gerade hochfährt.

Das entsprechend erweiterte Modell sieht so aus:

Jetzt sind es jeweils zwei mögliche Ereignisse statt nur einem, die aus einem der Bewegungszustände in den Ruhezustand führen. Ihre Namen stehen durch Komma getrennt neben den Transitionen.

Gleichzeitig haben wir eine klare Unterscheidung zwischen Ereignissen getroffen, die der Benutzer auslöst, und solchen, die vom Positionssensor der Jalousie stammen. Der SCT-Jargon spricht hier von Interfaces. Der Definitionsbereich legt fest, welche Interfaces es gibt und welche Events ihnen zugeordnet sind. In unserem Fall sind dies das Interface User mit den Events up und down sowie das Interface PosSensor mit den Events upperPosition und lowerPosition.

Bedingte Zustandsübergänge mit Variablen und Guard Conditions

Nun kümmern wir uns darum, Sturmschäden an der Jalousie zu vermeiden. Zu diesem Zweck besitzt die Jalousie einen Windgeschwindigkeitssensor, der Werte zwischen 0 (Windstille) und 100 (Maximalwert des Sensors) liefert.

Im Zustandsautomaten steht die Windgeschwindigkeit in der Variablen windspeed des Interfaces Wind zur Verfügung. Wie die Windgeschwindigkeit in die Variable hineinkommt, ist eine Frage, die uns hier noch nicht kümmern soll, um das Beispiel einfach zu halten. Das Interface Wind enthält außerdem die Konstante STRONG. Sie gibt an, ab welcher Geschwindigkeit der Wind als »stark« gelten soll und die Jalousie hochzufahren ist.

Nun gibt es ausgehend vom Zustand Moving down eine zusätzliche Transition (blauer Pfeil) zum Zustand Idle. Sie ist mit einer Bedingung versehen, nämlich „Wind.windspeed >= Wind.STRONG“. Diese sogenannte Guard Condition steht in eckigen Klammern und sorgt dafür, daß die Transition nur dann ausgeführt wird, wenn die Bedingung erfüllt ist. Eine weitere Transition führt von Idle zum Zustand Moving up – aber nur dann, wenn die Jalousie laut Positionssensor nicht bereits oben ist. Um diese Information verfügbar zu machen, wird das Interface PosSensor entsprechend erweitert.

Die »blauen« Transitionen im obigen Zustandsdiagramm sorgen also für das automatische Hochfahren der Jalousie. Jetzt müssen wir nur noch den Benutzer daran hindern, die Jalousie trotzdem wieder nach unten zu bewegen. Dafür sorgt an der Transition Idle → Moving down nun die dem Event User.down zugeordnete Guard Condition „Wind.windspeed < Wind.STRONG“.

Bei der Transition Moving up → Idle ist das allerdings nicht ganz so einfach, denn sie soll ja beim Event PosSensor.upperPosition in jedem Fall ausgeführt werden. Die Guard Condition bezieht sich aber immer auf alle genannten Ereignisse, wäre hier also nicht zielführend. Die richtige Lösung ist, die Transition in zwei einzelne Transitionen aufzuteilen: Die eine Transition kümmert sich um das Event User.down und enthält den Guard, die andere führt bei PosSensor.upperPosition ohne Zusatzbedingung zum Zustand Idle. Wer mag, kann das im Zustandsautomaten umsetzen; ich verzichte hier darauf, da die gewünschte Funktionalität letztlich trotzdem gewährleistet ist.

Wir könnten jetzt noch einen Lichtsensor einführen und mit dessen Hilfe wie oben beschrieben die Jalousie automatisch nach unten fahren, wenn es draußen sehr hell ist. Das ist jedoch kniffliger als beim Wind, weil der Benutzer sich darüber hinwegsetzen und die Jalousie wieder nach oben fahren kann. In diesem Fall soll sich die Automatik zurückhalten und die Jalousie nicht wieder herunterfahren – jedenfalls nicht sofort. Auf dieses Thema werde ich in einem weiteren Blogbeitrag eingehen, genauso wie auf die interaktive Simulation des Zustandsautomaten und die Generierung von Java-, C- oder C++-Code, die uns nicht nur die manuelle Programmierung erspart, sondern auch die Fehler, die dabei typischerweise anfallen.

(Diesen Beitrag gibt es auch im itemis-Blog.)

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s