Annexe · sujet d'examen

Les réseaux de Petri

Sujet de l'exercice 1 à l'examen (« pas d'exemples avant », a précisé la prof). Théorie, notation, règles de tirage, propriétés et exemples classiques.

~ 35 min Modèle formel de concurrence (Carl A. Petri, 1962) 10 flashcards · 5 QCM

🎥 Vidéos recommandées

🇫🇷 Introduction aux réseaux de Petri (Réseaux de Petri partie 1)
Informatique Théorique · 05:04 · 43k vues — Lien de la playlist sur les réseaux de Petri https://www.youtube.com/playlist?list=PLwp5OpRmcl_FqyvDqRMw9ZP3nXwrlqslB
🇫🇷 Comprendre la notion d'invariants de places (P-invariants) dans un réseau de Petri
Informatique Théorique · 08:00 · 11k vues — Vidéo sur les matrices d'incidences https://www.youtube.com/watch?v=OZ7UkwoVKToLien de la playlist sur les réseaux de Petri https://www.youtube.com/playlist
🇬🇧 Petri Net modeling and simulation program
Igor Kim · 04:29 · 18k vues — Tutorial video for very simple Petri Net simulation program. You can find it at http://petri.hp102.ru

1. Définition formelle

Réseau de Petri Un réseau de Petri est un quadruplet N = (P, T, F, M₀) où :

P = ensemble fini de places (cercles)
T = ensemble fini de transitions (rectangles ou barres)
F ⊆ (P × T) ∪ (T × P) = ensemble des arcs orientés
M₀ : P → ℕ = marquage initial (nombre de jetons dans chaque place)

Un marquage M : P → ℕ indique combien de jetons sont présents dans chaque place. L'évolution du réseau est le passage d'un marquage à un autre par tirage de transitions.

📌 Vocabulaire à connaître

Place = état possible / ressource (cercle)
Transition = événement / action (rectangle)
Arc = relation orientée place ↔ transition
Jeton = unité de marquage (point noir dans la place)
Marquage = état global du système

2. Notation graphique

Représentation visuelle standard :

Notation : places = cercles (avec jetons à l'intérieur), transitions = rectangles, arcs = flèches étiquetées (1 par défaut si non écrit).

Arcs pondérés Un arc peut avoir un poids entier ≥ 1. Si l'arc P → T a poids 3, il faut au moins 3 jetons dans P pour que T puisse tirer, et tirer en consomme 3. Par défaut, le poids est 1 et n'est pas écrit.

3. Règle de tirage

Une transition t est franchissable (ou sensibilisée) sous le marquage M ssi : Pour chaque place p en entrée de t, le nombre de jetons M(p) est au moins égal au poids de l'arc p → t.

Effet du tirage Tirer une transition t :

Consomme les jetons des places en entrée (selon les poids des arcs entrants)
Produit de nouveaux jetons dans les places en sortie (selon les poids des arcs sortants)

Le tirage est atomique : il se produit en une seule étape.

Exemple de tirage pas à pas

Tirage de T : T consomme 1 jeton dans P₁ et 1 jeton dans P₂, et produit 1 jeton dans P₃. Marquage : (2,1,0) → (1,0,1).

Notation matricielle

Soit m = |P| et n = |T|. On définit :

Pre[m × n] : matrice des arcs entrants (place → transition). Pre[p,t] = poids de l'arc p→t.
Post[m × n] : matrice des arcs sortants (transition → place). Post[p,t] = poids de l'arc t→p.
C = Post − Pre : matrice d'incidence.

Équation fondamentale Si on tire la transition t à partir de M et on obtient M' :

M' = M + C · e_t

où e_t est le vecteur unitaire correspondant à t (1 sur la colonne t, 0 ailleurs).

Plus généralement, si σ est une séquence de tirages représentée par un vecteur s (s[t] = nombre de fois où t est tirée) :

M' = M + C · s

4. Graphe des marquages atteignables

Définitions

Un marquage M' est atteignable depuis M s'il existe une séquence de tirages qui mène de M à M'.
L'ensemble d'atteignabilité R(M₀) contient tous les marquages atteignables depuis l'état initial.
Le graphe des marquages a pour nœuds les marquages atteignables et pour arcs les transitions étiquetées.

Construire le graphe des marquages permet de vérifier les propriétés (vivacité, bornitude, blocages) — c'est l'outil principal d'analyse.

Méthode de construction

Partir du marquage M₀
Pour chaque transition franchissable, calculer le marquage atteint
Si ce marquage est nouveau, l'ajouter et le traiter récursivement
Sinon, ajouter juste un arc
S'arrêter quand plus aucun nouveau marquage n'est atteint

⚠ Limite Pour un réseau borné, le graphe est fini et la méthode termine. Pour un réseau non borné, le graphe est infini — on doit utiliser le graphe de couverture (avec ω = ∞ comme marquage formel) pour analyser.

5. Propriétés à vérifier

Bornitude (boundedness) Une place p est k-bornée si pour tout marquage atteignable, M(p) ≤ k. Un réseau est borné si toutes ses places le sont. Le marquage ne peut pas exploser.

Sécurité (safety) Cas particulier : un réseau est sûr (ou 1-borné) si toutes les places ont au plus 1 jeton. Utile pour modéliser des flags booléens.

Vivacité (liveness) Une transition t est vivante si, depuis tout marquage atteignable, il existe une séquence qui la rend franchissable. Pas de blocage permanent. Un réseau est vivant si toutes ses transitions le sont.

Blocage (deadlock) Un marquage est bloqué si aucune transition n'est franchissable. Un réseau est sans blocage si aucun marquage atteignable n'est bloqué.

🎯 Vocabulaire à savoir pour l'examen

k-bornée : ∀M ∈ R(M₀), M(p) ≤ k
1-bornée / safe : M(p) ∈ {0, 1}
Vivante : aucune transition ne se bloque définitivement
Réversible : M₀ est atteignable depuis tout marquage atteignable
Persistant : si deux transitions sont franchissables, le tirage de l'une ne désensibilise pas l'autre

6. Patterns classiques à reconnaître

Séquence

Deux transitions doivent se faire l'une après l'autre. Une place entre les deux fait office de jeton de synchronisation.

Choix (conflit)

Deux transitions concurrentes partagent une place d'entrée. Le tirage de l'une désensibilise l'autre.

Synchronisation

Une transition attend que plusieurs places d'entrée aient un jeton — c'est un point de rendez-vous.

Exclusion mutuelle (sémaphore)

Une place « sémaphore » contient un jeton qui circule entre 2 sections critiques. Un seul processus peut être en section critique à la fois.

SC₁ et SC₂ sont les sections critiques. Le jeton du sémaphore central ne peut être pris que par un seul processus à la fois ⇒ exclusion mutuelle.

Producteur/Consommateur avec buffer borné

Modèle classique avec buffer de taille N. Un producteur dépose des éléments ; un consommateur les retire. Buffer plein bloque le producteur ; buffer vide bloque le consommateur.

Place buffer : nombre d'éléments dans le buffer (0 à N)
Place places_libres : initialement N jetons
Transition produire : consomme une place libre, ajoute un élément
Transition consommer : consomme un élément, libère une place

7. Stratégie pour l'examen

Méthode systématique pour résoudre un exo Petri

Identifier les composants : combien de places, de transitions, leurs noms, leurs poids
Écrire le marquage initial M₀ sous forme de vecteur
Identifier les transitions franchissables sous M₀ (toutes les places en entrée ont assez de jetons ?)
Calculer les marquages atteignables en tirant les transitions une à une — construire le graphe
Répondre aux questions sur les propriétés (bornitude, vivacité, deadlock…)

🎯 Pour analyser la bornitude
Construire le graphe des marquages atteignables. Si le graphe est fini, le réseau est borné (k = max des valeurs vues dans toutes les places).

🎯 Pour détecter un deadlock
Chercher dans le graphe un marquage où aucune transition n'est franchissable. Si un tel marquage existe et est atteignable, il y a un blocage.

🎯 Pour vérifier la vivacité
Une transition est vivante si depuis chaque marquage atteignable, il existe une séquence qui la rend franchissable. Sinon, elle peut « mourir ».

🎯 Pour l'exclusion mutuelle
Vérifier qu'aucun marquage atteignable n'a deux sections critiques avec un jeton simultanément. Souvent, regarder la place sémaphore suffit.

Erreurs fréquentes à éviter

Oublier que tous les arcs en entrée doivent être satisfaits pour qu'une transition soit franchissable (ET, pas OU).
Confondre place et transition graphiquement — les cercles tiennent les jetons, les barres ne sont que des événements.
Ne pas tenir compte des poids des arcs (par défaut 1, mais ils peuvent être plus).
Penser que tirer une transition est non-atomique — c'est en réalité instantané, tous les jetons sont consommés/produits en une étape.

★ Réviser l'annexe

Pour vérifier ta compréhension

Qu'est-ce qu'un réseau de Petri ?

Un modèle mathématique pour représenter des systèmes concurrents. Il est constitué de : places (cercles), transitions (rectangles ou barres), arcs (flèches reliant places et transitions) et marquage (jetons dans les places). Utilisé pour modéliser des protocoles, des systèmes distribués, des workflows.

Comment fonctionne le tir d'une transition ?

Une transition est franchissable si chaque place d'entrée contient au moins autant de jetons que le poids de l'arc entrant. Le tir consomme ce nombre de jetons des places d'entrée et produit autant de jetons (selon le poids des arcs sortants) dans les places de sortie.

Quelle est la différence entre un marquage atteignable et un marquage initial ?

Le marquage initial M₀ est la configuration de départ des jetons. Un marquage atteignable est un marquage qu'on peut obtenir à partir de M₀ en tirant une séquence de transitions. L'ensemble des marquages atteignables forme le graphe d'accessibilité.

Qu'est-ce qu'un réseau de Petri borné ?

Un réseau dans lequel le nombre de jetons dans chaque place est borné pour tout marquage atteignable. Si la borne est 1 pour toute place, on parle de réseau sauf ou 1-borné. Propriété importante car elle garantit un nombre fini d'états et donc une analyse algorithmique possible.

À quoi servent les réseaux de Petri dans la pratique ?

Modélisation et analyse de : protocoles de communication, workflows métier, systèmes manufacturiers, processus concurrents (interblocage, vivacité, équité). Permet de vérifier formellement des propriétés comme l'absence de deadlock ou la terminaison.

🃏 Flashcards

Définition formelle d'un réseau de Petri ?

Quadruplet N = (P, T, F, M₀) avec P places, T transitions, F arcs orientés, M₀ marquage initial.

Représentation graphique : cercle, rectangle, points ?

Cercles = places · rectangles = transitions · flèches = arcs · points dans les cercles = jetons.

Quand une transition t est-elle franchissable ?

Si toutes les places en entrée ont au moins le poids de l'arc qui les relie à t. C'est un ET, pas un OU.

Que fait le tirage d'une transition ?

① Consomme les jetons des places en entrée (selon poids des arcs entrants) · ② Produit des jetons dans les places en sortie (selon poids des arcs sortants). Atomique.

Qu'est-ce que la matrice d'incidence ?

C = Post − Pre. Pre[p,t] = poids de l'arc p→t. Post[p,t] = poids de t→p. Permet l'équation M' = M + C·e_t.

Définition de la bornitude ?

Une place est k-bornée si pour tout marquage atteignable, elle a au plus k jetons. Le réseau est borné si toutes les places le sont.

Définition de la vivacité ?

Une transition est vivante si depuis chaque marquage atteignable, il existe une séquence qui la rend franchissable. Pas de blocage permanent.

Qu'est-ce qu'un blocage (deadlock) ?

Un marquage où aucune transition n'est franchissable. Tout le système est figé.

Comment modéliser un sémaphore en Petri ?

Une place « sémaphore » avec 1 jeton. Les transitions prendre et libérer entourent la section critique. Le jeton ne peut être pris que par un seul processus à la fois.

Comment construire le graphe des marquages ?

Partir de M₀, calculer tous les marquages atteignables par tirages successifs, ne pas dupliquer les marquages déjà visités. Termine ssi le réseau est borné.

✎ Quiz éclair

1.Sur un réseau avec une place P (3 jetons) et un arc P → T de poids 2. T est-elle franchissable ?

Non, il faut exactement 2 jetons
Oui, 3 ≥ 2
Non, il faut 4 jetons
Seulement si P est sûr