Zustandsautomaten


Wenn wir von Zustandsautomaten reden, meinen wir meist endliche Zustandsautomaten (engl. finite state machines). Ursprünglich hat man diese aus Logik-Gattern gebaut, heute werden endliche Zustandsautomaten in Software implementiert. Nach wie vor sind Zustandsautomaten ein effizientes und mächtiges Mittel bei der Lösung von technischen Problemen. Sie sind beinahe in jedem Gerät bei dem es um die Bewältigung mehrerer Aufgaben und gute Fehlertoleranz geht, angefangen von der Waschmaschine, über die Aufzugssteuerung, die Kaffee-Maschine, bis hin zum Handy in Software oder Hardware umgesetzt.


1. Endliche Zustandsautomaten


Endliche Zustandsautomaten haben eine endliche Anzahl an Zuständen. Sie wechseln in einen anderen Zustand beim Eintreffen eines Ereignisses (engl. Event). In welchen Zustand gewechselt wird, hängt von dem Ereignis und dem aktuellen Zustand ab.

Einordnung endlicher Zustandsautomaten (engl. Finite State Machines) in der theoretischen Informatik:
image

In der Informatik und der Elektrotechnik ist das Prinzip des Automatenentwurfs ähnlich, die Umsetzung jedoch komplett verschieden.

In der Elektrotechnik werden endliche Zustandsautomaten (in dem Zusammenhang auch Schaltwerke genannt) durch das Zusammenschalten von Logik-Gatter entworfen (vgl. TietzeSchenk2002, S. 699). Noch vor der Zeit der Prozessoren gab es schon deterministischen, endlichen Automaten. Es gibt sie noch heute, allerdings werden diese mit einer Hardware-Beschreibungssprache wie z.B. VHDL umgesetzt (SkriptSehrVhdl, S. 99). Diese Hardware-Zustandsautomaten bestehen aus einem Schaltwerk aus Logikgattern (siehe nächste Abbildung) in die die Eingaben hineingehen und die Ausgänge zur der Außenwelt hinausgehen (HorowitzHill1996, Teil II, ab S. 84). Wie jeder Automat, so hat auch dieser einen Speicher für die Zustandsvariablen - ein Register. Dieses Register ist meist ein D-Flip-Flop, wie z.B. der Baustein 74HC573, ein 8-fach-D-Flip-Flop. Ich gehe hier darauf ein, denn es ist zwar nicht unbedingt notwendig aber sehr nützlich, zu verstehen, wie diese Hardware-Zustandsautomaten funktionieren, um einen gegenüber Störungen robusten, fehlertoleranten, ggf. an harte Echtzeitbedingungen geknüpften virtuellen Zustandsautomaten in Software implementieren zu können.

image

In der Informatik gibt es neben den endlichen Automaten auch Sonderformen wie Turingmaschinen, Kellerautomaten, nichtdeterministische Automaten etc., die leider meist sehr theoretisch und formal behandelt werden. Hier wird der Student mit Puming-Lemma und Co. bis zum Exzess beglückt. In der Praxis setzt der Informatiker oder Programmierer dann doch fast ausschließlich die deterministischen, endlichen Automaten und bestenfalls Kellerautomaten ein. Sollen Automaten in einer Programmiersprache implementiert werden, so werden sie als virtuelle Automaten umgesetzt, die nicht direkt auf der Hardware laufen, sondern als Programm auf der Hardware. Der Automat wird also simuliert. Diese virtuellen Automaten unterscheiden sich bei genauer Betrachtung insbesondere in den Echtzeit-Kriterien von den mit Logik-Gattern umgesetzten Automaten. In Anschluss ist nunmehr über virtuelle, endliche Zustandsautomaten die rede (Zustandsautomaten in Software).


2. Virtuelle, endliche Zustandsautomaten


