Gibt es ein typisches Implementierungsmuster für Zustandsmaschinen?

Wir müssen eine einfache Zustandsmaschine in implementieren C.
Ist eine Standard-Switch-Anweisung der beste Weg?
Wir haben einen aktuellen Zustand (Zustand) und einen Auslöser für den Übergang.

switch(state)
{
  case STATE_1:
     state = DoState1(transition);
     break;
  case STATE_2:
     state = DoState2(transition);
     break;
}
...
DoState2(int transition)
{
   // Do State Work
   ...
   if(transition == FROM_STATE_2) {
     // New state when doing STATE 2 -> STATE 2
   }
   if(transition == FROM_STATE_1) {
    // New State when moving STATE 1 -> STATE 2
   }
   return new_state;
}

Gibt es einen besseren Weg für einfache Zustandsmaschinen

EDIT: Für C++ denke ich, dass der Boost Zustandsdiagramm Bibliothek könnte der richtige Weg sein. Allerdings tut es das nicht Hilfe bei C. Konzentrieren wir uns auf den C-Anwendungsfall.

Ich bevorzuge für die meisten Zustandsmaschinen einen tabellengesteuerten Ansatz:

typedef enum { STATE_INITIAL, STATE_FOO, STATE_BAR, NUM_STATES } state_t;
typedef struct instance_data instance_data_t;
typedef state_t state_func_t( instance_data_t *data );

state_t do_state_initial( instance_data_t *data );
state_t do_state_foo( instance_data_t *data );
state_t do_state_bar( instance_data_t *data );

state_func_t* const state_table[ NUM_STATES ] = {
    do_state_initial, do_state_foo, do_state_bar
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    return state_table[ cur_state ]( data );
};

int main( void ) {
    state_t cur_state = STATE_INITIAL;
    instance_data_t data;

    while ( 1 ) {
        cur_state = run_state( cur_state, &data );

        // do other program logic, run other state machines, etc
    }
}

Dies kann natürlich erweitert werden, um mehrere Zustandsmaschinen usw. zu unterstützen. Übergangsaktionen können ebenfalls untergebracht werden:

typedef void transition_func_t( instance_data_t *data );

void do_initial_to_foo( instance_data_t *data );
void do_foo_to_bar( instance_data_t *data );
void do_bar_to_initial( instance_data_t *data );
void do_bar_to_foo( instance_data_t *data );
void do_bar_to_bar( instance_data_t *data );

transition_func_t * const transition_table[ NUM_STATES ][ NUM_STATES ] = {
    { NULL,              do_initial_to_foo, NULL },
    { NULL,              NULL,              do_foo_to_bar },
    { do_bar_to_initial, do_bar_to_foo,     do_bar_to_bar }
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    state_t new_state = state_table[ cur_state ]( data );
    transition_func_t *transition =
               transition_table[ cur_state ][ new_state ];

    if ( transition ) {
        transition( data );
    }

    return new_state;
};

Der tabellengesteuerte Ansatz ist einfacher zu pflegen und zu erweitern und einfacher Zustandsdiagrammen zuzuordnen.

Sie haben vielleicht meine Antwort auf eine andere C-Frage gesehen, in der ich FSM erwähnt habe! So mache ich es:

FSM {
  STATE(x) {
    ...
    NEXTSTATE(y);
  }

  STATE(y) {
    ...
    if (x == 0) 
      NEXTSTATE(y);
    else 
      NEXTSTATE(x);
  }
}

Mit den folgenden Makros definiert

#define FSM
#define STATE(x)      s_##x :
#define NEXTSTATE(x)  goto s_##x

Dies kann an den konkreten Fall angepasst werden. Beispielsweise können Sie eine Datei haben FSMFILE dass Sie Ihren FSM ansteuern möchten, also könnten Sie die Aktion des Lesens des nächsten Zeichens in das Makro selbst integrieren:

#define FSM
#define STATE(x)         s_##x : FSMCHR = fgetc(FSMFILE); sn_##x :
#define NEXTSTATE(x)     goto s_##x
#define NEXTSTATE_NR(x)  goto sn_##x

Jetzt haben Sie zwei Arten von Übergängen: Einer geht in einen Zustand und liest ein neues Zeichen, der andere geht in einen Zustand, ohne Eingaben zu verbrauchen.

Sie können die Handhabung von EOF auch automatisieren mit etwas wie:

#define STATE(x)  s_##x  : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
                             goto sx_endfsm;\
                  sn_##x :

#define ENDFSM    sx_endfsm:

Das Gute an diesem Ansatz ist, dass Sie ein Zustandsdiagramm, das Sie zeichnen, direkt in funktionierenden Code übersetzen können, und umgekehrt können Sie ganz einfach ein Zustandsdiagramm aus dem Code zeichnen.

Bei anderen Techniken zur Implementierung von FSM ist die Struktur der Übergänge in Kontrollstrukturen vergraben (while, if, switch …) und wird durch Variablenwerte (typischerweise a state Variable) und es kann eine komplexe Aufgabe sein, das schöne Diagramm mit einem verworrenen Code in Beziehung zu setzen.

