Autor: Pawel Wi\u015bniewski, Pawel Wi\u015bniewski Consulting<\/p>\n
State Machines sind ein wichtiger Bestandsteil von Software. Leider sind sie zu oft per Hand implementiert, z.B. unter Verwendung von if-else oder switch-case Konstruktionen. Solche Konstruktionen sind schwer zu verstehen und schwierig zu erweitern. Zus\u00e4tzlich sehen sie immer ein bisschen anders aus, weil sie stets wieder von vorne geschrieben werden. Der Vortrag zeigt eine L\u00f6sung auf Basis der Bibliothek Boost.SML. Die mit der Bibliothek erstellten State Machines sind nicht nur einfacher zu verstehen und zu erweitern, sie sind auch oft effizienter als die handgeschrieben Varianten.<\/strong><\/p>\n Embedded Systeme sind meistens eventgetrieben, das hei\u00dft, sie warten auf verschiedene (interne oder externe) Ereignisse. Wenn ein Ereignis auftritt, wird es abgearbeitet. Innerhalb der Verarbeitung k\u00f6nnen weitere interne Ereignisse generiert werden. Wenn es kein Ereignis zum Verarbeiten gibt, wird wieder gewartet.<\/p>\n Dieses Verhalten l\u00e4sst sich als sequentielle Software realisieren. Wenn die Reihenfolge von Events nicht bekannt ist oder wenn auf mehrere Events gewartet wird, wird eine sequentielle Software komplex. Es ist deutlich einfacher, ein eventgetriebenes Verhalten mit Zustandsautomaten abzubilden.<\/p>\n Zustandsautomaten lassen sich mit Hilfe von UML-Zustandsdiagrammen [1] graphisch projektieren. Ein Zustandsdiagramm zeigt die zur Laufzeit erlaubten Zust\u00e4nde eines Zustandsautomaten an und gibt Ereignisse an, die seine Zustands\u00fcberg\u00e4nge ausl\u00f6sen.<\/p>\n Die Zust\u00e4nde in einem Zustandsdiagramm werden durch Rechtecke mit abgerundeten Ecken dargestellt. Die Pfeile zwischen den Zust\u00e4nden symbolisieren m\u00f6gliche Zustands\u00fcberg\u00e4nge. Sie sind mit den Ereignissen beschriftet, die zu dem jeweiligen Zustands\u00fcbergang f\u00fchren.<\/p>\n Im Diagramm 1 (siehe\u00a0PDF<\/a>) sind die wichtigsten UML Elemente zu sehen.<\/p>\n Betrachten wir den Zustandsautomaten aus Diagramm 2 (siehe\u00a0PDF<\/a>). Er beinhaltet drei States (Wait for first value, Wait for second value und Calculate), zwei Events (value und done) und eine Aktion (insert_value).<\/p>\n Es w\u00e4re m\u00f6glich, diese State Machine mit Hilfe von if-else oder switch-case Konstruktionen zu implementieren. Der Quellcode k\u00f6nnte wie in Listing 1 (siehe\u00a0PDF<\/a>) (Switch-case) oder Listing 2 (siehe\u00a0PDF<\/a>) (if-else) aussehen. Leider ist auf den ersten Blick in beiden F\u00e4llen schwierig zu erkennen, was diese Software macht. Die Entry Aktion von State Calculate (Play_animation) ist in beiden F\u00e4llen (if-else und switch-case) mehr eine Exit-Aktion von State WaitForSecondValue. Das kann zu Schwierigkeiten f\u00fchren, wenn das System um weitere Transitionen in Richtung Calculate erweitert werden soll.<\/p>\n Wenn es mehrere Events und Transitionen im System gibt, wird der Quellcode lang und un\u00fcbersichtlich. Wenn wir unsere Software um weitere States erweitern m\u00f6chten, m\u00fcssen wir alle Bedingungen betrachten – auch diejenigen, die nicht leicht erkennbar sind.<\/p>\n Wir versuchen den Zustandsautomaten von Diagramm\u00a02 (siehe\u00a0PDF<\/a>) um ein einfaches Error-Handling zu erweitern, wie in Diagramm 3 (siehe\u00a0PDF<\/a>) zu sehen ist.<\/p>\n Der Quellcode (Listing 3, siehe\u00a0PDF<\/a>) ist nun fast doppelt so lang; eine extra Ebene mit einer if-Bedingung ist dazugekommen. Jetzt haben wir auch an zwei Stellen Stop_animation (in Zeile 11 und 24) als Exit-Aktionen f\u00fcr Calculate State. Bei realistischen Zustandsautomaten ergeben sich noch deutlich mehr Duplikate.<\/p>\n Das Verhalten von Zustandsdiagramm 2 (siehe\u00a0PDF<\/a>) l\u00e4sst sich mit Hilfe von UML 2.5 („Textuelle Repr\u00e4sentation“) als Zustandsautomat-Transitionen-Tabelle definieren (Listing 4, siehe\u00a0PDF<\/a>).<\/p>\n In der Transitionen-Tabelle k\u00f6nnen wir einfach sehen, unter welchen Bedingungen wir von State zu State kommen. Wenn wir unsere Transitionen-Tabelle um ein Error Handling erweitern wollen, m\u00fcssen wir nur die neuen Transitionen eintragen (Listing 5, siehe\u00a0PDF<\/a>).<\/p>\n Das Herz von [Boost].SML ist die Transitionen-Tabelle. Die Syntax basiert auf der gezeigten UML-Notation:<\/p>\n SourceState + event [Guard] \/ Action = TargetState<\/p>\n Die Transitionen-Tabelle von Listing 4 (siehe\u00a0PDF<\/a>) kann man f\u00fcr die Nutzung mit dem [Boost].SML Framework fast unver\u00e4ndert \u00fcbernehmen (Listing 6, siehe\u00a0PDF<\/a>).<\/p>\n Die Erweiterung der Tabelle ist genauso einfach wie in Listing 5 (siehe\u00a0PDF<\/a>).<\/p>\n Au\u00dfer der Transitionen-Tabelle m\u00fcssen wir alle Events, Aktionen und Guards definieren. Die Aktionen und Guards sind Callable [2] Elemente, wie z.B. Lambda-Funktionen (Listing 7, siehe\u00a0PDF<\/a>).<\/p>\n Der Unterschied zwischen den Aktionen und Guards ist, dass die Aktionen nichts zur\u00fcckgeben d\u00fcrfen und die Guards bool zur\u00fcckgeben m\u00fcssen. Events sind benutzerdefinierte Typen wie z.B. Strukturen (Listing 8, siehe\u00a0PDF<\/a>).<\/p>\n Der fertige Zustandsautomat aus Diagramm 2 (siehe\u00a0PDF<\/a>) ist in Listing 9 (siehe\u00a0PDF<\/a>) zu sehen. Dort sind gleich alle Zust\u00e4nde (Zeile 6-8), Aktionen (Zeile 11-13), Events (Zeile 2-3) und die Transitionen-Tabelle (Zeile 19-25) zu erkennen. Der gesamte Quellcode ist gut lesbar und l\u00e4sst sich einfach mit Diagramm 2 vergleichen. \u00c4nderungen sind leicht durchzuf\u00fchren, weil sich die Logik des Zustandsautomaten an einer Stelle befindet und einfach zu verstehen ist.<\/p>\n In Zeile 29 bis 44 ist eine einfache Anwendung eines Boost::SML Zustandsautomaten gezeigt. Es ist lediglich notwendig, den Zustandsautomaten zu instantiieren (Zeile 32), und dann k\u00f6nnen wir mit Hilfe von process_event Transitionen in unserem Zustandsautomaten ausl\u00f6sen (Zeilen 36, 39 und 42).<\/p>\n Zus\u00e4tzlich sehen wir in Zeile 33 die Pr\u00fcfung des RAM-Verbrauchs, durch die Instanz des Zustandsautomaten. Wenn die Instanz gr\u00f6\u00dfer als ein Byte ist, dann bekommen wir einen Fehler zur Compilezeit. Weitere Pr\u00fcfungen sind in Zeilen 34, 40 und 43 zu sehen. Dort wird gepr\u00fcft, ob die Transitionen richtig definiert sind. Unser Zustandsautomat soll im Zustand Wait_For_First_Value starten, diese Pr\u00fcfung findet in Zeile 34 statt. Weitere Pr\u00fcfungen werden nach Aufruf von process_event durchgef\u00fchrt. Diese Pr\u00fcfungen finden zur Laufzeit statt und k\u00f6nnen in Unit-Tests verwendet werden.<\/p>\nWas sind State Machines (Zustandsautomaten) und wof\u00fcr sind sie gut?<\/h2>\n
\n
Handgeschriebene Implementierungen (switch-case, if-else)<\/h2>\n
Die Grundlagen der Bibliothek [Boost].SML [3]<\/h2>\n
Vergleich der Ans\u00e4tze<\/h2>\n