Faculté de technologie

Système à évènements
Discrets

Département Pétrochimie et Génie des Procédés

Master 2 Automatisation,
2016-2017

Dr. Youcef Zennir

[email protected]

Y.ZENNIR Système à Evènements Discrets 1

 Contenu de la matière

Généralité sur les systèmes à évènements discrets

• Classes de systèmes
• Caractéristiques
• Problèmes
• Approches et méthodes
La modélisation
Définition, formalismes et domaines d’application
Objectifs
Les Systèmes à événements discrets (S.E.D.)
Un regard particulier sur un système
Comment déterminer les critères à prendre en compte
Deuxième exemple : Modélisation d’un réseau routier
Troisième exemple : Modélisation d’un système de
fabrication
Y.ZENNIR Système à Evènements Discrets 2
Contenu de la matière Réseaux de Pétri (R.D.P)

Introduction
Systèmes et modèles
Notions générales sur les systèmes et modèles
Un modèle, pour quoi faire ?
Quelques classes de systèmes à variables discrètes
Modélisation par Réseaux de Pétri
Modèle de base
Eléments de base
Evolution d’un RdP
Exemples de Réseaux de Pétri
Réseaux de Pétri avec une structure particulière
Structures fondamentales pour la modélisation des
systèmes
Eléments de modélisation
Y.ZENNIR Système à Evènements Discrets 3
Contenu de la matière Réseaux de Pétri (R.D.P)

Parallélisme ; Synchronisation; Partage de ressources

Mémorisation; Lecture; Capacité limité
Modélisation structurée
Approche par affinements successifs
Approche par compositions de RdPs
Propriétés des Réseaux de Pétri
Notations et définitions
Propriétés
Réseau de Pétri borné et Réseau sauf
Vivacité et blocage
Conflits; Invariants; Composante conservative
Composante répétitive

Y.ZENNIR Système à Evènements Discrets 4

Contenu de la matière Réseaux de Pétri (R.D.P)

Propriétés des RDP par graphes et arborescences de

marquages
Introduction
Construction de l’arborescence de couverture
Propriétés et intérêts de l’arborescence (graphe) de couverture

Propriétés des RDP par algèbre linéaire

Notations et définitions
Structure; Marquage; évolution ; Equation fondamentale
Pondération des places et invariants de marquage
Pondérations; Invariants de marquage
Composantes répétitives
Remarque sur le lien entre RdP ordinaire et RdP généralisé
Y.ZENNIR Système à Evènements Discrets 5
Contenu de la matière Réseaux de Pétri (R.D.P)

Propriétés des RDP par réduction

Règles de réduction préservant la vivacité et la bornitude
Règle de réduction R1 : substitution de places
Règle de réduction R2 : place implicite .
Règle de réduction R3 : transition neutre
Règle de réduction R4 : transitions identiques
Exemple de mise en œuvre des différentes règles R1 à R4
Règle s de réduction préservant les invariants de marquage

Règle de réduction Ra : transition impure

Règle de réduction Rb : transition pure
Exemple de mise en œuvre des règles Ra et Rb
Remarques
Y.ZENNIR Système à Evènements Discrets 6
Contenu de la matière Réseaux de Pétri (R.D.P)

Réseaux de Pétri colorés

Introduction aux RdPs colorés à travers des exemples
Réseaux de Pétri colorés (simplifiés)
Définition
Evolution du marquage d’un RdP coloré
Analyse d’un RdP coloré marqué
Un exemple d’application `a la modélisation de systèmes de
production
Modélisation d’un convoyeur de type FIFO
Modélisation d’une machine sur un convoyeur FIFO

Y.ZENNIR Système à Evènements Discrets 7

 Références conseillées
G. Birkhoff. Lattice Theory. Amer. Math. Soc. Coll. Pub.,
Providence, 1967 (3rd Ed.).
T.S. Blyth and M.F. Janowitz. Residuation Theory. Pergamon
Press, Oxford, England, 1972.
P. Chrétienne. Les Réseaux de Pétri Temporisés. Thèse d’état,
Université de Paris 6, Paris, France, 1983.
F. Baccelli, G. Cohen, G.J. Olsder, J.-P. Quadrat. Synchronization
and Linearity — An Algebra for Discrete Event Systems. Wiley,
New-York, 1992.
R.A. Cuninghame-Green. Minimax Algebra. Number 166 in
Lecture Notes in Economics and Mathematical Systems.
Springer-Verlag, Berlin, Germany, 1979.
P. Dubreil et M.L. Dubreil-Jacotin. Lec¸ons d’Algèbre Moderne.
Dunod, Paris, France, 1964.
Y.ZENNIR Système à Evènements Discrets 8
 Références conseillées
M. Gondran and M. Minoux. Linear algebra in dioids: a survey
of recent results. Annals of Discrete Mathematics.,19:147–
164, 1984.
M. Gondran et M. Minoux. Graphes et Algorithmes. Eyrolles,
Paris, 1979.
James L. Peterson. Petri Net Theory and the Modeling of
Systems. Prentice Hall, Englewood Cliffs, N.J. 07632, USA,
1981.
cours de Robert Valette disponible sur la page WEB :
http://www.laas.fr/˜robert/
Page WEB consacrée aux Réseaux de Petri :
http://www.daimi.au.dk/PetriNets/
Y.ZENNIR Système à Evènements Discrets 9
 Définition S.E.D
Le vocable “systèmes (dynamiques) à évènements discrets est relativement récent
(moins de dix ans) et recouvre un champ de recherches encore assez diverses, mais
qui cherchent à se fédérer sous ce drapeau. Ce domaine est actuellement très actif,
fait l’objet de nombreuses manifestations scientifiques, et a déjà son propre journal
spécialisé.
Un modèle est une représentation simplifiée capable de reproduire de façon
pertinente le comportement partiel d’un système.modèles mathématiques
• équations aux dérivées partielles : mécanique des fluides, géologie, météorologie,
Océanographie modèles fondés sur des méthodes d’apprentissage : réseaux de
neurones artificiels
• traitement de signal, contrôle de processus, classification de données,…
• modèles à la fois formels (langages ayant une définition mathématique) et semi-
graphiques : réseaux de Petri (RdP), Petri Nets (PN)
• Systèmes à Evénements Discrets (SED) : processus logistiques (organisation des
services, réseaux de transport), processus techniques (réseaux de télécommunications,
réseaux d’ordinateurs, chaînes de production, ateliers flexibles)

Y.ZENNIR Système à Evènements Discrets 10

 Objectifs S.E.D
Pour un système réel :
 comprendre (comportement)
 évaluer les performances (vitesse, capacité, coût, rendement, …)
 optimiser (par exemple : déterminer le nombre minimum de ressources pour
qu’une charge de travail donnée soit accomplie en un temps déterminé)
prévoir les évolutions, notamment dans des situations extrêmes (processus très lents,
ruptures, accidents, …)

Pour un projet :
 valider (comportement, performances)
 optimiser
Le mot « discret » ne signifie ni « temps discret » ni « état discret »
 Le temps et les états du système réel évoluent de façon continue, mais on ne
s’intéresse qu’à des instants particuliers. Seuls les faits importants pour l’étude
(certains évènements) sont considérés
1. arrivée ou départ d’une ressource (objet, personne, …)
2. début ou fin d’une action (d’un processus), …
Y.ZENNIR Système à Evènements Discrets 11
 Classes de systèmes S.E.D

Alors que la théorie classique des systèmes “continus” (y compris en temps discret)
et de l’Automatique s’intéresse à des systèmes “naturels” obéissant essentiellement
aux lois de la Physique, et descriptibles par des équations différentielles ou aux
dérivées partielles (ou leur discrétisation approchée en temps),

le vocable S.E.D recouvre des systèmes également dynamiques, mais dont la

dynamique échappe totalement à ce genre de description.

En réalité, c’est plutôt le niveau descriptif auquel on se place qui est à la source de
cette impossibilité : au lieu de s’intéresser au déroulement continu des phénomènes,
on ne se soucie que des “débuts” et des “fins” de ces phénomènes (les “évènements
discrets”) et `a leur enchaînement dynamique, logique ou temporel.