Ich habe diese Technik aus einem Artikel gelernt, der in der großartigen Zeitschrift “Computer Language” erschienen ist, die leider nicht mehr veröffentlicht wird.

Im UML destilliert von Martin Fowlersagt er (kein Wortspiel beabsichtigt) in Kapitel 10 Zustandsmaschinendiagramme (Hervorhebung von mir):

Ein Zustandsdiagramm kann auf drei Arten implementiert werden: verschachtelter Schalterdas Zustandsmusterund
Zustandstabellen.

Nehmen wir ein vereinfachtes Beispiel für die Zustände des Displays eines Mobiltelefons:

Verschachtelter Schalter

Fowler hat ein Beispiel für C#-Code gegeben, aber ich habe es an mein Beispiel angepasst.

public void HandleEvent(PhoneEvent anEvent) {
    switch (CurrentState) {
    case PhoneState.ScreenOff:
        switch (anEvent) {
        case PhoneEvent.PressButton:
            if (powerLow) { // guard condition
                DisplayLowPowerMessage(); // action
                // CurrentState = PhoneState.ScreenOff;
            } else {
                CurrentState = PhoneState.ScreenOn;
            }
            break;
        case PhoneEvent.PlugPower:
            CurrentState = PhoneState.ScreenCharging;
            break;
        }
        break;
    case PhoneState.ScreenOn:
        switch (anEvent) {
        case PhoneEvent.PressButton:
            CurrentState = PhoneState.ScreenOff;
            break;
        case PhoneEvent.PlugPower:
            CurrentState = PhoneState.ScreenCharging;
            break;
        }
        break;
    case PhoneState.ScreenCharging:
        switch (anEvent) {
        case PhoneEvent.UnplugPower:
            CurrentState = PhoneState.ScreenOff;
            break;
        }
        break;
    }
}

Zustandsmuster

Hier ist eine Implementierung meines Beispiels mit dem GoF State-Muster:

Zustandstabellen

Inspiriert von Fowler, hier ist eine Tabelle für mein Beispiel:

Source State    Target State    Event         Guard        Action
--------------------------------------------------------------------------------------
ScreenOff       ScreenOff       pressButton   powerLow     displayLowPowerMessage  
ScreenOff       ScreenOn        pressButton   !powerLow
ScreenOn        ScreenOff       pressButton
ScreenOff       ScreenCharging  plugPower
ScreenOn        ScreenCharging  plugPower
ScreenCharging  ScreenOff       unplugPower

Vergleich

Verschachtelte Schalter halten die gesamte Logik an einer Stelle, aber der Code kann schwer zu lesen sein, wenn es viele Zustände und Übergänge gibt. Es ist möglicherweise sicherer und einfacher zu validieren als die anderen Ansätze (kein Polymorphismus oder Interpretieren).

Die State-Pattern-Implementierung verteilt möglicherweise die Logik auf mehrere separate Klassen, was das Verständnis als Ganzes zu einem Problem machen kann. Andererseits sind die kleinen Klassen separat leicht zu verstehen. Das Design ist besonders anfällig, wenn Sie das Verhalten durch Hinzufügen oder Entfernen von Übergängen ändern, da es sich um Methoden in der Hierarchie handelt und viele Änderungen am Code vorgenommen werden können. Wenn Sie nach dem Designprinzip kleiner Schnittstellen leben, werden Sie feststellen, dass dieses Muster nicht wirklich gut funktioniert. Wenn die Zustandsmaschine jedoch stabil ist, sind solche Änderungen nicht erforderlich.

Der Zustandstabellen-Ansatz erfordert das Schreiben einer Art Interpreter für den Inhalt (dies könnte einfacher sein, wenn Sie die von Ihnen verwendete Sprache reflektieren), was im Vorfeld eine Menge Arbeit bedeuten kann. Wie Fowler betont, könnten Sie, wenn Ihre Tabelle von Ihrem Code getrennt ist, das Verhalten Ihrer Software ändern, ohne neu zu kompilieren. Dies hat jedoch einige Auswirkungen auf die Sicherheit; die Software verhält sich basierend auf dem Inhalt einer externen Datei.

Bearbeiten (nicht wirklich für C-Sprache)

Es gibt auch einen fließenden Schnittstellenansatz (auch bekannt als interne domänenspezifische Sprache), der wahrscheinlich durch Sprachen erleichtert wird, die dies getan haben erstklassige Funktionen. Das Staatenlose Bibliothek existiert und dieser Blog zeigt ein einfaches Beispiel mit Code. EIN Java-Implementierung (vor Java8) wird diskutiert. Mir wurde a gezeigt Python-Beispiel auf GitHub auch.

Ich habe auch den Tabellenansatz verwendet. Allerdings gibt es Overhead. Warum eine zweite Liste von Zeigern speichern? Eine Funktion in C ohne () ist ein konstanter Zeiger. Sie können also Folgendes tun:

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

typedef struct state
{
  state_func_t function;

  // other stateful data

} state_t;

