Kleiner endlicher Automat (finite state machine)

03.06.2012

Für ein Mikrocontrollerprojekt brauchte ich einen kleinen, übersichtlich zu implementierenden endlichen Automaten (FSM - finite state machine). D.h. ein Softwarekonstrukt, welches aufgrund bestimmter Ereignisse (hier Tastendrücke auf einer Fernbedienung) zwischen verschiedenen Zuständen wechselt. Zustandsautomaten habe ich schon eine ganze Menge implementiert und dafür auch fertige Bibliotheken genutzt. Doch für einen Mikrocontroller musste es eine besonders leichtgewichtige Implementierung sein.

Einleitung

Wie im Vorwort schon erwähnt, geht es hier um die übersichtliche und einfache Implementierung eines Zustandsautomaten für ein fernbedienbares Gerät. Um diese Darstellung nicht unnötig kompliziert werden zu lassen, beschränke ich mich auf ein einfaches Beispiel: Beispiel für einen kleinen, endlichen Automaten

Das hier skizzierte Gerät hat drei Zustände:

  • Gerät aus
    Von diesem Zustand aus kann in den Zustand “Normalbetrieb” gewechselt werden.
  • Normalbetrieb
    Von diesem Zustand aus kann in den Zustand “Einstellmodus” oder “Gerät aus” gewechselt werden.
  • Einstellmodus
    Von diesem Zustand aus kann in den Zustand “Normalbetrieb” gewechselt werden. Dabei können die gemachten Einstellungen beibehalten oder verworfen werden.

Zustände und Ereignisse

Die Zustände “Gerät aus”, “Normalbetrieb”, “Einstellmodus” werden durch “States” dargestellt. Durch Ereignisse (Events) wird zwischen diesen Zustände gewechselt. Es können jedoch auch bei einem Ereignis Arbeiten anfallen, welche erledigt werden müssen. Beispielsweise können Einstellungen gesichert oder geholt werden. In diesem Fall muss dies für den “Einstellmodus” geschehen. Wird er durch das Event “abbrechen” verlassen, muss der alte Status wieder geladen werden. Verlässt man den Status jedoch über das Event “speichern”, müssen die einzelnen Einstellungen in das EE-PROM des Mikrocontrollers geschrieben werden.

Die in der Headerdatei implementierte Bibliothek erlaubt es daher, bestimmten Events Funktionen zuzuordnen, welche ausgeführt werden, bevor der neue Zustand eingenommen wird. Diese können den Zustandswechsel sogar noch verhindern, wenn die Eingaben z.B. nicht gespeichert werden können.

So weit, so gut. Und nun?

Das nachfolgende Beispiel zeigt die Implementierung des Zustandsautomaten mit Hilfe der Headerdatei tiny_fsm.h.


#include "tiny_fsm.h"

SettingsStruct Settings;

DECLARE_EVENTS(main, Done, Cancel, EnterSettings);

STATEFUNC(main, Standby)
{
	/*Darauf warten dass etwas geschieht. Dann Done zurückgeben.*/
	while (NothingHappens()) {};

	return Done;
}

STATEFUNC(main, Settings)
{
	/*Einstellungen vornehmen. Danach entweder Cancel oder Done
	  zurückgeben. Dabei die Struktur Settings anpassen.*/
	while (DoSettings()) {};
	if (OkPressed)
		return Done;
	else
		return Cancel;
}

STATEFUNC(main, Running)
{
	/*Hauptprogramm ausführen. Entweder Done zurückgeben, 
	  wenn der Benutzer die Standby-Taste drückt oder
	  EnterSettings wenn der die Menü-Taste drückt*/
	while (true)
	{
		Keys key = getKey();
		switch (key)
		{
			case Menu:
				return EnterSettings;
			case Standby:
				return Done;
		}
	}
}

HANDLERFUNC(main, SaveSettings)
{
	/*Die Struktur "Settings" mit den Einstellungen sichern*/
}

HANDLERFUNC(main, LoadSettings)
{
	/*Die Struktur "Settings" mit den Einstellungen laden*/
}

void main()
{
	BEGIN_STATE_MACHINE(main, Standby)
		STATE(main, Running)
			EVENT(main, Done, Standby);
			EVENT(main, EnterSettings, Settings);
		END_STATE()

		STATE(main, Settings)
			EVENT_WITH_HANDLER(main, Done, Running, SaveSettings);
			EVENT_WITH_HANDLER(main, Cancel, Running, LoadSettings);
		END_STATE()

		STATE(main, Standby)
			EVENT_WITH_HANDLER(main, Done, Running, LoadSettings);
		END_STATE()
	END_STATE_MACHINE();
}

