Module CLIB/FSM : Mode d'emploi

Dernière mise à jour : 10/09/05 14:02 | clib

Un forum web "Bien programmer en C" permet de poser des questions sur les articles, le C en général, la programmation etc.

Home

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 :

La combinaison

constitue une transition.

Représentation graphique

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

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 :

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

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

FSM_engine()

Les paramètres sont :

Entrée
Retour

Les valeurs possibles sont :

Note d'implémentation

Les fichiers nécessaires sont

Interface

Implémentation

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


Valid XHTML 1.0! Valid CSS! Get Firefox!  Use OpenOffice.org Club d'entraide des développeurs francophones Code::Blocks
© Emmanuel Delahaye 1995-2005 | emmanuel dot delahaye at gmail dot com | Home | Forum | Livre d'or