void do_state_initial( state_t* );
void do_state_foo( state_t* );
void do_state_bar( state_t* );

void run_state( state_t* i ) {
    i->function(i);
};

int main( void ) {
    state_t state = { do_state_initial };

    while ( 1 ) {
        run_state( state );

        // do other program logic, run other state machines, etc
    }
}

Abhängig von Ihrem Angstfaktor (dh Sicherheit vs. Geschwindigkeit) möchten Sie natürlich nach gültigen Hinweisen suchen. Für Zustandsmaschinen mit mehr als drei oder mehr Zuständen sollte der obige Ansatz weniger Anweisungen umfassen als ein äquivalenter Schalter- oder Tabellenansatz. Sie könnten sogar makroisieren als:

#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))

Außerdem glaube ich aus dem Beispiel des OP, dass es eine Vereinfachung geben sollte, die beim Nachdenken / Entwerfen einer Zustandsmaschine vorgenommen werden sollte. Ich glaube nicht, dass der Übergangszustand für Logik verwendet werden sollte. Jede Zustandsfunktion sollte in der Lage sein, ihre gegebene Rolle ohne explizite Kenntnis vergangener Zustände auszuführen. Grundsätzlich entwerfen Sie, wie Sie von dem Zustand, in dem Sie sich befinden, in einen anderen Zustand übergehen.

Beginnen Sie schließlich nicht mit dem Entwurf einer Zustandsmaschine basierend auf “funktionalen” Grenzen, sondern verwenden Sie dafür Unterfunktionen. Unterteilen Sie die Zustände stattdessen danach, wann Sie warten müssen, bis etwas passiert, bevor Sie fortfahren können. Dies trägt dazu bei, die Anzahl der Male zu minimieren, die Sie den Zustandsautomaten ausführen müssen, bevor Sie ein Ergebnis erhalten. Dies kann beim Schreiben von I/O-Funktionen oder Interrupt-Handlern wichtig sein.

Außerdem ein paar Vor- und Nachteile der klassischen switch-Anweisung:

Vorteile:

• es ist in der Sprache, also ist es dokumentiert und klar
• Zustände werden dort definiert, wo sie aufgerufen werden
• kann mehrere Zustände in einem Funktionsaufruf ausführen
• Code, der allen Zuständen gemeinsam ist, kann vor und nach der switch-Anweisung ausgeführt werden

Nachteile:

• kann mehrere Zustände in einem Funktionsaufruf ausführen
• Code, der allen Zuständen gemeinsam ist, kann vor und nach der switch-Anweisung ausgeführt werden
• Switch-Implementierung kann langsam sein

Beachten Sie die beiden Attribute, die sowohl pro als auch contra sind. Ich denke, der Wechsel bietet die Möglichkeit, zu viel zwischen den Staaten zu teilen, und die gegenseitige Abhängigkeit zwischen den Staaten kann unüberschaubar werden. Für eine kleine Anzahl von Zuständen kann es jedoch am lesbarsten und am besten wartbar sein.

es gibt auch die logisches Gitter was wartungsfreundlicher ist, wenn die Zustandsmaschine größer wird

Verwenden Sie für eine einfache Zustandsmaschine einfach eine switch-Anweisung und einen Aufzählungstyp für Ihren Zustand. Führen Sie Ihre Übergänge innerhalb der switch-Anweisung basierend auf Ihrer Eingabe durch. In einem echten Programm würden Sie offensichtlich das “if(input)” ändern, um nach Ihren Übergangspunkten zu suchen. Hoffe das hilft.

typedef enum
{
    STATE_1 = 0,
    STATE_2,
    STATE_3
} my_state_t;

my_state_t state = STATE_1;

void foo(char input)
{
    ...
    switch(state)
    {
        case STATE_1:
            if(input)
                state = STATE_2;
            break;
        case STATE_2:
            if(input)
                state = STATE_3;
            else
                state = STATE_1;
            break;
        case STATE_3:
            ...
            break;
    }
    ...
}

switch() ist eine leistungsstarke und standardmäßige Möglichkeit, Zustandsmaschinen in C zu implementieren, aber es kann die Wartbarkeit verringern, wenn Sie eine große Anzahl von Zuständen haben. Eine andere übliche Methode besteht darin, Funktionszeiger zu verwenden, um den nächsten Zustand zu speichern. Dieses einfache Beispiel implementiert ein Set/Reset-Flip-Flop:

/* Implement each state as a function with the same prototype */
void state_one(int set, int reset);
void state_two(int set, int reset);

/* Store a pointer to the next state */
void (*next_state)(int set, int reset) = state_one;

/* Users should call next_state(set, reset). This could
   also be wrapped by a real function that validated input
   and dealt with output rather than calling the function
   pointer directly. */

/* State one transitions to state one if set is true */
void state_one(int set, int reset) {
    if(set)
        next_state = state_two;
}

/* State two transitions to state one if reset is true */
void state_two(int set, int reset) {
    if(reset)
        next_state = state_one;
}