Mode d'emploi FSM

Théorie des machines à états

Introduction

FSM signifie Finite State Machine, soit machine à nombre d'états fini. Dans cet article, j'utilise à la place le mot 'machine'.

Une machine à nombre d'états fini sert à modéliser le comportement séquentiel d'un objet. Elle comporte un nombre limité et défini d'états.

Définitions

Elle se définie par :

Des états stables que l'on peut décrire par un adjectif ou une expression du type 'en train de ...' (...ing en anglais)
- Au repos
- Ouvert
- Allumé
- En attente de réponse
- ...
Des évènements (conditions exterieures ou 'entrées') ...
- Ouverture
- Réception
- Echéance
- ...
... qui peuvent provoquer une action (sortie) et éventuellement un changement d'état.

La combinaison

état courant
état final
évènement
action

constitue une transition.

Représentation graphique

Soit une machine définie de la façon suivante :

3 états:
- STS_A
- STS_B
- STS_C
2 évènements
- EVT_X
- EVT_Y
4 transitions
- STS_A vers STS_B par EVT_X : ACT_1
- STS_B par EVT_Y : ACT_2 (pas de changement d'état)
- STS_B vers STS_C par EVT_X : pas d'action
- STS_C vers STS_A par EVT_Y : ACT_3

graphique

Représentation matricielle

On peut aussi utiliser une matrice avec l'état courant, et l'évènement. Chaque élément contient une transition comprenant un état futur (éventuel) et une action (éventuelle).


        |    EVT_X      |     EVT_Y     |
  ------|---------------|---------------|
  STS_A | STS_B / ACT_1 |       /       |
  ------|---------------|---------------|
  STS_B | STS_C /       |       / ACT_2 |
  ------|---------------|---------------|
  STS_C |       /       | STS_A / ACT_3 |
  ------|---------------|---------------|

Implémentation d'une machine à états en C

Méthode basique par switch-case

Pour les petites machines comme celle donnée en exemple (2 ou 3 etats / evenements), il est possible d'utiliser la méthode basique du switch-case. Généralement, on fera un switch-case par chaque état, et dans chaque branche, un switch-case par evènement pris en compte.

   switch (etat_courant)
   {
   case STS_A:

      switch (evenement)
      {
      case EVT_X:
         /* changement d'etat */
         etat_courant = STS_B;

         /* action */
         action (ACT_1);
         break;

      case EVT_Y:
         /* changement d'etat */

         /* action */
         break;
      }
      break;

   case STS_B:

      switch (evenement)
      {
      case EVT_X:
         /* changement d'etat */
         etat_courant = STS_C;

         /* action */
         break;

      case EVT_Y:
         /* changement d'etat */

         /* action */
         action (ACT_2);
         break;
      }
      break;

   case STS_C:

      switch (evenement)
      {
      case EVT_X:
         /* changement d'etat */

         /* action */
         break;

      case EVT_Y:
         /* changement d'etat */
         etat_courant = STS_A;

         /* action */
         action (ACT_3);
         break;
      }
      break;
   }

On voit tout de suite qu'il ne va pas être très facile d'implémenter une grosse machine. C'est pourquoi j'ai développé un module C permettant de coder n'importe quelle machine à état simplement selon une technique de programmation par évènement. L'implémentation étant basée sur une matrice interne, le temps de réponse est faible et constant (pas de balayage).

Utilisation du module CLIB/FSM

Introduction

Le principe est de créer une machine (FSM_init()) en fonction de son nombre d'états et d'évènements, ainsi que de son état inital. Ensuite, on crée les transitions, (FSM_transition()) qui sont définies par :

état courant
état final
évènement
action

Une fois configurée, la machine peut être sollicitée par des évènements avec la fonciton FSM_engine().

Pour des raisons d'efficacité, les évenements et les états doivent être numérotés de 0 à NB-1.

Exemple basique

#include <stdlib.h>
#include <stdio.h>

#include "ed/inc/fsm.h"

/* etats */
typedef enum
{
   STS_A,
   STS_B,
   STS_C,
   STS_NB
}
STS;

/* evenements */
typedef enum
{
   EVT_X,
   EVT_Y,
   EVT_NB
}
EVT;

/* definition des transitions */
static int tra_A_to_B_by_X (void *puser)
{
   char *s = puser;

   printf ("Action 1: %s\n", s);
   return 0;
}

static int tra_B_to_B_by_Y (void *puser)
{
   char *s = puser;

   printf ("Action 2: %s\n", s);
   return 0;
}

static int tra_B_to_C_by_X (void *puser)
{
   char *s = puser;

   printf ("pas d'action: %s\n", s);
   return 0;
}

static int tra_C_to_A_by_Y (void *puser)
{
   char *s = puser;

   printf ("Action 3: %s\n", s);
   return 0;
}

int main (void)
{
   /* creation de la machine */
   sFSM *my_fsm = FSM_init (EVT_NB, STS_NB, NULL, STS_A);

   if (my_fsm != NULL)
   {
      /* Configuration des transitions */
      FSM_transition (my_fsm, tra_A_to_B_by_X, "A->B/X", STS_A,STS_B, EVT_X);
      FSM_transition (my_fsm, tra_B_to_B_by_Y, "B->B/Y", STS_B,STS_B, EVT_Y);
      FSM_transition (my_fsm, tra_B_to_C_by_X, "B->C/X", STS_B,STS_C, EVT_X);
      FSM_transition (my_fsm, tra_C_to_A_by_Y, "C->A/Y", STS_C,STS_A, EVT_Y);

      /* Essais (evenements) */
      FSM_engine (my_fsm, EVT_Y, "Y1"); /* rien */
      FSM_engine (my_fsm, EVT_X, "X1"); /* -> B */
      FSM_engine (my_fsm, EVT_Y, "Y2"); /* B */
      FSM_engine (my_fsm, EVT_Y, "Y3"); /* B */
      FSM_engine (my_fsm, EVT_X, "X2"); /* -> C */
      FSM_engine (my_fsm, EVT_Y, "Y4"); /* -> A */

      /* destruction de la machine */
      FSM_end (my_fsm), my_fsm = NULL;
   }

   /* Dev-C++ trick ... */
   system ("pause");
   return 0;
}

Le résultat est

Action 1: X1
Action 2: Y2
Action 2: Y3
pas d'action: X2
Action 3: Y4
Appuyez sur une touche pour continuer . . .

Quelques explications à propos des paramètres des fonctions.

`FSM_init()`

Les paramètres sont :

Entrée

Le nombre d'evènements. Rappel : ils sont numérotés de 0 à N-1
Le nombre d'états. Rappel : ils sont numérotés de 0 à N-1
L'adresse du callback de debug ou NULL. Ce callback (de type fFSM_DEBUG) est appelé par chaque evènement causant une transition définie. Il permet de récupérer une structure d'information (sFSM_INFO) contenant des données sur l'état, l'évènement, la transition. Très utile pour mettre au point des machines complexes
L'état initial de la machine.

Retour

L'adresse de l'objet FSM crée dynamiquement ou NULL. Si il est non NULL, il est valide. Il doit être détruit par FSM_end()

`FSM_transition()`

Les paramètres sont :

Entrée

Le contexte
L'adresse de la fonction appelée par la transition (dans laquelle on va mettre l'éventuelle action). C'est un callback.
Le nom 'en clair' de la transition (utile au debug)
L'état courant (from)
L'état suivant (to)
L'évènement qui provoque la transition

