Réseaux de

Petri

Réseaux de Petri
1 Introduction

2 Définition

3 Fonctionnement d’un réseau

4 Séquence de franchissement
Présentation

Un réseau de Petri
est un modèle mathématique permettant la représentation
de systèmes distribués discrets (informatique, industriel),
introduit par Petri (1962).
est également un langage de modélisation, représenté sous
forme d’un graphe biparti orienté.

Étude des systèmes discrets dont les champs d’application sont

les systèmes de production (caractérisés par une variation
imprévisible des besoins).
Présentation

Système à Événements Discrets (SED), caractérisés par :

des contraintes de précédence (dans les gammes de
fabrication ou dans les algorithmes) ;
des effets de concurrence induits par le partage des
ressources ;
une structuration en tâches parallèles, asynchrones,
soumises à des contraintes temporelles strictes ou non.
Présentation

Systèmes complexes et couteux à mettre en œuvre :

valider les spécification ;
prévoir les performances ;
optimiser le fonctionnement (théorie des files d’attentes,
simulation, etc.).

Deux principaux types de représentation permettent d’aborder

les réseaux de Petri :
une représentation graphique sous forme de graphe,
permettant de capturer la dynamique du système ;
une représentation algébrique linéaire.
Présentation informelle

Un réseau de Petri est un graphe biparti dont on

particularise les deux familles de sommets : les places et
les transitions.
Comme dans tout graphe biparti, un arc ne relie jamais
deux sommets de la même famille.
Les places sont représentées par des cercles, tandis que les
transitions sont représentrées par des traits ou des
rectangles.

Correct Incorrect
Dynamique du système

Chaque place va contenir un nombre entier de jetons (ou

marques) pour modéliser la dynamique du système.

•• 2 jetons 25 25 jetons

Le marquage du réseau est constitué de toutes les marques

présentées dans le réseau à un instant donné.

Un réseau de Petri généralisé est un réseau dans lequel les

valuations des arcs ne sont pas forcément égales à 1. Un réseau
de Petri ordinaire est un réseau dont le graphe sous-jacent est
un 1-graphe.
Notation

On note souvent :
T l’ensemble des transitions ;
P l’ensemble des places ;
v la fonction de valuation des arcs ;
M(p) le marquage de la place p (i.e. le nombre de jetons
contenus dans p à un instant donné).
Exemple t1

•• p2

• p1

t2

3 • p4 p3

2 2

t4 t3
Tir de t2 t1

• p2

• p1

t2

3 •• p4 • p3

2 2

t4 t3
Tir de t4 t1

4 p2

• p1

t2

3 p4 • p3

2 2

t4 t3
Exemple t1

P = {p1 , p2 , p3 , p4 } 2
T = {t1 , t2 , t3 , t4 }
•• p2
v (t1 , p2 ) = 2, v (p2 , t2 ) = 1,
v (t4 , p2 ) = 3
M(p1 ) = 1, M(p2 ) = 2, • p1
M(p3 ) = 0, M(p
 4) = 1 ;
1
 2  t2
M0 =   0 


1
Γ−1 (t2 ) = {p2 },
Γ(t2 ) = {p3 , p4 }

3 • p4 p3

2 2

t4 t3
Transition validée

Chaque place de Γ−1 (t2 ) contient plus de jetons que la

valuation de l’arc la reliant à t2 .

