Composition Asynchrone

Dans le chapitre précédent, nous avons étudié un concept de modularité « verti­ cale », à savoir le raffinement hiérarchique par remplacement de modules par des modules équivalents. Ici nous considérons un concept de modularité « horizontale », c-à-d, la composition des modèles. Il existe deux façons naturelles de composer des réseaux de Petri: la fusion de transitions et la fusion de places. La fusion de transitions correspond à la synchronisation d’événements par (multi-)rendez-vous. Elle a déjà fait l’objet de nombreux travaux qui posent le problème de déterminer le comportement d’un système à partir des comporte­ ments de ses composants, ou de trouver sous quelles conditions des propriétés du système (vivacité, caractère borné) peuvent être déduites de celles de ses com­ posants. Mazurkievicz[4l] montre que la composition des ensembles de traces de deux réseaux est égal à l’ensemble des traces du réseau composé; Winskel[66] étudie le problème dans le cadre des catégories où la composition de deux réseaux par fu­ sion de transitions correspond au produit; Souissi[51,52] étudie la conservation de la vivacité dans la composition de deux réseaux à travers un medium de communi­ cation et la composition par rendez-vous multiples ordonnés; Valmari[59] propose une méthode de composition des graphes d’états correspondant à la composition par fusion de transitions: on associe à chaque composant son graphe qu’on réduit par des transformations conservant une certaine relation d’équivalence, puis on compose les graphes réduits, (voir aussi l’introduction du chapitre précédent.)

Composition par fusion de places

Cette opération admet plusieurs interprétations: le séquencement, l’alternative ou l’itération sont obtenues par des fusions de places quand les places sont con­ sidérées comme les préconditions et les postconditions d’une action (Kotov[37j); quand on fusionne des places représentant des ressources des systèmes, la fu­ sion s’interprète comme un partage de ressources ou un multiplexage si les places représentent l’état repos d’une unité. Dans le cas général, nous obtenons essentiellement la conservation des flots, et celle des espaces d’accueil quand leur accessibilité est indépendante des places partagées. En particulier, ce résultat implique que la composition de deux réseaux à interface ouverte robuste est un OI-réseau robuste.  La diificulté du problème a déjà été mise en évidence par d’autres travaux. Dans [53], Souissi étudie la conservation de la vivacité lors de la composition de réseaux par fusion de places, et est amené à supposer des conditions de mono­ tonie de vivacité des réseaux. Petrucci[45] présente un algorithme de construction du graphe des marquages de la composition de deux réseaux: dans le cas de la composition par fusion de places, l’algorithme est plus complexe et construit im­ plicitement plusieurs graphes pour chacun des composants. La relation entre un réseau composé et ses composants étant assez décevante dans le cas général, nous étudions la composition de réseaux appartenant à des classes plus restreintes, et nous nous intéressons à des propriétés particulières: nous considérons le problème du partage de ressources et la preuve modulaire de la propriété « il est toujours possible de libérer les ressources. »

tiels modélisés par des réseaux cycliques, et ont montré que l’ajout de certaines places empêchent le franchissement des séquences qui ne sont pas « fiables » (qui mènent à un blocage) et celles-ci seulement. Tazza[56] reprend le problème sur une classe de réseaux plus générale, où la stratégie d’allocation n’est plus optimale (c-à- d, certaines séquences fiables sont aussi interdites): il étudie alors quantitativement la déviation par rapport à l’optimum. Hauschildt et Valk[32] étudient à partir d’une représentation au moyen d’un réseau de Petri de l’algorithme du banquier, et dérivent des formules caractérisant les états fiables (qui ne mènent pas à un blocage). Nous n’étudions pas de stratégie d’allocation de ressources, mais des conditions que doivent vérifier les réseaux dans leurs demandes et libérations de ressources pour éviter l’interblocage. Le résultat principal de ce chapitre est une solution du problème d’interblocage dans les systèmes à ressources renouvelables, basée sur un ordonnancement des ressources. Notre solution diffère de la solution classique en ce qu’il existe des choix dans les suites de demandes de ressources. Dans la troisième section, nous définissons la classe des réseaux à ressources ordonnées: ce sont des réseaux à ressources renouvelables, où les ressources sont ordonnées et il est toujours possible de libérer une ressource de rang k sans de­ mander des ressources de rang j < k. Nous montrons alors que dans un tel réseau, il est toujours possible de libérer toutes les ressources. De plus, cette classe est fermée par composition ce qui implique que cette propriété est conservée.