Tutorials zu Zustandsautomaten [geschlossen]

73

Ich frage mich nur, ob jemand gute Tutorials im Internet zur Entwicklung von Zustandsautomaten kennt. Oder E-Books?

Ich fange an, an Zustandsautomaten zu arbeiten und brauche nur etwas Allgemeines, um loszulegen.

ant2009
quelle

Antworten:

138

Zustandsautomaten sind in C sehr einfach, wenn Sie Funktionszeiger verwenden.

Grundsätzlich benötigen Sie zwei Arrays - eines für Statusfunktionszeiger und eines für Statusübergangsregeln. Jede Statusfunktion gibt den Code zurück. Sie suchen die Statusübergangstabelle nach Status und Rückkehrcode, um den nächsten Status zu finden, und führen ihn dann einfach aus.

int entry_state(void);
int foo_state(void);
int bar_state(void);
int exit_state(void);

/* array and enum below must be in sync! */
int (* state[])(void) = { entry_state, foo_state, bar_state, exit_state};
enum state_codes { entry, foo, bar, end};

enum ret_codes { ok, fail, repeat};
struct transition {
    enum state_codes src_state;
    enum ret_codes   ret_code;
    enum state_codes dst_state;
};
/* transitions from end state aren't needed */
struct transition state_transitions[] = {
    {entry, ok,     foo},
    {entry, fail,   end},
    {foo,   ok,     bar},
    {foo,   fail,   end},
    {foo,   repeat, foo},
    {bar,   ok,     end},
    {bar,   fail,   end},
    {bar,   repeat, foo}};

#define EXIT_STATE end
#define ENTRY_STATE entry

int main(int argc, char *argv[]) {
    enum state_codes cur_state = ENTRY_STATE;
    enum ret_codes rc;
    int (* state_fun)(void);

    for (;;) {
        state_fun = state[cur_state];
        rc = state_fun();
        if (EXIT_STATE == cur_state)
            break;
        cur_state = lookup_transitions(cur_state, rc);
    }

    return EXIT_SUCCESS;
}

Ich stelle keine lookup_transitions()Funktion ein, da sie trivial ist.

So mache ich seit Jahren Zustandsmaschinen.

qrdl
quelle
15
Schön, danke dafür. Der einzig mögliche Fehler besteht darin, dass die lookup_transitions mit dieser Datenstruktur der Übergangstabelle wahrscheinlich linear (O (n)) sind. Es ist möglich, es mit einem multidimentionalen Array zu verbessern - garantiert O (1). Z.B. Die Tabelle kann als multidimentionales Array dargestellt werden, bei dem der Schlüssel der Status ist und der Wert ein Array, bei dem der Schlüssel der Rückkehrcode und der Wert der nächste Status ist: int state_transitions[][3] = { [entry] = { foo, end, foo }, ... } /* ok, fail, repeat */
Alex
2
Warum geben Ihre Statusfunktionen für die Suchfunktion nicht enum anstelle von ints zurück? Sie geben einen Ret-Code zurück, nicht wahr?
Django
Wäre es nicht viel einfacher, nur src_stateund dst_stateals Funktionszeiger zu haben? Ich verstehe den Vorteil nicht, sie vom Typ enum zu haben, wenn Sie sie nur verwenden, um einige Funktionszeiger in einem Array nachzuschlagen.
Multisync
2
@Multisync Im Allgemeinen ist state! = Function, es ist üblich, mehrere verschiedene Zustände zu haben, die tatsächlich dieselbe Funktion verwenden. Sie können beispielsweise mehrere Funktionen zum Vorbereiten von Nachrichten sowie eine Funktion zum Senden und eine Funktion zum Empfangen von Antworten verwenden. Diese beiden E / A-Funktionen werden jedoch in unterschiedlichen Zuständen verwendet.
Qrdl
Jeder Zustand kann als eine "sub_main_function" betrachtet werden. Aufgrund der Aktionen in diesen "sub_main_functions" kann er wieder in einen anderen Zustand wechseln. Verwenden wir einen Schalter. Jeder "case state:" hat mehrere Funktionen in der Seite, jemand mit mir?
Fuevo
29