Y.ZENNIR Système à Evènements Discrets 12

 Classes de systèmes S.E.D

Ces systèmes, généralement fabriqués par l’homme, ont une part croissante, voire
prépondérante, dans l’économie moderne.

Pourtant, sur le plan de la théorie, il ne bénéficiaient pas jusqu’à récemment d’un

“statut” et d’une conceptualisation comparables a ceux des systèmes continus.

De plus, ils étaient plutôt étudiés par la Recherche Opérationnelle que par
l’Automatique. En voici quelques exemples.

Systèmes de production, ateliers flexibles

Systèmes informatiques

Réseaux de communication

Planification de tâches

Y.ZENNIR Système à Evènements Discrets 13

 S.E.D
Caractéristiques
La plupart des systèmes énumérés ci-dessus présente les caractéristiques communes
suivantes.
Parallélisme.
De nombreux événements peuvent se dérouler simultanément et indépendamment dans
diverses parties du système.
Synchronisation.
L’accomplissement de certains événements nécessite la disponibilité simultanée de
plusieurs ressources ou la vérification simultanée de plusieurs conditions.

La fin d’un événement entraîne l’apparition simultané de plusieurs autres événements.

Par exemple, pour qu’une conversation téléphonique ait lieu, il faut qu’une ligne soit
disponible pour acheminer l’appel et que les deux interlocuteurs aient décroché.

La fin de la conversation marque la libération de la ligne, et le fait que les deux

interlocuteurs peuvent désormais vaquer à d’autres occupations. De telles
considérations peuvent être reprises par exemple `a propos d’un atelier flexible.
Y.ZENNIR Système à Evènements Discrets 14
 S.E.D
Concurrence

Certains événements excluent l’apparition simultanée d’autres événements. Par

exemple, une machine ne peut travailler que sur une seule pièce à la fois. à la SNTV,
les voies sont divisées en tronçons appelés “cantons”. Le “cantonnement” consiste à
exclure par un système de feux rouges la présence simultanée de deux trains sur le
même canton. Sur un bus d’ordinateur non multiplexé, un seul message peut transiter
à la fois.
Problèmes
Ce qui suit est une liste de problèmes-type soulevés par la conception, la
réalisation, la conduite ou la gestion, l’optimisation de ces systèmes.
Spécification

Avant de concevoir un système, il faut dire ce qu’on veut lui faire faire, quel doit être
sa “réponse” dans un certain nombre de situations-type, etc. Il se pose donc déjà un
problème de langage dans lequel ces desiderata trouveront une expression précise (et
donc vérifiable a posteriori).
Y.ZENNIR Système à Evènements Discrets 15
 S.E.D

Conception

Architecture. Une fois spécifié le comportement fonctionnel du système, il faut le

concevoir, notamment du point de vue de son architecture : composants,
agencement et articulations, mécanismes de synchronisation et d’exclusion.

Validation logique

Il faut ensuite vérifier que le système ainsi conçu répond bien aux spécifications
désirées, et qu’il n’engendre pas d’autres comportements indésirables. La cas typique
est le “deadlock” : pour commencer, Pierre attend que Paul commence, celui-ci
attend que Jacques commence, mais Jacques attend que Pierre commence. Un bel
exemple de deadlock est donné à la SNTV par le “fameux triangle de Gagny”
représenté schématiquement par la Figure 1.
Si on laisse trois trains s’engager dans la

Y.ZENNIR Système à Evènements Discrets 16

 S.E.D
Validation logique

configuration indiquée, c’est le blocage.

Le mécanisme de feux rouges devra éviter
d’atteindre cet état du système.

Figure 1. Le triangle de Gagny

Y.ZENNIR Système à Evènements Discrets 17

 S.E.D
Evaluation de performance

A cette étape, la notion de temps, jusque là, absente intervient. On cherche alors à
répondre à des questions du type : combien d’évènements d’un type donné se
produisent en une heure, à quelle date se produira le n-ième événement, etc.? Par
exemple, pour un système informatique spécialisé en annulation d’écho sur le signal
de parole transmis à partir d’une salle de téléconférence, il faut vérifier si la vitesse
de traitement du signal est compatible avec la vitesse normale d’élocution.

Ordonnancement

L’ordonnancement a pour but d’établir des politiques de priorité, de routage, etc.,

destinées à résoudre les problèmes posés par les phénomènes de concurrence. Il est
clair que la performance globale d’un système peut dépendre de la façon dont ces
phénomènes auront été arbitrés. À la limite, la politique d’ordonnancement elle-
même peut être la cause de deadlocks (et donc de performances “infiniment”
mauvaises).

Y.ZENNIR Système à Evènements Discrets 18

 Optimisation, dimensionnement S.E.D

L’ordonnancement peut être un premier “levier” d’une optimisation de performance.

Mais dès le choix de l’architecture, on risque d’avoir éventuellement engagé de façon
assez déterminante la performance du système.

A posteriori, on peut essayer d’améliorer les performances en dupliquant (ou en n-

pliquant) certaines ressources (machines, serveurs, buffers, etc.), mais ceci n’a
généralement de sens que sous une contrainte de budget donné, ou de coût à
minimiser.

Autre exemple : pour un “chip” spécialisé, une certaine surface de silicium est
disponible ; comment l’utiliser au mieux pour avoir la performance optimale? Doit-on
rajouter des buffers (effet “pipe-line”), un bus, un deuxième multiplieur, etc.?

Comme la discussion vient de le suggérer, la suite de questions ci-dessus n’est pas en

général résolue séquentiellement en une seule passe, mais bien par une démarche
itérative.

Y.ZENNIR Système à Evènements Discrets 19

 S.E.D

Approches et méthodes.
On cite ici quelques unes des approches les plus usuelles dans l’étude des
SEDs en précisant leur champ d’application.
Simulation “par évènements” sur ordinateur
Il s’agit de reproduire sur un ordinateur, éventuellement avec l’aide de langages de
programmation spécialisés pour la simulation, le déroulement de l’“histoire” du
système : le temps courant est égrené et les événements à venir sont stockés dans une
pile jusqu’à ce que les conditions soient réunies pour qu’ils “se produisent” et sortent
de la pile. Toutes sortes de compteurs et d’outils statistiques peuvent être “branchés”
sur une telle simulation.
Ce genre d’approche n’a a priori de limites que par la complexité du programme à
écrire et le temps d’exécution. Cependant, c’est une méthode “aveugle” ou “boîte
noire” en ce sens qu’il n’y a pas de compréhension analytique de la relation entre les
entrées (les choix faits a priori) et les sorties (les résultats observés), sauf `a
dépouiller des tonnes de listing permettant de suivre le déroulement des événements
pas à pas, ce qui est rarement praticable.
Y.ZENNIR Système à Evènements Discrets 20
 Approche “Pertubation Analysis” (PA) S.E.D

