Ich habe bisher immer nach Struktogrammen programmiert, würde mich nun aber gerne mit den Zustandsmaschinen vertraut machen. Ich habe schon einiges gesucht, das war dann aber jeweils für FPGAs gedacht oder allgemein zu komplex. Im Moment bin ich nur auf der Suche nach dem Prinzip einer einfachen Zustandsmaschine. Leider sind allfällige Beispiele im Internet sehr selten mit Code veranschaulicht. 1. Hat jemand ein paar Beispiele zu einer simplen Zustandsmaschine? 2. Ist es richtig, dass die Finite State Machine kein besonderer Typ der Zustandsmaschine sondern einfach ein anderer Name ist? 3. Meiner Meinung nach darf ich über einen Interrupt die Zustände nicht direkt ändern, da es sonst zu fatalen Fehlern führen könnte. Wie aber kann ich Interrupts in eine Zustandsmaschine einbeziehen? Sollte ich das etwa gänzlich vermeiden? 4. Muss ich bei der Realisierung der Zustandsmaschine neben dem Status auch noch den Event verwalten und verarbeiten? Falls ja, worauf richte ich dann die Switch-Case-Verzweigung? Auf den Status oder auf den Event? Ich hätte nun gesagt auf den Zustand; im Internet habe ich aber auch schon ein Beispiel gefunden, bei dem der Event als Auswahl verwendet wurde. Falls das Thema schon zu genüge diskutiert wurde, entschuldige ich mich. Ich habe bis jetzt einfach noch keine Basics gefunden.
1. -hab ich nicht 2. ja, ist der englische Ausdruck 3. nein, der Interrupt muß einen Event schicken, der den Zustand ändern kann (wehe, wenn im aktuellen zustand dieser Event nicht verarbeitet werden kann....) 4. Du mußt halt einen event verarbeioten können. Das hängt von der Realisierung ab... Die Switch case geht auf den event, für eden Zustand muß es eine eigene switch case geben. Oder das ganze geschachtelt, das gibt aber einen unübersichtlichen Sourcecode. Das hängt auch etwas von der Realisierung ab, ich würde pro Zustand eine Funktion machen, die die Events verarbeitet. Soviel als knappe Hinweise...
Also mit einem Switch-Case verarbeite ich den Event, um eine allfällige Zustandsänderung durchzuführen? Zwischen den Zustände selbst wird aber auch durch ein Switch-Case navigiert, oder etwa nicht? Ich habe das folgendermassen verstanden:
1 | #define STATE_A 1
|
2 | #define STATE_B 2
|
3 | #define STATE_C 3
|
1 | switch(state) |
2 | {
|
3 | case STATE_A: FUNKTA(); |
4 | break; |
5 | case STATE_B: FUNKTB(); |
6 | break; |
7 | case STATE_C: FUNKTC(); |
8 | break; |
9 | }
|
Beispiel für ein Zustand:
1 | void FUNKTA( void) |
2 | {
|
3 | |
4 | /* Funktion stark vereinfacht */
|
5 | LED0 = ~LED0; |
6 | |
7 | switch(event) |
8 | {
|
9 | case EVENT_B: status = STATUS_B; |
10 | break; |
11 | case EVENT_C: status = STATUS_C; |
12 | break; |
13 | }
|
14 | }
|
Natürlich fehlt hier in meinem Code einiges, es soll ja nur zu Verständigungszwecken dienen. Ist das so richtig? Natürlich könnte ich in der FUNKTA() die Events auch anders verarbeiten. Wichtig ist doch einfach, dass diese den Zustand ändern können, oder? Ich bin mir nicht ganz sicher, ob du den Status-Wechsel auch mit einem Switch-Case machen würdest...
Wie Du die Zustandsmaschine implementierst, ist völlig egal. Es gibt eklige, schöne und elegante Möglichkeiten dafür. Wenn man eine Sprache bzw. eine Compiler mit Tail-Call-Optimization hat, lassen sich Zustandsautomaten sehr elegant formulieren. Alternativ nimmt man eben ein "goto" oder ähnliches. Das Prinzip ist immer gleich: Du hast Zustände, Ereignisse und Aktionen. Aktionen können beim Verlassen und/oder Eintreten von Zuständen ausgeführt werden. Ereignisse ändern Zustände in Abhängigkeit vom aktuellen Zustand.
Hallo Stefan, Vorbemerkung: if-then-else-Friedhof und Zustandsautomat sind zwei völlig unterschiedliche Arten zu denken! Zu Deinen Fragen: 1. Waschmaschine, Geschirrspüle, Autowaschanlage, Registrierkasse, ... Mach' die Augen im täglichen Leben auf! 2. Ist das Gleiche. 3. Zustandsautomaten laufen generell folgendermaßen ab: 3.1 Der Automat befindet sich in einem Zustand Xn und wartet auf das nächste Ereignis. 3.2 Das Ereignis Y geschieht. Der Automat nimmt dieses Ereignis und verarbeitet es entsprechend seinem derzeitigen Zustand. Als Ergebnis der Verarbeitung wechselt er in den Zustand Xk. 3.3 (=3.1, aber in anderem Zustand) Der Automat wartet auf das nächste Ereignis. Das Ereignis führt keine Verarbeitung durch. Es meldet ausschließlich "Ich bin passiert" an den Zustandsautomaten und übergibt ihm u.U. Daten. Das klingt furchtbar abstrakt (und für einen Programmierer ungewohnt). Schau es Dir einfach am Beispiel "Registrierkasse an: - Kassiererin hat sich an Kasse angemeldet und wartet (1. Zustand, vor Verkauf). - Kunde kommt; sie zieht einen Artikel über den Scanner (Zustand --> 2. Zustand, im Verkauf). - sie zieht weitere Artikel eins nach dem anderen über den Scanner (Zustand jeweils 2. Zustand). - Band leer: sie haut "Endsummen-Taste" (---> 3. Zustand, Bezahlen, Geldschublade auf). - Kunde gibt Geld, sie tippt Betrag ein (---> 4. Zustand, Rückgeld). - sie schließt die Geldlade (---> 1. Zustand, vor Verkauf). 4. ja Du siehst hoffentlich: Zustandsautomaten sind eine andere - wie ich meine natürlichere - Art zu denken als die "strukturierte Programmierung". Die Umstellung erfordert von Dir allerdings einen erheblichen Denkaufwand. Im Endeffekt lohnt sich das Ganze allerdings, denn Zustandsautomaten erfordern vielfach einen erheblich geringeren Programmieraufwand als strkturierte Programme. Bei Registrierkassen z.B. spart der Zustandsautomat in der Implementierung mindestens 3/4 der Lines of Code gegenüber anderen Implementierungen. Grüße Bernhard
Bernhard Reichenbach wrote: > Programmierung". Die Umstellung erfordert von Dir allerdings einen > erheblichen Denkaufwand. Ich find den gar nicht so schlimm. Wie du schon schreibst, sind Zustandsautomaten eine ganz natürliche Sache. Wir alle sind damit groß geworden. Man muss die Welt um sich nur genau beobachten. Anderes Beispiel: Getränkeautomat. Der sitzt in seinem Zustand: Idle ( = Grundzustand, Wartend) Welche 'Ereignisse' können eintreten? Dazu muss man sich fragen: Welche Möglichkeit für Input gibt es denn überhaupt. So ein Getränkeautomat hat ja im wesentlichen nur 2 'Input-Möglichkeiten'. Da ist zum einen das Einwerfen einer Münze und zum anderen das Drücken der Auswurftaste. (Ist ein einfacher Automat. Geldrückgabe ist nicht :-) Also muss ich mich fragen: Was passiert den beim Einwurf einer Münze? Zunächst mal wird die Münze registriert und der Automat wechselt in einen neuen Zustand, nämlich Münzzählung. Den neuen Zustand möchte ich deswegen haben, weil im Idle Zustand auf der Anzeige irgendwelche Werbung angezeigt wird, während mit dem Einwurf der ersten Münze der eingeworfene Betrag angezeigt wird. Wird im Zustand Idle hingegen die Auswurftaste betätigt, so passiert gar nichts und der Automat bleibt im Zustand Idle Im Zustand Münzzählung gibt es wieder die beiden Input Möglichkeiten. Also muss ich mir für beide überlegen, was beim Eintreten des jeweiligen Events passieren soll. Münze eingeworfen: Münze wird registriert, Summe erhöht und angezeigt neuer Zustand ist nach wie vor Münzzählung Getränkeauswurf: Hier hängt es von einer weiteren Bedingung ab, wie es weiter geht. Ist die eingeworfene Summe < verkauspreis, dann verbleibt man im Zustand Münzzählung und es passiert nichts weiter Ist die Summe aber größ genug, dann wird ein Getränk ausgeworfen, das Wechselgeld ausgeworfen und der Automat wechselt wieder in den Zustand Idle. Automaten haben nun den Vorteil, dass sich ihre Logik leicht und vor allen Dingen losgelöst von einer Programmiersprache veranschaulichen lässt. jeder Automat besteht doch im Grunde aus einer Liste in der die Zustände + Bedingung zu Aktionen und einem neuen Zustand führt. Das kann man in Tabellenform darstellen. Ich sag hier absichtlich Bedigung, weil man auf die Art nicht nur externe Events zu einem Zustandswechsel nutzen kann, sondern auch interne Bedingungen, wie zb. ob die eingeworfene Geldmenge ausgereicht hat. Zustand Bedingung Aktion Neuer Zustand ----------------------------------------------------------- Ein Summe = 0 Idle Idle Münze Summe = Münzwert Zählung Ausgabe Idle Zählung Münze Summe += Münzwert Zählung Ausgabe Prüfung Prüfung Summe < Preis Zählung Summe >= Preis Getränk auswerfen Summe - Preis ausw. Summe = 0 Idle Anstatt in Tabellenform kann man einen Automaten auch wunderbar als Graphik darstellen. jeder Zustand ist ein Kreis. Zustandsübergänge werden durch Pfeile von einem Kreis zum anderen dargestellt. Beim Pfeil steht dabei, wann dieser Übergang genommen wird und welche Aktion dabei auszuführen ist. Insbesonders letztere Form eignet sich hervorragend dazu, einen Automaten zu entwerfen und die Funktionalität am Papier durchzu- spielen um Fehler im Ablauf zu finden. Ob man das dann in der Implementierung mit switch-case macht oder irgendwie anders, ist ein Implementierungsdetail, dass nicht weiter interessiert. Die Logik muss implementiert werden, wie auch immer man das macht. Es ist auch denkbar, dass man sich einen Interpreter macht, der auf Automaten in Tabellenform losgelassen wird. Dann steckt der Automat in dieser Kombination: Tabelle + Interpreter der die Tabelle abarbeitet. Aber auch hier: Für die Funktion des Automaten ist das unerheblich. Dessen Logik steckt in den Zustandsübergängen und den dabei ablaufenden Aktionen. Eine Zustandsmaschine ist ein Konzept und kein Programmierrezept.
Danke für eure Antworten. Das allgemeine Prinzip und der Ablauf ist mir eigentlich schon bekannt. Es stellt sich bei mir die Frage, wie ich eine simple Zustandsmaschine am besten in Code umsetze... Wie schon erwähnt gibt es ecklige, schöne und elegante Möglichkeiten. Da ich mit diesem Gebiet aber noch nicht so vertraut bin, weiss ich nicht, was eine schöne, und was eine unpassende Lösung ist. Ist die Art und Weise wie in Beitrag 3 dieses Threads in Ordnung, sofern an die Zustandsmaschine noch keine wahnsinnigen Ansprüche gestellt werden? Den Goto-Befehl will ich eigentlich lieber nicht verwenden. // Dieser Beitrag wurde verfasst, bevor ich die Antwort von Karl Heinz Buchegger gesehen habe. // Nun nach dem ich den Beitrag von Buchegger gelesen habe, bin ich mir bewusst, dass ich vom Begriff Zustandsautomaten wohl ein wenig zu konkrete Gedanken hatte. Grundsätzlich interessiert mich aber immer noch die Implementierung dieser Abläufe. Wie geht man da am besten ran?
Stefan Nüesch wrote: > Danke für eure Antworten. > > Das allgemeine Prinzip und der Ablauf ist mir eigentlich schon bekannt. > Es stellt sich bei mir die Frage, wie ich eine simple Zustandsmaschine > am besten in Code umsetze... Es gibt kein allgemeingültiges 'bestes'. Programmieren bedeutet oft Kompromisse schliessen. Das Beste ist immer das, was du beherrscht. > Ist die Art und Weise wie in Beitrag 3 dieses Threads in Ordnung, sofern > an die Zustandsmaschine noch keine wahnsinnigen Ansprüche gestellt > werden? Ja, sicher. > Grundsätzlich interessiert mich aber immer noch die Implementierung > dieser Abläufe. Wie geht man da am besten ran? Zeichne dir einen Plan, spiel in durch und wenn du überzeugt bist, dass du alle Zustände hast und alle Übergänge richtig sind, setz dich an deinen Editor und beginne mit der Implementierung. Ob du den äußeren switch über die Zustände machst oder ob du ihn über die Events machst, musst du von Fall zu Fall entscheiden. Je nachdem, was dir in der konkreten Situation am natürlichsten vorkommt. Letztendlich hast du konzeptionell ein 2D Array: Die Zeilenbeschriftungen sind die Zustände und die Spalten- beschriftungen sind die Bedingungen. Im Schnittpunkt aus Zeile und Spalte findet sich der neue Zustand bzw. die aus- zuführende Aktion. Ob du aber zum bestimmen der richtigen Zelle zuerst die Spalte oder zuerst die Zeile auswählst, ist weitgehend Geschmackssache, bzw. hat keinen wirklich triftigen technischen Grund.
Danke für deinen Beitrag. Ich denke meine letzten Einwände und Unklarheiten sind nun geklärt... ;)
Eine funktionierende Zustandsmachine gibt es von Atmel im Sourcecode zum butterfly. Für avr-gcc gibt es dazu auch einen port im Netz, falls du den brauchst, mal googeln. Oliver
Darauf wurde glaube ich noch nicht so eingegangen: >3. Meiner Meinung nach darf ich über einen Interrupt die Zustände nicht >direkt ändern, da es sonst zu fatalen Fehlern führen könnte. Wie aber >kann ich Interrupts in eine Zustandsmaschine einbeziehen? Sollte ich das >etwa gänzlich vermeiden? Die Interrupt-Service-Routine (ISR) sollte bekanntlich möglichst wenig Code enthalten. Du setzt z. B. nur ein Flag für dieses Interrupt auf 1. In jedem Status schreibst du nun ein Stückchen Code (if flag == 1 ...), wo steht, was gemacht werden soll, z. B. ein Übergang in einen anderen Zustand. Dann musst du noch irgendwo das Flag auf 0 zurück setzen.
>In jedem Status schreibst du nun ein Stückchen Code (if flag == 1 ...),
Ob du das flag pollst, oder den trigger für den interrupt spielt keine
rolle...
Was die Beispiele angeht: Schau dir Implementationen beliebiger Protokolle an (TCP, DMX, ...) - das sind alles FSMs. Ein Protokoll macht im Prinzip nichts anderes als 2 FSMs synchron zu halten bzw. zu synchronisieren. Grüße, phlo
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.