M(p2 ) ≥ v (p2 , t2 )
On dit que t2 est franchissable (tirable, validée). Si l’on tire
t2 , le marquage des places de Γ−1 (t2 ) et de Γ(t2 ) va être
modifié :
M(p2 ) ← M(p2 ) − v (p2 , t2 )
M(p3 ) ← M(p3 ) + v (t2 , p3 )
M(p4 ) ← M(p4 ) + v (t2 , p4 )
On note M0 [t2 > M1 : M0 valide la transition t2 , et le tir de t2
depuis M0 donne le marquage M1 .
Réseau de Petri généralisé

Def : Réseau de Petri généralisé

Un réseau de Petri généralisé est un quadruplet R tel que
R = (P, T , Pre, Post) avec :
P : ensemble des places du réseau ;
T : ensemble des transitions du réseau ;
Pre : application d’incidence avant, de P × T dans N.
∀p ∈ P, ∀t ∈ T , Pre(p, t) = v (p, t) si (p, t) ∈ G , 0 sinon.
Post : application d’incidence arrière, de P × T dans N.
∀p ∈ P, ∀t ∈ T , Post(p, t) = v (t, p) si (t, p) ∈ G , 0
sinon.
À chaque application d’incidence est associée une matrice
|P| × |T |.
Exemple t1

•• p2

• p1

t2 T1 T2 T3 T4
0 P1
 
1 0 0
P2
 0 1 0 0 
Pre = 
 0 0 2 0 
0 0 0 2 P3
P4
3 • p4 p3 
0 0 1 0

 2 0 0 3 
Post = 
 0

1 0 0 
0 1 0 0
2 2
les chiffres mis dans les
matrices sont les poids de
t4 t3 valuation
Exemple

P = {p1 , p2 , p3 , p4 }
p1 T = {t1 , t2 }
2 
2 0

 0 1 
t1 Pre =  
 0 1 
0 0
 
p2 p3 0 0
 1 0 
Post = 
 1 0 


0 2
t2  
−2 0
2  1 −1 
C =  1 −1 

p4
0 2
C = POST - PRE
Matrice d’incidence

Def : Matrice d’incidence

La matrice d’incidence du réseau est C = Post − Pre.

Def : Réseau pur

Un réseau de Petri R = (P, T , Pre, Post) est pur lorsque
∀p ∈ P, ∀t ∈ T , Pre(p, t) × Post(p, t) = 0 (membre à
membre).

Def : Réseau marqué

Un réseau marqué N est un couple (R, M) constitué d’un
réseau de Petri R et d’une application de marquage définie sur
P et à valeurs dans N (i.e. le marquage du réseau à un instant
donné).
Franchissement

Def : Tir d’une transition

Une transition t est tirable (ou franchissable, ou validée)
lorsque :
∀p ∈ Γ−1 (t) M(p) ≥ Pre(p, t)
Lorsqu’une transition est validée dans le marquage M0 , on note
M0 [t >.
Évolution du marquage

Def : Évolution du marquage

Soit N = (R, M) un réseau de Petri marqué de transitions T
et de places P. Le franchissement d’une transition t de T
validée dans le marquage M conduit au marquage M1 :

∀p ∈ P, ∀t ∈ T , M1 (p) = M(p) + C (p, t)

∀p ∈ P, ∀t ∈ T , M1 (p) = M(p) + Post(p, t) − Pre(p, t)
On note alors M[t > M1 .
Séquence

On s’intéresse à l’évolution du réseau lors du tir successif

de plusieurs transitions.
Lorsque M[t1 > M1 [t2 > M2 , on dit que la séquence de
transitions t1 t2 est franchissable depuis le marquage M.
On note M[t1 t2 > M2 .

Def : Séquence de franchissement

Une séquence de franchissement est un mot construit sur
l’alphabet T ∗ des transitions de T . On note σ une séquence de
franchissements.

Exemple
σ = t1 t2 et M[σ > M2 .
Séquence

Pour caractériser une séquence de franchissements σ, on utilise

son image commutative ~σ .
Exemple
 
1
σ = t1 t2 ; T = {t1 , t2 , t3 } ; ~σ =  1 
0
Séquence

Chaque composante de l’image commutative est le nombre

d’occurrences de la transition correspondante dans σ.
Exemple
 
1
 1 
σ~1 =   : σ1 = t1 t2 t3 ou σ1 = t3 t1 t2 ...
 1 
0
 
2
σ~2 =  3  : σ2 = t1 t2 t2 t1 t2 ou σ2 = t2 t2 t2 t1 t1 ...
0
Équation d’état

Théorème : Équation d’état

Soit σ une séquence finie de transitions tirable depuis un
marquage M d’un réseau R de matrice d’incidence C . On a :

M[σ > M1 ⇒ M1 = M + C~σ

Remarque 1
Il s’agit d’une condition nécessaire mais pas suffisante : il se
pourrait que σ ne soit pas franchissable depuis M !

Remarque 2
Deux étapes pour calculer un marquage :
démontrer que le marquage valide la séquence ;
calculer le marquage résultat.
Exercice

La séquence t1 t2 t1 est
p1 franchissable dans le réseau
marquéN =(R, M0 ) avec
2
4
t1  0 
M0 =   0 .


0
p2 p3
1 Exprimer ~σ .
2 On a M0 [σ > M. Calculer
t2 M.

2
p4
Transition source et transition puits

Def : Transition source

Une transition source ts d’un réseau de Petri (R, M0 ) est une
transition de T telle que Γ−1 (ts ) = ∅.

Def : Transition puits

Une transition puits tp d’un réseau de Petri (R, M0 ) est une
transition de T telle que Γ(tp ) = ∅.

Proposition : Validation d’une transition source

Une transition source est toujours validée.

Remarque
Les transitions source et puits permettent de modéliser des flux
continus.
Lancement de tâches en parallèle

p1

t1

p2 p3 p4

t2 t3 t4

p5 p6 p7

t5

p8
Communication asynchrone

Soient deux tâches τ1 et τ2 qui communiquent par messages.

τ1 émet un message en le plaçant dans un tampon de
communication tandis que τ2 est réceptrice, et est bloquée tant
qu’elle n’a pas reçu le message.
τ1 τ2
• p1 • p4

t1 p3 t2

p2 p5

Le nombre de jetons dans p3 correspond au nombre de

messages en attente.
Communication asynchrone

Soient deux tâches τ1 et τ2 qui communiquent par messages.

τ1 émet un message en le plaçant dans un tampon de
communication tandis que τ2 est réceptrice, et est bloquée tant
qu’elle n’a pas reçu le message.
τ1 τ2
p1 • p4

t1 • p3 t2

• p2 p5

Émission d’un message par τ1 .

Le nombre de jetons dans p3 correspond au nombre de

messages en attente.
Communication asynchrone

Soient deux tâches τ1 et τ2 qui communiquent par messages.

τ1 émet un message en le plaçant dans un tampon de
communication tandis que τ2 est réceptrice, et est bloquée tant
qu’elle n’a pas reçu le message.
τ1 τ2
p1 p4

t1 p3 t2

• p2 • p5

Réception d’un message par τ2 .

Le nombre de jetons dans p3 correspond au nombre de

messages en attente.
Section critique

Deux processus concurrents demandent l’accès à une section

critique en exclusion mutuelle. La procédure d’accès se
décompose de la manière suivante :
demander l’accès à la section critique ;
utiliser la ressource en section critique ;
libérer l’accès à la section critique.
Section critique

τ1 τ2
p1 p5 Prêt à entrer en SC

t1 t3 Gagner l’accès

p2 • p4 p6 Dans la SC

t2 t4 Libérer l’accès

p3 p7 Hors SC
Section critique

τ1 τ2
• p1 p5 Prêt à entrer en SC

t1 t3 Gagner l’accès

p2 • p4 p6 Dans la SC

t2 t4 Libérer l’accès

p3 p7 Hors SC
Section critique

τ1 τ2
p1 p5 Prêt à entrer en SC

t1 t3 Gagner l’accès

• p2 p4 p6 Dans la SC

t2 t4 Libérer l’accès

p3 p7 Hors SC
Section critique

τ1 τ2
p1 • p5 Prêt à entrer en SC

t1 t3 Gagner l’accès

• p2 p4 p6 Dans la SC

t2 t4 Libérer l’accès

p3 p7 Hors SC
Section critique

τ1 τ2
p1 • p5 Prêt à entrer en SC

t1 t3 Gagner l’accès

p2 • p4 p6 Dans la SC

t2 t4 Libérer l’accès

• p3 p7 Hors SC