Existe-t-il un modèle d'implémentation de machine d'état typique?

Nous devons mettre en œuvre une machine simple état C .
Une instruction switch standard est-elle la meilleure façon de procéder?
Nous avons un état actuel (état) et un déclencheur pour la transition.

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;
}

Existe-t-il un meilleur moyen pour les machines à états simples

EDIT: Pour C ++, je pense que la bibliothèque Boost Statechart pourrait être la voie à suivre. Cependant, cela n'aide pas avec C. Concentrons-nous sur le cas d'utilisation C.

Je préfère utiliser une approche basée sur une table pour la plupart des machines à états:

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

Cela peut bien sûr être étendu pour prendre en charge plusieurs machines à états, etc. Les actions de transition peuvent également être prises en charge:

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;
};

L'approche basée sur les tables est plus facile à maintenir et à étendre et plus simple à mapper aux diagrammes d'état.

Vous avez peut-être vu ma réponse à une autre question en C où j'ai mentionné FSM! Voici comment je le fais:

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

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

Avec les macros suivantes définies

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

Cela peut être modifié en fonction du cas spécifique. Par exemple, vous pouvez avoir un fichier FSMFILEque vous souhaitez conduire votre FSM, vous pouvez donc incorporer l'action de lecture du prochain caractère dans la macro elle-même:

#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

maintenant vous avez deux types de transitions: l'une passe à un état et lit un nouveau caractère, l'autre passe à un état sans consommer aucune entrée.

Vous pouvez également automatiser la gestion d'EOF avec quelque chose comme:

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

#define ENDFSM    sx_endfsm:

L'avantage de cette approche est que vous pouvez directement traduire un diagramme d'état que vous dessinez en code de travail et, inversement, vous pouvez facilement dessiner un diagramme d'état à partir du code.

Dans d'autres techniques d'implémentation de FSM, la structure des transitions est enterrée dans des structures de contrôle (tandis que, si, switch ...) et contrôlée par des variables value (typiquement une statevariable) et il peut être une tâche complexe de relier le joli diagramme à un code alambiqué.

J'ai appris cette technique à partir d'un article paru dans le grand magazine "Computer Language" qui, malheureusement, n'est plus publié.

J'ai également utilisé l'approche de la table. Cependant, il y a des frais généraux. Pourquoi stocker une deuxième liste de pointeurs? Une fonction en C sans le () est un pointeur const. Vous pouvez donc faire:

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

Bien sûr, en fonction de votre facteur de peur (c'est-à-dire sécurité vs vitesse), vous voudrez peut-être vérifier les pointeurs valides. Pour les machines à états de plus de trois états environ, l'approche ci-dessus devrait être moins d'instructions qu'une approche de commutateur ou de table équivalente. Vous pouvez même effectuer des macros comme:

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

De plus, je pense, d'après l'exemple de l'OP, qu'il y a une simplification à faire lors de la réflexion / conception d'une machine à états. Je ne pense pas que l'état de transition devrait être utilisé pour la logique. Chaque fonction d'état devrait être capable de remplir son rôle donné sans connaissance explicite de l'état ou des états passés. Fondamentalement, vous concevez comment passer de l'état dans lequel vous vous trouvez à un autre état.

Enfin, ne commencez pas la conception d'une machine à états basée sur des frontières «fonctionnelles», utilisez des sous-fonctions pour cela. Au lieu de cela, divisez les états en fonction du moment où vous devrez attendre que quelque chose se produise avant de pouvoir continuer. Cela aidera à minimiser le nombre de fois où vous devrez exécuter la machine à états avant d'obtenir un résultat. Cela peut être important lors de l'écriture de fonctions d'E / S ou de gestionnaires d'interruption.

En outre, quelques avantages et inconvénients de la déclaration de commutateur classique:

Avantages:

• il est dans la langue, donc il est documenté et clair
• les états sont définis là où ils sont appelés
• peut exécuter plusieurs états en un seul appel de fonction
• le code commun à tous les états peut être exécuté avant et après l'instruction switch

Les inconvénients:

• peut exécuter plusieurs états en un seul appel de fonction
• le code commun à tous les états peut être exécuté avant et après l'instruction switch
• la mise en œuvre du commutateur peut être lente

Notez les deux attributs qui sont à la fois pour et contre. Je pense que le changement permet un trop grand partage entre les États, et l'interdépendance entre les États peut devenir ingérable. Cependant, pour un petit nombre d'états, il peut être le plus lisible et maintenable.

Pour une machine à états simple, utilisez simplement une instruction switch et un type enum pour votre état. Effectuez vos transitions dans l'instruction switch en fonction de votre entrée. Dans un vrai programme, vous changeriez évidemment le "if (input)" pour vérifier vos points de transition. J'espère que cela t'aides.

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

Dans UML Distilled de Martin Fowler , il déclare (sans jeu de mots) dans le chapitre 10 State Machine Diagrams (c'est moi qui souligne):

Un diagramme d'état peut être implémenté de trois manières principales: le commutateur imbriqué , le modèle d' état et les tables d'état .

Prenons un exemple simplifié des états de l'écran d'un téléphone mobile:

Commutateur imbriqué

Fowler a donné un exemple de code C #, mais je l'ai adapté à mon exemple.

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;
    }
}