Ich bevorzuge die Verwendung von Funktionszeigern gegenüber gigantischen switchAnweisungen, aber im Gegensatz zu qrdls Antwort verwende ich normalerweise keine expliziten Rückkehrcodes oder Übergangstabellen.

In den meisten Fällen möchten Sie außerdem, dass ein Mechanismus zusätzliche Daten weitergibt. Hier ist ein Beispiel für eine Zustandsmaschine:

#include <stdio.h>

struct state;
typedef void state_fn(struct state *);

struct state
{
    state_fn * next;
    int i; // data
};

state_fn foo, bar;

void foo(struct state * state)
{
    printf("%s %i\n", __func__, ++state->i);
    state->next = bar;
}

void bar(struct state * state)
{
    printf("%s %i\n", __func__, ++state->i);
    state->next = state->i < 10 ? foo : 0;
}

int main(void)
{
    struct state state = { foo, 0 };
    while(state.next) state.next(&state);
}
Christoph
quelle
Sie geben mainkeinen Wert zurück. . . sollte es?
Dreamlax
1
@dreamlax: C99 5.1.2.2.3: Erreichen des Endes der main()impliziten Rückkehr0
Christoph
Diese Antwort hat mir sehr gut gefallen. Einfach und direkt. Gut gemacht.
AntonioCS
Entschuldigung, ich verstehe es wirklich nicht. Was passiert in der whileBedingung in der letzten Zeile? Rufen Sie an foo()? Welche Standardargumente werden angenommen, wenn keine angegeben sind?
Multisync
1
@Multisync Der Strukturinitialisierer in der vorherigen Zeile setzt state.next(einen Funktionszeiger) auf die Adresse von foo. Also state.next(&state)ist es dasselbe wie foo(&state)(die erste Iteration der Schleife zeigt später woanders hin). Zum Vergleich: Wenn dies C ++ foo()wäre , wäre es ein Mitglied der StateKlasse ( State::foo()) und würde keine Parameter annehmen. Sein Körper würde this->next = baranstelle von verwenden state->next = bar. In C müssen Sie das Äquivalent des thisZeigers explizit übergeben, da keine zustandsbehafteten Klassenbereiche vorhanden sind.
Dan Bechard
9

Leider sind die meisten Artikel über Zustandsautomaten für C ++ oder andere Sprachen geschrieben, die Polymorphismus direkt unterstützen, da es hilfreich ist, die Zustände in einer FSM-Implementierung als Klassen zu modellieren, die von einer abstrakten Zustandsklasse abgeleitet sind.

Es ist jedoch ziemlich einfach, Zustandsautomaten in C zu implementieren, indem entweder switch-Anweisungen verwendet werden, um Ereignisse in Zustände zu versenden (bei einfachen FSMs codieren sie so ziemlich direkt) oder Tabellen, um Ereignisse Zustandsübergängen zuzuordnen.

Hier finden Sie einige einfache, aber anständige Artikel zu einem Grundgerüst für Zustandsautomaten in C:

Bearbeiten : Site "in Wartung", Webarchiv-Links:

switchAnweisungsbasierte Zustandsautomaten verwenden häufig eine Reihe von Makros, um die Mechanik der switchAnweisung zu "verbergen" (oder verwenden eine Reihe von if/ then/ elseAnweisungen anstelle von a switch) und erstellen eine "FSM-Sprache" zur Beschreibung der Zustandsmaschine in C. Quelle. Ich persönlich bevorzuge den tabellenbasierten Ansatz, aber diese haben sicherlich Vorteile, sind weit verbreitet und können insbesondere für einfachere FSMs effektiv sein.

Ein solches Framework wird von Steve Rabin in "Game Programming Gems", Kapitel 3.0 (Entwerfen einer allgemeinen robusten KI-Engine) beschrieben .

Ein ähnlicher Satz von Makros wird hier diskutiert:

Wenn Sie sich auch für C ++ - Zustandsmaschinenimplementierungen interessieren, finden Sie noch viel mehr. Ich werde Hinweise posten, wenn Sie interessiert sind.

Michael Burr
quelle
1
Danke, das waren gute Artikel. Ich habe hier auch einen gefunden. en.wikipedia.org/wiki/Event_driven_finite_state_machine
ant2009
8

Zustandsautomaten sind nicht von Natur aus ein Tutorial, das erklärt oder sogar verwendet werden muss. Ich schlage vor, dass Sie sich die Daten ansehen und wie sie analysiert werden müssen.

Zum Beispiel musste ich das Datenprotokoll für einen Near Space-Ballonflugcomputer analysieren. Es speicherte Daten auf der SD-Karte in einem bestimmten Format (binär), das in eine durch Kommas getrennte Datei analysiert werden musste. Die Verwendung einer Zustandsmaschine ist hierfür am sinnvollsten, da wir je nach der nächsten Information ändern müssen, was wir analysieren.

Der Code wird mit C ++ geschrieben und ist als ParseFCU verfügbar . Wie Sie sehen können, erkennt es zuerst, welche Version wir analysieren, und von dort aus werden zwei verschiedene Zustandsautomaten eingegeben.

Es tritt in einem bekanntermaßen guten Zustand in die Zustandsmaschine ein. An diesem Punkt beginnen wir mit dem Parsen. Je nachdem, auf welche Zeichen wir stoßen, wechseln wir entweder zum nächsten Zustand oder kehren zu einem vorherigen Zustand zurück. Dies ermöglicht es dem Code grundsätzlich, sich selbst an die Art und Weise anzupassen, in der die Daten gespeichert werden, und ob bestimmte Daten überhaupt vorhanden sind oder nicht.

In meinem Beispiel ist die GPS-Zeichenfolge keine Voraussetzung für die Protokollierung des Flugcomputers. Daher kann die Verarbeitung der GPS-Zeichenfolge übersprungen werden, wenn die Endbytes für diesen einzelnen Protokollschreibvorgang gefunden werden.

Zustandsautomaten sind einfach zu schreiben, und im Allgemeinen folge ich der Regel, dass sie fließen sollen. Eingaben, die durch das System gehen, sollten mit gewisser Leichtigkeit von Zustand zu Zustand fließen.

X-Istence
quelle
2
@Chris: Near Space ist definiert als alles über 60.000 Fuß, unser Ballon hat 92.999 Fuß erreicht. Irgendwann wird der Latexballon aufgrund der Dekompression (das Gas dehnt den Ballon weiter aus) so groß, dass der Ballon platzt Zeigen Sie, dass das Near-Space-Fahrzeug frei auf die Erde zurückfällt (wir bringen einen Fallschirm vom Kurs ab). Weitere Informationen zu unseren Near-Space-Bemühungen und Google finden Sie im verknüpften Wiki. Es ist ein absolut großartiges Hobby!
X-Istence
4
Das klingt nach einem äußerst ineffizienten, lächerlich teuren, vielleicht etwas verschwenderischen und absolut fantastischen Hobby.
Chris Lutz
1
Viele leistungsstarke und wichtige Experimente wurden von Ballonplattformen aus durchgeführt. Sie müssen die Kosten mit denen für den Start einer gleichwertigen Umlaufbahnplattform vergleichen . Wenn Sie ungefähr 100.000 Fuß erreichen, ist Ihr Wärmemanagementproblem das eines Raumfahrzeugs wesentlich: Leitfähige und konvektive Heizung / Kühlung verschwinden im Vergleich zur Strahlung.
dmckee --- Ex-Moderator Kätzchen
1
@ Chris: Wir hatten ein Budget von 2000 US-Dollar, mit dem wir arbeiten konnten, und wir haben bisher zwei Ballons erfolgreich gestartet. Der teuerste Teil war das Helium zum Füllen der Latexballons, die der zweitteuerste Teil waren.
X-Istence
1
@ ChrisLutz Ich würde genau das Gegenteil argumentieren. Im Vergleich zur Alternative: Raketen; Es ist weitaus effizienter, kostengünstiger und deutlich weniger verschwenderisch, aber etwas weniger beeindruckend.
Dan Bechard
4