Retour

Un code d'erreur de type eFSM_ERR pouvant prendre les valeurs suivantes :

FSM_OK (0) : "No error"
FSM_ERR_STATUS_TOO_LARGE : "Status is too large"
FSM_ERR_EVENT_TOO_LARGE : "Event is too large"
FSM_ERR_TRANS_ALREADY_DEFINED : "Transition is already defined"

`FSM_engine()`

Les paramètres sont :

Entrée

Le contexte (FSM)
L'évènement
Le contexte utilisateur (pointeur de données anonyme) Cette adresse sera transmise au callback declenché par la transition. Le callback étant de niveau utilisateur, il saura quoi en faire.

Retour

Les valeurs possibles sont :

>= 0 : code retour du callback 'transition'.
-1 signifie qu'il s'est produit une erreur. La fonction FSM_last_err() retourne le code de la dernière erreur FSM.

Note d'implémentation

Les fichiers nécessaires sont

Interface

ed/inc/bits.h
ed/inc/fsm.h
ed/inc/pc_dbg.h
ed/inc/sys.h
ed/inc/sysalloc.h
ed/inc/types.h
ed/inc/fsm_err.itm

Implémentation

ed/src/fsm.c
ed/src/sys.c

D'autre part, il faut définir la macro globale FSM_DYN, par exemple de la façon suivante :


   -DFSM_DYN

sur la ligne de commande