Modèle d'état

Voici une implémentation de mon exemple avec le modèle d'état GoF:

Tables d'états

En s'inspirant de Fowler, voici un tableau pour mon exemple:

État source État cible Action de protection d'événement
-------------------------------------------------- ------------------------------------
Ecran Hors Ecran Eteint Appuyez sur Bouton Alimentation Affichage bas LowPowerMessage  
ScreenOff ScreenOn pressButton! PowerLow
ÉcranOn ScreenOff pressButton
Écran Hors écran Prise de charge Alimentation
Écran Sur l'écran Fiche de charge Alimentation
Écran de chargement Écran Off débranché

Comparaison

Le commutateur imbriqué conserve toute la logique au même endroit, mais le code peut être difficile à lire lorsqu'il y a beaucoup d'états et de transitions. C'est peut-être plus sûr et plus facile à valider que les autres approches (pas de polymorphisme ni d'interprétation).

L'implémentation du modèle d'état étend potentiellement la logique sur plusieurs classes distinctes, ce qui peut rendre sa compréhension dans son ensemble problématique. D'autre part, les petites classes sont faciles à comprendre séparément. La conception est particulièrement fragile si vous modifiez le comportement en ajoutant ou en supprimant des transitions, car ce sont des méthodes dans la hiérarchie et il peut y avoir beaucoup de changements dans le code. Si vous vivez selon le principe de conception des petites interfaces, vous verrez que ce modèle ne fonctionne pas vraiment bien. Cependant, si la machine à états est stable, de telles modifications ne seront pas nécessaires.

L'approche des tables d'états nécessite l'écriture d'une sorte d'interpréteur pour le contenu (cela peut être plus facile si vous avez une réflexion dans la langue que vous utilisez), ce qui pourrait être beaucoup de travail à faire au départ. Comme le souligne Fowler, si votre table est séparée de votre code, vous pouvez modifier le comportement de votre logiciel sans recompilation. Cela a cependant des implications sur la sécurité; le logiciel se comporte en fonction du contenu d'un fichier externe.

Edit (pas vraiment pour le langage C)

Il existe également une approche d'interface fluide (aka interne Domain Specific Language), qui est probablement facilitée par des langages dotés de fonctions de premier ordre . La bibliothèque Stateless existe et ce blog montre un exemple simple avec du code. Une implémentation Java (pré Java8) est discutée. On m'a également montré un exemple Python sur GitHub .

il y a aussi la grille logique qui est plus maintenable à mesure que la machine d'état devient plus grande

Pour les cas simples, vous pouvez utiliser votre méthode de style de commutation. Ce que j'ai trouvé qui fonctionne bien dans le passé, c'est de gérer également les transitions:

static int current_state;    // should always hold current state -- and probably be an enum or something

void state_leave(int new_state) {
    // do processing on what it means to enter the new state
    // which might be dependent on the current state
}

void state_enter(int new_state) {
    // do processing on what is means to leave the current atate
    // might be dependent on the new state

    current_state = new_state;
}

void state_process() {
    // switch statement to handle current state
}

Je ne sais rien de la bibliothèque boost, mais ce type d'approche est extrêmement simple, ne nécessite aucune dépendance externe et est facile à implémenter.

switch () est un moyen puissant et standard d'implémenter des machines d'état en C, mais il peut diminuer la maintenabilité si vous avez un grand nombre d'états. Une autre méthode courante consiste à utiliser des pointeurs de fonction pour stocker l'état suivant. Cet exemple simple implémente une bascule set / reset:

/* 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;
}

J'ai trouvé une implémentation C vraiment astucieuse de Moore FSM sur le cours edx.org Embedded Systems - Shape the World UTAustinX - UT.6.02x, chapitre 10, par Jonathan Valvano et Ramesh Yerraballi ....

struct State {
  unsigned long Out;  // 6-bit pattern to output
  unsigned long Time; // delay in 10ms units 
  unsigned long Next[4]; // next state for inputs 0,1,2,3
}; 

typedef const struct State STyp;

//this example has 4 states, defining constants/symbols using #define
#define goN   0
#define waitN 1
#define goE   2
#define waitE 3


//this is the full FSM logic coded into one large array of output values, delays, 
//and next states (indexed by values of the inputs)
STyp FSM[4]={
 {0x21,3000,{goN,waitN,goN,waitN}}, 
 {0x22, 500,{goE,goE,goE,goE}},
 {0x0C,3000,{goE,goE,waitE,waitE}},
 {0x14, 500,{goN,goN,goN,goN}}};
unsigned long currentState;  // index to the current state 

//super simple controller follows
int main(void){ volatile unsigned long delay;
//embedded micro-controller configuration omitteed [...]
  currentState = goN;  
  while(1){
    LIGHTS = FSM[currentState].Out;  // set outputs lines (from FSM table)
    SysTick_Wait10ms(FSM[currentState].Time);
    currentState = FSM[currentState].Next[INPUT_SENSORS];  
  }
}

Vous voudrez peut-être consulter le logiciel générateur libero FSM. A partir d'un langage de description d'état et / ou d'un éditeur de diagramme d'état (Windows), vous pouvez générer du code pour C, C ++, Java et bien d'autres ... ainsi qu'une documentation et des diagrammes sympas. Source et binaires d' iMatix

Cet article est un bon pour le modèle d'état (bien qu'il soit C ++, pas spécifiquement C).

Si vous pouvez mettre la main sur le livre " Head First Design Patterns ", l'explication et l'exemple sont très clairs.

L'un de mes modèles préférés est le modèle de conception d'état. Répondre ou se comporter différemment au même ensemble d'entrées donné.
L'un des problèmes liés à l'utilisation des instructions switch / case pour les machines à états est qu'au fur et à mesure que vous créez plus d'états, le switch / cases devient plus difficile / difficile à lire / maintenir, favorise un code spaghetti non organisé et de plus en plus difficile à changer sans casser quelque chose. Je trouve que l'utilisation de modèles de conception m'aide à mieux organiser mes données, ce qui est tout le but de l'abstraction. Au lieu de concevoir votre code d'état en fonction de l'état dont vous venez, structurez plutôt votre code de sorte qu'il enregistre l'état lorsque vous entrez dans un nouvel état. De cette façon, vous obtenez effectivement un enregistrement de votre état antérieur. J'aime la réponse de @ JoshPetit et j'ai poussé sa solution un peu plus loin, tirée directement du livre du GoF:

stateCtxt.h:

#define STATE (void *)
typedef enum fsmSignal
{
   eEnter =0,
   eNormal,
   eExit
}FsmSignalT;

typedef struct fsm 
{
   FsmSignalT signal;
   // StateT is an enum that you can define any which way you want
   StateT currentState;
}FsmT;
extern int STATECTXT_Init(void);
/* optionally allow client context to set the target state */
extern STATECTXT_Set(StateT  stateID);
extern void STATECTXT_Handle(void *pvEvent);

