Embed Size (px)
Citation preview
François VernadatINSA-DGEI - LAAS-CNRS
Modelisation de Systemes Concurrents
Partie I (Reseaux de Petri)
1 / 111
Outline
1 IntroductionSequentiel Vs ConcurrentSysteme Concurrents/ReactifsProprietes types des systemes concurrents/reactifsFormalisation : Modelisation/VerificationOrganisation du Cours
2 / 111
Sequentiel Vs Concurrent
Programme ”Classique” (sequentiel)
Caracteristiques :
Termine
Retourne un resultat
Donnees +/- complexesmais controle sequentiel(”simple”)
Exemples :“Fonctions” (tri, code, calcule,traitement image/signal, trans-forme/compilate, . . . )
Ingredients pour les expri-mer : fonctions/procedures,structures de donnees, struc-tures de controle condition-nelles/iteratives, . . .
Langages : Imperatif, fonction-nel, objet, logique, . . .
Correction = correction partielle + terminaisoncorrection partielle : si le programme termine il fournit un resultat correctterminaison : le programme termine toujours
3 / 111
Systeme Concurrents/Reactifs (> 70)
Caracteristiques :
Σ compose par des processusindependants
Communication,Synchronisation, ....
“partage” de ressources
Σ ne retourne pas de resultat
Terminaison en generalindesiree (deadlock)
Donnees +/- simples maiscontrole concurrent(”complique”)
Exemples :Protocoles de communica-tion, Controle/Commande,Σ-Embarques, . . .
Ingredients pour les expri-mer : etat/transition, non-determinisme, parallelisme,synchronisation, communica-tion, . . .
Formalismes : Machines aetats/Automates commu-nicants, Reseaux de Petri,Algebres de processus . . .
Correction = surete, vivacite, equite, . . .Necessite le plus souvent une analyse exhaustive de l’espace d’etats7→ model-checking
4 / 111
Proprietes types des systemes concurrents/reactifs
Accessibilite- Une certaine situation peut etre atteinte- Chaque action peut avoir lieu
Surete- Quelque chose de mauvais n’arrive jamais
Jamais plus de 2 processus en section critiqueJamais de debordement de buffersLa barriere est fermee lorsqu’un train est sur le passage a niv eau
Vivacite (absence de famine)- Quelque chose de bon finit par arriver
Un processus en attente d’une ressource finir par l’obtenirUn philosophe affame finira par manger
Equite(s)- Si une action peut avoir lieu une infinite de fois alors elle aura lieu une(infinite) de fois, . . .
Vivacite sous condition d’equiteS’il n’y a pas une infinite de pertes, tout message emis - perdu etretransmis - finira par arriver (Alternating Bit Protocol )
5 / 111
Formalisation : Modelisation/Verification
Ingredients
FormalisationM : Modele (formel) du comportement (issu de Rdp, AC, Alg.Proc,..)7→ Permet de decrire l’ensemble de tous les comportements du systeme
φ : Modele (formel) des proprietes (formalisme dedie)7→ Permet de formaliser les exigences a respecter
Verification Model − Checker :Outil de verification permettant de decider si M satisfait φ?
nb : Formel est une condition requise pour envisager l’automaticite
6 / 111
Organisation du Cours
Objectif : Introduction a la Formalisation des Systemes concurrents
Concepts caracteristiques : //, Causalite, non-determinisme,Competition, Synchronisation, Communication(synchrone/asynchrone, signal/passage de valeurs), . . .
Exemples/Problemes Exclusion mutuelle, Lecteurs/ecrivains,Philosophes, Choix distant, Terminaison,Dimensionnement, Controle de flux, Protocoles(token-ring, ouverture/fermeture de connexion)
Modelisation
Comportements : RdP, AC, . . .Proprietes : Proprietes Generales d’accessibilite, (petitapercu) de la logique temporelle)
Verification Algos classiques de Graphe, Techniques des observateurs,Analyse structurelle, Model-checking (petit apercu)
7 / 111
Organisation en 2 parties : RdP et AC
Reseaux de Petri (RdP) :Concepts, Exemples, Modelisation, Composition,Verification (Proprietes des Graphes, Observateurs,Analyse structurelle)
TPs : TINA (Time Petri Net Analyser) www.laas.fr/tina/
Automates Communicants (AC) :Exemples, Protocoles, Composition/Communication,Formalisation de proprietes, Model-checking (utilisation)
TPs : UPPAAL (Uppsala & Aalborg) www.uppaal.org/
Volume : 12 CM + 5 TPsPetri : 6 CM + 2.5 TP + PartielAutomates : 6 CM + 2.5 TP + Partiel
Evaluation : 1 note IE correspondant a deux Partiels (RdP & AC)Documents autorisesTPs non notes mais fort rapport avec les exos traites en partiels
8 / 111
Ordonnancement des 2 parties ?
(Quelques) Contraintes de causalite a respecter :1 Pour chaque partie, 5 CM doivent etre effectues avant de pouvoir
commencer les Tps associes2 On ne peut commencer le cours de la seconde partie que si le cours
de la 1ere est termine et si les Tps de la 1ere partie ont commence3 Les Tps de la premiere partie doivent etre termines avant de
commencer la seconde serie de Tps. . .
Une specification possible en reseaux de Petri
NbPetriCM_A_Faire
RdP-CM
CM_Petri_Faits
CM_AC_Faits
AC-CM
NbCM_AC_Afaire
NbTP_Afaire
DebutPetri_TP
Debut_AC
Debut_AC_TP
3 3
6
TP
55
6 6
PetriTpACTp
Petri : Classiques (incluant valuation des arcs) + priorites, arcsinhibiteurs, read-arc.
9 / 111
L’ensemble de tous les ordonnancements possibles
DebutPetri_TP
6
DebutPetri_TP
RdP-CM8
TP
9
Debut_AC10
TP
RdP-CM11
TP
12
AC-CM13
TP
Debut_AC14
TP
RdP-CM15
TP
16
AC-CM17
TP
AC-CM18
TP
Debut_AC19
TP
RdP-CM20
AC-CM21
TP
AC-CM22
TP
AC-CM23
TP
Debut_AC24
AC-CM25
TP
AC-CM26
TP
AC-CM27
TP
AC-CM28
AC-CM29
TP
AC-CM30
TP
AC-CM31
TP
AC-CM32
AC-CM33
TP
AC-CM34
TP
AC-CM35
TP
AC-CM36
TP
AC-CM37
TP
AC-CM38
TP
AC-CM39
TP
AC-CM40
TP
AC-CM41
AC-CM
TP
42
0
RdP-CM
1
RdP-CM
2
RdP-CM
3
RdP-CM
4
RdP-CM7RdP-CM
5
AC-CM
TP
50 AC-CM
TP
48 AC-CM
TP
46 AC-CM
Debut_AC_TP
44
TP
49
TP
47
Debut_AC_TP
43TP
45
La specification/solution en automates ....
10 / 111
Outline
2 Reseaux de PetriObjectifs/Organisation de la partie Petri
11 / 111
Reseaux de Petri
Historique
1962 These de Carl Adam Petri (RFA)
1970 Travail important (France & RFA)
1980 Conference Annuelle (Springer-Verlag)
Diffusion Mondiale : Universitaire & “Industrielle”http ://www.daimi.aau.dk/PetriNets/ :
Interet
Formalisme Rigoureux (semantique precise)
Expressivite+ Compact (vs machines a etats)(cf ordonnancement des 2 parties de ce cours)+ Concepts : //, Cooperation, Competition, Synchronisation, . . .+ Dualite Etat/Evenement
Possibilite d’Analyse : Structurelle, Exhaustive
Representation Graphique
6= extensions : temporel (temps reel), stochastique (performance), . . .
Nombreux outils (certains couples a des outils/formalismes industriels) 12 / 111
Sur cette partie ....
Objectifs
Introduction aux reseaux de Petri et a la modelisation/analyse de systemesconcurrents
un peu de theorie en CM
un peu de pratique en “TP”
Contenu : Introduction aux Reseaux Place/Transition
Definitions & Concepts de base
Enumeration, Proprietes
Composition
Equation Fondamentale des Reseaux de Petri
Decidabilite de la finitude de l’espace d’etats accessibles
Analyse Structurelle : Invariants
13 / 111
Outline
3 Reseaux Place/TransitionExemple introductifDefinitions GeneralesSemantiqueGraphe des Marquages accessiblesReseaux bornes
14 / 111
C.A Petri : Communication entre automates
Exemple introductif
2 processus (initialement) independants representes par des automates.D
p1
A
p2
B
p4 A1 est initialement en p1, il execute cycliquement A, B puisC pour se reinitialiser.
E
A
p3
D
p1
C
p5
A2 est initialement en p1, il execute A puis C et arrive enp5. Il peut executer E et revenir en p3 ou choisir de faire Det de se reinitialiser.
Quizz :
On veut contraindre A1 et A2 a commencer (action A) et a finir (action F)
ensemble. Quel sera le comportement global ?
Reseaux de Petri
D
p1
A
p2
B
p4
D
p1
A
p3
p5
C
E
A2 & A2
=Synchronisation⇒ p2
A
CB
p3
E
p5
p1
p4
D
15 / 111
Reseau Place/Transition
Definition Reseau Place/Transition
R =< P,T ,Pre,Post > ou
P est un ensemble fini de Places
T est un ensemble fini de TransitionsP ∩ T = ∅
Pre : P × T 7→ IN incidence avant
Post : P × T 7→ IN incidence arriere
Graphiquement
p2
A
CB
p3
E
p5
p1
p4
D
Marquage / Reseau Marque
Le reseau donne les regles defonctionnement du systeme, le marquagedonne l’etat du systeme
MarquageM : P 7→ IN (M ∈ INP)M(p) denote le marquagede la place p
Reseau marque N =< R,M >
... avec le marquage
p2
A
CB
p3
E
p5
p1
p4
D
16 / 111
Definition Alternative
Systeme d’addition de vecteursR =< P,T > ou
P est un ensemble fini de Places
T est un ensemble fini de TransititionsT ⊂ INP × INP
notations t ∈ T = (•t, t•)
p2
A
CB
p3
E
p5
p1
p4
D
Exemple
T = A,B,C ,DA B C D E
(
10000
,
01100
) (
01000
,
00010
) (
00100
,
00001
) (
00011
,
10000
) (
00011
,
10000
)
Remarques
Avec cette definition equivalente, les pre (•t) et post (t•) conditionsd’une transition ont le meme type qu’un marquage : •t, t•,M ∈ INP
17 / 111
Semantique des reseaux Place-Transition
Semantique
La semantique precise comment le modele evolue :- Quelles actions (transitions) sont possibles (sensibilisees) en fonction de letatdu systeme (marquage) ?
- Quel est l’effet d’une action (du tir d’une transition) sur l’etat du systeme
(marquage) ?
Sensibilisation d’une transition
Une transition t(•t, t•) est sensibilisee pour le marquage M ssi M ≥• t
On le note Mt→
Tir d’une transition (franchissement)
Soit t une transition et M un marquage tel que M[t >alors le tir de t a partir de M conduit en M ′ defini par : M ′ = M −• t + t•
On le note Mt→ M ′
Remarques
+ •t est le marquage minimum permettant de franchir t
+ t• est le marquage minimum atteint apres avoir franchi t
18 / 111
Exemples de sensibilisation/tir
Exemple de Sensibilisation
< N,M0 >
p2
A
CB
p3
E
p5
p1
p4
D
SensibilisationM0 ≥• A
donc M0A→
M0 =
10000
, •A =
10000
Exemple de Tir
TirM0
A→ M1
M1 = M0 −• A + A•A• =
01100
M1 =
01100
< N,M1 >
p2
A
CB
p3
E
p5
p1
p4
D
19 / 111
Non determinisme
< N,M1 >
p2
A
CB
p3
E
p5
p1
p4
D
M1B→ et M1
C→M1 ≥• BM1 ≥• C
M1•B •C
01100
01000
00100
Parallelisme (structurel/effectif)
Deux transitions t, t′ sont paralleles ssi •t ⊗• t′ = ~0ou (~v ⊗ ~v ′)(p) =Def ~v(p)× ~v ′(p) (∀p ∈ P)
Ici : B et C sont paralleles et pour M1, le parallelisme est effectif
Conflict (dual du parallelisme)
Deux transitions t, t′ sont en conflict ssi •t ⊗• t′ 6= ~0
20 / 111
Exemple de Parallelisme
M1B→ M2
M1C→ M3
Comme B//C
On a M3B→ et M2
C→De plus
M3C→ M4 et M3
B→ M4
< N,M2 >
p2
A
CB
p3
E
p5
p1
p4
D
< N,M3 >
p2
A
CB
p3
E
p5
p1
p4
D
< N,M4 >
p2
A
CB
p3
E
p5
p1
p4
D
Exemples de Conflict
< N,M4 >
p2
A
CB
p3
E
p5
p1
p4
D
M4D→ et M4
E→mais M4 6
D.E→et M4 6
E .D→M4
D→ M0 (et M0 6E→)
M4E→ M2 (et M2 6
D→)D et E sont en conflict enM4
< N,M0 >
p2
A
CB
p3
E
p5
p1
p4
D
< N,M2 >
p2
A
CB
p3
E
p5
p1
p4
D
21 / 111
Comportement d’un RdP (intuition)
M1
M0p1
M2p3p4M3 p2p5
M4 p4p5
A
BC
C B
E
D
E
p2p3
M0 M1 M2 M3 M4
10000
01100
00110
01001
00011
p1 p2p3 p3p4 p2p5 p4p5
22 / 111
Graphe des Marquages accessibles
Ensemble des Etats Accessibles : A(R,m0)
A0 = m0Ai = m ∈ INP/∃p ∈ Ai−1, ∃t ∈ T : p[t > mA(R,m0) =
⋃i≥0 Ai
Rien n’assure la convergence de la suite ! A(R,m0) peut etre infini
Graphe des Etats Accessibles : G (R,m0)
G(R,m0) =< A(R,m0),→, L > ou
A(R,m0) : ensemble des sommets
→ : la relation de transition est le plus petit ensemble verifiant :
(m1, t,m2) ∈→ ssi m1,m2 ∈ A(R,m0), t ∈ T et m1[t > m2
L : ensemble des labels de transition :
L ⊂ T defini par t ∈ L ssi m1[t > m2
Langage associe a un reseau L(R,m0)
L(R,m0) = σ ∈ T ∗ : m0σ→
23 / 111
Semi-algortihme de calcul de G (R ,m0)
semi-algorithme : car rien n’asssure la terminaison
Semi-Algorithme
– 1. Initialisation :Stack ← ∅ ; push m0 into StackA(R,m0)← ∅ ; enter m0 in A(R,m0)
– 2. Exploration :while Stack 6= ∅
loop pop(q) from stackTS ← t ∈ T : q [ t > ;∀t ∈ TS do
q [ t > q′;if q′ 6∈ A(R,m0)
then enter q′ in A(R,m0); put q′ onto Stackenter (q, t, q′)in →
24 / 111
Exercice : Calcul de G (N ,M0)
nb : les arcs de N sont values
< N, n0 >
24
X
2Y
C
5
A B
3
5
5
2
3
Q1 : Completez la description des transitions(•t, t•)
m0
42
X 4Y 2
A B C
(50,
23
) (21, ) ( , )
Q2 :Explorationde X 4Y 2
X 4Y 2 6 A→X 4Y 2 B→ X 2Y 4
X 4Y 2 C→ ?
Q3 :Explorationde X 2Y 4
X 2Y 4 A→ ?X 2Y 4 C→ ?X 2Y 4 B→ ?
Suite
Q4 : Explorez X 0Y 6
Q5 : Explorez X 5Y 1
Q5 : Explorez X 3Y 3
Q6 : Finissez laconstruction du graphe
25 / 111
Reseaux bornes
Quizz : Soit le reseau < IN, [0] >
Suc p0
Q1 : A-t-on [0]Suc→ ?
Q2 : l’ensemble des marquages de ce reseau est-ilfini ?
Reseau borne
Un reseau marque < N,M0 > est borne ssi
∃b ∈ IN : ∀p ∈ P, ∀M ∈ A(N,M0) : M(p) ≤ b
Un exemple de reseau 6-borne
< N, n0 >
24
X
2Y
C
5
A B
3
5
5
2
3
G < N, n0 >
A
B
1 X*2Y*4
0 X*4Y*2
B
2 Y*6C3
X*5Y
C
6
X*6
B
5 X*5Y
A
B
4 X*3Y*3
26 / 111
Reseau structurellement borne
Un reseau N structurellement borne ssi ∀m0 ∈ INP < N,m0 > est borne
Exemple de reseau structurellement borne
24
X
2Y
C
5
A B
3
5
5
2
3
Le nombre global de jetons dans le reseauest invariant quel que soit le marquage ;chaque transition modifie uniquement lalocalisation des jetons dans les placesmais laisse leur nombre inchange.
Plus petit reseau non borne : < IN, [0] >
Suc p0Il permet de generer INIl est meme structurellement non borne
En general, la propriete bornee depend du marquage initial (cf reseau G )
t3
t2
t1
p1p0
p2 p3
Trouvez la condition la plus generalesur m0 pour que :< G ,m0 > soit borne< G ,m0 > soit non borne
27 / 111
Reseaux bornes et Finitude de l’espace d’etats
Propriete : G (R,m0) est fini ssi < R,m0 > est borne
(⇒) Soit b = Max(m) pour m ∈ A(R,m0)ou Max(m) = max(m(p)) pour p ∈ P< R,m0 > est b-borne
(⇐) Soit b la borne de < R,m0 >alors A(R,m0) ⊂ [0, b]P qui contient (b + 1)|P| elements
A(R,m0) et G(R,m0) sont donc finis
Propriete
La finitude de l’espace des etats accessibles - et ce qui revient au meme - lapropriete k-borne sont decidables
nb : Tres important pour adresser des problemes de “dimensionnement”
7→ Arbre/Graphe de couverture [Karp& Miller 1969]
Construction “vue” plus tard
28 / 111
Outline
4 Exemples de modelisation en RdpUne histoire de pontJournee d’un planteur de bananesForme textuelle PetriPiscine
29 / 111
Une histoire de pont
Enonce
Un groupe de 4 personnes (A,B,C,D) se situe sur la rive gauche d’un fleuve etdoit se rendre sur la rive droite.Pour ce faire, ils doivent emprunter un pont mal eclaire qui ne peut supporterqu’une charge de deux personnes. Le groupe dispose d’une seule lampe depoche. Chaque traversee du pont necessite la possession de la lampe. Il estdonc necessaire de ramener la lampe de l’autre cote pour permettre unenouvelle traversee.Les 4 personnes marchent a une vitesse differente. Les temps de traversee pourchacun des individus est respectivement de 10 min pour A, 5 min pour B, 2min pour C et 1 min pour D.
Question : Quel est le temps minimal pour faire passer les 4 personnes sur larive droite ?
30 / 111
Principe de la modelisation
Les Places
- “booleens” : Lg, Ag, Bg, Cg, Dg, Lg, Ag, Bg, Cg, Dgindiquant la localisation (gauche/droite) des personnes et de la lampe.Initialement : Lg Ag Bg Cg Dg- “compteur” : Temps permet de cumuler le temps ecoule depuis le debut
Initialement : Temps*0
Les Transitions
6 transitions de la forme XYL2R representant le passage de gauche a droite(L2R) des personnes X et Y. Il faut que la lampe ainsi que X et Y soient agauche, ils sont a droite apres le tir. Le temps de la traversee (le max desdurees de passage) est ajoute a Temps.
4 transitions de la forme YR2L representant le retour (R2L). Il faut que lalampe et Y soient a droite. Ils sont a gauche apres le tir. Le temps de traverseede Y est ajoute a Temps.
1 transition stop materialisant la fin du “calcul”
31 / 111
Modelisation
Un modele (perfectible) possible
ABL2R
ACL2R
ADL2R
AR2L
BCL2R
BDL2R
BR2L
CDL2R
CR2L
DR2L
stop
AgAd
Temps
LdLg
Bg Bd
Cg
Cd
DgDd
fin
101010
10
5
5
5
2
2
Proprietes attendues
Ici on a un modele de calcul ( !)Terminaision : atteindre inevitablement un deadlock
Correction partielle : tous les etats de deadlock doivent marquer la place Fin32 / 111
Resultat de l’analyse
Le comportement (graphe des marquages)
0ABL2R
1ACL2R
2
ADL2R
3
BCL2R4
BDL2R5
CDL2R
6
AR2L
7
BR2L8
AR2L
9
CR2L10
AR2L
11
DR2L12
BR2L13
CR2L
14
BR2L15
DR2L
16
CR2L
17
DR2L
18
ACL2RABL2R
19
ADL2R
ABL2R
20 CDL2R
21
BCL2R
ABL2R
22BDL2R
ABL2R
23
CDL2R
24
ADL2RACL2R
25
BDL2RBCL2R26
BCL2R
ACL2R
27
BDL2R
ADL2R
28
CDL2R
ACL2R29
BCL2R
ACL2R
30
BDL2R
ADL2R
31
CDL2R
ADL2R32
ADL2RACL2R
33
BDL2RBCL2R34
CDL2R
BCL2R35
CDL2R
BDL2R36
ABL2R
37
ABL2R
38
AR2L
39
BR2L40
CR2L
41
AR2L
42
BR2L43
DR2L
44
BR2L
AR2L
45
CR2LAR2L
46
DR2LAR2L
47
AR2L
48
BR2L49
CR2L
50AR2L
51
BR2L52
DR2L
53
CR2L
BR2L54
DR2L
BR2L55
AR2L
56
CR2L
57
DR2L58
BR2L
AR2L
59
CR2L
AR2L
60
DR2L
AR2L
61 AR2L
62
BR2L63
CR2L
64
BR2L
CR2L
65
DR2LCR2L
66
AR2L
67
CR2L
68
DR2L69
BR2L
DR2L70
AR2L
71
BR2L72
DR2L73
AR2L
74
CR2L75DR2L
76
BR2L77
CR2L78
DR2L79
BR2L80
CR2L
81
DR2L82BR2L
83
CR2L84
DR2L85
DR2LCR2L
86
ADL2RACL2RABL2R
87
BDL2RBCL2R
ADL2RACL2R
ABL2R
88
CDL2RACL2R
ABL2R
89
CDL2R
ADL2R
ABL2R
90
ABL2R
BCL2R
ACL2RADL2R
91
BDL2RBCL2R
ABL2R
92
CDL2R
BCL2RABL2R93
CDL2R
BDL2R
ABL2R
94
BDL2R
ADL2RACL2R
95
BDL2RBCL2R
ACL2R
96
CDL2R
BCL2R
ACL2R
97
CDL2R
BDL2RBCL2RADL2R
ACL2R
98
BDL2RBCL2R
ADL2R
99
CDL2R
BDL2R
ADL2R
100
CDL2R
101
AR2L
102BR2L
103
CR2L
104
DR2L
105
stop
106
AR2L107
BR2L108
CR2L
109
DR2L110stop111
AR2L
112BR2L
113
CR2L
114
DR2L
115
stop
116
AR2L
117
BR2L
118
CR2L
119DR2L
120
stop
121
AR2L
122BR2L
123CR2L
124
DR2L
125stop
126
AR2L127BR2L128
CR2L129
DR2L130 stop131
AR2L132
BR2L
133CR2L
134
DR2L135
stop136
AR2L
137
BR2L138
CR2L
139
DR2L
140stop
141
AR2L
142
BR2L
143
CR2L
144DR2L
145
stop146
AR2L147BR2L148
CR2L149
DR2L150
stop151
AR2L152
BR2L153
CR2L
154
DR2L
155
stop
156
AR2L157
BR2L158
CR2L159
DR2L160
stop161
AR2L162
BR2L163 CR2L164
DR2L165
stop166
AR2L
167
BR2L168
CR2L169
DR2L
170
stop171
AR2L
172
BR2L
173
CR2L
174
DR2L
175stop
176
Taille : 177 marquages, 237 transitions
Borne, Bloquant (et c’est tant mieux !)
Le systeme se bloque inevitablement (terminaison)
Le systeme peut etre bloque sans marquer la placeFin (pas de correction partielle)
Temps minimal de Traversee : 17
Une analyse des “etats termi-naux” permet de recuperer les 6=temps de “transit”
Temps d’execution possibles :17, 19, 20 , 21, 23, 24, 26, 27,30, 33, 34, 36, 37, 40, 50
Traversee en 17 u.t
Passage de C et D 2 minRetour de C 4 min
Passage de A et B 14 minRetour de D 15 min
Passage de C et D 17 min
33 / 111
Exemple de Reseau non borne
Journee d’un planteur de bananes
Le planteur est initialement au champ ou il cueille des bananes (en quantite
suppose infinie). Il cesse son travail et se met a table pour manger quelques
bananes. A la fin du repas, il passe au jardin et jette quelques unes des peaux
de bananes mangees. Il part ensuite dormir.
(Un) reseau possible
rentre
leve
dort
cueille
mange
jette
champ
table
jardin
banane
peau
Son arbre de couverture
0
1 2
3 4
5 7
8
cueille rentre
cueille
rentre leve
levedort
dort
mange
mange
6
jette
leve
9
dort
10
AC : Sur-approximation ducomportement du planteur
34 / 111
Forme textuelle Petri
planteur.ndr
rentre
leve
dort
cueille
mange
jette
champ
table
jardin
banane
peau
planteur.net
pl champ (1)
tr rentre champ -> table
tr leve table -> jardin
tr dort jardin ->
tr cueille champ -> champ banane
tr mange table banane -> table peau
tr jette peau jardin -> jardin
pl champ (1)
# Commentaire
Remarques
2 mots-cles pl et tr et un separateur ->pl pour declarer le marquage initial specifique d’une place (0 par defaut)
Les places ne sont pas declareestr pour declarer les transitions :tr nom pre-conditions* -> post-conditions*
Ordre des declarations n’a pas d’importance 35 / 111
Le pont en textuel
pont.ndr
ABL2R
ACL2R
ADL2R
AR2L
BCL2R
BDL2R
BR2L
CDL2R
CR2L
DR2L
stop
AgAd
Temps
LdLg
Bg Bd
Cg
Cd
DgDd
fin
101010
10
5
5
5
2
2
Format textuel pont.net
tr ABL2R Lg Bg Ag -> Ld Bd Temps*10 Ad
tr ACL2R Lg Cg Ag -> Ld Cd Temps*10 Ad
tr ADL2R Lg Dg Ag -> Ld Dd Temps*10 Ad
tr BCL2R Lg Cg Bg -> Ld Cd Temps*5 Bd
tr BDL2R Lg Dg Bg -> Ld Dd Temps*5 Bd
tr CDL2R Lg Dg Cg -> Ld Dd Temps*2 Cd
tr AR2L Ad Ld -> Temps*10 Ag Lg
tr BR2L Bd Ld -> Temps*5 Bg Lg
tr CR2L Cd Ld -> Temps*2 Cg Lg
tr DR2L Dd Ld -> Temps Dg Lg
.../...
.../...
tr stop Dd Cd Bd Ad -> fin
pl Ag (1)
pl Lg (1)
pl Bg (1)
pl Cg (1)
pl Dg (1)
net pont36 / 111
Piscine
Enonce
Une piscine comporte c cabines pour se changer et p paniers pour deposer sesvetements.- On n’entre dans le piscine que si une cabine est libre. On attend un panierpour se changer et deposer ses vetements. On libere la cabine et on penetredans le bassin.
- On ne quitte le bassin que si une cabine est libre. On se change et on restitue
cabine et panier. On quitte la piscine.
Un modele possible
x6
7
x3
x7
7
T4T3
x4
T5
x5
T6
x1
T1
x2
public
1K
T2
37 / 111
Piscine : Legende du reseau
x6
7
x3
x7
7
T4T3
x4
T5
x5
T6
x1
T1
x2
public
1K
T2
T1 : le client entre a la piscine(si ∃ cabine libre (x6))
T2 : le client se deshabille(si ∃ panier libre (x7))
T3 : le client penetre dans le bassin(et restitue la cabine (x6))
T4 : le client quitte le bassin(si ∃ cabine libre (x6))
T5 : le client s’habille(et restitue le panier (x7))
T6 : le client quitte la piscine.
x1 : client en attente d’un panierx2 : client se deshabillex3 : client dans le bassinx4 : client s’habillex5 : client habille pret a sortirx6 : Compteur de cabines libresx7 : Compteur de paniers libres
38 / 111
Piscine : Le systeme peut-il se bloquer ?
Graphe des marquages pour c = p = 2
Graphe : 32 marquages, 57 transitions
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
21
22
23
24
25
26
27
28
29
30
31
20
T6
T6
T5
T6
T6
T4
T1
T6
T6
T3
T6
T5
T6
T2
T6
T4
T1
T5
T5
T6
T3
T5
T4
T1
T4
T1
T6
T2
T5
T3
T4
T1
T3
T6
T1
T5
T2
T2
T4
T3
T1
T5
T1
T4
T2
T1
T3
T4
T1
T3
T2
T3
T1
T2
T2
T1
T1
1 seul etat de Blocage : x1(2) x3(2)
Explosion combinatoire
Pour n = k = 10 7→ 7006 marquages, 28885 transitionsPour n = k = 15 7→ 38759 marquages 178703 transitionset toujours un seul etat de blocage ....
39 / 111
Outline
5 CompositionComposition & CommunicationCommunication Asynchrone & SynchroneAsynchrone Vs SynchroneProbleme du choix distant
40 / 111
Composition (produit) des reseaux de Petri
Objectif de la composition
Base : Pouvoir construire des systemes complexes a partird’elements plus simples.
Graal : Pouvoir deduire des proprietes des composants, unepropriete de la composition
Composition de Petri
Mecanisme de base : FusionFusion de Places et de Transitionsnb : Specification des elements fusionnes sera vue ulterieurement !
Composition Petri Vs Automates
Automates : Fusion de transitionsPetri : Analytique / Automates : Enumerative
41 / 111
Fusion de places
Graphiquement
On compose les reseaux en fusionnant les places MessageEnTransit
AprèsEnvoi
!mes
MessageEnTransit
AvantEnvoi
XAprèsRéception
?mes
AvantRéception
MessageEnTransit
=
AprèsEnvoi
!mes
MessageEnTransit
AvantEnvoi
AprèsRception
?mes
AvantRception
42 / 111
Fusion (produit) de transitions
Graphiquement
T0
P0 P2
P1
2
P3
X TO'
P0P4
P3 P2
= T0XTO'
P0
P1 P3
P4
P22
3
Analytiquement
Pour t = (•t, t•) et t ′ = (•t ′, t ′•), t⊗ t′ =Def (•t +• t ′, t• + t ′•)
Application :
TO = (
10100
,
01020
), TO ′ = (
10001
,
00110
) et TO ⊗ TO ′ = (
20101
,
01130
)
43 / 111
Composition & Communication
Fusion
2 modes de composition dans les reseaux de Petri
Fusion de placesPermet en general de modeliser la communication asynchrone :
L’emission du message precede sa receptionReception peut-etre bloquante
Fusion de transitionsPermet en general de modeliser la communication synchrone(rendez-vous) :
L’emission et la reception du message sont simultanesReception et Emission peuvent-etre bloquantes
44 / 111
Communication
Asynchrone
AprèsEnvoi
!mes
MessageEnTransit
AvantEnvoi
X
AprèsRéception
?mes
AvantRéception
MessageEnTransit
=
AprèsEnvoi
!mes
MessageEnTransit
AvantEnvoi
AprèsRception
?mes
AvantRception
L’emission precede la receptionL’emission est toujours possible, la reception peut etre bloquante.
Synchrone
AprèsEnvoi
!mes
AvantEnvoi
X
AprèsRéception
?mes
AvantRéception
=
AprèsRéception
!mes x ?mes
AprsEnvoi
AvantRéceptionAvantEnvoi
Emission et reception sont simultanees (cf rendez-vous)L’emission devient potentiellement bloquante.
45 / 111
Communication Asynchrone Vs Synchrone
Asynchrone simule par du Synchrone
AprèsEnvoi
!mes
AvantEnvoi
X !mes
MessageEnTransit
?mes X
AprèsRéception
?mes
AvantRéception
= ? ?
Asynchrone Vs Synchrone
On peut toujours simuler de l’asynchrone via du synchrone, mais lareciproque est fausse !En Uppaal, la communication de base est synchrone et on simulera lacommunication asynchrone via l’astuce ci-dessus.
Le controle d’un systeme concurrent/communiquant est notoirement plussimple en synchrone qu’en asynchrone, mais il n’est pas realiste de fairecommuniquer des entites distantes par rendez-vous !
46 / 111
Probleme du choix distant
Enonce
Deux entites distantes, Left et Right, peuvent communiquer par deuxcanaux a et b : Left emet sur a et recoit sur b tandis que Right emetsur b et recoit sur a.
SpecificationLeft
IdleL
ReinitL
?b?b!a
toInit
RightIdleR
ReinitR
?a!b
toInit
Probleme : Mettre en place un protocole permettant aux deux entites decommuniquer : Tout message emis doit etre inevitablement recu !
47 / 111
Choix distant synchrone !
IdleL
ReinitL
?b?b!a
toInit X
IdleR
ReinitR
?a!b
toInit
=
IdleR
ReinitR
RdvA
IdleL
toInitLtoInitRRdvB
ReinitL
Analyse
RdvB
RdvA1
toInitL
3
toInit
2
toInit
toInitL
0
Par construction : tout message emisest simultanement recu : Il y a doncbien communication entre les deuxentites
PB : Le rendez-vous entre deux sites distants n’est pas realiste.Defi : Disposer d’une implantation asynchrone permettant d’offrir lememe service (fonctionnement equivalent)
48 / 111
Choix distant asynchrone (V0)
Communication par envoi de message
AprèsEnvoi
!mes
AvantEnvoi
X !mes
MessageEnTransit
?mes XAprèsRéception
?mes
AvantRéception
=
AprèsEnvoi
!mes
MessageEnTransit
AvantEnvoi
AprèsRception
?mes
AvantRception
Mise en oeuvre (en textuel)
Pour TINA, en textuel (format .net), les transitions possedant le meme nomsont fusionnees. Il y a d’autres modes plus evolues (format .tpn vu en TP)
net left
tr ?b IdleL -> ReinitL
tr !a IdleL -> ReinitL
tr toInitL ReinitL -> IdleL
pl IdleL(1)
net right
tr ?a IdleR -> ReinitR
tr !b IdleR -> ReinitR
tr toInitR ReinitR -> IdleR
pl IdleR(1)
net LeftToRight
tr !a -> LtoR
tr ?a LtoR ->
net RightToLeft
tr !b -> RtoL
tr ?b RtoL ->49 / 111
Composition de base dans TINA (transitions)
Utilisation basique de .tpn
# fichier cdasy.tpn
source left.net
source right.ndr
source LeftToRight.net
source RightToLeft.net
# on peut mixer :
# textuel (.net)
# graphique (.ndr)
# ou encore (.tpn)
# cdasy.net automatiquement obtenu
tr !a IdleL -> LtoR ReinitL
tr !b IdleR -> ReinitR RtoL
tr ?a IdleR LtoR -> ReinitR
tr ?b IdleL RtoL -> ReinitL
tr toInitL ReinitL -> IdleL
tr toInitR ReinitR -> IdleR
pl IdleL (1)
pl IdleR (1)
En graphique : cdasy.ndr
IdleR toInitR
LtoR
!a ?a
!bIdleLtoInitL ?b
RtoL
ReinitLReinitR
50 / 111
Analyse (via le graphe de couverture)
Caracteristiques generales
Non borne – Places LtoR et RtoLA part ca : Non bloquant, Reinitialisable, Vivant ....
Exploration Partielle
!a
1
toInitR
toInitL0
?b?a
4
!b
2
toInitR
10
toInitL
9
!a!b
3
!a
21
!b
20
toInitR
6
toInitL
7
toInitLtoInitR
18
toInitR
8
toInitL
5
Il peut y avoir communication0:!a->1:?a->4
Mais ce n’est pas obligatoire !0:!a->1:b!->3:toInL->7:toInR->18
montre que l’on peut avoirune infinite d’emissions sansqu’il y ait aucune reception
Suite en TP UPPAAL
Controle de flux (Accuse de reception) : borne mais interblocageSolutions : Priorite, Tirage au sort, . . . 51 / 111
Outline
6 Proprietes generales des ReseauxBloquantReinitialisable / propreQuasi-vivaciteVivaciteInfiniment actifLien entre ces differentes proprietesDecision des proprietes generales via les CFC
52 / 111
Proprietes generales d’accessibilite
Blocage / Deadlock / Puits
N est sans blocage ssi ∀m ∈ G(R,m0), ∃t ∈ T : m[ t >
N#1 : Exemple de reseau non bloquant
p2
A
CB
p3
E
p5
p1
p4
D
M1
M0p1
M2p3p4M3 p2p5
M4 p4p5
A
BC
C B
E
D
E
p2p3
N#2 : Exemple de reseau bloquant
t0
?in
p1
t2
Perte
t1
!out
p0
2
Epsilon
0
p0
1
p1
t2t1
t0
53 / 111
Reinitialisable (propre)
N est Reinitialisable (propre) ssi ∀m ∈ G(R,m0),∃ω ∈ T+ : mω→ m0
nb : ω ∈ T+ impose que ω soit non nulle
N#1 : reseau propre
p2
A
CB
p3
E
p5
p1
p4
D
M1
M0p1
M2p3p4M3 p2p5
M4 p4p5
A
BC
C B
E
D
E
p2p3
N#2 : reseau non propre
t0
?in
p1
t2
Perte
t1
!out
p0
2
Epsilon
0
p0
1
p1
t2t1
t0
54 / 111
Quasi-vivacite
1 Une transition t est quasi-vivante ssi ∃m ∈ G(R,m0) : mt→
2 Le reseau est quasi-vivant si chacune de ses transitions est quasi-vivante.
Un transition non vivante est dite morte
N#2 : reseau quasi-vivant
t0
?in
p1
t2
Perte
t1
!out
p0
2
Epsilon
0
p0
1
p1
t2t1
t0
N#3 : Reseau non quasi-vivant : transition PB-mutex morte
Idle1
CS1
take1 Semaphore take2
Idle2
CS2
Lib2Lib1
PB-Mutex
Lib2Lib1
0
Idle1 Semaphore Idle2
take1
1
Idle2 CS1
take2
2
Idle1 CS2
nb : le fait que pb-mutex soit morte permet de verifier la proprieted’exclusion mutuelle (principe de verification par la methode desobservateurs) 55 / 111
N est Vivant
1 Une transition t est vivante ssi ∀m ∈ G(R,m0) : ∃ω ∈ T ∗ : mω.t→
2 Le reseau est vivant si chacune de ses transitions est vivante.
Un transition non vivante est dite non vivante ( !)
N#4 : reseau non reinitialisable mais vivant
24
X
2Y
C
5
A B
3
5
5
2
3
1
0
23
6 5
4
B
B
C
A
B
B
C
A
N#2 : Reseau quasi-vivant, bloquant et non vivant
t0
?in
p1
t2
Perte
t1
!out
p0
2
Epsilon
0
p0
1
p1
t2t1
t0
N#5 : quasi-vivant,non bloquant, aucune transition vivante
t1 t3
p0
t0
p1p3
t2t3 t0
1 0 t2t1
2
56 / 111
Infiniment actif
Un reseau est infiniment actif ssi ∀k ∈ IN, ∃σ ∈ TK : mσ→
Le reseau admet au moins une sequence de franchissement infinie.
N#2 : Reseau bloquant et infiniment actif
t0
?in
p1
t2
Perte
t1
!out
p0
2
Epsilon
0
p0
1
p1
t2t1
t0
N#6 : Reseau non infiniment actif
t0 t1
p1
10
p0
0
t0
1
t1
2
t0
3
t1t0
4
t1
5
t0
6
t1t0
7
t1t0
8
t1
9
t0
10
t1t0
11
t1t0
12
t1
t0
13
t1
14
t0
15
t1t0
16
t1t0
17
t1t0
18
t1t0
19
t1
20
t0
21
t1t0
22
t1t0
23
t1t0
24
t1t0
25
t1
t0
26
t1
27
t0
28
t1t0
29
t1t0
30
t1t0
31
t1t0
32
t1
t0
33
t1
t0
34
t1
35
t0
36
t1t0
37
t1t0
38
t1t0
39
t1t0
40
t1
t0
41
t1
t0
42
t1
t0
43
t1
44
t0
45t1
t0
46
t1t0
47
t1t0
48
t1t0
49
t1t0
50
t1
t0
51
t1
t0
52
t1
t0
53
t1
54
t0
55
t1
t0
56t1
t0
57
t1t0
58
t1t0
59
t1t0
60
t1
t0
61
t1
t0
62
t1
t0
63
t1
t0
64
t1
65
Toutes les sequences sont de longueur bornees (ici par 10)57 / 111
Lien entre ces differentes proprietes
Reinitialisable ⇒ Sans blocage
Vivant ⇒ Sans blocage
Reinitialisable et Vivant sont sans rapportN#4 est vivant sans etre reinitialisableN#3 est reinitialisable sans etre vivant
Reinitialisable + Quasi-Vivant ⇒ Vivant
Sans blocage ⇒ Infiniment actifReciproque fausse (cf N#2)
Pas de rapport entre Infiniment actif et quasi-vivacite, vivacite, propre
Pas de rapport entre borne et bloquant, quasi-vivacite, vivacite, propreReseau N#7 est non borne et contient une infinite d’etats de blocage
Non borne ⇒ Infiniment actifReciproque fausse (par ex N#2)
Reseau N#7 : non borne et avec une infinite de deadlocks
p0
t0 t1
p1A(N#7, p0.p1) =p0.p1k : k ∈ IN ∪ p1k : k ∈ IN
p1k : k ∈ IN contient les deadlocks
58 / 111
Decision des proprietes generales via les CFC
(Rappels) Composantes fortement connexes (CFC/SCC)
Etant donne un graphe oriente G =< S ,→>
1 C ⊂ S est une composante fortement connexe de G ssi C est unsous-ensemble maximal verifiant : u, v ∈ C alors ∃σ1, σ2 ∈ T ∗ : u
σ1→ v etvσ2→ u
2 Les CFC forment une partition du graphe et induisent une relationd’equivalence ∼cfc : s ∼cfc q ssi s et q appartiennent a la meme CFC.
Sur l’ exemple S/∼cfc = a, b, e, c, d , h, f , g3 On peut “ quotienter” le graphe initial (G =< S ,→>) pour obtenir le
graphe quotient des CFC : G/∼cfc=< S∼cfc ,→∼cfc> defini par :S∼cfc = S/∼cfc et →∼cfc = (s, q) ∈→: s 6∼cfc q
2
c,d,h
1
f,g
0
a,b,e
4 Une cfc est “pendante” ssi ∀e ∈ cfc, e → q ⇒ q ∈ cfcf , g est pendante
5 Une cfc est “triviale” ssi elle est reduite a un point et ne contient pas deboucle. 59 / 111
Decision de (certaines) proprietes generales via les CFC
Soit < R,m0 > un reseau borne :
1 < R,m0 > est bloquant ssi G(R,m0)/∼cfc contient au moins une cfcpendante triviale.
2 < R,m0 > est propre ssi G(R,m0)/∼cfc contient une seule cfc.
3 < R,m0 > est infiniment actif ssi G(R,m0)/∼cfc contient au moins unecfc non triviale.
4 < R,m0 > est vivant ssi chaque cfc pendante de G(R,m0)/∼cfc contienttoutes les transitions.
nb : les cfc n’apportent pas de reponse sur la quasi-vivacite ou sur le caractere
borne
Retour sur N#4
24
X
2Y
C
5
A B
3
5
5
2
3
- 3 cfc donc N#4 n’est pasreinitialisable- chaque cfc pendante (il n’ yen a qu’une) contient toutes lestransitions : N#4 est vivant- 2 cfc non triviales donc N#4est infiniment actif
60 / 111
Reseau N#0
Ceci est un reseau constitue par uneunique transition (pas de place)
t0
Exercice : Completez le tableau suivant
N #0 #1 #2 #3 #4 N#5 #6 #7
Bloquant
Reinitialisable
Quasi-Vivant
Vivant
Infiniment Actif
Borne
61 / 111
Outline
7 Decision de la propriete K BorneQuelques rappelsCaracterisation des reseaux Infiniment actifsCaracterisation des reseaux non bornesArbre de couvertureAlgorithme de Karp & Miller
62 / 111
Quelques rappels ....
Reseau borne
Soit < N,M0 > un reseau marque
1 Une place p ∈ P est b-bornee ssi ssi ∃b ∈ IN, ∀M ∈ A(N,M0) : M(p) ≤ b
2 < N,M0 > est b-borne ssi chacune de ses places est b-bornee
3 < N,M0 > est borne ssi ∃b ∈ IN : < N,M0 > est b-borne
N#8 : Producteur/Consommateur
BacProducteur
prod cons
Consommateur
Place Bac est nonbornee
Producteur
prod cons
Consommateur
AntiBac
Bac
K
Les places Bac et AntiBacsont complementaires
et sont k-bornees
Remarques
Le semi-algorithme de construction du graphe des marquages n’apporte pas dereponse.La propriete “borne “ est importante puisqu’elle conditionne la possibilited’implantation du modele 63 / 111
Decision de la propriete k-borne
Les grandes etapes
Proprietes de Monotonie
Caracterisation des reseaux infiniment Actifs
Algorithme de Karp & MillerArbre de Couverture & Graphe de Couverture
Monotonie : Soit un reseau marque < N,m0 >
Sensibilisation/Tir (rappels)
1 t(•t, t•) est sensibilisee pour le marquage M ssi M ≥• t
2 Si M ≥• t alors Mt→ M ′ avec M ′ = M −• t + t•
nb : Si X ≥ M alors Xt→ X ′ et X ′ − X = M ′ −M = −•t + t•
A(N,m0),G(N,m0), L(N,m0)
Soit M ≥ m0 alors|A(N,m0)| ≤ |A(N,M)|, |G(N,m0)| ≤ |G(N,M)|, L(N,m0) ⊆ L(N,M)
64 / 111
Caracterisation des reseaux Infiniment actifs
Sequences repetitive
Une sequence de transitions σ ∈ T ∗ est dite repetitive ssi∀M ∈ A(N,m0) : M
σ→ M ′ ⇒ M ′σ→
Prop : σ ∈ T ∗ est repetitive ssi ∀M ∈ A(N,m0) : Mσ→ M ′ ⇒ M ′ ≥ M
N#2 : bloquant, borne et infiniment actif
t0
?in
p1
t2
Perte
t1
!out
p0
2
Epsilon
0
p0
1
p1
t2t1
t0
La sequence t0.t1 est repetitive (Xt0.t1→ X (∀X )) et franchissable
Caracterisation des reseaux Infiniment actifs
(rappel) Un reseau est infiniment actif ssi il admet au moins une sequence defranchissement infinie.
Prop : Un reseau est infiniment actif ssi il admet une sequence de
franchissement repetitive65 / 111
Sequence repetitive croissante
Sequence repetitive croissante pour une place donnee
Une sequence de transitions σ ∈ T ∗ est dite repetitive croissante pour une
place p ssi ∀M ∈ A(N,m0) : Mσ→ M ′ ⇒ M ′ ≥ M et M ′(p) > M(p)
N#9 : Un autre reseau non borne
p2
A
B
p1 p3
C
La sequence C .A est repetitive croissante pourla place P2
001
C→100
A→011
avec001≤
011
ou p3C→ p1
A→ p2p3
Exercice : Exploration Partielle de G (N#9, p3)
4 50
3
6
21
p3 p2p3 p2*2p3 p2*3p3
p1 p1p2 p1p2*2
Reliez les marquages entre-euxDonnez les(des) sequencesrepetitives croissantes
66 / 111
Caracterisation des reseaux non bornes
Caracterisation des reseaux non bornes
Une place p est non bornee ssi le reseau admet une sequence de franchissementrepetitive croissante pour la place p
(rappel) Un reseau est non borne ssi il admet une place non bornee
Arbre de Couverture (Karp & Miller)
Arbre de Couverture : Structure finie permettant de detecter toutes les placesnon bornees et de donner une borne a toutes les autres.
Principe : Explorer l’espace d’etats de facon a detecter toutes les sequencesrepetitives croissantes
1 Chaque marquage explore sera compare a tous ses predecesseurs : on doitdonc etre capable de remonter dans le passe. On utilise donc un arbre aulieu d’un graphe
2 On veut etre aussi capable de donner une borne pour les places bornees :on considere des pseudo-marquages (∈ (IN ∪ ω)P) pour lesquels lesplaces non bornees sont marquees par ω. On obtient ainsi une“couverture” (finie) de l’ensemble (infini) des marquages reels.
67 / 111
Arbre de couverture
Definition de INω et des operations afferentes
INω = IN ∪ ω∀n ∈ IN : n < ω
n + ω = ω + n = ωω − n = ω (n − ω n’est pas defini)
On etend de la meme maniere +,−, < a INPω
Intuition de l’arbre de couverture (AC (R,m0))
Les sommets de l’arbre de couverture sont des ω-marquages (∈ INωP)
Propriete de couverture : AC(R,m0) “couvre” A(R,m0)
∀m ∈ A(R,m0),∃m′ ∈ AC(R,m0) : m ≤ m′
68 / 111
Algorithme de Karp & Miller
Algorithme construction de AC (R,m0)
Soit q un sommet etiquete par mSi q admet un ancetre p ayant la meme etiquette
Alors q n’a pas de fils.Sinon
Pour chaque transition t sensibilisee en m : mt→ mt
q admet un fils qt ,l’arc reliant q a qt est etiquete par tet le sommet qt est etiquete par Ω(mt)
Definition de Ω(mt)(p)
Pour chaque place p ∈ PSi qt admet un ancetre a etiquete par ma
avec ma ≤ mt et ma(p) < mt(p)Alors Ω(mt)(p) = ω Sinon Ω(mt)(p) = mt(p)
69 / 111
Exemples d’arbres de couverture
N#10 : Reseau non borne et son arborescence de couverture
p1
p2
t3t1 t2
p3
N#9 (deja vu)
p2
A
B
p1 p3
C
C1
p1
A2
p2*wp3
B
3
p1p2*w
C
4
p1p2*w
A5
p2*wp3
A6
p2*wp3
0
p3
70 / 111
Arbre et Graphe de couverture
Proprietes de l’arbre de couverture [Karp-Miller 69]
Soit un reseau marque < R,m0 >
1 AC(R,m0) est fini
2 < R,m0 > est non borne ssi ∃ q ∈ AC(R,m0),∃p ∈ P tel que q(p) = ω
3 Une place p est non bornee ssi ∃q ∈ AC(R,m0) tel que q(p) = ω
4 Une place bornee p a pour borne Max(q(p) : q ∈ AC(R,m0))
Graphe de Couverture GC (R,m0)
GC(R,m0) : Quotient de l’arbre de couverture obtenu en identifiant lessommets etiquetes par le meme marquage
Exemple N#9 : Arbre et Graphe de couverture
C1
p1
A2
p2*wp3
B
3
p1p2*w
C
4
p1p2*w
A5
p2*wp3
A6
p2*wp3
0
p3
S/ ∼=0, 1, 2, 5, 6, 3, 4
A A
B
C
C0' 1' 2' 3'
2′ ↔ 2, 5, 6 et 3′ ↔ 2, 471 / 111
Graphe de Couverture
Proprietes du Graphe de Couverture GC (R,m0)
1 Si < R,m0 > est borne alors GC(R,m0) = G(R,m0)
2 ∀σ ∈ T ∗ Si m0σ→ m dans < R,m0 >
alors dans GC(R,m0) on a aussi m0σ→ m
Reciproque fausse : Une sequence dans le graphe de couverture necorrespond pas forcement a une sequence de franchissement du reseau.
L’introduction des ω-marquages peut se traduire par l’apparition desequences de franchissement qui n’existent pas en realite.
3 L(R,m0) ⊂ L(GC(R,m0))(Graphe de couvreture est une sur-approximation du comportement reel)
N#11 : Reseau parentheses (expressions bien parenthesees)
[ ]
nbpo
[[w]
] [w]
[
[w]
[0] [[w][0]
[,]
[]]] n’est pas bien parenthesee ( 6∈ L(R,m0)) mais est “reconnue” par le graphede couverture (∈ L(GC(R,m0))
Les langages de Dick ne sont pas rationnels : imposssible de les reconnaıtre par
des automates a etats finis 72 / 111
Journee d’un planteur de bananes
Reseau
rentre
leve
dort
cueille
mange
jette
champ
table
jardin
banane
peau
Graphe de Couverture
0
1 2
3 4
5 7
8
cueille rentre
cueille
rentre leve
levedort
dort
mange
mange
6
jette
leve
9
dort
10
73 / 111
Outline
8 Analyse StructurelleMatrice d’incidenceEquation Fondamentale des reseaux de PetriIntuition de l’analyse structurelleInvariants : definitions, calculs et proprietesExemple de modelisation et de verification par analyse structurelleAnalyse structurelle avec TINA
74 / 111
Introduction
Objectif
B
T
TBAR
C
P2
A
D
P1
Etre capable d’obtenir certainesproprietes du reseau uniquementpar une analyse de la struc-ture/topologie du reseau.
Approche de la verification
Elegante : pas d’exploration de l’espace d’etats
Manuelle : calculs automatiques mais interpretation “manuelle”
Puissante (possiblement) : analyse parametree
Decevante (possiblement) : peut echouer a monter une propriete vraie
75 / 111
Reseaux Place/Transition (rappels)
Definition RdP (rappel)
R =< P,T ,Pre,Post > ou- P, ensemble fini de Places- T , ensemble fini de Transitions- Pre : P × T 7→ IN- Post : P × T 7→ IN
p2
A
CB
p3
E
p5
p1
p4
D
A B ...(•A,A•) (•B,B•)
(
10000
,
01100
) (
01000
,
00010
)
Matrices Pre et Post associees
Pre A B C D E
1 1 0 0 0 02 0 1 0 0 03 0 0 1 0 04 0 0 0 1 05 0 0 0 1 1
Post A B C D E
1 0 0 0 1 02 1 0 0 0 03 1 0 0 0 14 0 1 0 0 05 0 0 1 0 0
76 / 111
Matrice d’incidence
Un autre exemple
X
Y
CA B
5
3
3
2
5
5
2
Pre A B C
5 2 00 1 5
Post A B C
2 0 53 3 0
Matrice d’incidence
C : P × T 7→ ZZC = Post - PreC(p, t) = t•(p)−• t(p)
C A B C
−3 −2 53 2 −5
Reseaux Purs
N est pur ssi t•(p)ו t(p) = 0 ∀t, ∀p
Prop : Si N est pur, Il est possible de retrouver N a partir de C .•t(p) = −Max(0,−C(p, t)) et t•(p) = Max(0,C(p, t))
Dans le cas general, C correspond a une infinite de reseaux distincts.
77 / 111
Image commutative d’une sequence de transitions¯
¯ : T ∗ 7→ INT definie par σ(t) = |σ|tou | | : T ∗ × T 7→ IN est definie par
|ε|t = 0 et |u.σ|t =
1 + |σ|t si u = t|σ|t sinon
Exemple : T = t1, t2, t3, t4
σ1 = t1.t2.t2.t3|σ1|t1 = |σ1|t3 = 1|σ1|t2 = 2,|σ1|t4 = 0
σ1 =
1210
σ2 = t4.t2.t1.t3 |σ1|t = 1 ∀t ∈ T σ1 =
1111
σ3 = t3.t2.t1.t2|σ3|t1 = |σ1|t3 = 1,|σ1|t2 = 2,|σ1|t4 = 0
σ3 =
1210
NB ¯ n’est pas injective (σ3 6= σ1ETσ3 = σ1) 78 / 111
Equation Fondamentale des reseaux de Petri
L’equation
Soient m1,m2 ∈ A(R,m0), σ ∈ T ∗ : Si m1σ→ m2 Alors m2 = m1 + C .σ
Reciproque FAUSSE(1) on travaille avec σ et non σ
(2) on raisonne avec C et non avec Pre & Post
Corollaires
1 ∀m ∈ G(R,m0), ∃σ ∈ T ∗ m = m0 + C .σfondement de l’analyse structurelle
2 Soient m1,m2 ∈ A(R,m0) et σ ∈ T ∗ tels que m2 = m1 + C .σSi ∃p ∈ P : m2(p) < 0 Alors NON (m1
σ→ )
79 / 111
Exemple d’application
Equation RdP : Si m1σ→ m2 Alors m2 = m1 + C .σ
X
Y
CA B
5
3
3
2
5
5
2
C A B C
−3 −2 53 2 −5
Si S = BBCA alors S =121
et C .S =−3 −2 53 2 −5
⊗121
=−22
Ici42
BBCA→ M ′ avec M ′ =42
+−22
=24
De meme,51
BBCA→ M ′′ avec M ′′ =51
+−22
=33
80 / 111
Analyse structurelle/statique
Exploitation du corollaire de l’equation fondamentale des RdP
∀m ∈ G(R,m0), ∃σ ∈ T ∗ : m = m0 + C .σ
Principe : eliminer une des inconnues
Chercher les applications F telle que F .C = 07−→ F .m = F .m0 Invariants lineaires de Place
Chercher les σ verifiant C .σ = 07−→ m0
σ→ m avec m0 = m Invariants lineaires de Transitions
Retour sur la matrice d’incidence C
C ∈ ZZP×T
Image de C , Im(C) = M ∈ ZZP : ∃σ ∈ ZZT : C .σ = MNoyau de C , Ker(C) = σ ∈ ZZT : C .σ = 0
Prop : A(N,m0) ⊆ Im(C) (∀m0 ∈ INP)
81 / 111
Invariants de Place (Intuition)
B
T
TBAR
C
P2
A
D
P1
Focus sur les places T et TBar
1 A et C ne sont pas connectees aux places T et TBarPour x ∈ A,C, Si m
x→ m′
alors m′(T ) = m(T ) et m′(TBar) = m(TBar)
2 Si mB→ m′ alors m′(T ) = m(T ) + 1 et m′(TBar) = m(TBar)− 1
3 Si mD→ m′ alors m′(T ) = m(T )− 1 et m′(TBar) = m(TBar) + 1
donc pour t ∈ B,DSi m
t→ m′ alors m(T ) + m(TBar) = m′(T ) + m′(TBar)
82 / 111
Invariants de Place (Intuition)
B
T
TBAR
C
P2
A
D
P1
Bilan
1) A, C laissent m(T ) et m(TBar) invariants2) & 3) B, D laissent la Somme m(T ) + m(TBar) invariante⇒ m(T ) + m(TBar) est invariante
Conclusion
∀m ∈ A(R,m0) : m(T ) + m(TBar) = m0(T ) + m0(TBar)
Resutat tres general puisqu’il est independant du marquage initial.Impossible a obtenir en utilisant les approches exhaustives type arbre decouverture.
83 / 111
Invariants de Transition (Intuition)
Exemple
B
T
TBAR
C
P2
A
D
P1
P1
P2
TTBar
A.B.C .D→
P1
P2
TTBar
La sequence A.B.C.D laisse le marquage invariant
Dans le detail ....
P1
P2
TTBar
A→
P1 + 1P2
TTBar
B→
(P1 + 1)− 1P2
T + 1TBar − 1
C→
P1
P2 + 1T + 1TBar − 1
D→
P1
(P2 + 1)− 1(T + 1)− 1(TBar − 1) + 1
Verification
C A B C D
P1 1 −1 0 0P2 0 0 1 −1T 0 1 0 −1TBar 0 −1 0 −1
×
1111
=
0000
84 / 111
Invariants de Place (P semi-flots)
Objectif Chercher les applications F tq F .C = 0 et par suite F .m = F .m0
Propriete : Soit F telle que F .C = 0
En posant P = p1, p2 . . . pn et en developpant F .m = F .m0 on obtient :
j=n∑j=1
fj ×m(pj) =
j=n∑j=1
fj ×m0(pj)
j=n∑j=1
fj ×m(pj) = Constante(m0) (∀m ∈ INP)
Propriete : Soit F a coefficients dans IN telle que F .C = 0
Si fi 6= 0 alors la place pi est bornee
fi ×m(pi ) = Cste(m0)− (∑
j∈[1,p]\i
fj ×m(pj))
m(pi ) = 1/fi × (Cste(m0)−∑
j∈[1,p]\i
fj ×m(pj)
m(pi ) ≤ m(m0)/fi Et pi est bornee85 / 111
Invariants de Place du Producteur/Consommateur
B
T
TBAR
C
P2
A
D
P1
1 −1 0 00 0 1 −10 1 0 −10 −1 0 −1
On resoud FP1 FP2 FT FTBar × C =
0000
F .C = 0 ssi FP1 FP2 FT FTBar = λ. 0 0 1 1
Comme FT & FTBar 6= 0 on a T et TBar bornees
De plus, en prenant m0 =
000k
et en developpant F .m = F .m0 on obtient :
m(T ) ≤ K & m(T ′) ≤ K (∀m ∈ G(R,m0))
86 / 111
Composante Conservative, Repetitive
Composante Conservative - Invariant de Place, P semi-flots
Def : B ⊆ P est un invariant de Place ssi ∃F ≥ 0 tq ||F || = B et F .C = 0ou ||F || = pi ∈ P : Fi 6= 0
Prop : Si B est un invariant de place, alors toute place p de B est borneereciproque fausse
Def : R est conservatif (consistent) si P est couvert par des invariants de place
Prop : Si R est conservatif/consistent alors R est borne
Composante Conservative - Invariant de Transitions, T semi-flots
Def : S ⊆ T est un invariant de Transition ssi∃s ∈ T ∗ telle que ||σ|| = S et C .σ = 0
Def : R est repetitif (invariant) si T est couvert par des invariants de transition
Prop : Si R est vivant et borne est Alors R est repetitif
nb :
Infinite possible d’invariants. L’analyse permet d’en obtenir une base.87 / 111
Exemple de reseau sans invariant de place
rentre
leve
dort
cueille
mange
jette
champ
table
jardin
banane
peau
T semi-flot
Cueille.Mange.Jette est une sequence invariante
Pour que l’invariant de transitions soit effectif(soit franchissable) il faut au moins 3 planteurs ;un au champ, un a table et un dans le jardin.
Aucun P semi-flot
Pour m0 donne et m ∈ A(R,m0) on am(champ) + m(table) + m(jardin) ≤ m0(champ) + m0(table) + m0(jardin)
Les places champ, table et jardin ne forment pas un invariant de place, pourautant les places champ, table et jardin sont bornees.
On sait par ailleurs que banane et peau sont non bornees et ne peuvent
appartenir a un invariant de place.
88 / 111
Modelisation et verification struturelle du Pb deslecteurs/ecrivains
Enonce
Lecteurs et ecrivains en concurrence pour acceder a une (abstraction) de basede donnees. Modeliser un arbitre (controleur) permettant de synchroniser leslecteurs et les ecrivains pour assurer les proprietes de surete ci-dessous
C1 : Pas plus de k lectures simultanees
C2 : Pas plus d’un ecrivain dans la base
C3 : Pas de lecture et d’ecriture simultanement dans la base
Aspects non traites :
Vivacite/”Absence de Famine” : Toute requete (de lecture ou d’ecriture)est satisfaite au bout d’un temps fini.
Maintien de la coherence des donnees (si une valeur est lue alors ellecorrespond a la derniere valeur ecrite).
89 / 111
Un modele possible
Modelisation parametree
Modele de la base de donnees “generique” :entier positif k est un parametre du marquage et du reseau.
On suppose que la population de lecteurs et d’ecrivains est infinie.
90 / 111
Legende
Les “composants”A droite les lecteurs, a gauche les ecrivains et au centre le controle.Les “lieux”
une salle de lecture et d’une salle d’ecriture,
deux salles d’attente : l’une pour les lecteurs et l’autre pour les ecrivains.
Le “controle” : Mutex synchronise lecteurs et ecrivains.
Expression dans le modele des proprietes attendues : ∀m ∈ A(R,m0)
C1 : m(Lecture) ≤ k Pas plus de k lectures simultanees
C2 : m(Ecriture) ≤ 1 Pas plus d’un ecrivain dans la base
C3 : m(Ecriture)×m(Lecture) = 0Pas de lecture et d’ecriture simultanees
Remarque Modelisation/Verification
On fait le modele pour l’analyser/verifier. On doit avoir identifier (avant) lesproprietes que l’on voudra verifier. On doit donc s’assurer, au plus tot, que l’onest deja capable de les exprimer dans/avec le modele.
Si on est pas capable de les exprimer (simplement) alors on ne pourra pas les
verifier (surement).91 / 111
Calcul et exploitation des P semi-flots
On resoud F .C = 0En ayant pris P = [Lecture,Mutex ,Ecriture,Attente Lecture,Attente Ecriture]On obtient F = λ(1, 1,K , 0, 0)
Sachant que K > 0 on en deduit que les places Lecture, Ecriture et Mutex sontbornees.
De plus, pour m0 =
0K000
et m ∈ A(R,m0) on a
F .m = (1, 1,K , 0, 0)×
m(Lecture)M(Mutex)M(Ecriture)M(Attente Lecture)m(Attente Ecriture
= F .m0 = 0
et finalement m(Lecture) + m(Mutex) + k ×m(Ecriture) = K
92 / 111
Verification structurelle des proprietes
1 En isolant m(Lecture) dans l’invariant, on obtient :
m(Lecture) = K − (m(Mutex) + K ×m(Ecriture))
Comme un marquage est une application a valeurs dans les entiersnaturels, on en deduit C1 : m(Lecture) ≤ K .
2 C2 : m(Ecriture) ≤ 1 peut etre obtenue de facon identique en isolantm(Ecriture) dans l’invariant et en se souvenant que K est strictementpositif.
3 En prenant la negation de C3, on obtient
m(Lecture) > 0 et m(Ecriture) > 0
On a donc m(Lecture) + K ×m(Ecriture) > K + 1
D’un autre cote, l’invariant nous assure que :
m(Lecture) + K ×m(Ecriture) ≤ k
Comme K > 0, on aboutit ainsi a la contradiction et C3 est validee.
93 / 111
Quid de K = 0
Bilan
L’analyse structurelle ne permet plus d’assurer C2 et C3.
La place Mutex n’est plus une pre-condition de la transitionEntree Ecrivains ; L’arc correspondant disparaıt car il est value par 0 et lenombre d’ecritures simultanees devient non borne.
La lecture devient impossible puisque le marquage initial de la placeMutex est nul.
94 / 111
Bilan Analyse structurelle
Analyse parametree
Possibilite de pouvoir travailler avec l’analyse structurelle sur un reseauparametre.
Les proprietes attendues ont ete etablies non pas pour un reseau marque maispour toute une famille (infinie) indexee par K > 0 de reseaux marques.
Une approche exhaustive (construction du graphe d’accessibilite, arbre de
couverture de Karp et Miller) n’aurait pu etre conduite puisque nous aurions du
auparavant fixer une valeur pour le parametre K .
Vivacite/Surete
L’analyse structurelle est une approche seduisante pour la verification desproprietes dites de “Surete”
“Rien de mauvais ne peut arriver”
L’analyse structurelle n’appporte (en general) pas de reponse pour laverification des proprietes dites de “Vivacite”
“Quelque chose de bon doit arriver”95 / 111
Analyse structurelle avec TINA
Enonce
Deux processus (banalises) partagent deux ressources (A et B). L’un des
processus se procure d’abord A (OqpA), puis se procure B (OqpAB), il travaille
(WorkAB) puis il retourne au repos en liberant (FreeAB) les deux ressources.
L’autre processus procede dans l’ordre inverse : obtention de B puis de A.
OqpA OqpAB
OqpBOqpBA
Bidle
2
WaitB
WaitA
workAB
FreeAB
A
workBA
FreeBA
Exploration de l’espace d’etats0 : A B idle*2
1 : B WaitB idle
2 : idle workAB
3 : WaitA WaitB
4 : A WaitA idle
5 : idle workBA
OqpA
1
OqpAOqpB3
OqpAB
2
FreeBAFreeAB
0
OqpBA
5
OqpB
4
96 / 111
Analyse structurelle avec TINA : P Semi-flots
(rappel)
0 : A B idle*2
1 : B WaitB idle
2 : idle workAB
3 : WaitA WaitB
4 : A WaitA idle
5 : idle workBA
P-SEMI-FLOWS GENERATING SET
invariant
A WaitB workAB workBA
WaitA WaitB idle workAB workBA
B WaitA workAB workBA
Interpretation/Remarques
Invariant (conservatif) : Reseau structurellement borne
Ensemble (infini) des invariants est genere par une base de 3 invariantsm(A) + m(WaitB) + m(workAB) + m(workBA) = cstea(m0)
m(WaitA)+m(WaitB)+m(idle)+m(workAB)+m(workBA) = csteb(m0)m(B) + m(WaitA) + m(workAB) + m(workBA) = cstec(m0)
L’exclusion mutuelle peut etre prouvee en utilisant Inv1 (ou Inv3)
97 / 111
Analyse structurelle avec TINA : T Semi-flots
OqpA
1
OqpAOqpB3
OqpAB
2
FreeBAFreeAB
0
OqpBA
5
OqpB
4
T-SEMI-FLOWS GENERATING SET
consistent
FreeAB OqpA OqpAB
FreeBA OqpB OqpBA
Interpretation/Remarques
Consistent (i.e., repetitif)chaque transition appartient a un invariant de transitions
Ensemble (infini) des invariants est genere par une base de 2 invariantsFreeAB OqpA OqpABFreeBA OqpB OqpBA
Interpetation :Si M − OqpA.OqpAB.FreeBA− >
alors M − OqpA.OqpAB.FreeBA− > M(1) l’orde des transitions dans la sequence n’est pas fourni !(2) un tel marquage M n’est pas forcement accessible.
L’existence de ces invariants laisse presager la possibilite de famine !C’est bien le cas ici ! 98 / 111
Outline
9 Boıte a Outils TINAFormalisation : Modelisation/Verification avec TINATINA ToolboxMethodes Formelles et Process IndustrielsLiens
99 / 111
Formalisation : Modelisation/Verification (Rappel)
Ingredients
FormalisationM : Modele (formel) du comportement (issu de Rdp, AC, Alg.Proc,..)7→ Permet de decrire l’ensemble de tous les comport ements du systeme
φ : Modele (formel) des proprietes (formalism e dedie)7→ Permet de formaliser les exigences a respecter
Verification Model − Checker :Outil de verification permettant de decider si M satisfait φ?
nb : Formel est une condition requise pour envisager l’automaticite
100 / 111
TINA (TIme Petri Net Analyser)
TINA Toolbox (http ://www.laas.fr/tina)
Environnement d’edition, simulation, verification de reseaux de Petrietendus.Freeware / Linux, Solaris, MacOS, Windows
Processus de verification en 3 Etapes
Modelisation
⇒ modele formel M de l’application⇒ proprietes attendues Φ, dans la logique L
Abstraction de M
preservant les formules de L⇒ graphe d’etats abstraits fini Abs
Verification des formules Φ sur A (Model-Checking)
⇒ VRAI ou un contre-exemple(M |= Φ⇔ Abs |= Φ)
101 / 111
TINA
Modeles formels
Reseaux de Petri Temporels + Priorites, Donnees, Chronometres
Descriptions de haut niveau en FIACRE (compilees)
Abstractions
Graphes de couverture
Espaces d’etats exacts
Reductions ordre partiel
Graphes de classes
Graphes d’etats essentiels
Verification
State/Event LTL (natif)
Mu-Calcul (natif)
Exportation abstraction vers outils CADP, MEC
102 / 111
TINA Toolbox (http ://www.laas.fr/tina)
nd (netdraw)
Graphic and textual editor Of Time Petri Net or Transition Systems
Simulating interactively net descriptions in all formats accepted by tina
Interfaced with other tools
tina, sift (state space generators)
Input : Petri nets + time, priorities, preemption, data (API)
Builds : behavior abstractions, Preserving some classes of properties
Output : in verbose form or in model-checkers formats
selt, muse
Model checkers for SE-LTL temporal logic and modal µ-calculus
struct, plan, etc
Structural analysis, Path analysis, converters, etc
Vu cette annee : nd, tina, struct103 / 111
Methodes Formelles et Process Industriels
104 / 111
Liens
Outils
http://www.laas.fr/tina
http://www.laas.fr/fiacre
Projets
Topcased : www.topcased.orgSpices : www.spices-itea.orgOpenEmbeDD : openembedd.orgItemis : itemis-anr.orgQuarteft : quarteft.loria.frCESAR : www.cesarproject.eu
OpenETCS : openetcs.orgINGEQUIP, OCE, MOISE :www.irt-saintexupery.com/
105 / 111
Outline
10 EpilogueConclusionBibliographie PetriTable des Matieres
106 / 111
En conclusion pour la partie Petri
Interet des RdP
Formalisme Rigoureux (semantique precise)
Expressivite+ Compact (vs machines a etats)+ Concepts : //, Cooperation, Competition, Synchronisation, . . .+ Dualite Etat/Evenement
Possibilites d’Analyse : Structurelle, Exhaustive
Representation Graphique
Aspects non traites
Reductions
Extensions des RdP
arcs inhibiteurs, priorites (voir tp)Donnees (Reseaux colores, Reseaux Predicat/transitions)Temps (temps reel)Stochastique (performances)
+ generalement (hors rdp) : techniques de verification107 / 111
Bibliographie
G.W Brams (ouvrage collectif)Reseaux de Petri : Theorie et Pratique (2 tomes) - Masson -1980
W. ReisigPetri Nets. An Introduction Springer-Verlag EATCS 1985
C. ReutenauerAspect Mathematiques des Reseaux de PetriEtudes et recherches en informatique Masson - 1989
K. JensenColoured Petri Nets - Springer-Verlag EATCS 1992
W. ReisigElements od Distributed Algortithms : Modeling and Analysis with PetriNets Springer-Verlag 1998
M. Diaz (Editeur)Les Reseaux de Petri. Modeles fondamentaux,Hermes Science, Traite IC2, 2001
M. Diaz (Editeur)Petri Nets. Fundamental Models, Verification and Applications,ISTE & Wiley, N 978-1-84821-079-0, 2009
108 / 111
Table des Matieres
1 Introduction
2 Reseaux de Petri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Reseaux Place/Transition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1 Exemple introductif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 Definitions Generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 Semantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 Graphe des Marquages accessibles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .225 Reseaux bornes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Exemples de modelisation en Rdp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 Une histoire de pont . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 Journee d’un planteur de bananes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 Forme textuelle Petri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 Piscine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5 Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401 Composition & Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442 Communication Asynchrone & Synchrone . . . . . . . . . . . . . . . . . . . . . . . 453 Asynchrone Vs Synchrone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464 Probleme du choix distant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
109 / 111
6 Proprietes generales des Reseaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .521 Bloquant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532 Reinitialisable / propre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543 Quasi-vivacite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554 Infiniment actif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575 Lien entre ces differentes proprietes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586 Decision des proprietes generales via les CFC . . . . . . . . . . . . . . . . . . . . 59
7 Decision de la propriete K Borne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621 Caracterisation des reseaux Infiniment actifs . . . . . . . . . . . . . . . . . . . . . 652 Caracterisation des reseaux non bornes . . . . . . . . . . . . . . . . . . . . . . . . . . 663 Arbre de couverture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684 Algorithme de Karp & Miller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .69
Analyse Structurelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 741 Matrice d’incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 762 Equation Fondamentale des reseaux de Petri . . . . . . . . . . . . . . . . . . . . .793 Intuition de l’analyse structurelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824 Invariants : definitions, calculs et proprietes . . . . . . . . . . . . . . . . . . . . . . 855 Exemple de modelisation et de verification par analyse structurelle 896 Analyse structurelle avec TINA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
110 / 111
8 TINA (Time Petri Net Analyser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .991 Formalisation : Modelisation/Verification avec TINA . . . . . . . . . . . . 1012 TINA Toolbox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1033 Methodes Formelles et Process Industriels . . . . . . . . . . . . . . . . . . . . . . 1044 Liens et Projets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
9 Epilogue1 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1072 Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1083 Table des Matieres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
111 / 111