Dieser Code implementiert den, in der Grafik dargestellten, endlichen Automaten. Um ihn zu verstehen, muss man sich zuerst die Definition in main() ansehen. Die Zeile BEGIN_STATE_MACHINE deklariert einen endlichen Zustandsautomaten mit dem Namen main. Die Benennung der einzelnen Automaten erlaubt es, mehrere in der gleichen Quelldatei zu verwenden. Jede BEGIN_STATE_MACHINE-Zeile, muss durch eine passende END_STATE_MACHINE Zeile abgeschlossen werden.

Deklaration der Zustände

Die einzelnen Zustände (States) werden durch eine STATE-Deklarationen festgelegt. Als Parameter erhält das STATE-Makro den Namen der State-Machine (hier main) und den Namen des Status. Für jeden Status muss eine mit STATEFUNC (siehe weiter unten) deklarierte Funktion vorhanden sein, welche den Zustand implementiert. Ist dies nicht der Fall, wird beim Compilieren der Fehler ausgegeben, dass die Funktion nicht gefunden werden konnte.

Innerhalb des Zustandes werden nun die Ereignisse festgelegt, welche zum Verlassen des Zustandes verwendet werden können. Hierfür existieren zwei Makros:

  • Das Makro EVENT legt fest, dass bei dem angegebenen Event der festgelegte neue Zustand eingenommen wird. Hierfür wird zuerst der Name des Automaten, als zweites der Name des Ereignisses und als drittes der neue Zustand übergeben.
  • Das Makro EVENT_WITH_HANDLER, welches zusätzlich zu den Parametern des EVENT-Makros noch eine Funktion (welche mit HANDLERFUNC deklariert werden muss) entgegen nimmt, die vor dem Übergang in den neuen Zustand aufgerufen wird.

Implementieren von Zuständen

Jeder Zustand muss vor der Nutzung im Automaten implementiert werden. Hierfür wird das Makro STATEFUNC genutzt. Die beiden Parameter des Makros sind der Name des Zustandsautomaten für welchen der Zustand nutzbar sein soll und der Name des Zustandes. Ein Zustandswechsel wird durch Ereignisse ausgelöst welche einfach als Rückgabewert der Zustandsfunktion zurückgegeben werden.

Gibt ein Zustand einen Wert zurück, welcher nicht in der Deklaration des Automaten als Ereignis (Event) angegeben wurde, wird der Zustand einfach wieder aufgerufen und das Event ignoriert.

Deklarieren der Ereignisse

Die einzelnen, für den Zustandsautomaten gültigen Ereignisse werden direkt vor den einzelnen Zuständen über das Makro DECLARE_EVENTS festgelegt. Dieses Makro erzeugt ein Enum, wodurch die Zustände auch in der IDE als korrekte Rückgabewerte eines Zustandes erkannt werden. Alle gültigen Ereignisse müssen hier festgelegt werden. Einzelne Ereignisse können jedoch als Ergebnis unterschiedlicher Zustände verwendet werden. Dies ist am Beispiel des “Done”-Ereignisses gut zu sehen.

Implementieren einer Übergangsroutine

Für bestimmte Übergänge können zusätzlich noch die bereits erwähnten Übergangsroutinen (Event-Handler) definiert werden. Diese erlauben es vor dem neuen Zustand vorbereitende Aktionen auszuführen. Darüber hinaus können Sie die Zustandsänderung noch verhindern, falls dies nötig werden sollte. Eine Übergangsroutine wird über das Makro HANDLERFUNC deklariert. Hier muss, wie beim Zustand auch, der Name des Automaten und ein Handler-Name vergeben werden. Dieser Handlername wird als vierter Parameter dem Makro EVENT_WITH_HANDLER übergeben. Der neue Zustand wird nur dann eingenommen, wenn die Übergangsroutine true zurück gibt. Gibt sie false zurück, wird einfach der aktuelle Zustand wieder aufgerufen.

Vor- und Nachteile

Ein Vorteil des hier dargestellten endlichen Automaten ist, dass sein Code nicht viel komplexer ist, als die Implementierung der einzelnen Statusübergänge von Hand. Das lässt sich auch daran erkennen, dass die Headerdatei (inkl. Kommentaren) weniger als 100 Zeilen lang ist. Trotzdem bleibt der Code frei von großen Select-Statements oder if-Kaskaden und ist dadurch gut lesbar.

Als Nachteil könnte man anführen, dass zwischen den einzelnen Zuständen Informationen nur über globale Variablen ausgetauscht werden können. Ich sehe das jedoch eher als Vorteil, zwingt es einen doch, die einzelnen Zustände möglichst unabhängig von einander zu implementieren.

Versionsgeschichte

  • Version 1.0
    Erste Implementierung für C++.

  • Version 1.1
    Die Header-Datei kompiliert nun auch mit C-Compilern.

Download

Die Headerdatei kann direkt als tiny_fsm.h heruntergeladen und in eigene Projekte eingebunden werden. Die Datei ist public domain. D.h. jeder kann damit tun und lassen was er möchte. Eine andere Lizenz wäre wohl länger als die eigentliche Implementierung :)