Das ist alles was Sie wissen müssen.

int state = 0;
while (state < 3)
{
    switch (state)
    {
        case 0:
            // Do State 0 Stuff
            if (should_go_to_next_state)
            {
                state++;
            }
            break;
        case 1:
            // Do State 1 Stuff    
            if (should_go_back) 
            {
                state--;
            }    
            else if (should_go_to_next_state) 
            {
                state++;
            }
            break;
        case 2:
            // Do State 2 Stuff    
            if (should_go_back_two) 
            {
                state -= 2;
            }    
            else if (should_go_to_next_state) 
            {
                state++;
            }
            break;
        default:
            break;
    }
}
ChaosPandion
quelle
7
Ich würde es für besser halten, den Status explizit festzulegen, aber das bin nur ich.
Chris Lutz
2
Sie haben viel ausgelassen, zum Beispiel: Unterzustände; Ereignisse und Ereignis / Zustand-Kombinationen; Zustandsübergangsdiagramme; Wachen ("Status nicht ändern, wenn"); Zustandseintritts- und Zustandsausgangsmethoden ("Führen Sie beim Verlassen dieses Zustands die folgende Methode aus").
ChrisW
2
Dies vereinfacht Zustandsmaschinen zu stark und ist kein besonders gutes Beispiel.
X-Istence
2
Machen Sie etwas, das sehr einfach ist, nicht zu kompliziert.
ChaosPandion
1
Sicher, als Grundgerüst dafür, wie eine Basis-Zustandsmaschine aussehen könnte, könnte dies ausreichen. Aber ich denke, es ist nicht ganz "alles, was Sie wissen müssen". Möglicherweise möchten Sie Ihren Status auch nicht signieren.
Mrduclaw
4

Die objektorientierte Modellierung in Echtzeit war fantastisch (1994 veröffentlicht und jetzt für nur 81 Cent plus 3,99 US-Dollar Versand verkauft).

ChrisW
quelle
3
1 neu ab 60,20 USD und 24 gebraucht ab 0,81 USD. Das ist ziemlich humorvoll.
März
Interessant, dass der Referrer auf diesem Link StackOverflow ist.
Carl
2
@ Carl Auto-
ChrisW
3

In C gibt es eine Menge Lektionen zum Erlernen der handwerklichen Zustandsmaschinen, aber ich möchte auch den Ragel-Zustandsmaschinen-Compiler vorschlagen:

http://www.complang.org/ragel/

Es gibt eine recht einfache Möglichkeit, Zustandsautomaten zu definieren. Anschließend können Sie Diagramme erstellen, Code in verschiedenen Stilen (tabellengesteuert, goto-gesteuert) generieren, diesen Code analysieren, wenn Sie möchten usw. Und es ist leistungsstark und kann in der Produktion verwendet werden Code für verschiedene Protokolle.

Roman Khimov
quelle
-6

Zustandsautomaten können für ein komplexes Problem sehr komplex sein. Sie sind auch unerwarteten Fehlern ausgesetzt. Sie können sich in einen Albtraum verwandeln, wenn jemand auf einen Fehler stößt oder die Logik in Zukunft ändern muss. Sie sind auch ohne das Zustandsdiagramm schwer zu verfolgen und zu debuggen. Strukturierte Programmierung ist viel besser (zum Beispiel würden Sie wahrscheinlich keine Zustandsmaschine auf Mainline-Ebene verwenden). Sie können die strukturierte Programmierung auch im Interrupt-Kontext verwenden (wo normalerweise Zustandsautomaten verwendet werden). Weitere Informationen finden Sie in diesem Artikel "Makros zum Simulieren von Multitasking- / Blockierungscode auf Interrupt-Ebene" unter codeproject.com.

eddyq
quelle
Beantwortet die Frage nicht. Stattdessen wird in einem Editorial erläutert, warum Zustandsautomaten schlecht sind.
the_endian