Cette approche tournée vers l’optimisation n’est pas à proprement parler une
description nouvelle des SEDs mais plutôt une technique de calcul de sensibilité
de certaines grandeurs par rapport à certains paramètres.

On doit s’appuyer sur une première trajectoire nominale obtenue par simulation ou
par tout autre moyen.

Sans répéter la simulation pour une valeur légèrement différente d’un paramètre, on
cherche à évaluer les modifications de la trajectoire qui résulteraient d’une petite
modification de ce paramètre.

On obtient ainsi par différence finie une sorte de “gradient stochastique”

susceptible d’être utilisé en optimisation dans l’algorithme itératif du même nom.

Y.ZENNIR Système à Evènements Discrets 21

 Réseaux de files d’attente S.E.D

Le système est modélisé en termes de serveurs et de clients en attente dans les files
devant les serveurs. Les clients circulent d’une file à une autre après avoir reçu un
service.

Les temps de service sont aléatoires et obéissent à des lois de probabilité données.
Il existe un certain nombre de résultats analytiques montrant que, sous certaines
conditions, la loi conjointe p(x1;…..; xn) des longueurs {xi}i=1…n de n files en
régime stationnaire peut s’écrire sous “forme produit”, c’est-`a-dire

ce qui est a priori surprenant puisque les variables aléatoires xi sont loin d’être
indépendantes. On parle alors de “réseaux jacksoniens”. Cependant, ce type de
résultat nécessite des hypothèses souvent

Y.ZENNIR Système à Evènements Discrets 22

 S.E.D
Réseaux de files d’attente
irréalistes (e.g. temps de service poissoniens, pas de blocage du service amont par
saturation de la file d’attente aval, etc.).

Il existe aussi des tentatives d’extensions de cette théorie par des résultats
approchées. Cependant, il faut considérer ces approches comme des outils
d’évaluation “en moyenne” et sur le long terme, plutôt que comme de véritables
outils d’étude de phénomènes dynamiques.

Automates

On fait ici allusion à des extensions de la théorie des automates par le point de vue
“commande” des automaticiens. Un automate reconnaît, ou engendre, un langage
qui est l’ensemble des “mots” (trajectoires) formés de suites ordonnées de “lettres”
(associées aux états de l’automate) qu’il est susceptible de produire en considérant
toutes les transitions possibles entre états

Y.ZENNIR Système à Evènements Discrets 23

 S.E.D
Automates
La commande consiste à limiter le langage au plus grand sous-langage contenu dans
un vocabulaire donné (concrètement, celui qui évite les “gros mots”, c’est-à-dire les
suites d’événements ou les états indésirables) en ayant la possibilité
d’inhiber certaines transitions.

Cette théorie est actuellement bien adaptée à l’étude de l’aspect logique du

fonctionnement, des questions de validation, etc. Par contre, elle a plus de mal à
incorporer l’aspect quantitatif de l’évaluation de performance.
Réseaux de Petri (RdP)

Les RdP sont un langage graphique de description des phénomènes

de synchronisation et de concurrence. Les RdP temporisés permettent de plus de
prendre en compte les aspects “évaluation de performance”.

Y.ZENNIR Système à Evènements Discrets 24

 S.E.D

Réseaux de Petri (RdP)

Un certain nombre de propriétés des systèmes ainsi décrits (invariants au cours du

fonctionnement, présence de deadlocks, etc.) peuvent être étudiées dans ce cadre.

En temps que langage graphique, les RdP ont sur le plan pratique les avantages et
les inconvénients de ce type de représentation : concision et clarté pour des systèmes
simples, difficulté d’utilisation pour des systèmes atteignant un certain niveau de
complexité.

Dans ce cas, `a l’instar des “blocs-diagramme” utilisés par les automaticiens pour
décrire graphiquement les systèmes continus, une approche hiérarchisée (procédant
par zooms successifs sur des parties du système de plus en plus détaillées) est
hautement recommandable.

Y.ZENNIR Système à Evènements Discrets 25

 Introduction Réseaux de Petri (RdP)

Les systèmes technologiques, de plus en plus souvent d’une grande complexité, qui ont
envahi notre quotidien sont l’œuvre des ingénieurs. Pour l’ingénieur, se posent alors
plusieurs problèmes importants : comment réussir à appréhender le comportement de
ses systèmes afin de les concevoir, les réaliser et/ou les commander ?

La description du comportement attendu du système constitue le cahier des charges.

Celui-ci est en général défini par différents intervenants, intéressés par les aspects
fonctionnels du produit, les besoins du consommateurs, les contraintes de coût, le
marketing, etc...

Du fait de la complexité de plus en plus forte des systèmes technologiques, il apparaît

de plus en plus nécessaire de disposer de méthodes et d’outils de conception, de
réalisation et/ou de commande qui soient particulièrement efficaces.

Au centre de ces méthodes et de ces outils, se trouve en général la modélisation.

L’objectif de ce cours est de présenter la modélisation par Réseaux de Petri.

Y.ZENNIR Système à Evènements Discrets 26

 Introduction Réseaux de Petri (RdP)

Les Réseaux de Petri ont été développés pour permettre la modélisation de classes
importantes de systèmes qui recouvrent des classes de systèmes de production, de
systèmes automatisés, de systèmes informatiques et de systèmes de communication,
pour n’en citer que quelques-uns, afin de permettre leur conception, leur évaluation et
leur amélioration.

Dans ce chapitre d’introduction, les notions de système et de modèle sont rappelées : la

modélisation par Réseaux de Petri est mise en perspective avec les outils de
modélisation précédemment étudiés. L’intérêt de la modélisation est ensuite discutée.

Le chapitre se termine sur une discussion succincte sur les systèmes auxquels les
Réseaux de Petri (RDP) peuvent être appliqués.

Y.ZENNIR Système à Evènements Discrets 27

 Systèmes et modèles Réseaux de Petri (RdP)
Notions générales sur les systèmes et modèles
Un système est une portion de la réalité définie par une frontière organisée en fonction
d’un but. En général, un système est constitué par un ensemble d’éléments en
interaction dynamique. Il possède des entrées et des sorties. Elles sont caractérisées
par des variables de flux.

Un modèle est une représentation, souvent en termes mathématiques, des relations qui
existent entre les variables de sortie et les variables d’entrée d’un système.

Cette représentation nécessite souvent l’introduction de variables supplémentaires

appelées variables d’état.

A un instant donné, la valeur des variables d’état caractérise un système : leur

connaissance avec celle des valeurs dans le futur des variables d’entrée permet à l’aide
du modèle de déterminer les valeurs des variables de sortie dans le futur.

