Revision [13269]

This is an old revision of ZustandsAutomaten made by ToBo on 2012-03-18 00:40:43.

 

Zustandsautomaten


Wenn wir von Zustandsautomaten reden, meinen wir endliche Zustandsautomaten. ZustandsDiagramm Zustandsdiagramme sind eine grafische Darstellung von 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 hängt von den Ereignis und dem aktuellen Zustand ab.

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

In der Informatik und der Elektrotechnik werden unterschiedliche Schwerpunkte verfolgt.

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 DetEndlAutomaten deterministischen, endlichen Automaten. Es gibt sie noch heute, allerdings werden diese mit einer Hardware-Beschreibungssprache wie z.B. Vhdl VHDL umgesetzt. Siehe dazu Modellierung von FSMs in VHDL in HorowitzHill1996, Teil II, ab S. 84 oder 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. 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. Es ist nützlich zu begreifen, wie diese Zustandsautomaten funktionieren, um einen gegenüber Störungen robusten virtuellen Automaten 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 DetEndlAutomaten deterministischen, endlichen Automaten und 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 deshalb bei genauer Betrachtung insbesondere in den Echtzeit-Kriterien von den mit Logik-Gattern umgesetzten Automaten. In Anschluss ist nunmehr über virtuelle, EndlicherAutomat endliche Zustandsautomaten die rede (Zustandsautomaten in Software).



Seit dem Einzug der Computer und Mikrocontroller in der Steuerungstechnik sind nun auch virtuelle, EndlicherAutomat 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.



Man kann zwischen einem Mealy-Automaten, einem Moore-Automat und der Kombination aus beiden, den Harel-Automaten, unterscheiden.



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

image



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



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.



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 SoftwareUml2 UML2 oder allgemein Harel-Automaten.



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 FunctionPointerStateMachine in C mit Function-Pointern, die ich im Rahmen einer Studienarbeit bei Prof. Dr. Robra erstellen musste. Tolle Sache!



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.



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


  • ZustandsDiagramm Zustandsdiagramme
  • State invariant
  • defer gibt an, dass ein Event nicht im aktuellen Zustand verarbeitet werden kann, jedoch im nachfolgenden Zustand eine Rolle spielen könnte.



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