1

Systèmes à événements discrets

[Link]@[Link]
Département ISYS (Systèmes Embarqués) –
ESIEE/Université Paris Est
Sep 2019

Système à événements discrets (SED)

• Système dont l’état change seulement à certains instants lors de l'occurrence d'évènements
particuliers.

• Exemples :

1
 3

…dans les systèmes embarqués

TRANSPORT TELECOM - MOBILE

ROBOTIQUE IMAGE - SIGNAL

Systèmes à événements discrets

● Différents modes de fonctionnement

● Séquences automatisées

● régulation, asservissement

● Surveillance

● ….
VIE PRATIQUE INDUSTRIE MEDICAL

Objectifs et prérequis
• Objectifs
▫ Vous découvrirez la modélisation des systèmes complexes à l’aide
du langage uniformisé UML
▫ Vous approfondirez le diagramme de machine à états finis
(statechart) pour la modélisation dynamique des systèmes
réactifs temps réel
▫ Vous utiliserez l’outil IBM Rhapsody pour construire des modèles
exécutable
▫ Vous réaliserez un exemple concret et complet du domaine de
l’automobile : un régulateur/limiteur de vitesse
• Prérequis
▫ La théorie des machines à états finis
▫ La connaissance des bases de l’orienté objet

2
 5

Pourquoi modéliser ?
Dans toute les discipline, on modélise depuis longtemps des systèmes
complexes

• Maitriser la complexité

• Réduire les risques

• Pour communiquer

▫ Masquage des détails

▫ Abstraction

Qu'est-ce qu'un modèle ?

• Simplification de la réalité pour mieux comprendre
▫ modèle mathématique, physique, visuels, textuels…

• Un bon modèle : A est un bon modèle de B si A permet de répondre de

manière satisfaisante à des questions prédéfinies sur B (D.T. ROSS)

• Un modèle est différent d’un simple dessin !

3
 7

Qu’y a-t-il en dessous d’un modèle?

• Syntaxe concrète

• Syntaxe abstraite et sémantique

▫ Un monde encore plus important…
Les éléments du modèle et leurs liens
▫ Facteur clé pour
Calcul, analyse
Simulation, test, validation
Traçabilité
…

Qu’y a-t-il en dessous d’un modèle?

Syntaxe concrète

Syntaxe abstraite et sémantique

4
 9

MBSE ?
• Model-based system engineering
• Passer du document-centric au
model-centric
• Les modèles ne sont pas seulement
dédiés à la documentation
• Les modèles deviennent des entités
de premier plan
▫ Traçabilité
▫ Aide à la conception,
développement, validation…

10

AVANT
Cycle en V : cycle classique de conception

5
 11

Ingénierie des modèles

Problématique
• Conception du logiciel embarqué
▫ Cycle en V : cycle classique de conception
développement orienté CODE

…
Codage 1 Codage 2 codage 3 codage n

Temps et coût de développement ++

12

Ingénierie des modèles

• Conception du logiciel embarqué
▫ Cycle en V : cycle classique de conception
▫ Approche dirigée par les MODELES

Modèle

Génération automatique
de code

6
 13

Ingénierie des modèles

• Conception du logiciel embarqué
▫ Cycle en V : cycle classique de conception
▫ Approche dirigée par les MODELES
Machines à états finis + temps réel = statechart

Modèles

Simulation

Génération automatique
de code

14

Langage et outil
• Outil : IBM Rational Rhapsody
• Environnement de modélisation, spécification et simulation de système temps réel
• Génération automatique de code C, C++, Java et Ada.
• Langage UML (Unified Modelling Language)
▫ Notation graphique standardisé orientée multi-vues
▫ Machine à états finis est une vue du système: vue comportementale
▫ Formalisme orientée objet: schéma classes/objets est une autre vue du système (vue
structurelle)

Modèles

Simulation

7
 15

Langages et outils
• Machine à états (temps réel)
▫ IBM Statemate (payant, licence académique)

• Machine à états et UML (temps réel)