Y.ZENNIR Système à Evènements Discrets 28

 Systèmes et modèles Réseaux de Petri (RdP)
Notions générales sur les systèmes et modèles
Un scénario est constitué par un instant initial t0, un instant final t1 > t0, la valeur des
variables d’état à l’instant initial t0 et par la valeur des variables d’entrée pour chaque
instant appartenant à l’intervalle [t0; t1].

Un modèle serait idéal s’il est capable de reproduire de façon exacte le comportement
du système.
Cela signifie que si, à un instant donné, on connaît la valeur des variables d’état du
système et que si on connaît la valeur des variables d’entrée dans le futur (et le présent),
les relations mathématiques qui constituent le modèle permettent de déterminer
exactement les valeurs des variables de sortie qui peuvent être observées
expérimentalement.
Un des principes fondamentaux (et philosophiques) des Sciences de l’Ingénieur est
qu’il est impossible d’obtenir le modèle idéal d’un système. Au mieux, on peut obtenir
un “bon” modèle, c’est-`a-dire, un modèle qui permette de déterminer de façon
approchée les valeurs des variables de sortie qui peuvent être observées
expérimentalement.
Y.ZENNIR Système à Evènements Discrets 29
 Systèmes et modèles Réseaux de Petri (RdP)
Notions générales sur les systèmes et modèles
Les variables d’un système peuvent être de nature différente, par exemple :

continues définies sur R,

discrètes définies sur N,

logiques définies sur 0; 1 ,

Suivant la nature des variables d’entrée, de sortie et d’état, les outils de

modélisation utilisés sont différents.

Dans le tableau qui suit, est présenté un ensemble non exhaustif d’outils de
modélisation précédemment étudiés.

Y.ZENNIR Système à Evènements Discrets 30

 Systèmes et modèles Réseaux de Petri (RdP)

Les Réseaux de Petri ont été inventés par Carl Maria Petri au début des années
soixante. Des travaux ultérieurs ont permis de développer les Réseaux de Petri
comme un outil de modélisation des systèmes à variables d’entrée, de sortie et d’état
discrètes. C’est aussi un outil de modélisation pour les systèmes à variables logiques
puisque ceux-ci sont un cas particulier des systèmes à variables discrètes.

Y.ZENNIR Système à Evènements Discrets 31

 Systèmes et modèles Réseaux de Petri (RdP)

Un caractère très intéressant est que les modèles Réseaux de Petri sont sous la
forme d’une représentation mathématique graphique.

Ce point est important car le fait d’écrire sous forme graphique un modèle plutôt
que sous forme d’équations peut permettre de le rendre lisible par des personnes
dont la formation scientifique n’est pas forcement poussée.

Le modèle Réseaux de Petri a d’ailleurs donné naissance au Grafcet, un langage

de spécification et de programmation d’automates industriels.

Dans le langage Grafcet, le caractère graphique est ici fondamental car ce langage
doit être accessible à la fois à l’industriel, l’ingénieur, le technicien et l’ouvrier car
c’est un outil graphique.

Y.ZENNIR Système à Evènements Discrets 32

 Systèmes et modèles Réseaux de Petri (RdP)

Le passage d’une personne `a l’autre doit alors se faire sans perte d’information,
ce que permet l’utilisation d’un modèle. Ce problème est suffisamment central
pour qu’un énorme effort soit consacré au niveau de la définition et de la mise en
œuvre de normes et de standards industriels. Par exemple, la modélisation du
fonctionnement demandée à un automate industriel est possible par l’utilisation du
Grafcet, qui est un outil de modélisation dérivant des RdP. Le langage Grafcet a
fait l’objet de plusieurs normes.

Lors de la conception d’un nouveau système technologique, le cahier des charges

exprime le comportement attendu du système. La question fondamentale est de
garantir que le système qui a été conçu (sur le papier) remplit bien le cahier des
charges, voire possède un comportement “satisfaisant”. L’approche traditionnelle de la
conception d’un système consiste à le concevoir sur le papier, à le réaliser et à faire
des expériences sur le système correspondant à des scénarios types afin de vérifier si
son comportement est satisfaisant et s’il est nécessaire de l’améliorer voire de le
reconcevoir. Cette approche pose plusieurs problèmes. Dans certains cas, il est
impossible de réaliser des expériences sur le système
Y.ZENNIR Système à Evènements Discrets 33
 Systèmes et modèles Réseaux de Petri (RdP)

(par exemple, systèmes spatiaux). Parfois, cela peut être dangereux si des
informations manquent sur son comportement possible. De façon plus courante, une
telle approche est longue et coûteuse, ce que permettent de moins en moins les
contraintes économiques.

Une alternative est de définir le système technologique à l’aide d’un modèle. En plus
de l’avantage vu précédemment, pour un scénario donné, un modèle permet en
général de calculer numériquement les valeurs des variables d’état et de sortie, ce qui
est plus court et plus économique que de les mesurer au cours d’une expérience.

Cela est désigné par le terme de simulation. La simulation permet ainsi dans une
certaine mesure de tester si le comportement du système est satisfaisant et de mettre
en évidence certains problèmes.

Elle ne remplace pas complètement l’expérimentation qu’il est nécessaire d’effectuer

si à l’issue de la simulation le comportement du système semble satisfaisant.

Y.ZENNIR Système à Evènements Discrets 34

 Systèmes et modèles Réseaux de Petri (RdP)

Le problème de la simulation est que, même si le modèle est bon, on ne peut tester
qu’un nombre limité de scénarios.

Si le choix des scénarios types n’est pas pertinent par rapport à l’ensemble des
scénarios auxquels sera confronté le système durant son existence, il est difficile de
prévoir si le comportement du système sera satisfaisant dans tous les cas.

Une alternative est de parfois pourvoir garantir qu’à partir d’une propriété du
modèle, le modèle étant supposé bon, le comportement du système sera (ou non)
satisfaisant pour une famille de scénarios.

On parle d’analyse. L’analyse d’un système repose sur l’étude des propriétés
mathématiques de son modèle.

Y.ZENNIR Système à Evènements Discrets 35

 Quelques classes de systèmes à variables discrètes

Les RdP permettent la modélisation de systèmes à variables d’entrée, d’état

et de sortie discrètes.

Quels types de systèmes cela recouvre-t-il ? On va simplement présenter

succinctement quelques classes de systèmes ; cette présentation n’étant pas
exhaustive.

Une première application est la modélisation de processus de fabrication de

systèmes industriels manufacturiers.

Un processus est une suite d’opérations effectuées dans un ordre bien

Y.ZENNIR Système à Evènements Discrets 36

 Rédaction
Cahier des charges

Conception
système

Modélisation
(RdP)

Analyse Propriétés Simulation

Modèle Modèle

Non
Cahier des charges
Oui
Non
Oui Comportement

Réalisation du système

Expérimentation Figure 2
Y.ZENNIR du système Système à Evènements Discrets 37
 Quelques classes de systèmes à variables discrètes

déterminé. L’industrie manufacturière est caractérisée par la production de pièces en

série (par exemple, production de véhicules), soit des variables discrètes représentant
des nombres de pièces.

