Ecole Mohammadia
d’Ingénieurs
Filière Génie Electrique
3ème année, option AII
Systèmes à Evénements
Discrets (SED)
N. SBITI
Applications : systèmes informatiques
réseaux de télécommunication
systèmes de production
1
Introduction
L’évolution rapide de la technologie de l’information
et de la communication a favorisé l’apparition de
nouveaux systèmes dynamiques souvent hautement
complexes.
Exemples : systèmes informatiques, réseaux de
télécommunications, systèmes de contrôle du trafic aérien,
systèmes de production automatisés...
L’activité dans ces systèmes est due à l’occurrence
d’événements discrets asynchrones, dont certains sont
contrôlables (appui sur un bouton de M/A), et d’autres
incontrôlables (défaillance d’un équipement).
Ces systèmes sont appelés systèmes à événements discrets
(SED).
(exemples)
Pour concevoir et exploiter correctement ces
systèmes hautement complexes, on a besoin d’outils
adaptés de modélisation, de conception, d’analyse, de
validation, de commande…
2
SED
Introduction
Système de production
• simplification du système physique
• hypothèses concernant les données
Très fidèle
non exploitable
Modèle (RdP, RFA, autre…)
Non fidèle
très exploitable
Analyse
Simulation Méthodes
analytiques
Performances du modèle
Résultats
3
SED
Introduction
Exemples de SED :
• Automatismes séquentiels (variables binaires)
• Systèmes avec file d’attente :
Pour utiliser des ressources, il faut attendre (guichet
de banque, machine dans un atelier de production,
CPU…)
3 éléments de base dans une file d’attente :
Les entités qui attendent leur tour : les clients
Les ressources pour lesquelles l’attente a lieu : les serveurs
L’espace d’attente : la file
Clients: personnes, pièces dans un système de production,
messages, tâches ou jobs ou transactions dans un système
informatique, voitures utilisant le réseau routier…
Serveurs: personnes, machines dans un système de
production, canaux de transmission, CPU ou périphériques,
feux de circulations…
Files: queue à un guichet de banque ou à un arrêt de bus,
aires de stockage des pièces, buffers…
Nombre de ressources limité => Attente
SED
Introduction
Exemples de SED (suite) :
Système à base de files d’attente
Système de production manufacturier
Les clients: les pièces
Les serveurs: les machines, les robots, les
convoyeurs
Les files: aires de stockage des pièces
Arrivée Départ
pièces M1 M2 pièces
Les pièces qui arrivent passent par 2 machines avant de
quitter le système. Le stock d’entrée de la 2 ème machine a
une capacité limitée à 2 (notion de blocage de la mach.1).
C’est un SED:
Ensemble des événements: E={a, f1, d2}
a : arrivée d’une pièce
f1 : fin de traitement d’une pièce par M1
d2: départ d’une pièce
Espace d’état: X={(x1, x2): x10, x2{0,1,2,3}}
x1 : nombre de pièces en attente pour M1
x2 : nombre de pièces en attente pour M2
SED
Introduction
Exemples de SED (suite) :
MAIS, selon le niveau de détail souhaité pour le modèle, on
peut aussi choisir:
X={(x1, x2): x1{L, O, B}, x2{L, O}}
x1 : état de la mach.1 (libre, occupée, bloquée)
x2 : état de la mach.2 (libre, occupée)
SED
Partie A : MEF
PARTIE A
Machines à Etats
Finis
SED 7
Partie A : MEF
Introduction
Automates ou machines à états finis/infinis
(Finite/Infinite State Machine, Automata) : outil de
modélisation des SED permettant l’étude du
comportement logique des systèmes séquentiels (l’état
suivant dépend des entrées et de l’état actuel du
système).
Domaines d’application :
• automatique : productique.
• circuits digitaux électroniques.
• informatique.
• génération ou reconnaissance de langages
formels.
• systèmes biologiques…
SED 8
Partie A : MEF
Automate de base
Définition : 3-uplet (S, I, f ) avec :
• S : ensemble d’états
• I : ensemble ou alphabet d’entrées
• f : fonction définissant les transitions.
f :SIS
Soit q S, e I :
x = f (q,e)
x : état suivant
Représentation graphique :
graphe orienté
sommets : états, arc : relation f
q e
SED 9
Partie A : MEF
Exemple : automate à 3 états et 4 transitions :
• S = { q 1 , q2 , q 3 }
• I = {e 1 , e 2 , e 3 , e 4 }
• q 2 = f ( q1 , e 1 )
q 3 = f ( q1 , e 2 )
q 1 = f ( q3 , e 4 )
q 1 = f ( q2 , e 3 )
e4 q1 e3
e2 e1
q3 q2
SED 10
Partie A : MEF
Représentation matricielle :
automate à n états {q1, q2 …, qn},
r entrées {e1, e2 …, er}
matrice n r
e1 e2 e3 e4
q1 q2 q3 - -
q2 - - q1 -
q3 - - - q1
SED 11
Partie A : MEF
Exemple : station de perçage
Attente
Marche
Avance
Fin avance
Perçage
Fin perçage
Recul
Fin recul
SED 12
Partie A : MEF
Automate
(autre définition)
Définition : 5-uplet (S, I, f, O, g) avec :
• S, I, f : idem
• O : ensemble ou alphabet de sorties
• g : application sur O.
si g : S O Machine de Moore
(fonction des états)
si g : S I O Machine de Mealy
(fonction des transitions)
Machine séquentielle :
• asynchrone : 1 entrée change
état et/ou sortie change
• synchrone :
état et/ou sortie ne changent que sur H
(condition implicite)
SED 13
Partie A : MEF
Machine de Moore
g est une fonction de l’ensemble des états sur
l’ensemble des sorties :
g :SO
Entrées (I )
Logique de séquencement
(état suivant)
f
Registre d’état (S)
N bits
Sorties (O )
Logique de sortie
g
+ état initial
Implantation : états codés sur N bits,
t.q. n 2N
SED 14
Partie A : MEF
Exemples de machines de
Moore asynchrones
Soit O = {o1, o2, o3} avec :
o1 = g (q1) o2 = g ( q 2 ) o3 = g (q3)
e1 e2 e3 e4
q1 q2 q3 - - o1
q2 - - q1 - o2
q3 - - - q1 o3
e4 e3
q1/o1
état initial : q1
e2 e1
q3/o3 q2/o2
Série de valeurs d’entrées : e2e4e1e3e2
Série de valeurs de sorties: o3o1o2o1o3
SED 15
Partie A : MEF
S = {q0, q1, q2, q3} I = {a, b} O = {0 , 1 }
b
a b q0/1
a
q1/0
q0 q1 q3 1
a
q1 q3 q1 0 a b
q2 q0 q3 0 b a
q3 q3 q2 1
q2/0 q3/1
b
Si état initial : q0 (sortie correspondante : 1)
Série de valeurs d’entrées : abab
Série de valeurs de sorties : 0010
SED 16
Partie A : MEF
Une machine qui détecte les ‘aab’
S = {q0, q1, q2, q3} I = {a, b} O = {0, 1}
a b
q0 q1 q0 0 Sort la
valeur 1
q1 q2 q0 0 pour la série
d’entrées
q2 q2 q3 0 ‘aab’
q3 q1 q0 1
a
b a
a
a b
q0/0 q1/0 q2/0 q3/1
b
b
SED 17
Partie A : MEF
Machine de Mealy
g est une fonction de l’ensemble des transitions sur
l’ensemble des sorties :
g :SIO
Entrées (I )
Logique de séquencement
(état suivant)
f
Registre d’état (S)
N bits
Sorties (O )
Logique de sortie
g
+ état initial
Implantation : états codés sur N bits, t.q. n 2N
SED 18
Partie A : MEF
Exemples de machines de Mealy
asynchrones
Automate à 3 états et 4 transitions
• S = { q 1 , q2 , q 3 }
• I = {e 1 , e 2 , e 3 , e 4 }
• q 2 = f ( q1 , e 1 ) q3 = f ( q1 , e 2 )
q 1 = f ( q3 , e 4 ) q1 = f ( q2 , e 3 )
Soit O = {o1, o2, o3 , o4} avec :
o1 = g(q1, e1) o2 = g(q1 , e2) o3 = g(q2 , e3)o4 = g(q3 , e4)
e1 e2 e3 e4
q1 q2 /o1 q3 /o2 - -
q2 - - q1 /o3 -
q3 - - - q1 /o4
SED 19
Partie A : MEF
Exemples de machines de Mealy
asynchrones
Automate à 3 états et 4 transitions
• S = { q 1 , q2 , q 3 }
• I = {e 1 , e 2 , e 3 , e 4 }
• q 2 = f ( q1 , e 1 ) q3 = f ( q1 , e 2 )
q 1 = f ( q3 , e 4 ) q1 = f ( q2 , e 3 )
Soit O = {o1, o2, o3 , o4} avec :
o1 = g(q1, e1) o2 = g(q1 , e2) o3 = g(q2 , e3)o4 = g(q3 , e4)
e4/o4 q1 e3/o3
e2/o2 e1/o1
q3 q2
SED 20
Partie A : MEF
Une machine qui détecte les ‘aab’
a/0
b/0
a/0
a/0
q0 q1 a/0 q2 b/1 q3
b/0
b/0
q1 b/1
a/0 aaabb
a/1
q0 b/0 q2
a/0
01110
q3
b/1
b/1
a/1
SED 21
Partie A : MEF
Protocole de communication simple
Si un message arrive (a) et que l’émetteur est libre,
le message subit un traitement, sinon il est ignoré.
Le traitement consiste à :
- Garder une copie du message et envoyer
l’original à travers le canal de transmission.
- Générer un time-out
Si la transmission est réussie, un accusé de réception
arrive (r) et la copie peut être supprimée (sortie=1).
Si le time-out expire (t), le message est considéré
comme perdu et est retransmis.
r/1
t/0
I a/0 M T
t/0
a/0 a/0
SED 22
Partie A : MEF
Description d’un circuit logique :
A B
NAND DELAY OR
OR
q0 : A=0,B=0 q1 : A=0,B=1 q2 : A=1,B=0 q3 : A=1,B=1
On a :
•A = NAND(Entrée, OR(Ancien A, Ancien B))
•B = Ancien A
•Sortie = OR(Ancien B, Entrée)
0 1
q0 q2 /0 q2 /1
q1 q2 /1 q0 /1
q2 q3 /0 q1 /1
q3 q3 /1 q1 /1
SED 23
Partie A : MEF
Description d’un circuit logique :
A B
NAND DELAY OR
OR
q0 : A=0,B=0 q1 : A=0,B=1 q2 : A=1,B=0 q3 : A=1,B=1
On a :
•A = NAND(Entrée, OR(Ancien A, Ancien B))
•B = Ancien A
•Sortie = OR(Ancien B, Entrée)
q0 0/0, 1/1
1/1
0/1
q1 q2
1/1
1/1 0/0
q3
0/1
SED 24
Partie A : MEF
Propriétés des MEF
Etats équivalents
• 2 états sont équivalents et donc fusionnables en
un seul, s’ils ont la même évolution future (
l’entrée appliquée -> même état d’arrivée, même
sortie)
Automates équivalents et automate minimal
• 2 automates équivalents : série d’entrées
choisie, les séries de sorties obtenues pour chacun
des 2 automates sont identiques.
• Parmi les automates d’une même classe
d’équivalence, celui qui possède le plus petit nb
d’états est dit minimal.
Equivalence des machines
• Pour toute machine de Moore, il existe une
machine de Mealy équivalente, et réciproquement.
SED 25
Partie A : MEF
Moore Mealy
a a/s
b b/s
q/s q
c c/s
a,b
a
a q1/1
q0/0 q3/1
b
b b
q2/0
a/1,b/1
a/1
a/1 q1
q0 q3
b/0
b/0 b/1
q2
a/0
SED 26
Partie A : MEF
Mealy Moore
b/s1 b
a/s1 a
a/s1 a/s1
q
a/s1 q1/s1 q2/s2
b/s2 b
b/s2 b/s2 b/s2
q1 q1/s3
c c
a/s1 c/s3 b/s2 a b
q2 q21/s1 q22/s2
Mealy Moore
SED 27
Partie A : MEF
Machine synchrone de Moore/Mealy
(automatisme séquentiel)
Etat initial : q1
a S
b Machine
synchrone
h
ab 00 01 11 10 S
q1 q1 q1 q3 q2 0
00
q2 q3 q3 q2 q2 0
10
q3 q1 q1 q3 q2 1
11
SED 28
Partie A : MEF
Machine synchrone de Moore/Mealy
(automatisme séquentiel)
Etat initial : q1
a S
b Machine
synchrone
h
a ab/1
a/0
q1 /0 q1q3
ab a
ab a/1 ab/0
a
q2 /0
q2 a/0
ab a
q3/1 Mealy
ab
Moore
SED 29
Partie A : MEF
Moore paramétré
Spécification comportementale de type Moore (sorties
attachées aux états) mais la valeur de certaines
sorties, sur certains états, dépend de la valeur des
entrées.
Entrées (I )
Logique de séquencement
(état suivant)
f
Registre d’état (S)
N bits
Sorties (O )
Logique de sortie
g
+ état initial
SED 30
Partie A : MEF
Machines séquentielles synchrones
Exemple de machines dérivées d’une même
Spécification comportementale (état initial S1)
S1 S1
I1 I1 I1/O1 I1/O2
S2/O1 S3/O2 S2
Moore Mealy
S1
S2 O1 si I1
O2 si I1
Moore paramétré
SED 31
Partie A : MEF
Comparaison temporelle
I1
éta S1 S3 S1 S2 S1 S3
t
Moore
O1
O2
Différence
éta S1 temporelle
S1 S2
S2 S1 S2
Mealy
t
O1
O2
paramétré
éta S1 S2 S1 S2 S1 S2
t
Moore
O1
Différence
O2
fonctionnelle
SED 32
