Formalisme des réseaux de Pétri (RdP)

Les systèmes informatiques en général et les réseaux de grande taille en particulier sont caractérisés par un aspect structurel statique auquel sont associés des grandeurs évolutives constituant la partie dynamique. Il est nécessaire de disposer de bases théoriques pour aider le concepteur à garder une démarche cohérente pour la modélisation des réseaux. Nous présentons donc une possibilité de modélisation, de simulation et d’analyse des réseaux à l’aide des réseaux de Pétri. 

Quelques définitions

CONDITION – EVENEMENT – une condition est la description de l’état d’une ressource du système modélisé (une machine est au repos, une machine est en réparation, une commande est en attente). Une condition est soit vraie soit fausse. – un évènement est une action qui se déroule au sein du système et dont la réalisation dépend de l’état du s ystème (début du t raitement sur une machine, panne sur une machine, début de traitement d’une commande). Dans le formalisme des Rdp, la condition est matérialisée à l’aide d’une place. Formalisme des réseaux de Pétri (RdP) 32 3.2 Définition d’un RdP Un réseau de Pétri est un graphe orienté comportant : – un ensemble fini de places, P = {P1, P2, ……………, P n} symbolisées par des cercles et représentant des conditions : o une ressource du système (exemple : une machine, un stock, ….) o l’état d’une ressource du système (exemple : machine libre, stock vide,…..). – un ensemble fini de transitions, T = {T1, T2, …, Tn} symbolisées par des tirets (rectangles) et représentant l’ensemble des évènements (les actions se déroulant dans le système) dont l’occurrence provoque la modification de l’état du système. – un ensemble fini d’arcs orientés qui assurent la liaison d’une place vers une transition ou d’une transition vers une place. Figure 7 : Eléments d’un RdP 

Marquage d’un RdP 

Marquage Le marquage d’un RdP est précisé à l’intérieur des places par un nombre fini (positif ou nul), de marques ou de jetons. Une place est donc vide ou marquée. Lorsque la place représente une condition logique, la présence d’un jeton indique que cette condition est vraie ; fausse dans le cas contraire. Lorsque la place représente une ressource au sens le plus large, elle peut contenir plusieurs jetons. Figure 8 : lien place arc transition Place : Arc Transition : P1 P2 T1 « Une place contient un nombre ≥0 de marques » 33 3.3.2 Marquage initial Le marquage initial, M0, d’un RdP correspond à la distribution de jetons dans chacune des places du RdP et précise l’état initial du système, retenu pour l’analyse. M0 = [ M0(P1), M0(P2), M0(P3), M0(P4)] = [ 2, 0, 1, 0 ] avec M0 (Pi) = marquage initial de la place Pi. On notera M (Pi) le marquage de la place Pi. Remarques : – le marquage initial est représenté sous forme d’un vecteur colonne : 2 0 M0 = 1 0 Un jeton peut avoir plusieurs significations en fonction de la place dans laquelle elle se trouve.

Dynamique des RdP 

Place d’entrée et place de sortie

A chaque transition, il peut être relié des places d’entrée et des places de sortie. Les places d’entrée sont les places d’où sont issues les arcs orientés vers la transition ; les places de sortie sont celles où aboutissent les arcs orientés issus de la transition. 2 1 Figure 9 : marquage initial 34 Figure 10 : place d’entrée et place de sorite On note °Tn, l’ensemble des places d’entrées de la transition Tn (PE1 ε °Tn) ; On note Tn°, l’ensemble des places de sortie de la transition Tn (PS1 ε Tn°). Remarque : on dit de manière symétrique l’ensemble des transitions d’entrée et l’ensemble des transitions de sortie d’une place. 3.4.1.1 Validation d’une transition Une transition est validée (ou sensibilisée ou franchissable ou tirable) lorsque toutes ses places d’entrées contiennent au moins un jeton. M (Pi) >1 M (Pj) = 0 La transition Tn n’est pas franchissable M (Pi) >1 M (Pj) = 1 La transition Tn est franchissable . Figure 11 : Franchissabilité d’une transition 3.4.1.2 Franchissement d’une transition Le franchissement d’une transition ou tir d’une transition, consiste à retirer une marque dans chacune des places d’entrées de la transition et à ajouter une marque dans chacune des places de sortie de la même transition. 35 Figure 12 : tir d’une transition “Le franchissement de la transition Tn à partir de Mx conduit au marquage My.”, se note : Mx (Tn My).

Transition source

Une transition source est une transition qui ne comporte aucune place d’entrée ; c’est une transition toujours franchissable et le franchissement a lieu lorsque l’événement associé se produit.

Transition puits

Une transition puits est une transition qui ne comporte aucune place de sortie ; le franchissement d’une transition puits enlève des jetons de toutes les places d’entrée de la transition. Figure 13 : tir des transitions source et puits. Remarques : – Lorsqu’une transition est validée, cela n’implique pas qu’elle sera immédiatement franchie ; cela ne représente qu’une possibilité de franchissement ou d’évolution du RdP. 36 – Pour les RdP, il y a un seul franchissement à la fois. Ces remarques impliquent que lorsque plusieurs transitions sont sensibilisées dans un même marquage (les transitions sont franchissables en parallèle), l’ensemble des marquages suivants sera obtenu en considérant toutes les possibilités de franchissement des transitions les unes après les autres. Ainsi N transitions sensibilisées conduiront à N marquages, permettant ainsi d’étudier l’ensemble des comportements possibles. Cependant, ce mode de fonctionnement conduit à une explosion combinatoire des marquages pour les RdP de grande taille. Voici un exemple de RdP où on met en exergue les transitions franchissables et la distribution des jetons après le franchissement de chacune des transitions