On peut l’opposer à l’industrie lourde de transformation de la matière (par exemple,

chimie lourde) qui est caractérisée par des flux continus de matière, d’énergie, soit des
variables continues.

Un processus de fabrication manufacturier utilise des ressources : les machines qui

effectuent les différentes opérations, les stocks, les convoyeurs entre les différentes
machines, etc...

Il apparaît alors des problèmes d’organisation et plus particulièrement, des problèmes

de synchronisation et de coopération entre des processus travaillant en parallèle et
partageant des ressources.

Ces problèmes ont une acuité de plus en plus forte.

Y.ZENNIR Système à Evènements Discrets 38
 Quelques classes de systèmes à variables discrètes

D’une part, la réduction des coûts a entraîné la diminution, voire la suppression des
stocks (flux tendu).
Par exemple, le moteur d’un camion est livré à l’usine d’assemblage à la date (et
quasiment à l’heure) de son montage.

D’autre part, l’adaptation aux goûts du public (pour un coût limité) a entraîné une
grande diversification des pièces produites, voire une individualisation complète
(exemple des cabines de camions).

Pour garantir un fonctionnement efficace du système, ces problèmes doivent donc

être abordés par des méthodes efficaces.

Y.ZENNIR Système à Evènements Discrets 39

 Quelques classes de systèmes à variables discrètes

Si les systèmes industriels manufacturiers effectuent des transformations sur des

pièces, les systèmes informatiques (par exemple un système d’exploitation)
effectuent eux aussi des transformations mais sur de l’information.

On peut définir un processus informatique de façon similaire à un processus

manufacturier. Il utilise des ressources de même type : processeurs pour
transformer l’information, mémoires pour la stocker, bus et réseaux pour la
transporter, etc ...

On est donc confronté aux mêmes problèmes. Il en est de même pour le

fonctionnement de réseaux informatiques.

Du fait de l’augmentation de la complexité des systèmes informatiques et de leurs

interconnexions, ces problèmes sont très difficiles `a aborder, sans méthodes
particulièrement efficaces.

Y.ZENNIR Système à Evènements Discrets 40

 Quelques classes de systèmes à variables discrètes

De façon plus générale, les problèmes d’organisation, de synchronisation et de

coopération entre des processus travaillant en parallèle et partageant des ressources
apparaissent dans de nombreux systèmes.

Il peut s’agir de traiter du trafic dans des réseaux que ce soit des réseaux
de communication ou des réseaux routiers.

Il peut aussi s’agir d’organiser la diffusion de l’information au sein d’une entreprise

(par la mise en place d’un système d’information supporté par un système
informatique) ou la gestion d’un projet...

Y.ZENNIR Système à Evènements Discrets 41

 Modélisation par Réseaux de Petri

Modèle de base
Eléments de base

Un graphe peut être défini par un ensemble d’éléments appelés nœuds ou sommets
et un ensemble de relations appelées arrêtes ou arcs.

Un exemple est donné Figure 3 :

les nœuds sont constitués par les carrés étiquetés A, B, C et D;
les arcs sont constitués par les droites étiquetées
1 (qui relie le sommet A au sommet B),
2 (qui relie le sommet A au sommet C),
3 (qui relie le sommet B au sommet C) et
4 (qui relie le sommet C au sommet D).

Les arcs peuvent être orientés : on parle alors de graphe orienté.

Les sommets peuvent être de plusieurs types.

Y.ZENNIR Système à Evènements Discrets 42
 Modélisation par Réseaux de Petri

Exemple Figure 3: de Graphe (gauche) et Graphe

orienté (droite)
Un Réseau de Petri (RdP) est un graphe orienté comprenant deux types de
sommets :
– les places
– les transitions

Y.ZENNIR Système à Evènements Discrets 43

 Modélisation par Réseaux de Petri

Ils sont reliés par des arcs orientés

Un arc relie soit une place à une transition, soit une transition à une place jamais
une place à une place ou une transition à une transition. Tout arc doit avoir à
son extrémité un sommet (place ou transition).

Un exemple de Réseaux de Petri est représenté Figure 4.

A chaque place et transition, un nom peut être associé : par exemple sur le RdP de
la Figure 4, les places sont nommées P1, P2, P3 et P4 et les transitions T1, T2 et
T3.
T1 est reliée à P1 par un arc orienté de T1 vers P1 : on dit que P1 est en sortie ou
en aval de T1.
P1 est reliée à T2 par un arc orienté de P1 vers T2 : on dit que T2 est en sortie de
P1.
De même, on peut dire que P1 est en entrée ou en amont de T2. La place P3 est en
entrée de T1.

Y.ZENNIR Système à Evènements Discrets 44

 Modélisation par Réseaux de Petri

Figure 4

Cas particuliers

Transition source pas de place en entrée de la transition

Transition puits pas de place en sortie de la transition

Y.ZENNIR Système à Evènements Discrets 45
 Modélisation par Réseaux de Petri

Une place correspond à une variable d’état du système qui va être modélisé et une
transition à un évènement et/ou une action qui va entraîner l’évolution des variables
d’état du système.

A un instant donné, une place contient un certain nombre de marques ou jetons qui va
évoluer en fonction du temps : il indique la valeur de la variable d’état à cet instant.

Quand un arc relie une place à une transition, cela indique que la valeur de la variable
d’état associée à la place influence l’occurrence de l’évènement associé à la transition.

Quand un arc relie une transition à une place, cela veut dire que l’occurrence de
l’évènement associé à la transition influence la valeur de la variable d’état associée à
la place.

Y.ZENNIR Système à Evènements Discrets 46

 Exemple de l’atelier de coupe de bois :
Un atelier est constitué d’une machine de coupe et d’un stock.

Quand une commande arrive et que la machine de coupe est disponible, la commande
peut être traitée (découpe).

Une fois le traitement terminé, la commande qui a été traitée est stockée.

Sinon, la commande doit attendre que la machine de coupe se libère avant de pouvoir
être traitée.

Y.ZENNIR Système à Evènements Discrets 47

 Exemple de l’atelier de coupe de bois :

Figure 5

Il faut noter les choses suivantes.

– Chaque place contient un nombre entier (positif ou nul) de marques ou jetons. Elle
indique la valeur de la variable d’état associée à la place.

Par exemple, les 3 marques dans P2 représentent 3 commandes en attente.

Y.ZENNIR Système à Evènements Discrets 48
 Exemple de l’atelier de coupe de bois :

Le nombre de marques dans une place peut s’interpréter comme le nombre de

ressources disponibles.
Par exemple, dans la place P1, une marque indique qu’une machine est disponible,
pas de marque indique que la machine n’est pas disponible.

Ces ressources sont consommées ou/et produites au cours du temps.

Par exemple, dans la place P2, le nombre de marques indique le nombre de
commandes en attente d’être traitées par la machine de coupe, c’est-à-dire le
nombre de “ressources” qui vont être consommées.

Une marque dans la place P3 indique qu’une commande est en train d’être traitée
par la machine de coupe. Le nombre de marques dans la place P4 indique le
nombre de commandes qui ont été traitées et stockées.

La fin de la coupe par la machine se traduit par la suppression de la marque dans la

place P3 et par la création d’une marque dans la place P1 et dans la place P4.

Y.ZENNIR Système à Evènements Discrets 49

 Exemple de l’atelier de coupe de bois :
Les marques d’une même place n’ont pas d’identité individuelle : elles sont
indiscernables. Par exemple, chaque commande en attente dans la place P2 est
traitée de la même façon que les autres.
On appelle marquage M d’un Réseau de Petri le vecteur du nombre de marques
dans chaque place : la iième composante correspond au nombre de marques dans la
iième place. Il indique `a un instant donné l’état du RdP. Par exemple, le marquage
du RdP présenté précédemment est donné par :

