Forum: Mikrocontroller und Digitale Elektronik Einige Fragen zu Zustandsmaschinen


von Dida N. (quader)


Lesenswert?

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.

von Bernhard M. (boregard)


Lesenswert?

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...

von Dida N. (quader)


Lesenswert?

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...

von Unbekannter (Gast)


Lesenswert?

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.

von Bernhard R. (barnyhh)


Lesenswert?

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

von Karl H. (kbuchegg)


Lesenswert?

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.

von Dida N. (quader)


Lesenswert?

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?

von Karl H. (kbuchegg)


Lesenswert?

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.

von Matthias L. (Gast)


Lesenswert?


von Dida N. (quader)


Lesenswert?

Danke für deinen Beitrag.
Ich denke meine letzten Einwände und Unklarheiten sind nun geklärt... ;)

von OliverSo (Gast)


Lesenswert?

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

von Gast (Gast)


Lesenswert?

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.

von Matthias L. (Gast)


Lesenswert?

>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...

von phlo-g (Gast)


Lesenswert?

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
Noch kein Account? Hier anmelden.