Université de Tunis El Manar

Faculté des Sciences de Tunis

Département des Sciences de l’informatique

Modélisation des protocoles de

communication par les réseaux de Pétri
(chapitre 4)

P R ÉS ENTÉ : D R . H I C HE M M R AB ET
S EC T I ON I C E 4
A .U 2 0 2 5 /20 2 6

PLAN
Introduction (concurrence ou parallélisme, synchronisation,
gestion de ressources)
Familles des RdPs (RdP PT, RdP Temps continu, RDP
stochastique)
RdP Places-Transitions (place, transition et jeton)
Concepts et définitions
Matrice d’incidence (C(p,t) = Post(p,t) – Pré(p,t))
Équation fondamentale du franchissement
Graphe de marquage (comportement du système, vivant, borné,
etc.)
Protocoles de communication (synchronisation par rendez-vous
(transition partagée), par envoi de signal (place partagée) et par
appel-réponse)
COURS MODÉLISATION DES PROTOCOLES PAR RDP 2

1
 Introduction
Les Réseaux de Pétri (RdP) Créés par Carl Adam Pétri en
1962 afin de modéliser la composition et la communication
entre automates.
Le 1er modèle, appelé RdP CE (conditions-événements)
reposait sur l’utilisation des valeurs booléennes, vrai et
faux.
Les RdP PT (places-transitions) généralisent les RdP CE en
manipulant des valeurs entières.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 3

Introduction
Les RdP modélisent efficacement les aspects concurrents,
synchrones et asynchrones des protocoles de
communication grâce à leur représentation graphique des
états (places), événements (transitions) et flux de jetons.
Les états du protocole (idle, wait_ACK, transmitting) se
représentent par des places contenant des jetons, tandis
que les événements (envoi trame, réception ACK, timeout)
sont des transitions activées par des conditions (arcs
inhibiteurs pour timeouts).
Parfait pour MAC layers (CSMA/CD, TDMA) et couches
transport (TCP states).

COURS MODÉLISATION DES PROTOCOLES PAR RDP 4

2
 Introduction
RdP permet aussi la gestion des ressources :

1. Buffers finis : Places à capacité limitée (bornes sur

places).
2. Canaux : Places colorées avec types de trames
(données/ACK/NAK).
3. Sémaphores : Places pour accès exclusif aux ressources
partagées (MAC layer).

COURS MODÉLISATION DES PROTOCOLES PAR RDP 5

Exemple 1
(sauvegardé en format GIF avec JARP)

Éléments de vocabulaire : les jetons, le marquage, les places, les

transitions, le tir ou le franchissement d’une transition, transition
tirable ou franchissable.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 6

3
 Les familles de RdP

COURS MODÉLISATION DES PROTOCOLES PAR RDP 7

Les familles de RdP

Trois grandes familles (qui ne sont évidemment pas étanches) peuvent se
distinguer.
Elles correspondent à trois domaines sémantiques :
1. La sémantique discrète (RdP PT et ses dérivés) pour les comportements qui
peuvent se représenter par des graphes finis ou dénombrables d’états;
2. La sémantique continue (RdP T et ses dérivés) pour les comportements qui
nécessitent la prise en considération explicite d’un temps dense;
3. La sémantique stochastique (RdP S et ses dérivés) pour les comportements
qui incluent des distributions de franchissement et conduisent à des
processus stochastiques (chaînes de Markov, etc.).

COURS MODÉLISATION DES PROTOCOLES PAR RDP 8

4
 Quelques outils de base pour
manipuler des RdP
Disponibles sur le site « Petri Nets World »:
◊ JARP : éditeur graphique, simulation, sauvegarde en GIF, JPEG, etc. Plate-
forme Java.
◊ RENEW : éditeur graphique, simulation, sauvegarde EPS, PS, XML. Plate-
forme Java.
◊ PetriNet Kernel (PNK) : éditeur graphique (très peu intuitive), simulation.
Plate-forme Java.
◊ INA : PAS d’éditeur graphique, analyses poussées. Plate-forme Windows.
◊ SIMPRES : éditeur graphique, simulation. Plate-forme Java.
◊ Danamics : éditeur graphique, simulation, analyses simples. Plate-forme
Java.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 9

Automates et machines à états