0 
 3
M = 
1 
 
 2
On appelle marquage initial, noté M0, le marquage `a l’instant initial (t = 0).

Y.ZENNIR Système à Evènements Discrets 50

 Modélisation par Réseaux de Petri

Définition : On appelle Réseau de Petri non marqué le quadruplet Q =< P; T; I;O >
où
– P est un ensemble fini non vide de places ;

– T est un ensemble fini non vide de transitions ;

– P T=∅;

– I(Ti) est l’ensemble des places qui sont en entrée de la transition i ;

– O(Ti) est l’ensemble des places qui sont en sortie de la transition i.

On appelle Réseau de Petri marqué R =< Q;M0 > o`u M0 est le marquage initial.

Q définit la structure du RdP. Le marquage `a un instant donné définit la valeur des

variables d’état du RdP à un instant donné.

Y.ZENNIR Système à Evènements Discrets 51

 Modélisation par Réseaux de Petri

Dans l’exemple de l’atelier de coupe, on a :

P = P1; P2; P3; P4 ;

T = T1; T2; T3 ;

I(T1) = {},
I(T2) = {P1; P2},
I(T3) = {P3} ;

O(T1) ={P2},
O(T2) = {P3},
O(T3) ={P1; P4}.

Y.ZENNIR Système à Evènements Discrets 52

 Evolution d’un RdP
L’évolution d’un RdP correspond à l’évolution de son marquage au cours du temps
(évolution de l’état du système) : il se traduit par un déplacement de marques ce qui
s’interprète comme la consommation/production de ressources déclenchée par des
évènements ou des actions. Déterminer l’évolution d’un RdP correspond en fait à le
simuler, terme plus généralement utilisé en modélisation.

Transition validée
Transition non validée
Figure 6
Y.ZENNIR Système à Evènements Discrets 53
 Evolution d’un RdP

Transition validée
Une transition est dite validée si toutes les places en amont (c’est-à-dire en entrée)
de celle-ci possèdent au moins une marque. Une transition source est par définition
toujours validée.

Dans l’exemple de l’atelier de coupe, la transition T3 est validée ainsi que la

transition T1 (transition source). La transition T2 n’est pas validée.

Franchissement ou tir
Si la transition est validée, on peut effectuer le franchissement de cette transition :
on dit alors que la transition est franchissable. Le franchissement consiste à

– retirer une marque dans chacune des places en entrée de la transition ;

– ajouter une marque à chacune des places en sortie.

Dans l’exemple de l’atelier de coupe (figure 5), le franchissement de T3 mène au

marquage suivant :
Y.ZENNIR Système à Evènements Discrets 54
 Evolution d’un RdP
1 
 3
M = 
0 
 
 3

Remarque
Une transition validée est ici forcement franchissable : les deux termes peuvent être
donc employés indifféremment.
Lorsqu’une transition est validée, cela n’implique pas qu’elle sera immédiatement
franchie. Cela veut dire que les conditions nécessaires à son franchissement sont
effectivement réunies : l’action et/ou l’événement associé à la transition sont alors
possibles.

Dans l’exemple de l’atelier de coupe, pour que la machine de coupe commence la

commande (franchissement de la transition T2), il est nécessaire que la machine soit
disponible (une marque dans la place P1) et qu’au moins une commande soit en
attente (au moins une marque dans la place P2). Cela ne veut pas dire que la machine
va commencer `a traiter immédiatement la commande.
Y.ZENNIR Système à Evènements Discrets 55
 Evolution d’un RdP

Dans le cas d’un réseau de Petri “de base” (par exemple pas d’utilisation de
temporisation), le franchissement, une fois décidé, est instantané.

Dans l’exemple de l’atelier de coupe, les transitions T2 et T3 correspondent au début

et à la fin du traitement de la commande par la machine de coupe.

Figure 7
Y.ZENNIR Système à Evènements Discrets 56
 Notion de RdP autonome et non autonome

Un RdP autonome décrit le fonctionnement d’un système de façon autonome, c’est-

à-dire dont l’évolution est régi par ses propres lois. La succession des quatre saisons
peut être ainsi modélisée par un RdP autonome.

L’état du système est caractérisé par :

Figure 8 :
Quatre saisons

Y.ZENNIR Système à Evènements Discrets 57

 Notion de RdP autonome et non autonome

On suppose qu’à l’instant initial t = 0, la saison est l’´été. On obtient alors le RdP
représenté (figure 8).

Il s’agit ici de donner une description qualitative du cycle des saisons. Si le

franchissement d’une transition est conditionné par un événement, un ordre
extérieur ou encore par le temps, on parle alors de RdP non autonome.

Le RdP décrivant le fonctionnement de l’atelier de coupe est-il autonome ?

Si non, comment le rendre autonome ?

Y.ZENNIR Système à Evènements Discrets 58

 Exemples de Réseaux de Petri Modèle d’une réaction chimique

Modèle d’une réaction chimique On considère maintenant la réaction chimique

suivante qui se produit en présence de catalyseur (platine) :

H 2 + C2 H 4 Platine
→ C2 H 6

L’état du système est caractérisé par :

– La quantité de H2 (nombre de marques dans la place P1)

– La quantité de C2H4 (nombre de marques dans la place P2)
– La quantité de platine (nombre de marques dans la place P3)
– La quantité de C2H6 (nombre de marques dans la place P4)

L’état du système va évoluer quand :

– La réaction chimique se produit (franchissement de la transition T1)

Y.ZENNIR Système à Evènements Discrets 59

 Modèle d’une réaction chimique

Figure 9 : Réaction chimique

On suppose qu’au départ on a deux unités d’H2, une unité de C2H4, une unité de C2H6 et
que le platine est libre.
Le nombre de marques dans chaque place correspond ici à la quantité de chaque produit
chimique. La présence de platine est absolument nécessaire à la réaction chimique : la
place P3 doit être impérativement en entrée de la transition T1. Cependant, quand la
réaction chimique se produit, le platine étant un catalyseur, il n’est pas consommé. Par
suite, la place P3 doit être en sortie de la transition T1 de façon à restituer la ressource
après que la réaction se soit produite.

Y.ZENNIR Système à Evènements Discrets 60

 Modèle d’une réaction chimique
La réaction chimique a été supposée être un événement instantané. En réalité, la
réaction a une certaine durée caractérisée par un début (où les réactifs se fixent sur le
catalyseur afin de réagir) et par une fin (les réactifs ont fini de réagir et libère le
catalyseur).

