1
Master Informatique - Spcialit SAR
NI405 - Modlisation des systmes rpartis
Introduction aux
rseaux de Petri de haut niveau
(les rseaux colors)
1 - Modlisation
J.F. Peyre - C. Dutheillet
Pourquoi les rseaux de haut niveau ?
Problme :
n processus en exclusion mutuelle sur 1 ressource
Attente2
Attente
n = 12
En cours
Ressource
Repos
En cours2
Repos2
Pourquoi les rseaux de haut niveau ?
Problme 2 :
n1 processus en exclusion mutuelle sur n2 ressources
n1 = 2
n2 = 2
Pourquoi les rseaux de haut niveau ?
Les rseaux de Petri ordinaires
ne capturent pas les symtries dun problme
ne permettent pas dassocier des informations aux jetons
Ne permettent pas de paramtrer la solution dun problme
Utiliser une notation concise et paramtre des rseaux
de Petri :
les rseaux de haut-niveau
Les rseaux de Petri colors
Dfinition informelle
Chaque place p est caractrise par un
domaine de couleur C(p)
Un jeton dune place p est un lment de
C(p)
P2
C2
P1
C1
X1
Chaque transition t est caractrise par
un domaine de couleur C(t)
Le domaine de couleur dune transition
caractrise la signature de cette transition
Les fonctions de couleur sur les arcs
dterminent les instances de jetons
ncessaires, consommes et produites lors
du franchissement dune transition
X2
t
C1 x C2
<X1,X2>
P3
C1 x C2
Un exemple
n processus appartenant une
classe de processus C = {1, , n},
en exclusion mutuelle sur une
ressource non signe
Un processus est soit dans ltat
Attente, soit dans ltat EnCours,
soit dans ltat Repos.
Attente
X
EnCours
Ressource
Pour passer de Attente
EnCours, un processus a besoin
de la ressource.
C(Attente) = C(EnCours) = C(Repos) = C
C(Ressource) = {}
Repos
M0(Repos) = C. All
X : Bag(C) Bag(C)
cc
Un autre exemple
n1 processus appartenant une
classe de processus C1 = {1, , n1},
en exclusion mutuelle sur n2
ressources appartenant
C2 = {1, , n2}
Un processus X1 est soit dans ltat
Attente, soit dans ltat EnCours,
soit dans ltat Repos.
Attente
X1
X1
<X1,X2>
<X1,X2>
X1
X2
EnCours
X2
Ressources
X1
Pour passer de Attente EnCours,
Repos
un processus X1 a besoin dune
ressource X2.
C( Attente) = C(Repos) = C1
M0(Repos) = C1 . All
C(EnCours) = C1 x C2
M0(Ressource) = C2 . All
C(Ressource) = C2
Multi-ensemble
Soit A un ensemble fini et non vide.
Un multi-ensemble a sur A est une fonction de A vers
IN.
On note
a=
a(x).x
x A
o a(x) dsigne le nombre doccurrences de x dans a.
Bag(A) dsigne lensemble des multi-ensembles sur A
10
Notations fonctionnelles
f1 : Bag(C1) Bag(C2)
f2 : Bag(C'1) Bag(C'2)
g : Bag(C) Bag(C1)
< f1, f2> : Bag(C1) x Bag(C'1) Bag(C2) x Bag(C'2)
(x, y) < f1 (x), f2 (y)>
f1
g : Bag(C) Bag(C2)
x f1 (g(x))
11
Notations vectorielles
Soit F un vecteur sur A index par I ( F(i) A )
F(i) dsigne la ime composante de F
On note F par une somme formelle :
F = F(i).i
iI
12
Dfinition formelle : la structure
Un rseau de Petri color est un 6-uplet
<P, T, C, W-, W+, M0>
P est lensemble des places, T est lensemble des
transitions (P T = , P T )
C dfinit pour chaque place et chaque transition son
domaine de couleur
W- ( = Pr) (resp. W+ = Post), indexe sur P x T, est la
matrice dincidence arrire (resp. avant) du rseau
W-(p, t) et W+ (p, t) sont des fonctions linaires de couleurs
dfinies de Bag(C(t)) dans Bag(C(p))
13
Complments la dfinition
M0 est le marquage initial du rseau ; cest un vecteur
index par P et M0(p) est un lment de Bag(C(p))
Les transitions peuvent tre gardes par une fonction
Bag(C(t)) {0, 1}
Les domaines de couleurs sont gnralement des produits
cartsiens
14
Dfinition formelle : la dynamique
Soit CN = <P, T, C, W-, W+, M0> un rseau color.
Un marquage M de CN est un vecteur index par P,
avec M(p) Bag(C(p))
Une transition t est franchissable pour une instance
ct C(t) et un marquage M si et seulement si :
Soit t est non garde, soit la garde vaut 1 (= vrai) pour ct
p P, M(p) W-(p, t)(ct)
15
La dynamique (suite)
Le marquage M atteint aprs le franchissement de t
pour une instance ct partir du marquage M est dfini
par :
p P, M(p) = M(p) - W-(p, t)(ct) + W+(p, t)(ct)
On note :
M [(t, ct)> M
(t, ct)
M M
16
Exemple de franchissement
P2
C2
P1
C1
X1
X2
Soit x1 C1, x2 C2
t est franchissable pour (x1, x2) ssi
1) P1 contient au moins un jeton de couleur x1
(X1(x1, x2) = x1)
t
C1 x C2
<X1,X2>
2) P2 contient au moins un jeton de couleur x2
P3
C1 x C2
Si on franchit t pour (x1, x2) alors
1) Un jeton de couleur x1 est retir de P1
2) Un jeton de couleur x2 est retir de P2
3) Un jeton de couleur <x1, x2> est produit dans
P3 : <X1, X2> (x1, x2) = <x1, x2>
17
Exemple (suite)
C1 = {a, b, c}
C2 = {, }
X1
P2
C2
P1
c
C1
P2
C2
P1 a+c
C1
X1
X2
t, (a, )
t
C1 x C2
<X1,X2>
P3
<c,> C x C
1
2
X2
t
C1 x C2
<X1,X2>
P3
<c,>
+<a,>
C1 x C2
18
Fonctions de couleur de base
n
C=
ei
Ci
i=1 j=1
un domaine de couleur construit par produit
cartsien des classes de couleurs, dans lequel
la classe Ci apparat ei fois.
Dans la pratique, C est le domaine dune transition.
c = <c11, c12, , c1e1, , cn1, cn2, , cnen > C
Identit/Projection :
Note par une variable : X, Y, ou X1, ou X11, ou p, q,
Xij(c) = cij
Y(<x, y>) = y
q(<p, q, r>) = q
19
Fonctions (suite)
Successeur (sur Ci ordonne circulairement)
Note Xi++ ou (Xi 1) ou Xi!
Xij++(c) = successeur(cij)
La relation successeur est dfinie par
lordre dnumration des lments
de la classe Ci
Diffusion / Synchronisation (sur Ci)
Note Ci.All ou SCi
Ci. All(c) =
x
x C i
La valeur est indpendante de llment
choisi dans Ci
20
Modlisation du problme des trains
Problme :
n1 trains sont rpartis sur une voie circulaire
dcompose en n2 sections
Pour des raisons de scurit, un train ne peut entrer
dans une section que si cette section et la suivante sont
libres (distance de scurit)
21
Modle(s) ?
Domaines de couleurs :
C1 = {tr_1, , tr_n1}
C2 = {sc_1, , sc_n2}
Dynamique :
Ltat du systme est donn par un ensemble dassociations <n
train, n section> place Tr_Sc
Une section disponible est une ressource permettant le mouvement
dun train place Sc_Dispo
Une transition permet de reprsenter la progression dun train
22
Des solutions
Tr_Sc
C1 x C2
<t,s>
<t,s++>
C1 x C2
<s> +
<(s++)++>
<s++> +
<(s++)++>
Sc_Dispo
C2
Tr_Sc
C1 x C2
<t,s>
[y = s++]
<s> +
<y++>
<t,y>
C1 x C2
<y> +
<y++>
Sc_Dispo
C2
23
Ou encore
Tr_Sc
C1 x C2
<t,s>
<t,s++>
C1 x C2
<s-->
<s++>
Sc_Dispo
C2
s reprsente maintenant la
section demande
Attention au marquage initial !
24
Dpliage de rseau
Pour obtenir un rseau ordinaire ayant le mme
comportement que le rseau color
Pour chaque place ou transition, on cre autant dinstances que son
domaine de couleur contient dlments
Les connexions sont obtenues en dpliant les fonctions de
couleur
Parfois le seul moyen dobtenir des rsultats sur le
modle
Mais on ne sait pas exprimer les rsultats sur le modle dorigine
-> interprtation parfois difficile
Facilement automatisable
25
Dpliage de rseau
Soit CN = <P, T, C, W-, W+, M0> un rseau color.
Le rseau ordinaire sous-jacent (dpli) est le rseau
CNd = <Pd, Td, Cd, W-d, W+d, M0d> o
Pd =
Td =
( p,c p ) est lensemble des places
p P,c p C ( p )
(t,c t ) est lensemble des transitions
t T ,c t C (t )
M0d (p, cp) = M0 (p)(cp) est le marquage initial
/
26
Dpliage (suite)
W-d (p, cp)(t, ct) = W- (p, t)(ct)(cp) est la fonction
dincidence arrire
W+d (p, cp)(t, ct) = W+ (p, t)(ct)(cp) est la fonction
dincidence avant
Proposition :
M [ (t, ct) >CN M Md [ (t, ct) >CNd Md
o Md(p, c) = M(p)(c)
27
Exemples de dpliage (1)
P
C
(P,1)
(P,2)
(P,3)
(t,1)
(t,2)
(t,3)
(Q,1)
(Q,2)
(Q,3)
X
t
C
Dpliage
X
Q
C
C = {1, 2, 3}
28
Exemples de dpliage (2)
P
C
(P,1)
(P,2)
(P,3)
(t,1)
(t,2)
(t,3)
(Q,1)
(Q,2)
(Q,3)
X
t
C
Dpliage
X++
Q
C
C = {1, 2, 3}
29
Exemples de dpliage (3)
(P,1)
P
C
(P,2)
(P,3)
All.C
t
Dpliage
t
All.C
Q
C
C = {1, 2, 3}
(Q,1)
(Q,2)
(Q,3)
30
Exemples de dpliage (4)
(P,1) (Q,2) (Q,3) (P,3) (Q,1) (P,2)
S-X
Dpliage
(t,3)
(t,2)
S-X++
X++
R
(t,1)
S
(R,2) (S,3) (S,1) (R,1) (S,2) (R,3)
C = {1, 2, 3}
C(P)= C(Q)= C(R)=
C(S)= C
31
Arc inhibiteur color
Pour tester quune place est vide
P
Pour tester quune place ne contient pas de jeton de
couleur a
P
t
X
[X = a]
Les ensembles de couleur sont finis
pas de modlisation du type lecteur/crivain avec un nombre infini
de lecteurs
32
Dpliage darc inhibiteur
C = {a, b, c}
Pa
Pb
Pc
Pb
Pc
S
t
t
Pa
P
C
X
t
[X = a]
ta
33
Modlisation : les philosophes
N philosophes sont assis autour dune table et pensent.
De temps en temps, ils mangent dans un bol de riz pos
devant eux
Problme : il ny a que N baguettes, et chaque
philosophe a besoin de 2 baguettes pour manger
Version 1 : il y a N baguettes poses au milieu de la table.
34
Les philosophes (suite)
Version 2 : les baguettes sont disposes entre les
philosophes. Pour manger, un philosophe doit prendre
la baguette sa gauche et celle sa droite.
a) Un philosophe prend ses 2 baguettes en mme temps
b) Il prend dabord celle de droite, puis celle de gauche
c) Il prend lune puis lautre
35
Modlisation : lalgorithme de Peterson
But :
raliser lexclusion mutuelle de 2 processus au moyen de
variables partages
Processus x (x == 1 ou x == 2)
Flag[x] = 0;
Flag[x] == 1 : x demande la section
critique
Turn : identit du dernier processus
ayant demand la section critique
While (1) {
Flag[x] = 1;
Turn = x;
wait until
((Flag[x++] = 0) || (Turn = x++));
Section critique
Flag[x] = 0;
}
36
Gnralisation N processus
Principe :
escalier (N-1) niveaux
Un processus peut passer du niveau
j au niveau j+1 si :
N=3
Soit il nest pas le dernier arriv au
niveau j,
Soit il est seul au niveau j et tous les
niveaux suprieurs sont libres
SC
nv2
Un seul processus peut aller au del
du niveau N-1
section critique
nv1
nv0
37
Lalgorithme pour N processus
Processus x (x == 1 . . N-1)
Flag[x] = 0;
While (1) {
For (j=1; j<N; j++) {
Flag[x] = j;
Turn[j] = x;
wait until
((y x, (Flag[y] < j)) || (Turn[j] x))
}
Section critique
Flag[x] = 0;
}
