GL3

Modélisation des systèmes

Chapitre 4 :
Réseaux de Petri

Olfa Mosbahi
olfamosbahi@[Link]
Modélisation Réseaux de Petri (Introduction)

Formalisme Graphique

Objectif: Modéliser le comportement dynamique d’un système discret.

Modèle opérationnel exprimant à la fois le flot de contrôle et le flot de

données.

Avantages:
▪ Permet de considérer la structure du système et l’évolution du flot de
données.
▪ Permet de représenter les changements d’états et la causalité des
événements que provoquent ces changements.
▪ Modèle solidement assis sur des bases formelles.
Modélisation Éléments d’un Réseaux

Un réseau de Petri est composé:

p
1. d’un ensemble fini de places

2. d’un ensemble fini de transitions t

3. d’un ensemble fini de flèches reliant

- soit une place à une transition,
- soit une transition à une place.
Modélisation Étiquetage des Éléments

t3
p1 p3
t1
3
2 p6

p2 p4

t2 p5

▪ Chaque place est étiquetée par son nom.

▪ Chaque transition est étiquetée par son nom.
▪ Une flèche peut être étiquetée d’un nombre entier (>1) indiquant le
nombre d’occurrence de cette flèche, c’est-à-dire, le nombre de jetons
nécessaires pour que la flèche soit « activée ».
▪ S’il n’y a pas d’étiquette, l’occurrence est 1, par défaut.
Modélisation Définition Formelle

Un réseau de Petri est un quadruplet

R = <P,T, Pre, Post>

P est un ensemble fini de places,

T est un ensemble fini de transitions,

Pre : P x T → N est l’application d’incidence avant. Elle contient la valeur

entière «n» associée à l’arc allant de «p» à «t» (poids d’un arc),

Post : P x T → N est l’application d’incidence arrière. Elle contient la valeur

entière «n» associée à l’arc allant de «t» à «p» (poids d’un arc).
Modélisation Définition Formelle

Un réseau de Petri est un quadruplet

R = <P,T, Pre, Post>

P= {p1,p2,p3,p4} ; T={t1,t2}
p1
Pre(p1,t1)= 2;
t1 Pre(p2,t1)=1
Pre(p3,t2)=1
2 Post(p3,t1)=1;
p2 t2 Post(p4,t2)=1
p3 p4 Le reste:
Post(pi,tj)=0 et Pre(pi,tj)=0
Modélisation Précisions Terminologique

Places d’entrée d’une transition t = Places de sortie d’une transition t =

places dont proviennent les flèches places vers lesquelles sont orientées
entrant de la transition. les flèches qui sortent de la transition.

In(t) = {p  P | Pre(p,t) > 0} Out(t) = {p  P | Post(p,t) > 0}

p1
t1 In(t1)= {p1,p2}
In(t2)= {p3}
2
p2 t2 Out(t1)= {p3}
p3 Out(t2)= {p4}
p4
Modélisation Réseau Marqué

▪ L’état d’un réseau de Petri est défini en plaçant des jetons dans ses places.
▪ Chaque état est caractérisé par un marquage indiquant le nombre de jetons
contenus par chaque place.
Un marquage = Affectation d’un entier non-négatif à chaque place.
R est un réseau de Petri <P,T, Pre, Post>
Un réseau marqué est un couple M est un marquage, cad une application
N = <R, M> M : P → N,
M(p) est le nombre de jetons dans p  P

Marquage t3
p1 p3
t1
M(p1)=3 3
M(p2)=1 2 p6
M(p3)=1
M(p4)=0 2
M(p5)=0 p4
p5
M(p6)=0 p2 t2
Modélisation Exemple

Avant franchissement Après franchissement

P1 P2
P1 P2

P3 P4
P3 P4

Les marquages sont les suivants :

Avant franchissement : M(P1) = 3 ; M(P2) = 4 ; M(P3) = 1 ; M(P4) = 0

Après franchissement : M(P1) = 1 ; M(P2) = 3 ; M(P3) = 2 ; M(P4) = 3

Modélisation Règles de Franchissement

Une transition est dite «franchissable» si chacune de ses places

d’entrée contient un nombre de jetons supérieur ou égal à celui indiqué
sur la flèche correspondante.

Une transition t est franchissable ssi

 p  P, M(p)  Pre(p,t),
ou alternativement,
 p  In(t), M(p)  Pre(p,t),

t3
p1 p3
t1
3
2 p6

2
p4
p5
p2 t2
Modélisation Franchissement (suite)

❑ Une transition franchissable peut être franchie (ou tirée).