Seit dem Einzug der Computer und Mikrocontroller in der Steuerungstechnik sind nun auch virtuelle, endliche Zustandsautomaten möglich (engl. Virtual Finite State Machines, VFSM). Bei der Umsetzung dieser Art von Zustandsautomaten müssen jedoch einige Randbedingungen im Gegensatz zu realen Zustandsautomaten beachtet werden. Wie die Väter der Zustandsautomaten in Hardware, so benötigt auch der VFSM einen Takt. Ohne einen regelmäßigen Takt sind die Zustandswechsel eines Zustandsautomaten, egal ob Hardware oder Software nicht vorhersehbar. Hier empfiehlt es sich bei harten Echtzeit-Anforderungen einen Timer auf einem Mikrocontroller zu verwenden. Existieren keine Echtzeitbedingungen, dann ist selbstverständlich ein variabler Takt, der von der Auslastung anderer Systemprozesse z.B. unter Windows oder Linux auf einem PC abhängig sein könnte zulässig.


3. Typen


Man kann zwischen einem Mealy-Automaten, einem Moore-Automat und der Kombination aus beiden, den Harel-Automaten, unterscheiden. Die Unterschiede lassen sich sehr gut mit Zustandsdiagrammen erläutern. Zustandsdiagramme sind eine grafische Darstellung von Zustandsautomaten.


3.1Mealy-Automat


Mealy-Automat führt Aktionen im Zustandsübergang aus.

image


3.2Moore-Automat


Moore-Automat führt Aktionen beim Betreten und Verlassen eines Zustands aus.
image


3.3Harel-Automat


Harel-Automat sind Hybride aus Mealy- und Moore-Automaten, sie erlauben zudem bedingte Zustandsübergänge, Zustände mit Gedächtnis, nebenläufige Zustände. Siehe dazu Balzert2000, S. 323 und Zustandsautomaten der SoftwareUml2 UML2.|

4. Erweiterte Zustandsautomaten


Erweiterte, endliche Zustandsautomaten besitzen abgesehen von ihren Zuständen, als Erweiterung lokale Variablen, die das Verhalten beim Eintreffen von Ereignissen beeinflussen können, wie bei Zustandsautomaten der UML2 oder allgemein Harel-Automaten.


5. State-Event-Matrix


Die Übergangstabelle (engl. State Event Matrix) bietet eine lückenlose Definition von Übergängen von jedem möglichen Zustand in alle anderen möglichen Zustände in Abhängigkeit von den möglichen Ereignissen. Die Übergangstabelle ist ein effektives Mittel um alle Fälle eines Zustandsautomaten zu erfassen. Bei sicherheitskritischen Anwendungen ein unentbehrliches Muss, auch wenn die Anzahl der Zustände und Ereignisse überschaubar ist!

Beispiel zu State-Event-Matrix in Wiegelmann2004, S. 158, allerdings ist der Zustandsautomat dort leider etwas ineffizient mit SWITCH- und CASE-Anweisungen implementiert. Diese haben den Nachteil mit steigender Anzahl von Ereignissen eine zunehmende Laufzeitabhängigkeit aufzuweisen. Siehe dazu die Implementierung mit in C mit Function-Pointern, die ich im Rahmen einer Studienarbeit bei Prof. Dr. Robra erstellen musste. Tolle Sache!


6. Zustandstabellen


Werden nur bei virtuellen, endlichen Zustandsautomaten benötigt. Eine Zustandstabelle definiert, unter welchen Bedingungen von dem aktuellen Zustand in einen anderen gewechselt wird und was bei Eintritt in den betrachteten Zustand und beim Verlassen dieses Zustandes ausgeführt wird.


7. Testplan


Der Testplan ist eine Methode zum Test von Zustandsautomaten. Es gibt sie je nach Abwägung von Sicherheit und Aufwand in zwei Stufen.
  • Testplan für Zustandsautomaten
    • Stufe 1: Zustandsabdeckung: Jeder Zustand wird mindestens einmal erreicht.
    • Stufe 2: Abdeckung aller Zustandswechsel: Jeder Zustandsübergang wird mindestens einmal ausgeführt.

Siehe dazu ScriptRobra2007


8. Relevant




Siehe auch
Valid XHTML :: Valid CSS: :: Powered by WikkaWiki