stateCtxt.c:

#include "stateCtxt.h"
#include "statehandlers.h"

typedef STATE (*pfnStateT)(FsmSignalT signal, void *pvEvent);

static FsmT      fsm;
static pfnStateT UsbState ;

int STATECTXT_Init(void)
{    
    UsbState = State1;
    fsm.signal = eEnter;
    // use an enum for better maintainability
    fsm.currentState = '1';
    (*UsbState)( &fsm, pvEvent);
    return 0;
}

static void ChangeState( FsmT *pFsm, pfnStateT targetState )
{
    // Check to see if the state has changed
    if (targetState  != NULL)
    {
        // Call current state's exit event
        pFsm->signal = eExit;
        STATE dummyState = (*UsbState)( pFsm, pvEvent);

        // Update the State Machine structure
        UsbState = targetState ;

        // Call the new state's enter event
        pFsm->signal = eEnter;            
        dummyState = (*UsbState)( pFsm, pvEvent);
    }
}

void STATECTXT_Handle(void *pvEvent)
{
    pfnStateT newState;

    if (UsbState != NULL)
    {
         fsm.signal = eNormal;
         newState = (*UsbState)( &fsm, pvEvent );
         ChangeState( &fsm, newState );
    }        
}


void STATECTXT_Set(StateT  stateID)
{
     prevState = UsbState;
     switch (stateID) 
     {
         case '1':               
            ChangeState( State1 );
            break;
          case '2':
            ChangeState( State2);
            break;
          case '3':
            ChangeState( State3);
            break;
     }
}

statehandlers.h:

/* define state handlers */
extern STATE State1(void);
extern STATE State2(void);
extern STATE State3(void);

statehandlers.c:

#include "stateCtxt.h:"

/* Define behaviour to given set of inputs */
STATE State1(FsmT *fsm, void *pvEvent)
{   
    STATE nextState;
    /* do some state specific behaviours 
     * here
     */
    /* fsm->currentState currently contains the previous state
     * just before it gets updated, so you can implement behaviours 
     * which depend on previous state here
     */
    fsm->currentState = '1';
    /* Now, specify the next state
     * to transition to, or return null if you're still waiting for 
     * more stuff to process.  
     */
    switch (fsm->signal)
    {
        case eEnter:
            nextState = State2;
            break;
        case eNormal:
            nextState = null;
            break;
        case eExit:
            nextState = State2;
            break;
    }

    return nextState;
}

STATE  State3(FsmT *fsm, void *pvEvent)
{
    /* do some state specific behaviours 
     * here
     */
    fsm->currentState = '2';
    /* Now, specify the next state
     * to transition to
     */
     return State1;
}

STATE   State2(FsmT *fsm, void *pvEvent)
{   
    /* do some state specific behaviours 
     * here
     */
    fsm->currentState = '3';
    /* Now, specify the next state
     * to transition to
     */
     return State3;
}

Pour la plupart des machines d'état, en particulier. Machines à états finis, chaque état saura quel devrait être son prochain état et les critères de transition vers son état suivant. Pour les conceptions d'état lâche, cela peut ne pas être le cas, d'où la possibilité d'exposer l'API pour les états de transition. Si vous désirez plus d'abstraction, chaque gestionnaire d'état peut être séparé dans son propre fichier, qui est équivalent aux gestionnaires d'états concrets du livre GoF. Si votre conception est simple avec seulement quelques états, alors stateCtxt.c et statehandlers.c peuvent être combinés en un seul fichier pour plus de simplicité.

