Boost Your State Machines

Autor: Pawel Wiśniewski, Pawel Wiśniewski Consulting

Beitrag - Embedded Software Engineering Kongress 2017

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ätzlich sehen sie immer ein bisschen anders aus, weil sie stets wieder von vorne geschrieben werden. Der Vortrag zeigt eine Lösung 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.

Was sind State Machines (Zustandsautomaten) und wofür sind sie gut?

Embedded Systeme sind meistens eventgetrieben, das heißt, sie warten auf verschiedene (interne oder externe) Ereignisse. Wenn ein Ereignis auftritt, wird es abgearbeitet. Innerhalb der Verarbeitung können weitere interne Ereignisse generiert werden. Wenn es kein Ereignis zum Verarbeiten gibt, wird wieder gewartet.

Dieses Verhalten lässt 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.

Zustandsautomaten lassen sich mit Hilfe von UML-Zustandsdiagrammen [1] graphisch projektieren. Ein Zustandsdiagramm zeigt die zur Laufzeit erlaubten Zustände eines Zustandsautomaten an und gibt Ereignisse an, die seine Zustandsübergänge auslösen.

Die Zustände in einem Zustandsdiagramm werden durch Rechtecke mit abgerundeten Ecken dargestellt. Die Pfeile zwischen den Zuständen symbolisieren mögliche Zustandsübergänge. Sie sind mit den Ereignissen beschriftet, die zu dem jeweiligen Zustandsübergang führen.

Im Diagramm 1 (siehe PDF) sind die wichtigsten UML Elemente zu sehen.

• Initial - Startpunkt des Zustandsautomaten
• State – Zustand
• Transition - Zustandsübergang
• Event – Ereignis, das einen Zustandsübergang auslöst
• Guard - Bedingung für die Transition
• Action - Aktion während der Transition
• Final - Ende des Zustandsautomaten
  
  

Handgeschriebene Implementierungen (switch-case, if-else)

Betrachten wir den Zustandsautomaten aus Diagramm 2 (siehe PDF). Er beinhaltet drei States (Wait for first value, Wait for second value und Calculate), zwei Events (value und done) und eine Aktion (insert_value).

Es wäre möglich, diese State Machine mit Hilfe von if-else oder switch-case Konstruktionen zu implementieren. Der Quellcode könnte wie in Listing 1 (siehe PDF) (Switch-case) oder Listing 2 (siehe PDF) (if-else) aussehen. Leider ist auf den ersten Blick in beiden Fällen schwierig zu erkennen, was diese Software macht. Die Entry Aktion von State Calculate (Play_animation) ist in beiden Fällen (if-else und switch-case) mehr eine Exit-Aktion von State WaitForSecondValue. Das kann zu Schwierigkeiten führen, wenn das System um weitere Transitionen in Richtung Calculate erweitert werden soll.

Wenn es mehrere Events und Transitionen im System gibt, wird der Quellcode lang und unübersichtlich. Wenn wir unsere Software um weitere States erweitern möchten, müssen wir alle Bedingungen betrachten - auch diejenigen, die nicht leicht erkennbar sind.

Wir versuchen den Zustandsautomaten von Diagramm 2 (siehe PDF) um ein einfaches Error-Handling zu erweitern, wie in Diagramm 3 (siehe PDF) zu sehen ist.

Der Quellcode (Listing 3, siehe PDF) 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ür Calculate State. Bei realistischen Zustandsautomaten ergeben sich noch deutlich mehr Duplikate.

Die Grundlagen der Bibliothek [Boost].SML [3]

Das Verhalten von Zustandsdiagramm 2 (siehe PDF) lässt sich mit Hilfe von UML 2.5 ("Textuelle Repräsentation") als Zustandsautomat-Transitionen-Tabelle definieren (Listing 4, siehe PDF).

In der Transitionen-Tabelle können wir einfach sehen, unter welchen Bedingungen wir von State zu State kommen. Wenn wir unsere Transitionen-Tabelle um ein Error Handling erweitern wollen, müssen wir nur die neuen Transitionen eintragen (Listing 5, siehe PDF).

Das Herz von [Boost].SML ist die Transitionen-Tabelle. Die Syntax basiert auf der gezeigten UML-Notation:

SourceState + event [Guard] / Action = TargetState

Die Transitionen-Tabelle von Listing 4 (siehe PDF) kann man für die Nutzung mit dem [Boost].SML Framework fast unverändert übernehmen (Listing 6, siehe PDF). 

Die Erweiterung der Tabelle ist genauso einfach wie in Listing 5 (siehe PDF).

