Réseaux de Petri et programmation système

Un réseau de Petri est un graphe orienté ${\cal G}=({\cal N},{\cal A})$ avec deux sortes de noeuds : les places (représentées par des cercles) et les transitions (représentées par des rectangles). Un exemple est donné en figure . Si on note ${\cal P}$ l'ensemble des places et ${\cal T}$ l'ensemble des transitions, on a donc ${\cal N}={\cal P}\cup {\cal T}$. Les arcs relient les places aux transitions et vice-versa, mais il n'y a jamais un arc entre deux noeuds de même nature.

Des jetons (représentés par des petits disques sur la figure ) circulent dans le graphe de la manière suivante. On se donne une application $M:{\cal P}\to\ensuremath{\mathbb{N}}$ appelée marquage qui reprsente le nombre de jetons dans chaque place. On dit qu'une transition $T\in{\cal T}$ est tirable ou franchissable si toute place en amont de $T$ a au moins un jeton. Quand on tire une transition, on fait disparaître un jeton de chaque place en amont et on en fait apparaître un dans chaque place en aval.

Figure: Réseau de Petri avec ses situations de blocages quand une des transitions tombe en panne

Une des grandes questions face à un réseau de Petri est de savoir si celui-ci est vivant, c'est-à-dire si quelle que soit la façon de tirer les transitions, le système ne se bloque jamais.

Une autre notion importante pour un réseau de Petri est d'être borné, c'est-à-dire que le nombre de jetons par place reste majoré quelle que soit l'évolution du système.

On s'intéresse à une sous-classe des réseaux de Petri vivants et bornés. On suppose qu'une des transitions tombe en panne et on veut alors savoir si le système reste vivant ou s'il se bloque et dans quel état (voir figure ).

La définition précédemment donnée d'un réseau de Petri n'est pas sans rappeler les IPC de System V de type sémaphore. Il s'agira pour ce TER de simuler des réseaux de Petri grâce à cette technique, puis de simuler une panne et de regarder si le système reste vivant de trois façons différentes :

-

par la programmation de l'algorithme exposé dans [1],

-

par un choix aléatoire de la transition à tirer parmi les transitions tirables,

-

par un déroulement ``en parallèle'' de toutes les transitions tirables (par création de processus ou de threads).