❑ Lorsqu’une transition est franchie, les jetons des places d’entrée sont déplacés
vers les places de sortie.
❑ Le nombre exact des jetons retirées/rajoutées pour une place donnée
correspond à l’étiquette sur la flèche correspondante.
❑ Le franchissement d’une transition franchissable t transforme le marquage
initial M en le nouveau marquage M’ tel que :

 p  P, M’(p) = M(p) – Pre(p,t) + Post(p,t)

p1 p3 t3
t1
3
2 p6
2
p4
p5
p2 t2
Modélisation Validation d’une transition

Une transition est validée (on dit aussi sensibilisée ou franchissable ou encore tirable) si
toutes ses places d’entrée contiennent au moins un jeton.
Modélisation Validation d’une transition

▪ Soit Pre(i, T) le poids d'un arc amont i de la transition T.

▪ Soit Post(j, T) le poids d'un arc aval j de la transition T.

Si  Pre(i,T)   Post(j,T) alors T est génératrice

Si  Pre(i, T)   Post(j, T) alors T est consommatrice
Si  Pre(i, T) =  Post(j, T) alors T est conservatrice
Modélisation Non-déterminisme

t2 ou t3 ?
t3
p1 p3
t1
3
2 p6

2
p4
p5
p2 t2

Si plus d’une transition est franchissable, le choix de la transition à franchir

est non-déterministe.
Modélisation Séquence Franchissement

Étant donnée un marquage initial d’un RP, une séquence de franchissement

est une suite de transitions franchies dans l’ordre, l’une après l’autre.

p1 t3 Séquences de
p3 franchissement
t1
possibles:
3
2 p6 <t1,t2>
<t1, t3>
2 <t3,t1>
p4
p5
p2 t2 Mi <s> Mj

Cette séquence est dénotée par une chaîne de transitions <t1, …, tn> telle que :
t1 est franchissable depuis le marquage initial

t2 est franchissable depuis le marquage obtenu par la tirée de t1, etc.

Modélisation Sémantique des Réseaux

Un réseaux de Petri peut être interprété en termes de

processus, d’actions et de ressources.

▪ Les transitions servent à modéliser les actions des processus.

▪ Les jetons représentent des ressources consommables.
▪ Le franchissement d’une transition représente l’exécution d’une
action (consommation & production de ressources).
▪ Les flèches entrantes indiquent les conditions à satisfaire avant l’action
(ressources nécessaires).
▪ Les flèches sortantes représentent les conditions à satisfaire après
l’action (ressources à produire).
▪ La présence d’un jeton marque la satisfaction, partielle ou totale, d’une
condition (i.e. présence d’une ressource).
Modélisation Exemple 1

Solution :
▪ Le marquage initial est : M0 = [0 3 0]
▪ Les matrices E (Pre) et S (Post) sont :
Modélisation Exemple 2
Modélisation Sémantique des Réseaux
Modélisation Sémantique des Réseaux
Modélisation Sémantique des Réseaux
Modélisation Propriétés des réseaux de Petri

1- Concurrence

Transitions concurrentes : un couple de transitions dont le

franchissement de l’une n’empêche pas celui de l’autre (quel que soit le
marquage).

p1
p2

t1 p9
t2
t1 et t2
p3 sont concurrentes
p4
…
t3 mais pas t3 et t4
t4

p5 p6
Modélisation Propriétés des réseaux de Petri

❑ Concurrence structurelle: Deux transitions t1 et t2 sont

concurrentes structurellement si elles n’ont aucune place d’entrée
commune i.e.

In(t1)  In(t2) = 

❑ Concurrence effective: Deux transitions t1 et t2 sont concurrentes

effectivement pour un marquage donnée M ssi elles sont
concurrentes structurellement et sont franchissables i.e.

In(t1)  In(t2) = 
et  p  P, M(p)  Pre(p,t1) et M(p)  Pre(p,t2)
Modélisation Propriétés des réseaux de Petri

2- Conflit
❑ Transitionsconflictuelles : Ensemble de transitions dont le
franchissement de l’une empêche le franchissement de l’autre.

p1 Si on tire t3, t4 n’est

plus franchissable
t1 p9
t2 Le choix entre t3 et t4
est non déterministe.
p3
p4
t3 et t4 sont
t3 conflictuelles
t4

p5 p6
Modélisation Propriétés des réseaux de Petri

❑ Conflitstructurel: Deux transitions t1 et t2 sont en conflit structurel si

elles ont au moins une place d’entrée en commun i.e.

In(t1)  In(t2)  

❑ Confliteffectif: Deux transitions t1 et t2 sont en conflit effectif pour un

marquage M ssi elles sont en conflit structurel et sont franchissables de
façon exclusive i.e.

In(t1)  In(t2)  
 p  P, M(p)  Pre(p,t1) et M(p)  Pre(p,t2) et
 p  P, M(p) < Pre(p,t1) + Pre(p,t2)
Modélisation Propriétés des réseaux de Petri