On introduit donc une place supplémentaire P5 qui indique si oui (une marque dans
P5) ou non (pas de marque dans P5) les produits réagissent `a la surface du
catalyseur. Une transition supplémentaire T2 est introduite : le franchissement de T1
correspond maintenant au début de la réaction chimique et le franchissement de T2
à la fin de celle-ci.

Y.ZENNIR Système à Evènements Discrets 61

 Modèle d’opérations sur deux entiers naturels

Soient n1 et n2 deux entiers naturels. On veut modéliser l’addition de ses deux

entiers par un RdP.
L’état du système est caractérisé par :

– Le nombre n1 à l’instant initial (nombre de marques dans la place P1)

– Le nombre n2 à l’instant initial (nombre de marques dans la place P2)
– La somme n1 + n2 à l’instant final (nombre de marques dans la place P3)

L’état du système va évoluer quand :

– Une marque est enlevée de P1 pour être placée dans P3 (franchissement de la

transition T1)
– Une marque est enlevée de P2 pour être placée dans P3 (franchissement de la
transition T2)

Y.ZENNIR Système à Evènements Discrets 62

 Modèle d’opérations sur deux entiers naturels

Opérations sur des entiers naturels : Addition

Figure 10

On veut maintenant modéliser la soustraction de ces deux entiers par un RdP. La

soustraction est définie de la façon suivante : si n1  n2 alors le résultat est n1- n2,
sinon le résultat est 0.
L’état du système est caractérisé par :
– Le nombre n1 à l’instant initial (nombre de marques dans la place P1)
– Le nombre n2 à l’instant initial (nombre de marques dans la place P2)
– La résultat de l’opération à l’instant final (nombre de marques dans la place P3)
L’état du système va évoluer quand :
– Une marque est enlevée de P1 pour être placée dans P3 (franchissement de la
transition T1)
– Une marque est enlevée de P2 et de P3 (franchissement de la transition T2)
Y.ZENNIR Système à Evènements Discrets 63
 Modèle d’opérations sur deux entiers naturels

Opérations sur des entiers naturels : soustraction

Figure 11

Exemple :

On considère maintenant la multiplication de ces deux entiers. Le RdP obtenu est

représenté par la graphe suivant. A l’instant initial, la place P1 contient n1 marques
et la place P2 contient n2 marques. A l’instant final, la place P6 contient n1* n2
marques.

Vérifier que ce modèle RdP représente bien la multiplication des deux entiers ?.

Y.ZENNIR Système à Evènements Discrets 64

 Modèle d’opérations sur deux entiers naturels

Figure 12
Opérations sur des entiers naturels : multiplication

Y.ZENNIR Système à Evènements Discrets 65

 Réseaux de Petri avec une structure particulière

La structure d’un Réseau de Petri est définie par le RdP non marqué qui a été noté
Q dans la définition précédente.

Les RdPs avec une structure particulière ont des propriétés que n’ont pas
forcement les RdPs en général.
Graphe d’états

Un réseau de Petri est un graphe d’états si et seulement si toute transition a

exactement une place d’entrée et une place de sortie.

Figure 13

Graphe d’états ou pas

Y.ZENNIR Système à Evènements Discrets 66
 Réseaux de Petri avec une structure particulière
Graphe d’événements
Un réseau de Petri est un graphe d’événements si et seulement si toute place a
exactement une transition d’entrée et une transition de sortie.

Figure 15

Graphe d’événements ou pas

Y.ZENNIR Système à Evènements Discrets 67

 Réseaux de Petri avec une structure particulière

RdP sans conflit

Un réseau de Petri est dit sans conflit si et seulement si toute place a au plus une
transition de sortie.
Un conflit (structurel)
Correspond à l’existence d’une place Pi qui a au moins deux transitions de sortie
Tj , Tk, etc..

Notation < Pi; Tj ; Tk; …. >.

Sur le RdP de droite de la figure suivante, on a le conflit < P1;  T2; T3  >.
Quand la place P1 contient une marque, les transitions T1 et T2 sont
franchissables.
Seule une des deux transitions peut être franchie : il est nécessaire de prendre une
décision pour savoir laquelle des deux le sera effectivement.

L’absence ou la présence d’un conflit est une propriété importante d’un réseau de
Petri.
Y.ZENNIR Système à Evènements Discrets 68
 Réseaux de Petri avec une structure particulière

Figure 16

Sans conflit Avec conflit

RdP à choix libre : Un RdP est dit à choix libre si et seulement si les transitions
de sortie de tous ses conflits n’admettent qu’une seule place d’entrée.

RdP à choix libre étendu : Un RdP est dit à choix libre étendu si et seulement si
pour chaque conflit, toutes les transitions de sortie de celui-ci admettent les
mêmes places d’entrée.

Exemple : soit un RdP à choix libre étendu qui admet le conflit <P1,  T2, T3>.
Si T2 admet aussi pour place d’entrée P2 alors forcement T3 admet P2 comme
place d’entrée.
Y.ZENNIR Système à Evènements Discrets 69
 Réseaux de Petri avec une structure particulière

RdP simple Un réseau de Petri est dit simple si et seulement si toutes ses
transitions n’interviennent que dans un seul conflit au maximum.
Le RdP représenté dans la Figure 17 A est simple ; celui représenté dans la
Figure 17. B n’est pas simple.

Figure 17.A: RdP simple

Figure 17.B RdP qui n’est pas simple

Y.ZENNIR Système à Evènements Discrets 70

 Réseaux de Petri avec une structure particulière
RdP pur : Un RdP est dit pur si et seulement s’il n’existe pas de transition ayant
une place d’entrée qui est aussi place de sortie. Le RdP représenté par la Figure 9
n’est pas pur car la place P3 est place d’entrée et place de sortie de la transition
T1. On parle alors de RdP impur.

Propriété Tout RdP impur peut être transformé en un RdP pur.

Le RdP représentant une réaction chimique Figure 9, `a gauche n’est pas pur
puisque la place P3 est à la fois place en entrée et en sortie de la transition T1.
Par contre, une description plus fine de la réaction chimique a donné le RdP
Figure 9, `a droite. Ce RdP est pur. Cependant, il est plus complexe. Cet exemple
montre que des “transitions impures” peuvent ainsi introduites
pour simplifier le modèle RdP d’un système. Un autre exemple est donné par les
deux RdPs représentés Figure 18 qui sont équivalents.

Y.ZENNIR Système à Evènements Discrets 71

 Réseaux de Petri avec une structure particulière

Figure 18
RdP impur équivalent à un RdP pur

Y.ZENNIR Système à Evènements Discrets 72

 Structures fondamentales pour la modélisation des systèmes
Les RdPs permettent de modéliser un certain nombre de comportements
importants dans les systèmes : le parallélisme, la synchronisation, le partage de
ressources, la mémorisation et la lecture d’information, la limitation d’une capacité
de stockage. Dans cette section, sont présentées les différentes structures
apparaissant dans un réseau de Petri reproduisant ce type de comportements.
Eléments de modélisation
Parallélisme
Le parallélisme représente la possibilité que plusieurs processus évoluent
simultanément au sein du même système. On peut provoquer le départ simultané de
l’évolution de deux processus à l’aide d’une transition ayant plusieurs places de
sortie. Pour cela, le RdP doit contenir la structure présentée Figure 19, gauche. Par
convention, lorsqu’un carré grisé apparaît dans une figure, cela indique que seule
une partie du RdP a été représentée : pour la compréhension de l’explication, le reste
du RdP est supposé ne pas être important. Le franchissement de la transition T1 met
une marque dans la place P2 (ce qui marque le déclenchement du processus 1) et une
marque dans la place P3 (ce qui marque le déclenchement du processus 2).
Il est ensuite
Y.ZENNIR Système à Evènements Discrets 73
 Structures fondamentales pour la modélisation des systèmes

possible de synchroniser l’achèvement des deux processus, voir Figure 19,

droite. La place P22 correspond `a la fin du processus 1 et la place P23 `a la fin
du processus 2. Le RdP évoluera par franchissement de la transition T12. Pour
cela, il est nécessaire que les places P22 et P23 contiennent chacune au moins
un jeton, c’est-`a-dire que les processus 1 et 2 soient terminés. Le RdP total est
représenté Figure 21.

