Wer Informatik studiert, wird irgendwann mit dem Konzept des Automaten konfrontiert. Meist geschieht dies recht abstrakt im Rahmen der theoretischen Informatik und vielen Studenten bleibt der praktische Nutzen selbst nach dem Ablegen der Prüfung verborgen. Dabei können gerade diskrete, endliche Automaten (DEA) sehr nützlich sein um kniffelige, praktische Probleme zu lösen.
Naiver Spaghetticode
Auf einem Mikrocontroller wollte ich in C ein serielles Kommunikationsprotokoll implementieren. Die Spezifikation war nicht allzu komplex, aber die Umsetzung auf der Zielhardware führte schnell zu Problemen – insbesondere mit Interrupts.
Interrupts sind eine Unterbrechung des Hauptprogramms, damit der Mikrocontroller auf eintretende Ereignisse reagieren kann. Nach der Abarbeitung des Programmcodes zu ihrer Behandlung wird das Hauptprogramm fortgesetzt. Klassische Quellen von Interrupts sind Timer, Zähler, Taster oder die Kommunikationsbaugruppen des Mikrocontrollers (sog. USARTs).
Mein naiver Programmcode hatte sich mittlerweile zu einem Irrgarten aus unzähligen Funktionsaufrufen mit Massen an if/else- und switch/case-Ausdrücken entwickelt. Eine Fehlersuche war schwierig bis unmöglich. Immer wieder verursachten unvorhergesehen auftretende Interrupts kurioses Fehlverhalten. Mir wurde klar, dass ich solchen Code niemals verlässlich und wartbar bekommen würde.
Erkenntnisse
Die Interrupts wurden durch meinen Mikrocontroller sauber serialisiert. Es wird immer nur ein Interrupt gleichzeitig bearbeitet. Neue Ereignisse werden nach Priorität eingereiht. Aber die Mathematik ist manchmal gegen einen. Auf 14 interne Zustände kamen 6 externe Ereignisse und ergaben insgesamt 14·6 = 84 zu prüfende Kombinationen. Auf alle Kombinationen sollte das Programm richtig reagieren.
Dunkel erinnerte ich mich an das Studienwissen längst vergangener Semester. Könnte ich die Komplexität meines Problems eventuell anders angehen und dadurch besseren Code erhalten?
Automaten zur Rettung
Ein gut entworfener DEA weist angenehme Eigenschaften auf. Zwei davon sind die Vollständigkeit und die Widerspruchsfreiheit.
Vollständig ist ein Automat, wenn ein Folgezustand aus jedem aktuellen internen Zustand heraus auf jede mögliche Eingabe definiert ist.
Widerspruchsfrei ist ein Automat, wenn alle Folgezustände eindeutig sind.
Genau diese Eigenschaften brauchte ich. Mein Code sollte alle 84 Kombinationen abdecken und sich in allen Fällen eindeutig verhalten. Also begann ich mit der Modellierung meines Kommunikationsprotokolls als Automatengraph. Schnell waren die Zustände als Kästen im Visualisierungsprogramm platziert und durch beschriftete Pfeile über die eintretenden Ereignisse miteinander verbunden. Alle Zustandsübergänge, die sogenannten Transitionen, waren hierbei unmittelbare Folge eines Hardware-Interrupts oder von Interaktionen des Protokollcodes mit der Hauptanwendung.
Die Lehre konfrontiert den Studenten häufig mit taktgesteuerten Automaten, die mit jedem Takt ihre Ausgabe- und Zustandsüberführungsfunktionen aus der Eingabe neu berechnen. Mein Automat wurde durch den Eintritt von Ereignissen getaktet und „konsumierte“ als Eingabe das Ereignis selbst. Sozusagen ein ereignisgesteuerter, diskreter, endlicher Automat mit der Menge aller möglichen Ereignisse als Eingabealphabet.
Für echte Vollständigkeit hätte mein Automatengraph von jedem Zustand aus Transitionen für alle Ereignisse enthalten müssen – im schlimmsten Falle wieder 84 Stück. Dies hätte jedoch der Übersichtlichkeit nicht gut getan und ich entschloss mich, im Graphen nur das „gewöhnliche Verhalten“ des Protokolls abzubilden, also die erwünschten Transitionen und die erwartbaren Fehler. Im Weiteren wählte ich eine einfache Tabelle als Hilfsmittel. Zustände als Reihentitel, Ereignisse als Spaltentitel und den Folgezustand eindeutig im Schnittpunkt eintragen – übrig blieben all die Lücken unbedachter Kombinationen, die mir so viele Probleme bereitet hatten.
Es galt nun, das Verhalten für diese Lücken festzulegen. Kann das Ereignis ignoriert werden? Stellt es einen Programmierfehler dar, wenn diese Kombination tatsächlich auftritt? Oder fehlt hier schlicht ein Stück reguläres Verhalten, das bei der Modellierung übersehen wurde?
Besserer C-Code
Nachdem ich mit einer lückenlosen Tabelle der Vollständigkeit und Widerspruchsfreiheit Rechnung getragen hatte, war es an der Zeit, meinen Code aufzuräumen. Einfach drauflos zu programmieren, ist eine gute Methode, ein Problem und seine Fallstricke in kurzer Zeit kennenzulernen. Die Literatur bezeichnet diese Entwurfsmethode gerne als Rapid Prototyping, gefolgt von dem Rat, den Prototypen auf jeden Fall zu entsorgen.
Ich war gewillt, den Rat anzunehmen und hatte auch schon eine bessere Idee: Eine Look-Up-Tabelle im Arbeitsspeicher meines Mikrocontrollers. Mit einer Anzahl von m Zuständen und n Ereignissen legt man ein Array der Größe m·n an. Man findet den Folgezustand des aktuellen Zustand k aus [0 … m-1] bei Eintritt des Ereignisses l aus [0 … n-1] an der Position k·n+l.
Der folgende Beispielcode zeigt wie einfach der Automat in C spezifiziert werden kann. Füllt man die Look-Up-Tabelle mit sinnvollen Folgezuständen, wird der Zustand durch Aufruf der Funktion Transition ( ) gewechselt. Ungültige Transitionen lassen sich über StateInvalid abfangen. StateIgnore kann zum Ignorieren von Ereignissen genutzt werden (vgl. Eigenschleife).
typedef enum { StateInvalid, StateIgnore, State0, State1, NumStates } StateType; typedef enum { Event0, Event1, Event2, NumEvents } EventType; StateType LookUpTable[(NumStates * NumEvents)] = {StateInvalid}; StateType CurrentState = State0; void Transition(EventType Event) { if (Event >= NumEvents) FatalError(); uint8_t const LookUpPosition = ((CurrentState * NumEvents) + Event); StateType const NewState = LookupTable[LookUpPosition]; if (NewState == StateInvalid) FatalError(); if (NewState == StateIgnore) return; CurrentState = NewState; }Mit einer Implementierung nach diesem Muster, konnte ich den gesamten Protokollautomaten bei garantierter Vollständigkeit und Widerspruchsfreiheit in nur 84 Byte Arbeitsspeicher meines Mikrocontrollers abbilden.
Auch das Debugging verbesserte sich erheblich. Durch eigene Typdefinitionen und die Deanonymisierung der Zustände und Ereignisse via enum lies sich im Debugger meiner Entwicklungsumgebung nun sehr schön verfolgen, welches Ereignis wann für Chaos gesorgt hatte.
Legt man im Speicher nicht nur den Folgezustand, sondern auch einen Funktionspointer ab (vgl. struct), so kann man mit etwas mehr Speicherplatz neben dem reinen Zustandswechsel auch begleitende Aktionen ausführen – wie das Starten eines Timers oder das Leeren eines Puffers.
Ein weiterer Vorteil dieser Implementierung ist die algorithmische Komplexität von O(1). Dies bedeutet, dass die erforderliche Rechenzeit für einen Zustandswechsel konstant und von der Anzahl der Transitionen unabhängig ist. Das Prüfen von Bedingungen in langen konditionellen Codepfaden kann je nach Struktur und Compiler gerne O(n) sein.
Seine Grenzen findet dieser Ansatz in der Problemgröße. Wachsen die Zustandsmenge und das Eingabealphabet an, so steht irgendwann nicht mehr genug Speicherplatz zur Verfügung, um die Überführungsfunktion vollständig darin abzulegen. Man kann sich an diesem Punkt weiterer Tricks bedienen. Optimierte Zustandscodierung, Minimierung der Überführungsfunktion mittels boolescher Algebra oder das Zerlegen eines großen Automaten in mehrere kleine sind gängige Methoden.
Finale
Gerne hätte ich berichtet, dass mein Automat auch gleich perfekt funktioniert hat, doch der erste Stresstest mit wildem Ziehen und Stecken der Leitungen brachte alles aus dem Tritt. Letztlich genügten aber wenige Anpassungen des Automatenentwurfs, um es zu richten. Die Änderungen am Modell ließen sich direkt in die nun klare und robuste Codebasis übernehmen und das Programmieren fühlte sich an wie Malen nach Zahlen.
Im Prinzip hatte ich gerade die modellbasierte Entwicklung samt automatischer Codesynthese entdeckt. Wächst Dir die Komplexität über den Kopf, dann beschreibe das Problem und seine Lösung auf einer (Meta-)Ebene, die der Komplexität angemessen ist. Nehme die Beschreibung und übersetze sie zurück in die Ebene, auf der das Problem gelöst werden muss. Ist die Beschreibung auf der Metaebene ausreichend formal, so kann dies theoretisch automatisiert erfolgen.
Für den Programmierer im Allgemeinen bedeutet dies, dass es sehr produktiv sein kann, sich vom Code zu lösen und etwas Zeit in die Modellierung eines Problems zu investieren. Es ist gut für das Verständnis, liefert besseren Code und ist eine Form der Dokumentation.
Mir selbst wurde erneut deutlich, dass Lernen nicht im Hörsaal stattfindet und auch nicht vor der Prüfung. Es ist die Bewältigung echter Aufgabenstellungen, die „Gehörtes“ nachhaltig ins Bewusstsein rückt. Merkwürdige Dinge schlummern seit langem im eigenen Werkzeugkasten, doch plötzlich erkennt man ihren Nutzen und erneuert die persönliche Wertschätzung.