Rappel : Les modèles fondés sur les automates et les machines à états
reposent sur trois hypothèses.
Hypothèse 1
Il existe, dans le système modélisé, une notion d’état global, un ensemble
de ces états et une représentation explicite de ces états.
Hypothèse 2
Le fonctionnement (ou le comportement) du système modélisé peut se
décrire par des règles permettant de passer d’un état global de départ
(donné) à un autre état global d’arrivée (donné).
La transition s’effectue quand survient un événement conditionnant
l’évolution du système.
À partir de ces deux hypothèses, la description du système est définie par
un graphe global qui représente le fonctionnement du système.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 10

5
 Automates et machines à états
Hypothèse 3
C’est l’hypothèse de l’indivisibilité des transitions entre états. Lorsqu’un
événement survient, celui-ci doit être totalement terminé avant l’arrivée
d’un autre événement.
Implication de cette hypothèse sur la signification des modèles : Quand des
actions complexes sont associées aux transitions, elles doivent être
exécutées complètement avant d’atteindre l’état suivant.
En conséquence, il n’existe que deux états globaux, l’un avant, l’autre après.
On ne peut pas dire : je franchis partiellement la transition X.
Conséquence sur le travail de modélisation : Les transitions modélisées
doivent aussi être effectivement indivisibles dans le système considéré. Si
certaines instructions peuvent être interrompues, la modélisation doit en
tenir compte.
Ces trois hypothèses tiennent encore dans la modélisation par RdP.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 11

Des machines à états aux RdP

Un réseau de Pétri est un modèle défini par :
◊ un ensemble de places, notées graphiquement par des
cercles;
◊ un ensemble de transitions, notées graphiquement par des
barres ou des rectangles;
◊ un ensemble d’arcs, notés par des flèches qui joignent les
places aux transitions et les transitions aux places;
◊ une distribution de jetons dans les places.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 12

6
 Exemple 2
Conséquence de la notion de transition : La
transition permet ainsi de composer des machines
à états.
Conséquence de la notion de marquage : Le
système ne sera plus modélisé par la considération
d’un état global mais par celle d’un ensemble de
sous-états (places) spécifiques (liés aux jetons).
L’ensemble des places marquées constituera l’état
du RdP complet.
Conséquence de la notion de jeton : Une place
peut représenter la consommation de « n »
ressources ou, à l’inverse, la production de « n »
ressources.
COURS MODÉLISATION DES PROTOCOLES PAR RDP 13

Concepts et définitions
Définition 1
Un réseau de Pétri Places-transitions R se définit comme un
uplet : (P, T, Pré, Post) où :
1. P est l’ensemble des places;
2. T est l’ensemble des transitions;
3. Pré = P x T  N (ensemble des entiers), une application
d’incidence avant où Pré(p, t) contient la valeur entière « n
» associée à l’arc allant de « p » à « t ».
4. Post = P x T  N, une application d’incidence arrière où
Post(p, t) contient la valeur entière « n » associée à l’arc
allant de « t » à « p ».
COURS MODÉLISATION DES PROTOCOLES PAR RDP 14

7
 Concepts et définitions
À propos des places :
◊ « p » est une place d’entrée de la transition « t » si Pré(p, t) > 0
◊ « p » est une place de sortie de la transition « t » si Post(p, t)>0
Représentation matricielle
Il est facile de construire une représentation matricielle d’un RdP PT.
On construit la matrice correspondant à Pré et celle correspondant à Post.
 Les lignes identifient les places et les colonnes, les transitions. Une intersection
(i,j), dans Pré, correspond au coût associé à l’arc menant de la place « i » à la
transition « j », tandis qu’une intersection (i,j), dans Post, correspond au coût
associé à l’arc menant de la transition « j » à la place « i ».

COURS MODÉLISATION DES PROTOCOLES PAR RDP 15

Exemple 3

Ce cette manière, il est facile d’aller chercher, tout ce qui sort d’une place (cas 1),
tout ce qui entre dans une place (cas 2), tout ce qui entre dans une transition (cas
3) et tout ce qui sort d’une transition (cas 4).

COURS MODÉLISATION DES PROTOCOLES PAR RDP 16

8
 Définition 2
Le marquage d’un RdP est une application M :P  N
donnant pour chaque place le nombre de jetons qu’elle
contient.
Le marquage initial sera noté mo et M(p) indique le
marquage de la place « p ».