D'après mon expérience, l'utilisation de l'instruction «switch» est le moyen standard de gérer plusieurs états possibles. Bien que je sois surpris que vous transmettez une valeur de transition au traitement par état. Je pensais que l'intérêt d'une machine à états était que chaque état effectuait une seule action. Ensuite, l'action / l'entrée suivante détermine le nouvel état vers lequel effectuer la transition. Donc, je me serais attendu à ce que chaque fonction de traitement d'état effectue immédiatement tout ce qui est fixé pour entrer dans l'état, puis décide ensuite si une transition est nécessaire vers un autre état.

Il existe un livre intitulé Practical Statecharts in C / C ++ . Cependant, il est bien trop lourd pour ce dont nous avons besoin.

Pour le compilateur qui prend en charge __COUNTER__, vous pouvez les utiliser pour des mashines d'état simples (mais volumineux).

  #define START 0      
  #define END 1000

  int run = 1;
  state = START;    
  while(run)
  {
    switch (state)
    {
        case __COUNTER__:
            //do something
            state++;
            break;
        case __COUNTER__:
            //do something
            if (input)
               state = END;
            else
               state++;
            break;
            .
            .
            .
        case __COUNTER__:
            //do something
            if (input)
               state = START;
            else
               state++;
            break;
        case __COUNTER__:
            //do something
            state++;
            break;
        case END:
            //do something
            run = 0;
            state = START;
            break;
        default:
            state++;
            break;
     } 
  } 

L'avantage d'utiliser à la __COUNTER__place des nombres codés en dur est que vous pouvez ajouter des états au milieu d'autres états, sans renuméroter à chaque fois tout. Si le compilateur ne prend pas en charge __COUNTER__, de manière limitée, il est possible de l'utiliser avec précaution__LINE__

Vous pouvez utiliser un framework de machine d'état UML minimaliste dans c. https://github.com/kiishor/UML-State-Machine-in-C

Il prend en charge la machine à états finie et hiérarchique. Il n'a que 3 API, 2 structures et 1 énumération.

La machine à états est représentée par la state_machine_tstructure. C'est une structure abstraite qui peut être héritée pour créer une machine à états.

//! Abstract state machine structure
struct state_machine_t
{
   uint32_t Event;          //!< Pending Event for state machine
   const state_t* State;    //!< State of state machine.
};

L'état est représenté par un pointeur vers la state_tstructure dans le cadre.

Si le framework est configuré pour la machine à états finis state_tcontient alors ,

typedef struct finite_state_t state_t;

// finite state structure
typedef struct finite_state_t{
  state_handler Handler;        //!< State handler function (function pointer)
  state_handler Entry;          //!< Entry action for state (function pointer)
  state_handler Exit;           //!< Exit action for state (function pointer)
}finite_state_t;

Le framework fournit une API dispatch_eventpour distribuer l'événement à la machine d'état et deux API pour la traversée d'état.

state_machine_result_t dispatch_event(state_machine_t* const pState_Machine[], uint32_t quantity);

state_machine_result_t switch_state(state_machine_t* const, const state_t*);

state_machine_result_t traverse_state(state_machine_t* const, const state_t*);

Pour plus de détails sur la manière d'implémenter la machine d'état hiérarchique, reportez-vous au référentiel GitHub.

exemples de code
https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine/readme.md
https://github.com/kiishor/UML-State-Machine-in -C / blob / master / demo / simple_state_machine_enhanced / readme.md

En C ++, considérez le modèle State .

Votre question est similaire à "existe-t-il un modèle d'implémentation de base de données typique"? La réponse dépend de ce que vous voulez réaliser? Si vous souhaitez implémenter une machine à états déterministe plus grande, vous pouvez utiliser un modèle et un générateur de machine à états. Des exemples peuvent être consultés sur www.StateSoft.org - SM Gallery. Janusz Dobrowolski

Boost a la bibliothèque d'états. http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html

Cependant, je ne peux pas en parler. Je ne l'ai pas (encore) utilisé moi-même