Außer der Transitionen-Tabelle müssen wir alle Events, Aktionen und Guards definieren. Die Aktionen und Guards sind Callable [2] Elemente, wie z.B. Lambda-Funktionen (Listing 7, siehe PDF).

Der Unterschied zwischen den Aktionen und Guards ist, dass die Aktionen nichts zurückgeben dürfen und die Guards bool zurückgeben müssen. Events sind benutzerdefinierte Typen wie z.B. Strukturen (Listing 8, siehe PDF).

Der fertige Zustandsautomat aus Diagramm 2 (siehe PDF) ist in Listing 9 (siehe PDF) zu sehen. Dort sind gleich alle Zustände (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ässt sich einfach mit Diagramm 2 vergleichen. Änderungen sind leicht durchzuführen, weil sich die Logik des Zustandsautomaten an einer Stelle befindet und einfach zu verstehen ist.

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önnen wir mit Hilfe von process_event Transitionen in unserem Zustandsautomaten auslösen (Zeilen 36, 39 und 42).

Zusätzlich sehen wir in Zeile 33 die Prüfung des RAM-Verbrauchs, durch die Instanz des Zustandsautomaten. Wenn die Instanz größer als ein Byte ist, dann bekommen wir einen Fehler zur Compilezeit. Weitere Prüfungen sind in Zeilen 34, 40 und 43 zu sehen. Dort wird geprüft, ob die Transitionen richtig definiert sind. Unser Zustandsautomat soll im Zustand Wait_For_First_Value starten, diese Prüfung findet in Zeile 34 statt. Weitere Prüfungen werden nach Aufruf von process_event durchgeführt. Diese Prüfungen finden zur Laufzeit statt und können in Unit-Tests verwendet werden.

Vergleich der Ansätze

	Handgeschriebene Konstruktionen	Boost::SML
Komplexität	Abhängig von der Anzahl States und Events	Konstant
Erweiterbarkeit/Wartbarkeit	Abhängig von der Anzahl States und Events	Konstant
Testbarkeit	Komplex, fragile Tests	Einfacher
Run time	Abhängig von Code-Qualität, meistens langsamer	Schnell, Jump Table
Compile time	Schnell	Etwas langsamer
Abhängigkeiten	keine	C++14

 

Die handgeschriebenen Konstruktionen sind meistens komplex. Für die Implementierung der Transitionen brauchen wir zusätzliche Variablen mit Zustandsinformationen und Bedingungen für die Transitions-Logik. Die if-else Konstruktionen sind für Compiler schwierig zu optimieren und brauchen mehrere CPU-Takte für die Abarbeitung. Handgeschriebene Zustandsautomaten sind fragil, und man muss alle Änderungen vorsichtig durchführen.

In Boost::SLM Framework wird die Transitionslogik als Jump-Tabelle zur Compile-Zeit generiert, das macht den Compile-Process etwas langsamer, reduziert aber die Laufzeit, weil der Compiler den Zustandsautomaten besser optimieren kann. Zusätzlicher Vorteil ist das einfachere Testing, weil Transationen, Aktionen und Guards per Design getrennt sind. Es ist einfach, Einzelteile separat zu testen. Tests sind stabiler, weil bei Änderungen der Zustandsautomatenlogik nur die Tests, die die Transitionen testen, angepasst werden müssen.

Mit Nutzung von Frameworks wie z.B. Boost::SML können wir Entwicklungszeit sparen. Unsere Software wird einfacher zu lesen, zu erweitern und zu testen. Meistens wird die Laufzeit auch schneller, weil der größte Teil von Entscheidungen zu Kompilierzeit getroffen wird.

References

[1] http://www.omg.org/spec/UML/2.5/

[2] http://en.cppreference.com/w/cpp/concept/Callable

[3] http://boost-experimental.github.io/sml/index.html

 

Beitrag als PDF downloaden

---

Implementierung - unsere Trainings & Coachings

Wollen Sie sich auf den aktuellen Stand der Technik bringen?

Dann informieren Sie sich hier zu Schulungen/ Seminaren/ Trainings/ Workshops und individuellen Coachings von MircoConsult zum Thema Implementierung /Embedded- und Echtzeit-Softwareentwicklung.

 

Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie hier.

---

Implementierung - Fachwissen

Wertvolles Fachwissen zum Thema Implementierung/ Embedded- und Echtzeit-Softwareentwicklung steht hier für Sie zum kostenfreien Download bereit.

Zu den Fachinformationen

 
Fachwissen zu weiteren Themen unseren Portfolios finden Sie hier.