▫ IBM Rational Rhapsody ((payant, éval 30j, licence académique)
[Link]
[Link]
• UML
▫ Rationnel Rose (payant)
[Link]
▫ Poseidon (gratuit)
[Link]
▫ Visual paradigm (gratuit)
[Link]
▫ ArgoUML (gratuit)
[Link]
▫ …

16

Démo !

8
 17

La modélisation structurelle

La modélisation
comportementale

18

Cas d’étude
Une montre digitale
• Un cadran, quatre boutons (power, mode, set,
start/stop) et une batterie.
• Un microcontrôleur pour gérer les modes de
fonctionnement (le contrôleur)
• Affichage de l’heure courante
• Mise en veille et gestion de la batterie
• Fonction chronomètre

9
 19

Modéliser vs spécifier

Modéliser
Logiciel
embarqué
Spécifier

Spécification Modélisation
Système de contrôle Procédé

Décrire la structure du système

E S E S +
Le comportement dynamique

E S

20

La structure d’un système : une classe

Nom du système
Structure représentant le système : une classe / un objet

Caractéristiques quantifiables : attributs

Comportement exécuté à la demande : operations

Comportement dynamique : statechart

• manipule les attirbuts
• appelle les opérations

10
 21

Exemple : Simulateur d’un véhicule

• Modélisation de la structure d’un système : Classe / Object

▫ Données du système : attributs
▫ Traitements de base : méthodes
▫ Comportement dynamique : statechart

classe

double vitesse;
Nom double latenceAcc = 300;
double latenceFrein = 150;
bool défaut = false;
attributs <visibilité> <nomAttribut> : <type> = <valeur par défaut>
Accelerer ( intensité ) { }
dynMoteur ( ) { }
méthodes <visibilité> <nomOpération> (listeParamètres) : <typeRetour>

22

Exemple : un distibuteur de billets

• Modélisation de la structure d’un système : Classe / Object

▫ Données du système : attributs
▫ Traitements de base : méthodes
▫ Comportement dynamique : statechart

classe
DAB
nom char* nomBanque;
char* nomEmplacement;
nomBanque: char* bool enPanne;
nomEmplacement: char* attributs
enPanne : bool = false
insererCarte( c ) { }
choisirOp( ) { }
insererCarte( c: Carte ): int
choisirOp( ) : void méthodes

<visibilité> <nomAttribut> : <type> = <valeur par défaut>

<visibilité> <nomOpération> (listeParamètres) : <typeRetour>

11
 23

Etude de cas (TD)

Spécification Modélisation
Système de contrôle Procédé

E S E S

E S

• Identifier les attributs et les opérations du

procédé

24

12
 25

Les statecharts
• Système à événements discrets
▫ Systèmes temps réel
▫ Systèmes réactifs à leur environnement

Machines à état fini pour le temps réel = les statecharts

▫ [Link] [1987]
▫ Extension temps réel pour la description comportementale
des systèmes réactifs

• Statecharts = diagrammes d'états +

hiérarchie +
orthogonalité +
communication par diffusion

Plusieurs types d’états

• Etat initial
▫ un seul par diagramme

• Etat intermédiaire
▫ Aucun ou plusieurs possibles

• Etat final
▫ Plusieurs possibles

• Pseudo-états
▫ dépend des outils

13
 27

Transition
• Représente le passage instantanée et unidirectionnel d’un état à un autre
• Format

• À l’arrivée d’une événement, sous une certaine condition, l’action réalise un

traitement lors du changement d’état

28

Transition
• Représente le passage instantanée et unidirectionnel d’un état
à un autre

• Déclenchée :
▫ Par un événement
▫ Automatique, à la fin d’une activité

• Condition de garde : condition booléenne qui autorise ou

bloque la transition

• Action : traitement réalisé lors du changement d’état

• Syntaxe : <Événement> [<Garde>] / <Action>

<Tirgger> [<Guard>] / <Action>

14
 29

Etude de cas (TD)

Spécification Modélisation
Système de contrôle Procédé

E S E S

E S

• Identifier les entrées/sorties du système

• Identifier les états stables du procédé et décrire
son comportement

30

Déclencheur (trigger)

• En provenance des dispositifs d’entrées (capteurs, boutons…),

de l’utilisateur (via IHM…)
▫ SignalEvent – evName(params)
Ex.: evAllumer, evEteindre,…

• En provenance d’horloge (timers…)

▫ Représente le passage du temps : une durée décomptée à partir
de l’entrée dans l’état courant
▫ TimeEvent (passage du temps) – tm(durée)

• CallEvent – triggered operation()

▫ appel d’une opération par un autre objet –

15
 31

Garde
• Les changements d’état interne
• Une contrainte supplémentaire pour une transition
• Une condition booléenne
▫ opérande : attributs ou expressions booléennes
▫ opérateurs : ! || &&
• Evaluation de la condition :
▫ ev [garde] : condition évaluée à l’arrivée de « ev »
▫ [garde] : condition évaluée à l’entrée de l’état (cas de Rhapsody)
tm(100)
Transition réflexive utilisant tm

S1 [garde]

S2

32

Les sorties d’une statechart

• Action dans une transition
▫ Traitement basique: suite d’instrcutions

▫ Traitement modulaire : appel de méthodes internes

▫ Communication :
diffusion d’un événement en interne (asynchrone)
Rhapsody : GEN (<nom_evt>([<argument>]) )
Appel synchrone d’une opération réactive
Rhapsody : trigerredOperation();

16
 33

Les actions dans un état

• Dans un état
▫ à l’entrée entry / <action>
▫ à la sortie exit / <action>

34

Les actions dans un état

• Dans un état
▫ à l’entrée entry / <action>
▫ à la sortie exit / <action>

17
 35

Exemple : les actions dans un état

evCarte/lecture();

Saisie_code_secret

idle entry / NePlusAffEntreesClavier()

exit / ReAffEntreesClavier()

evValider / A2(); Lecture ()

{numCB=params->num;}

evCarte lecture(); NePlusAffEntreesClavier();

evValider ReAffEntreesClavier(); A2();

36

Exemple : les actions dans un état

18
 37

Réactions internes à un état

• Définir une activité qui ne nécessite pas de quitter l état en cours

Activité nécessitatnt un certain temps d’exécution: action
relativement longue (Interaction utilisateur, signal
d’attente…)
▫ Format : evt [Garde] / action

38

Réaction dans un état

• Réaction : evt [Garde] / action e4 / A6( );
e1 / A1( );

Etat2
Entry / A3( );
Etat 1
Reaction : e3 / A5( );

Exit / A4( );

e2 / A2( );

19
 39

Réaction dans un état

• Réaction : evt [Garde] / action e4 / A6( );
e1 / A1( );

Etat2
Entry / A3( );
Etat 1
Reaction : e3 / A5( );

Exit / A4( );

e2 / A2( );
e3 A5 ( ); (le contexte est préservé)

e4 A4( ); A6( ); A3( ); (le contexte est réinitialisé)

40

Exemple : les actions dans un état

evCarte/lecture();

Saisie_code_secret

idle entry / NePlusAffEntreesClavier()

evKey/ codeU=codeU*10+params->c;
exit / ReAffEntreesClavier()

evValider / A2(); Lecture ()

{numCB=params->num;}

20
 41

Les actions : résumé

• entry, exit : actions courtes
• Si action relativement longue :

1. Réaction dans un état

2. État hiérarchique les sous-statechart

42

État hiérarchique
• Structurer un comportement complexe
Abstraction, hiérarchie

• Dans le sous-statechart, on retrouve les mêmes règles

état initial obligatoire.

21
 43

État hiérarchique
• Exemple

44

État hiérarchique
• Factoriser des transitions communes
▫ Mêmes événements / actions

22
 45

État hiérarchique
• Factoriser des transitions communes
▫ Mêmes événements / actions

46

État hiérarchique
• Suspendre/ré-initialiser un comportement
Running

A
prêt
EvOn B
Arrêt
EvImprimer
EvFin

EvOff
C
impression

État OU

23
 47

État hiérarchique
• Suspendre/reprendre un comportement ?
Running
« Comment traiter par exemple
l’ouverture du bac à papiers ? »
A
prêt
EvOn B
Arrêt
EvImprimer
EvFin EvOff
C
impression

État OU

48

Pseudo-état Historique (dernier état visité)

Running
EvOn
Arrêt
prêt
EvOff
EvImprimer
EvFin

ouvertureBacPapier suspendue
impression

H
fermetureBacPapier
État OU
• H : mémorise le dernier état visité
• L'événement fermetureBacPapier entraîne l'état Running, raffiné
par prêt et impression, le dernier état visité ( lors de la dernière
occurrence de ouvertureBacPapier) sera choisi
E

24
 49

Pseudo-état Historique (dernier état visité)

• Gestion des interruptions

D
Interruption – reprise

B
IT

C
h

50

Statecharts en concurrence
• Plusieurs comportement concurrent
▫ Super-état AND

▫ Évolution parallèle des sous-statecharts

▫ État courant : n-uplet (S0,...Sn); n=nbre de sous-statechart

25
 51

Statecharts en concurrence
• Dans un état composite

52

Statecharts en concurrence
• Exemple

26
 53

Statecharts en concurrence
• Exemple

54

Statecharts en concurrence
• Transitions simultanées
englobant

A C

e e

B D

•Les transitions sont simultanées :

à partir de l'état <A,D> la transition e permet d'être en <B,C>
notée <A,D> -e-> <B,C>

27
 55

Statecharts en concurrence
• Préemption d’un état AND
englobant

A C

t E
e e

B D

F G

La transition "t" entraîne l'arrêt immédiat des deux régions F et

G.

56

Classe concurrente
• Traitement bloquant dans un thread séparé
Classe active
▫ Propriété concurrency = « active »

▫ Surcharger l’opération OnReaction * execute()

28
 57

Etude de cas (TD)

• Une montre digitale
▫ est munie
d’un écran pour afficher le temps
de quatre boutons : power, mode, set, start/stop…
une batterie
▫ propose une fonction horloge: affichage de l’heure
courante
▫ se mets en veille après un certain délai d’inactivité

• Compléter le statechart en intégrant les

fonctionnalités ci-dessus

58

Synchroniser des statecharts

• Via une variable (garde)
▫ attention problème d’accès concurrent

• Via un événement
▫ Macro : GEN(<event>)

• Via un état
▫ Macro : IS_IN(<etat>):bool

• Via une barrière de synchronisation : fork/join

29
 59

Synchronisation via un événement

L'événement e entraîne la génération de f qui déclenche simultanément
C ->D et E -> F
<A,C,E> -- e -> <B,D,F>

diffusion

A C E

e/GEN(f); f f

B D F

60

Exemple : vérification d'un invariant

testInvariant

A C INIT

e/GEN(INV_E1); INV_E2 INV_E1

f/GEN(INV_E2);

B D VERIF

E1 E2 INVARIANT

• invariant par niveau ( par système)

• les notions de sûreté et vivacité peuvent être exprimées sur les
diagrammes
E

30
 61

Synchronisation via un état

• IS_IN ( B ) retourne true si l’état courant de la région concurrente est égal à B

test

A C

e [IS_IN(B)]

B D

62

Synchroniser via des barrières

• Fork and Join

parallele

B C

A F

D E join
fork

31
 63

Synchroniser via des barrières

• Fork and Join

64

Synchroniser via des barrières

• Fork and Join

32
 65

Pseudo état
• Pseudo-état conditionnal

/a0()
Branche1 : ev [cnd1] / a0() ; a1();
/a_else() Branche2 : ev [cnd2] / a0() ; a2();
/a1() /a2() Branche_else : ev [else] / a0() ; a_else();

66

Exemple
• Contrôleur d’ascenseur

33
 67

Attention au non déterminisme

englobant

D
A C
A

e C
e e/x=1; e/x=0;

B B D

Quelle transition choisir,

en général il y a préemption Que vaut x ?
de l'englobant ?

68

Etude de cas (TD)

• Une montre digitale
▫ est munie
d’un écran pour afficher le temps
de quatre boutons : power, mode, set, start/stop…
une batterie
▫ propose une fonction horloge: affichage de l’heure
courante
▫ se mets en veille après un certain délai d’inactivité
▫ Propose une fonction chronomètre
Le bouton mode active successivement les deux modes
horloge et chronomètre
Le bouton StartStop lance/arrête le chronomètre
Le bouton Set remet le chrono à zéro
Pas de veille possible dans le mode chronomètre

34
 69

Etude de cas (TD)

• Une montre digitale
▫ est munie
d’un écran pour afficher le temps
de quatre boutons : power, mode, set, start/stop…
une batterie
▫ propose une fonction horloge: affichage de l’heure courante
▫ se mets en veille après un certain délai d’inactivité
▫ Propose une fonction chronomètre
Le bouton mode active successivement les deux modes horloge et
chronomètre
Le bouton StartStop lance/arrête le chronomètre
Le bouton Set remet le chrono à zéro
Pas de veille possible dans le mode chronomètre
▫ Paralléliser/synchroniser les fonctionnalités
▫ Simuler la consommation de la batterie selon les modes:
Mode veille : conso = 1% / 5s
Hors mode veille : conso = 1% / 2s

70

Références
• Bruce Powel Douglass. Doing Hard-Time. Developing Real-Time
Systmes with UML, objects, Frameworks and Patterns. Addison-
Wesley, 1997.
• Hassan Gomaa. Designing Concurrent, Distributed, and Real-Time
Applications with UML. Addison-Wesley, 2000.
• Grady Booch, James Rumbaugh, Ivar Jacobson. Le guide de
l’utilisateur UML. Eyrolles, 2000.
• Pierre-Alain Muller. Modélisation objet avec UML. Eyrolles, 1997.
• C.G. Cassandras, S. Lafortune. Introduction to Discrete Event
Systems. Kluver Academic Publishing 1999.
• [Link]
• [Link]
• [Link] UML - Declercq -
slides [Link]

35