Mode d'emploi du gestionnaire d'automates FSM

Module FSM de la bibliothèque CLIB

Emmanuel Delahaye

Le module FSM de la bibliothèque CLIB est un gestionnaire d'automates (Finite State Machine) ♪

- Titre : Mode d'emploi du gestionnaire d'automates FSM

- Auteur : Emmanuel Delahaye

- Parution : 10 septembre 2005

- Mise à jour : 7 mars 2013

- Licence : Copyright ® 2008 Emmanuel Delahaye. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Théorie des machines à états

- I-A. Introduction

- I-B. Définitions

- I-C. Représentation graphique

- I-D. Représentation matricielle

- II. Implémentation d'une machine à états en C

- II-A. Méthode basique par switch-case

- II-B. Utilisation du module CLIB/FSM

- II-B-1. Introduction

- II-B-2. Exemple basique

- II-B-3. Note d'implémentation

I - Théorie des machines à états

I-A - 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.

I-B - Définitions

Elle se définit 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 extérieures ou 'entrées')…

- ouverture,

- réception,

- éché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.

I-C - Représentation graphique

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

- trois états :

- STS_A,

- STS_B,

- STS_C ;

- deux événements :

- EVT_X,

- EVT_Y ;

- quatre 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.

I-D - 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 |
------|---------------|---------------|

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

II-A - Méthode basique par switch-case

Pour les petites machines comme celle donnée en exemple (deux ou trois états / événements), 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 événement pris en compte.

switch (etat_courant)
{
case STS_A:

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

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

case EVT_Y:
/* changement d'état */

/* action */
break;
}
break;

case STS_B:

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

/* action */
break;

case EVT_Y:
/* changement d'état */

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

case STS_C:

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

/* action */
break;

case EVT_Y:
/* changement d'état */
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).

II-B - Utilisation du module CLIB/FSM

II-B-1 - 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 initial. 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 fonction FSM_engine().

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

II-B-2 - 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;

/* événements */
typedef enum
{
EVT_X,
EVT_Y,
EVT_NB
}
EVT;

/* définition 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)
{
/* création 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 (événements) */
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()

Entrée :

- le nombre d'évé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 évé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. S’il est non NULL, il est valide. Il doit être détruit par FSM_end().

 FSM_transition()

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()

Entrée

- le contexte (FSM) ;

- l'événement ;

- le contexte utilisateur (pointeur de données anonyme) Cette adresse sera transmise au callback déclenché 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.

II-B-3 - 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.