COURS MODÉLISATION DES PROTOCOLES PAR RDP 17

Définition 3
Le fonctionnement d’un RdP se définit comme suit.
 Pour un marquage «M», une transition « t » est dite tirable (ou franchissable
ou sensibilisée) SSI
 pi ∈ P, on a M(pi)  Pré(pi, t)
C’est-à-dire, pour toutes les places «pi », entrées de « t», le nombre de
jetons dans « pi », M(pi), est supérieur ou égal au poids de l’arc allant de « pi »
à « t ».
Quelques notations supplémentaires :
◊ Le fait que «t» est tirable depuis « M » se notera : M[t〉
◊ Le tir de «t» depuis « M » donnant le nouveau marquage « M’ » se notera :

M[t〉M’

COURS MODÉLISATION DES PROTOCOLES PAR RDP 18

9
 Définition 4
Dans un RdP PT, toute transition tirable « t » peut être tirée et son tir
conduit à un nouveau marquage M’ définit par :
p ∈ P, M’(p) = M(p) – Pré(p, t) + Post(p, t)
Exemple d’un tir grâce à un calcul matriciel sur le réseau de l’exemple 3
On veut tirer t1, le nouveau marquage sera :

COURS MODÉLISATION DES PROTOCOLES PAR RDP 19

Ce qui donne graphiquement :

COURS MODÉLISATION DES PROTOCOLES PAR RDP 20

10
 Définition 4
La définition 4 permet d’exprimer la synchronisation de
base dans les systèmes :
◊ la causalité (un événement « t » précède toujours un autre
événement « t’ ») et le parallélisme;
◊ l’attente (par le manque de jetons);
◊ l’accroissement et la diminution du parallélisme et/ou des
ressources;
◊ le non-déterminisme;
◊ les conflits.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 21

Définition 4
On remarquera facilement que la section «Post–Pré» de
l’équation de la définition 4 peut se simplifier en
considérant la matrice d’incidence, C, du réseau construite
en calculant d’abord la matrice correspondant à la section
encadrée :
M’ = M + Post(p,t) – Pré(p, t)
Nous avons d’ailleurs illustré comment, à partir d’un calcul
matriciel, on peut facilement déduire le nouveau marquage
« M’ ».

COURS MODÉLISATION DES PROTOCOLES PAR RDP 22

11
 Définition 5
La matrice d’incidence d’un réseau, notée C, est définie par :
 p ∈ P, A t ∈ T, C(p,t) = Post(p,t) – Pré(p,t)
Grâce à cette définition, on peut exprimer le calcul d’un
nouveau marquage « M’ », à partir d’un marquage « M »,
s’obtient, suite au tir de la transition « t », en calculant, pour
toute place « p » du réseau :
M’ = M + C(p,t)

COURS MODÉLISATION DES PROTOCOLES PAR RDP 23

Suite de notre exemple

L’exemple du tir de la transition « t » peut donc s’exprimer
avec la matrice d’incidence C :

COURS MODÉLISATION DES PROTOCOLES PAR RDP 24

12
 Définition 6 : Équation fondamentale
du franchissement
Ainsi, étant donnée une situation où :
M[t1〉M1, M1[t2〉M2, …, Mn[tn〉M’
alors on obtient l’équation fondamentale du franchissement :

où s est le vecteur caractéristique de la séquence de transitions :

s = t1 t2 … tn
tel que s(t) donne le nombre d’occurrences de la transition « t »
dans « s ». On note :
M[s〉M’

COURS MODÉLISATION DES PROTOCOLES PAR RDP 25

Définition 6 : Équation fondamentale

du franchissement
Ainsi, on peut facilement calculer le nouveau marquage induit par
le franchissement de la séquence t1t2t3 dans le réseau précédent.
On obtiendrait :

 Ou encore, si vous avez besoin d’un autre exemple, le nouveau

marquage induit par le franchissement de la séquence t1t2t3t1 :

COURS MODÉLISATION DES PROTOCOLES PAR RDP 26

13
 Graphe d’accessibilité ou graphe de
marquage
Définition 7
L’ensemble des marquages accessibles A(R,mo) se définit
par le plus petit ensemble :
mo ∈ A et si M ∈ A et M–tM’ alors M’ ∈ A.
L’ensemble A définit l’ensemble des marquages accessibles
par un ensemble de vecteurs qui indiquent le nombre de
jetons dans chaque place.
Exemple : le marquage actuel de l’exemple 3 après le tir de
« t1 » est le vecteur : [5, 10].

COURS MODÉLISATION DES PROTOCOLES PAR RDP 27

Définition 8
Le graphe des marquages accessibles G(R, mo) est défini
comme le graphe dont les nœuds sont les marquages
accessibles de A(R, mo) et dont les arcs sont les noms des
transitions impliquées dans les tirs menant d’un marquage à
un autre.
Le graphe des marquages permet de déterminer le
comportement du système modélisé par RdP:
1. Borné et vivant,
2. Non borné et vivant,
3. Borné et bloquant

COURS MODÉLISATION DES PROTOCOLES PAR RDP 28

14
 Exemple 4

COURS MODÉLISATION DES PROTOCOLES PAR RDP 29

Le graphe d’accessibilité de ce
réseau est :

COURS MODÉLISATION DES PROTOCOLES PAR RDP 30

15
 Exemple 4 (suite)
On peut également utiliser une autre notation.
Notons i(avec flèche) pour indiquer que la place « i » est marquée par un
jeton et ni (avec flèche) , si la place « i » est marquée de « n » jetons.
Alors le graphe précédent peut s’exprimer comme suit :

COURS MODÉLISATION DES PROTOCOLES PAR RDP 31

Exemple 5

Évidemment, un graphe de marquage peut être infini.

Il est facile de voir ce fait en examinant la place « p2 » qui ne fait
que recevoir des jetons.
COURS MODÉLISATION DES PROTOCOLES PAR RDP 32

16
 Exemple 6

COURS MODÉLISATION DES PROTOCOLES PAR RDP 33

Le graphe d’accessibilité est encore une

fois infini. En voici une partie :

COURS MODÉLISATION DES PROTOCOLES PAR RDP 34

17
 Exemple 7

COURS MODÉLISATION DES PROTOCOLES PAR RDP 35

Graphe de marquage

COURS MODÉLISATION DES PROTOCOLES PAR RDP 36

18
 Vérification des RdPs par aspects de
protocoles

Aspect protocole Modélisation Pétri Vérification

Contrôle d'accès Concurrence stations Équité, vivacité
Automatic Repeat Request États
Absence deadlock
(ARQ) protocols récepteur/émetteur
Sliding Window Fenêtres dynamiques Bornes buffers
Handshake Synchronisation Correctness

COURS MODÉLISATION DES PROTOCOLES PAR RDP 37

Concurrence et synchronisation
Quelques exemple qui permet la concurrence et
synchronisation des protocole de communication :
1. Sélection de trames : Places multiples pour buffers
d'envoi, transitions concurrentes pour priorités.
2. Handshakes : Synchronisation émetteur/récepteur via
jetons partagés (rendez-vous).
3. ARQ/Sliding Window : Places pour fenêtres
émetteur/récepteur, transitions pour avance/recul
fenêtre.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 38

19
 Schémas de synchronisation
élémentaire
Concurrence ou parallélisme
Synchronisation
1. Par rendez-vous
2. Par signal (sémaphore)
3. Par appel-réponse
4. Mémorisation
5. Exclusion mutuelle
6. Lecteurs/écrivains
7. Tampon borné de N espaces

COURS MODÉLISATION DES PROTOCOLES PAR RDP 39

Concurrence ou parallélisme

COURS MODÉLISATION DES PROTOCOLES PAR RDP 40

20
 A. Synchronisation par Rendez-vous

COURS MODÉLISATION DES PROTOCOLES PAR RDP 41

B. Synchronisation par signal

(sémaphore)
 Si la place «signal» est marquée
et la place «attente» ne l’est
pas, cela signifie que le
processus P1 a envoyé le signal
mais le processus P2 ne l’a pas
encore reçu.
 Si, par contre, la place «signal»
n’est pas marquée et que la
place «attente» est marquée,
cela signifie que le processus P2
est en attente du signal.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 42

21
 C. Synchronisation par appel-
réponse
 Une variante du modèle
précédent qui consiste à faire
un signal d’appel provenant du
processus P1 et un signal de
réponse provenant du
processus P2.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 43

D. Mémorisation
 Dans tous les modèles, on peut compter le nombre de tirs
d’une transition en utilisant une place sans sortie.
 Évidemment, dans le cas des modèles B et C, les places
«attente» peuvent servir à indiquer combien d’instances
d’un processus sont en attente.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 44

22
 E. Exclusion mutuelle

La section critique de
l’un ou l’autre des deux
processus est exécutée
de manière exclusive
grâce à la place «
verrou ».

COURS MODÉLISATION DES PROTOCOLES PAR RDP 45

F. Lecteurs/écrivains
Il s’agit d’une variante du «verrou
».
Ici on désire M écrivains et N
lecteurs.
Les écrivains ne peuvent pas
écrire en même temps (donc sont
en exclusion mutuelle).
Les écrivains et les lecteurs ne
peuvent écrire et lire en même
temps (donc sont en exclusion
mutuelle).
Cependant, les lecteurs peuvent
lire en parallèle. Voici le modèle
simple de ce système.
COURS MODÉLISATION DES PROTOCOLES PAR RDP 46

23
 G. Tampon borné de N espaces

 Une variante du modèle

précédent.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 47

Protocoles de communication
1. Modèles de base
Prenons deux processus, P1 et P2 qui s’échange un
message M.
La notation !M indique l’envoie du message et ?M, la
réception du message.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 48

24
 Protocoles de communication

Il existe, d’après nos modèles précédents, trois manières

de modéliser le système : par rendez-vous (fusion), par
envoi de signal (place partagée) et par appel-réponse:
1. Solution A : fusion ou rendez-vous (solution
symétrique)
2. Solution B : envoi de signal ou place partagée (solution
asymétrique)
3. Solution C : appel-réponse (solution asymétrique)

COURS MODÉLISATION DES PROTOCOLES PAR RDP 49

Solution A : fusion ou rendez-vous

(solution symétrique)

Notons que lors de la synchronisation des deux processus, un

passage de valeurs peut avoir lieu mais n’est pas représenté par
ce modèle.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 50

25
 Solution B : envoi de signal ou place
partagée (solution asymétrique)
Le marquage de la place M indique que le message a été envoyé
mais non encore reçu.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 51

Solution C : appel-réponse
(solution asymétrique)
Ce modèle ajoute et explicite le fait que l’émetteur attend une
réponse avant de poursuivre son activité.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 52

26
[Link] simple d’une connexion
Le processus P1 peut ouvrir une connexion par envoi du message
A1 et le processus P2 peut également ouvrir une connexion par
envoi du message A2.
Mais seul le processus P1 possède le droit de fermer la connexion
ouverte par envoi du message B.
Voici les deux processus :

COURS MODÉLISATION DES PROTOCOLES PAR RDP 53

Solution A: rendez-vous

COURS MODÉLISATION DES PROTOCOLES PAR RDP 54

27
 Solution A: rendez-vous
La graphe d’accessibilité est normale.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 55

Solution B: envoi du signal

COURS MODÉLISATION DES PROTOCOLES PAR RDP 56

28
 Solution B: envoi du signal

La section de graphe d’accessibilité ci-dessous exprime le fait que

les places A1 et B peuvent recevoir un nombre arbitrairement élevé
de jetons.
Ce comportement est susceptible d’entraîner un dépassement des
ressources.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 57

Solution C: appel-réponse

COURS MODÉLISATION DES PROTOCOLES PAR RDP 58

29
 Solution C: appel-réponse
La section de graphe d’accessibilité ci-dessous exprime un
comportement qui amène un blocage.
En effet, les tirs, dans un ordre quelconque de !A1 et !A2,
conduisent au marquage des places AT1, A1, AT2 et A2.
Dans cet état, aucune transition n’est tirable.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 59

Synthèse
Le tableau suivant résume les trois comportements distincts des
modèles présentés.

COURS MODÉLISATION DES PROTOCOLES PAR RDP 60

30
 Références
Diaz, Michel (2001) Les Réseaux de Petri – Modèles fondamentaux,
Hermes Science Publications : Paris.
Peterson, J. L. (1977) « Petri Nets », Computing Surveys, vol. 9, N° 3,
pp 223-252.
[Link]

COURS MODÉLISATION DES PROTOCOLES PAR RDP 61

31