Situation de Famine

« Famine (starvation) : Un processus (une partie du réseau)

est en situation de famine s’il se voit refuser l’accès
à une ressource pendant un temps indéfini. »

▪ Il se peut donc qu’un processus soit privé, pendant une période

indéfinie, d’une ressource, car la séquence des transitions franchies
ne lui permet jamais de consommer cette ressource.

p1 Processus
t1 p9 B
t2
p3 p4
<t1,t2,t3,t1,t3,t1,t3,…>
t3 Séquence de
t4 franchissement
Processus non équitable.
A p5 p6 Processus B en famine!
Modélisation Propriétés des réseaux de Petri

3- Interblocage

« Interblocage (deadlock) : un RP est dit être en

situation d’interblocage lorsque, dans un marquage donné M,
aucune transition n’est franchissable. »

Cas typique: Privation mutuelle

Le processus A est arrêté car il a besoin d’une ressource détenue par B, alors
que le processus B est arrêté car il a besoin d’une ressource détenue par A.

p1 p2 p3 p4

t1 t2
Modélisation Propriétés des réseaux de Petri

3- Interblocage

M0(p1)=1 p1 p2
M0(p2)=1
M0(p9)=2 t1 p9
M0(_)=0 t2
p3
p4
t3
t4
<t1,t2,t3,t4>
p5 p6
2 2
Mn(p5)=1 t5 t6
Mn(p6)=1
Mn(_) = 0 p7 t7 t8
p8

Interblocage!!
Modélisation Propriétés des réseaux de Petri

4- Vivacité (exemple)

p1 un jeton de R est
si
t1 p2 t3
consommé par t2 et
l’autre immédiatement
p1 p3 après
t1 par t6
alors t3 et t7 ne
p2
peuvent plus être
t2 t4
franchies faute de
t2jeton restant dans R.
Rien ne peut plus
évoluer.

Réseau de petri risquant l’interblocage

Modélisation Propriétés des réseaux de Petri

4- Vivacité (exemple)

p1
t1 p2 t3 Réseau de pétri vivant,
c’est à dire sans
p1 possibilité
p3 t1
d’interblocage
p2car les 2 jetons de R
t2 t4 sont consommés et
t2
rendus simultanément.

Réseau de petri vivant

Modélisation Réseaux de Petri, Bilan

Bonnes propriétés des RP

▪ K- borné : Un RdP est k-borné si le marquage de chaque place est

toujours inférieur ou égal à k, quelle que soit la séquence de
franchissement réalisée.
▪ Vivant : Un RdP est vivant si pour toute transition et pour tout marquage
accessible, il existe une séquence de franchissement permettant de
franchir cette transition.
N.B. Un RP vivant ne peut pas se retrouver en situation d’interblocage.

Avantages des RP

▪ Bien adapté pour la modélisation de systèmes concurrents et/ou temps-réel.

▪ Possibilités intéressantes de vérification et d’évaluation des performances.
▪ Outils CASE pour développer, analyser et vérifier les modèle de RP.
Modélisation Réseaux de Petri, Bilan

Inconvénients
▪ Complexité
▪ Lacunes: la version « classique» des RdP ne permet pas :
▪ de distinguer les données d’une place selon les valeurs de leurs attributs,
▪ de prendre en compte les contraintes temporelles,
▪ d’offrir une représentation à différents niveaux d’abstraction.

Modèles étendus des RdP

Il existe des modèles avancés de RdP permettant d’étendre leur expressivité :

▪RdP avec politique d’ordonnancement :

possibilité d’attacher des priorités aux transitions permettant de déterminer quelle transition
tirée parmi toutes celles franchissables.

▪RdP colorés : affectation de valeurs aux jetons.

▪RdP temporisés : ajout de contraintes temporelles au niveau des transitions.

Modélisation Exemple

Producteur-Consommateur
Un exemple concret (et simple!) de réseau de Petri.

Objectif : Modéliser la coordination entre deux processus dont un est le

producteur et l’autre le consommateur d’une ressource avec un
tampon à deux places, la modélisation :

▪ Le producteur produit un objet (item) et le dépose dans un tampon,

▪ Le consommateur prend l’objet du tampon et le « consomme ».
▪ Contrainte: avant que le consommateur ne puisse exécuter l’action
« consommer », le producteur doit avoir fini l’action « produire ».

Producteur : Consommateur :
• produit • retire
• dépose • consomme
Modélisation Exemple

Producteur-Consommateur

Prêt-à-produire Prêt-à-prendre
bac

produit dépose prend consomme

Prêt-à-déposer Prêt-à-consommer
Modélisation Exemple
Producteur-Consommateur

Prêt-à-prendre
bac

produit dépose prend consomme

Prêt-à-consommer