=====Zustandsautomaten===== Wenn wir von Zustandsautomaten reden, meinen wir meist [[EndlicherAutomat|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. ==a==Endliche Zustandsautomaten==a== 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 [[EndlicherAutomat|endlicher Zustandsautomaten]] (engl. Finite State Machines) in der theoretischen Informatik: {{image url="images/15_automaten.dot.png"}} 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 [[DetEndlAutomaten|deterministischen, endlichen Automaten]]. Es gibt sie noch heute, allerdings werden diese mit einer Hardware-Beschreibungssprache wie z.B. [[Vhdl|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 [[series7400|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 url="images/ZustandsautomatLogik.png"}} 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 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__, [[EndlicherAutomat|endliche Zustandsautomaten]] die rede (Zustandsautomaten in Software). ==a==Virtuelle, endliche Zustandsautomaten==a== 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. ==a==Typen==a== 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 [[ZustandsDiagramm|Zustandsdiagrammen]] erläutern. [[ZustandsDiagramm|Zustandsdiagramme]] sind eine grafische Darstellung von Zustandsautomaten. =a=Mealy-Automat=a= Mealy-Automat führt Aktionen im Zustandsübergang aus. {{image url="images/ATFS_AutomatMealy.png"}} =a=Moore-Automat=a= Moore-Automat führt Aktionen beim Betreten und Verlassen eines Zustands aus. ~{{image url="images/ATFS_AutomatMoore.png"}} =a=Harel-Automat=a= 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]].| ==a==Erweiterte Zustandsautomaten==a== 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. ==a==State-Event-Matrix==a== 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! ==a==Zustandstabellen==a== 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. ==a==Testplan==a== 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 ==a==Relevant==a== ~-[[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. ~-[[https://www.johner-institut.de/blog/iec-62304-medizinische-software/zustandsautomat/ Unterscheidung zwischen Zustandsautomat für die Implementierung von Software und die Beschreibung von Anforderungen als Zustandsautomat]], Instituts-Journal: Ausgabe 06/15, Prof. Dr. Johner ~-[[Schaltwerke]] ---- Siehe auch {{backlinks}}