Figure 19 :
Parallélisme

Y.ZENNIR Système à Evènements Discrets 74

 Structures fondamentales pour la modélisation des systèmes

Figure 20 :
Parallélisme

Y.ZENNIR Système à Evènements Discrets 75

 Figure 21

Y.ZENNIR Système à Evènements Discrets 76

 Structures fondamentales pour la modélisation des systèmes

La machine à remplir et à boucher La machine à remplir et à boucher des

bouteilles est composée de trois postes travaillant en parallèle.

– Le poste 1 sert au transfert et au chargement. Dans un premier temps, on sort le

vérin de transfert B pour à décaler le convoyeur d’une position vers la droite.
Ensuite, le vérin A sert au chargement d’une nouvelle bouteille vide.

– Le poste 2 sert au remplissage des bouteilles à l’aide de la vanne D.

Le poste 3 est le poste de bouchage.

Les actions de chargement d’une bouteille, remplissage d’une bouteille et bouchage

d’une bouteille sont effectuées en parallèle. Le transfert par le vérin B n’est effectué
que lorsque ces trois opérations sont terminées.

Y.ZENNIR Système à Evènements Discrets 77

 Synchronisation

Mutuelle
La synchronisation mutuelle ou rendez-vous permet de synchroniser les opérations
de deux processus.

Un exemple est donné Figure 2.20. Le franchissement de la transition T7 ne peut se

faire que si la place P12 du processus 1 et la place P6 du processus 2 contiennent
chacun au moins une marque. Si ce n’est pas le cas, par exemple la place P12 ne
contient pas de marque,

Y.ZENNIR Système à Evènements Discrets 78

 RdP machine à remplir et à boucher Synchronisation mutuelle

le processus 2 est “bloqué” sur la place P6 : il attend que l’évolution du

processus 1 soit telle qu’au moins une marque apparaisse dans la place P12.

Y.ZENNIR Système à Evènements Discrets 79

 Exemple
On considère un système magasin/consommateur. Le magasin vend un seul
type de produits entreposés dans un stock de capacité limité : son état est
caractérisé par le nombre de produits en stock et par le nombre d’emplacements
libres dans le stock.

Le nombre de produits disponibles dans le magasin augmente quand le magasin

est livré et diminue quand le consommateur effectue un achat. Le
consommateur a deux états : soit il consomme, soit il va faire ses courses.

On suppose qu’`a l’instant initial, le magasin a deux emplacements de libre et un

seul produit stocké et que le consommateur est en train de consommer.

Y.ZENNIR Système à Evènements Discrets 80

RdP système magasin/consommateur

Sémaphore
Les opérations du processus 2 ne peuvent se poursuivre que si le processus 1 a atteint
un certain niveau dans la suite de ses opérations. Par contre, l’avancement des
opérations du processus 1 ne dépend pas de l’avancement des opérations du processus
2. D’après Figure 2.22, le processus 2 ne peut franchir la transition T8 que si la place
P0 contient au moins une marque. Une marque est ajoutée dans la place P0 lorsque
l’évolution du processus 1 amène le franchissement de la transition T17. L’évolution du
processus 2 va donc dépendre de l’évolution
Y.ZENNIR Système à Evènements Discrets 81
 Sémaphore

Exemple
On désire effectuer deux opérations : a  b + e et a  b + c  d
On dispose de deux processeurs pouvant travailler en parallèle. Afin de
gagner du temps, on décide que le premier processeur effectuera
l’opération a£b tandis que parallèlement le second effectuera l’opération
cd. Quand le processeur 1 aura terminé le produit, il y ajoutera e. Quand
le processeur 2 aura terminé l’opération c  d, si le processeur 1 a terminé
le produit a  b, il fera la somme des deux produits, sinon il attendra que le
produit a£b soit terminé pour pouvoir l’effectuer.
Y.ZENNIR Système à Evènements Discrets 82
 L’état du système est caractérisé par :
– le processeur 1 effectue l’opération a  b (une marque dans la place P1)
– le processeur 2 effectue l’opération c  d (une marque dans la place P2)
– le résultat de a  b est disponible (une marque dans la place P3)
– le résultat de c  d est disponible (une marque dans la place P4)
– le processeur 1 effectue l’addition (a  b) + e (une marque dans la place P5)
– le processeur 2 effectue l’addition (a  b) + (c  d) (une marque dans la place
P6)

L’état du système va évoluer quand :

– fin de l’opération a  b (franchissement de la transition T1)
– fin de l’opération c  d (franchissement de la transition T2)
– début l’addition (a  b) + (c  d) (franchissement de la transition T3)

A l’instant initial, le processeur 1 effectue l’addition (a  b) + e, que le résultat de

a  b est disponible et que le processeur 2 effectue l’opération c  d.
Y.ZENNIR Système à Evènements Discrets 83
 Calculs parallèles

Y.ZENNIR Système à Evènements Discrets 84

Partage de ressources

Cette structure va modéliser le fait qu’au sein du même système plusieurs processus
partagent une même ressource. Figure 2.24, la marque dans la place P0 représente une
ressource mise en commun entre le processus 1 et le processus 2. Le franchissement de
la transition T17 lors de l’évolution du processus 1 entraîne la “consommation” de la
marque présente dans la place P0. La ressource que constitue cette marque n’est alors
plus disponible pour l’évolution du processus 2 puisque le franchissement de la
transition T7 n’est plus possible. Lors de l’évolution du processus 1, lorsque la
transition T18 est franchie, une marque est alors “redonnée” `a la place
P0 : la ressource redevient alors disponible pour l’évolution des deux processus.

Partage d’une mémoire par deux programmes informatiques

Deux programmes informatiques, programme 1 et programme 2 partagent un espace

mémoire unique. Quand un des deux programmes l’utilise, l’autre ne peut pas y avoir
accès. L’état du système est caractérisé par :

Y.ZENNIR Système à Evènements Discrets 85

 Partage de ressource

Y.ZENNIR Système à Evènements Discrets 86

 A l’instant initial, les deux programmes n’ont pas besoin de la mémoire qui est donc
disponible.

Partage d’une mémoire par deux programmes

Y.ZENNIR Système à Evènements Discrets 87