Les réseaux de pétri, apparut dans la thèse de Carl Adam Pétri en 1962 est un modèle mathématique servant à représenter divers systèmes électroniques de façon dynamique.
Le réseau de Pétri se base sur les diagrammes UML.
Le réseau de pétri est un 5-uplet (collection ordonnée d’objets) : PN = (P, T, F, Pre, Post)∪M0.
Les transitions sont l’ensemble des d’instructions à exécuter comme s’il n’y avait qu’un processus. Les transitions représentent aussi les sections critique ou point de synchronisation.
Les transitions sont les actions qui font changer le système d’état. Les places amont sont les conditions préalables à la réalisation de l’action.
Il existe deux types de transitions:
Transition source : C’est une transition sans place amont. Par construction, elle est toujours validée.
Transition puit : C’est une transition sans place aval. Par construction, elle ne produit aucun jeton.
Les transitions ordonnées : L’ensemble des transitions est muni d’une relation d’ordre : si plusieurs transitions sont valid́ées, c’est la plus petite qui est tirée.
Ce sont les ressources nécessaires pour valider la transition. Les places ou jetons sont produits (ou libérées) en franchissant la transition.
Réseaux de Petri non autonomes: A chaque transition est associé un événement ou le temps. La transition n’est tirable que si elle est validée et que si la condition est réalisée.
Transition validé : Une transition est validée si et seulement si l’ensemble des places amont contient au moins un jeton.
Il est interdit de tirer simultańement plusieurs transitions. Le tirage d’une transition est atomique : Il n’existe pas d’état intermédiaire dans le tirage de la transition.
Voici un état initial de réseau de pétri. On peut voir que aucune transition n’a été faite et que l’on a 3 jetons au début.
La première transition que l’on fait est celle de gauche car on a utilisé le jeton du milieu pour faire la transition de gauche et donc on n’a plus ce jeton pour faire la transition de droite qui doit donc attendre :
Pour faire une transition, on a besoin de autant de jeton que l’on a de flèche pointé sur la transition que l’on souhaite faire.
Ici on peut voir que la dernière transition dans la partie gauche a été faite car on avait un jeton et une flèche vers la transition donc c’était possible.
L’étape que l’on voit sur la gauche les deux jetons ont pu remonter pour que l’on puisse s’occuper de la partie droite.
Comme on a vue dans l’étape précédente, les deux jetons sont de nouveaux disponible.
On peut donc faire la transition à droite :
Ici on peut voir que la dernière étape a été faite : il y avait un seule jeton et une flèche.
Une fois cette transition effectuée, les deux jetons peuvent revenir et on revient à l’état initial :
Il existe différente façon de faire un schéma en réseau de pétri. On va voir les différentes variantes juste en dessous :
Sur certain schéma de réseau de pétri, les flèches entre les transitions sont regroupé en une seule avec un numéro à côté.
Le numéro corresponds au nombre de flèche et donc au nombre de jeton dont vous aurez besoin pour faire la transisiton.
On ajoute un ensemble de capacités sur les places de sorte que les transitions amont soient invalidées si le nombre de jetons dans la place est suffisant.
Dans un réseau de pétri, la couleur indique la place et la transition d’origine.
L’arc inhibiteur permet de valider une transition que lorsque la place est vide. Il sera dit aussi test à zéro.
On dit qu’un réseau de Petri est mort ou bloqué si plus aucune transition n’est validée. Un des intérêts des RdP est de pouvoir détecter l’existence de ces possibilités de comportements.
On va voir un exemple :
Deux personnes, Bob et Dylan, ont besoin d’une perceuse et de forêt pour percer un trou.
Comme on peut le voir sur le réseau de pétri à droite, Bob empreinte la perceuse en même temps que Dylan prends les forêts.
C’est une situation bloquante car chaqu’un à l’outils dont l’autre a besoin : Bob a besoin des forêts que Dylan a emprunté et inversement pour Dylan qui a besoin de la perceuse.
Conclusion : On a un réseau de pétri mort car plus aucune transition peut être faite.
Une des solutions pour éviter ce soucis est que les ressources doivent être prise dans le même sens pour Bob et Dylan. Ceci aurait permit que Dylan ne prenne pas les forêts car il aurait été bloqué du fait que Bob ai prit la perceuse. Dylan aurait donc attendu que Bob finisse d’utiliser la perceuse avant de prendre la perceuse puis forêt. Le fait de ne pas prendre la ressource quand un autre pourrait en avoir besoin s’appelle le sémaphore.
Les sémaphores gère un nombre de ressources disponibles. Ceci permet de gérer des mises en attente et les réveils correspondants.
Les deux actions possible d’un sémaphore sont :
∗ P : tenter d’occuper une ressource ou attendre
∗ V : libérer une ressource et la réveiller
Les contraintes des sémaphores c’est de ne pas occuper plus de ressources qu’il n’y en a au départ, d’attendre que s’il n’y a pas de ressources disponibles et de finir les instructions dans le temps impartie.