Chapitre 7 sur 10. Formuler les propriétés correctement et distinguer un réseau sans blocage d’un réseau vivant.
1. Bornitude et sûreté au sens des réseaux
Une place est k-bornée si aucun marquage accessible ne lui attribue plus de k jetons. Le réseau est borné si une borne finie convient à toutes ses places. Il est sauf, ou 1-borné, si chaque place possède au plus un jeton dans tout état accessible.
Le réseau d’une demande et d’un agent est sauf. Le tampon de capacité deux du chapitre 9 est borné mais non sauf. Ce sens technique de « sûreté » ne prouve pas la sécurité informatique d’une application.
Considérons une place Stock et une transition qui consomme un jeton puis en produit deux. Depuis un jeton, les marquages 1, 2, 3, 4… sont accessibles. La quantité gagne une unité à chaque événement : le réseau est non borné.
2. Blocage ou fin normale ?
Un marquage est bloqué si aucune transition n’y est franchissable. Dans notre premier modèle, (0,1,0,1) est bloqué mais représente une fin attendue : le travail est accompli. Un blocage avec une demande en attente et un agent perdu serait au contraire indésirable.
La propriété utile dépend donc du contrat métier. On peut demander que le seul état terminal soit un état d’achèvement, au lieu d’exiger « aucun état terminal » pour un processus qui doit se terminer.
3. Vivacité et possibilités futures
Une transition est vivante si, depuis tout marquage accessible, il existe une continuation qui permet de la franchir. Le réseau est vivant lorsque toutes ses transitions le sont. Le mot « existe » est important : il ne promet pas qu’un ordonnanceur choisira effectivement cette continuation.
Dans un cycle Repos → Démarrer → Actif → Revenir → Repos avec un jeton initial, les deux transitions sont vivantes. Depuis chaque état, on peut rejoindre l’état qui autorise l’autre transition. Un processus terminé à usage unique n’est pas vivant selon cette définition, même si sa fin est correcte.
4. Absence de blocage, famine et équité
Imaginons une transition Boucler sur une place marquée et une transition Fantôme sur une autre place vide, sans aucun moyen de l’alimenter. Boucler reste possible partout : le réseau n’a aucun blocage. Pourtant Fantôme ne peut jamais se produire ; le réseau n’est pas vivant.
Même la vivacité ne garantit pas qu’une transition sera choisie sur une exécution particulière. Un choix défavorable peut reporter indéfiniment une action. Une hypothèse d’équité appartient à l’analyse des exécutions et doit être précisée, jamais supposée silencieusement.
Trois exercices corrigés
Exercice 1 : Borné mais pas sauf
Un tampon atteint (0,2). Peut-il être sauf ? Peut-il être borné ?
Voir la correction de l’exercice 1
Il n’est pas sauf : sa seconde place contient deux jetons. Il peut rester borné, par exemple si la somme des deux places est constamment égale à 2. Cette distinction concerne tous les états accessibles.
Exercice 2 : Sans blocage mais non vivant
Expliquez le contre-exemple Boucler/Fantôme.
Voir la correction de l’exercice 2
Boucler possède toujours un jeton d’entrée qu’elle rend après usage. Fantôme exige un jeton dans une place qui reste vide. Il existe toujours un franchissement, mais la transition Fantôme est morte : aucune continuation ne l’activera.
Exercice 3 : Une fin correcte
Le réseau agent n’est pas vivant. Est-il nécessairement mal conçu ?
Voir la correction de l’exercice 3
Non. Il traite une demande puis s’arrête correctement. La propriété attendue est ici l’achèvement sans perte de ressource, pas la possibilité de recommencer chaque transition indéfiniment.
Références pour approfondir
Introduction universitaire PetriSim, Javier Esparza : notes universitaires sur les réseaux de Pétri. Cours, cas et figures rédigés pour PandaCodeur ; aucune figure universitaire reproduite. Les exemples NKILItech sont fictifs.