Ecole Mohammadia d’Ingénieurs

3ème année

TD 2 SED
RdP Autonomes

EXERCICE 1 : Modélisation de deux calculateurs utilisant une mémoire commune

Deux calculateurs utilisent une mémoire commune. On suppose que chaque calculateur peut
avoir trois états : soit il n’a pas besoin de la mémoire, soit il la demande mais ne l’utilise pas encore,
soit il l’utilise.

Questions :
1- Modéliser le fonctionnement de ce système par un RdP.
2- Quels sont les invariants de marquage minimaux de ce RdP. Le réseau complet est-il
conservatif ?

Mémoire
Calculateur 1 Calculateur 2
commune

EXERCICE 2 : Gestion des cabines et des paniers d’une piscine

On considère le protocole suivant de gestion des cabines et des paniers d’une piscine. A
l’entrée, un client qui a trouvé une cabine libre y entre et se change en posant ses vêtements dans la
cabine. Il demande ensuite un panier qu’il remplit pour libérer la cabine. Après la baignade, le client
rentre dans une cabine avec son panier, le vide et le libère. Ensuite il se rhabille et libère la cabine.

Questions :
1- Soit Nc le nombre de cabines et Np le nombre de paniers. Modéliser ce protocole avec
Nc=3 et Np=5.
2- Le nombre de clients à la baignade (c’est-à-dire après déshabillage et avant rhabillage)
est-il borné ?
3- Montrer qu’il y a un état de blocage. Y a-t-il blocage pour toutes valeurs de Nc et Np ?
4- Proposer un protocole légèrement différent permettant d’éviter ce blocage.

EXERCICE 3 : Modélisation d’un système informatique multitâche

Supposons que deux tâches à exécuter sur ordinateur se partagent une même unité centrale.
Une exécution à tour de rôle (Round Robin) consiste à exécuter une partie de la tâche 1, puis une
partie de la tâche 2 (par exemple une instruction de chaque tâche) et ainsi de suite.

1
 Questions :
1- Modéliser par un RdP autonome ordinaire l’exécution à tour de rôle de quatre tâches,
avec exécution d’une instruction de chaque tâche à chaque fois. Donner le marquage
initial en supposant qu’au départ, les tâches 1, 2, 3 et 4 sont en attente et que seule la
tâche 1 est autorisée.
2- Modéliser par un RdP généralisé l’exécution à tour de rôle de deux tâches avec les taux
suivants : 3 instructions de la tâche 1 puis 5 instructions de la tâche 2. Donner le
marquage initial en supposant qu’au départ, les tâches 1 et 2 sont en attente et que seule
la tâche 1 est autorisée. Déterminer à partir du graphe les invariants linéaires de places
de ce RdP généralisé, les interpréter et retrouver ce résultat par le calcul.

EXERCICE 4 : Modélisation d’un système Producteur-Consommateur

Un « producteur » produit une seule pièce à la fois. Quand sa production est finie, il dépose la
pièce produite dans un stock s’il y a de la place libre dans ce stock dont la capacité est de 3 unités.
Dès qu’il a pu faire le dépôt, il commence à produire une autre pièce. Un « consommateur », dès qu’il
a fini de consommer (une seule pièce à la fois), prélève une pièce dans le stock s’il n’est pas vide. La
figure 4 représente ce système de production.

Dépôt Retrait

Producteur Stock Consommateur

(capacité 3)

Questions :
1- Représenter le fonctionnement de ce système par un RdP avec un marquage initial
correspondant à la figure ci-dessus.
Ce RdP est constitué de 6 places et de 4 transitions :
P1 : producteur prêt à déposer
P2 : producteur en cours de production
P3 : emplacements libres dans le stock
P4 : pièces en stock
P5 : consommateur en cours de consommation
P6 : consommateur prêt à consommer

T1 : fin de production
T2 : dépôt
T3 : retrait
T4 : fin de consommation

2- Calculer les invariants de marquage de ce système. Quelles sont leurs

significations ?

EXERCICE 5 : Modélisation d’une ligne de fabrication

On considère l’atelier à flot symbolisé sur la figure suivante :

p1, p2 p1, p2
M1 M2

ST1 ST2 2
 Des pièces arrivent dans le stock ST1, passent sur la machine M1, puis dans le stock ST2, et
enfin sur la machine M2 avant de sortir de l’atelier. Les stocks ont une capacité illimitée. Il ne peut y
avoir qu’une seule pièce sur chaque machine.
Il y a deux types de pièces, p1 et p2. Les pièces arrivent dans un ordre quelconque (elles sont
donc placées en vrac dans ST1), mais elles passent sur les machines dans un ordre bien défini : c’est
une alternance p1 puis p2 puis p1…

Question : Décrire ce fonctionnement par un RdP.

EXERCICE 6 : Ordonnancement de tâches

On considère un ordonnancement de tâches PERT (Program Evaluation and Review

Technique) avec recyclage. On définit 4 tâches dont les exécutions sont conditionnées par les règles
suivantes.
Au départ, seule la tâche 1 est exécutable. Les tâches 2 et 3 ne peuvent être exécutées
qu’après la fin de la tâche 1 (attention : cela ne signifie pas qu’elles commencent simultanément). La
tâche 4 ne peut être exécutée qu’après la fin des tâches 2 et 3.
Enfin, la tâche 1 ne peut être réexécutée qu’après la fin de la tâche 4 et le cycle recommence
indéfiniment.

Questions :

1- Modélisez ce système par un RdP autonome en tenant compte des indications suivantes.
Places du RdP : P1 : la tâche 1 est exécutable
P2 : la tâche 1 est terminée et la tâche 2 est donc exécutable
P3 : la tâche 1 est terminée et la tâche 3 est donc exécutable
P4 : la tâche 2 est terminée
P5 : la tâche 3 est terminée
EXi (i = 1, 2, 3, 4) : la tâche i est en cours d’exécution

Transitions du RdP : T1 : début d’exécution de la tâche 1

T2 : fin d’exécution de la tâche 1
T3 : début d’exécution de la tâche 2
T4 : début d’exécution de la tâche 3
T5 : fin d’exécution de la tâche 2
T6 : fin d’exécution de la tâche 3
T7 : début d’exécution de la tâche 4
T8 : fin d’exécution de la tâche 4
2- Quel est le graphe de marquage de ce RdP? A partir de ce graphe, déterminer 2
séquences répétitives de franchissement minimales.
3- Déterminer graphiquement à partir du RdP 2 invariants de marquage minimaux. A l’aide
du graphe des marquages, vérifier les équations obtenues.
4- Ce RdP est-il borné ? avec ou sans blocage ? vivant ? répétitif ? conservatif ? avec ou sans
conflit ? Justifiez vos réponses en vous référant au graphe des marquages.

3
EXERCICE 7 : Arbre de couverture d’un RdP

On considère le RdP suivant, avec le marquage initial M0 = (1,1,0,0).

P1 P2

T1

P3

T2

P4

T3

Question : Construire l’arbre de couverture de ce RdP et utilisez-le pour montrer que le

marquage vide (0,0,0,0) n’est pas atteignable.

EXERCICE 8 : Graphe des marquages d’un RdP

Soit le RdP généralisé défini par :

L’ensemble des places : P = {P1, P2, P3}
L’ensemble des transitions : T = {T1, T2, T3} 2 0 1 0 0 1
Les matrices d’incidence avant et arrière : W- = et W+ =
1 1 0 1 0 1
Questions : 0 0 1 1 1 0

1- Dessiner le RdP correspondant en complétant la figure ci-contre.

P1 P2
2- Soit M0 =
1 le marquage initial de ce RdP.
0 T1
T3 T2
1
Donner alors le graphe des marquages de ce RdP. P3
A partir du graphe des marquages et sans faire de calculs :
Que peut-on dire concernant la transition T 1 ? Ce RdP est-il vivant ? Est-il conservatif ?
réinitialisable ? Justifier les réponses.

3- Soit M’0 = 2 un autre marquage initial de ce RdP.

1
1
Donner de nouveau le graphe des marquages de ce RdP. Y a-t-il blocage ? Ce RdP est-il
vivant ? Justifier les réponses.

4
EXERCICE 9 : Modélisation de chariots

Figure 1- Un seul chariot

1- Un chariot Ch1 transporte du matériel d’un point de chargement C1 à un point de

déchargement D en empruntant une voie ferrée unique découpée en deux secteurs
S1 et S0 (voir figure 1). Au départ, le chariot stationne sur le point de chargement
C1. Il emprunte le secteur S1 puis S0 de la voie ferrée pour arriver au point de
déchargement D. Après avoir stationné en D, il emprunte le secteur S0 puis S1 afin
de regagner le point de chargement.

Représenter le fonctionnement du chariot par un RdP ordinaire. Le modèle doit

prendre en compte le fait qu’il ne peut y avoir qu’un seul chariot, que ce soit dans le
point de chargement C1 ou le secteur S0 ou le secteur S1 ou encore le point de
déchargement D. On définira avec soin :
-les places (10)
-les transitions (7)
-le marquage initial.

Figure 2- Deux chariots

2- Un deuxième chariot Ch2 transporte du matériel d’un second point de chargement

C2 au point de déchargement D en empruntant une voie ferrée découpée en deux
secteurs S1 et S0 (voir figure 2). Au départ, le chariot Ch1 (respectivement Ch2) est
sur le point de chargement C1 (resp. C2). Noter que le point de déchargement D et
le secteur S0 sont communs aux chariots Ch1 et Ch2. Le chariot Ch1
(respectivement Ch2) sur la voie S1 (resp. S2) ne peut emprunter la voie S0 que si
cette voie et le point de déchargement D sont libres.

5
 Représenter le fonctionnement de cet ensemble de deux chariots par un RdP
ordinaire. On définira avec soin :
-les places (18)
-les transitions (12)
-le marquage initial.

EXERCICE 10 : Pilotage KANBAN

Figure 1

La Figure 1 représente la conduite d’un système de production par kanban. Un « kanban »

est un mot japonais qui signifie « étiquette ». Le système de production est constitué de deux mailles
en série. La maille i (i=1, 2) est composée du système de production i et de son stock de produits finis
STi.
A l’entrée du système, les pièces sont stockées dans le stock ST 0 (jamais vide). Pour qu’une
pièce du stock STi-1 soit traitée par le système de production i, il faut qu’elle porte un kanban i.
Lorsque son traitement par le système i est terminé, elle est déposée dans le stock ST i avec son
kanban qui lui reste attribué. Quand une pièce est retirée du stock ST i pour être traitée par le système
i+1 ou pour satisfaire la demande d’un client, on la sépare de son kanban i (qui est ramené à l’entrée
du système i) et on lui adjoint un kanban i+1 si elle doit être traitée par le système i+1. Chaque
système de production ne peut traiter qu’une seule pièce à la fois.

Un nombre fixe de kanbans est attribué à chaque maille du système : trois kanbans de type 1
pour la maille 1 et deux kanbans de type 2 pour la maille 2.

A l’état initial :
- Les systèmes de production 1 et 2 sont libres.
- Le stock ST1 contient 3 produits finis de la maille 1 (produits semi-finis du
système), munis de leurs kanbans de type 1.
- Le stock ST2 contient 2 produits finis de la maille 2 (produits finis du système),
munis de leurs kanbans de type 2.
- Aucune demande de production (en provenance du consommateur) n’a été
enregistrée.

1- Modéliser le fonctionnement de ce système de production à l’aide d’un RdP ordinaire,

constitué de 10 places et de 5 transitions que vous définirez avec soin. Indiquez le marquage
initial.

Indications de places :
ST0 : pièces brutes dans le stock ST0.
STi: paires (pièce, kanban) de la maille i dans le stock STi. (i=1,2).
SPOi : système de production i occupé par une paire (pièce, kanban). (i=1, 2)
SPLi : système de production i libre. (i=1, 2)
Ki : kanbans de type i libres à l’entrée de la maille i. (i=1, 2).
DA : demandes de production (en provenance du consommateur) en attente.

6
 2- En ne considérant pas les places ST0 et DA (non bornées), déterminer graphiquement les
invariants de marquage de ce RdP, les interpréter. En déduire les bornes supérieures relatives à
chacune des places de ce RdP.

3- Que se passe-t-il, si à partir d’un état quelconque du système (pas forcément l’état initial), on
arrête l’arrivée des demandes externes et on attend suffisamment longtemps ?

EXERCICE 11 : Usine de recyclage

On considère le recyclage de produits de deux types p 1 et p2, par une usine équipée de deux
machines M1 et M2.
La machine M1 permet le recyclage complet de produits p1 ou p2.
La machine M2 ne permet que le recyclage de produits de type p2.
Chaque machine ne peut recycler qu’un seul produit à la fois.
A la sortie de l’usine de recyclage, les produits de type p 1 (respectivement p2) sont utilisés par
les consommateurs avant d’être renvoyés à l’usine de recyclage. A l’instant initial, les consommateurs
utilisent N1 produits de type p1 et N2 produits de type p2 ; les machines M1 et M2 sont disponibles.

Questions :

I) Modélisation de l’usine de recyclage

Donner le modèle RdP de ce système en complétant la Figure 2, et en n’oubliant pas

d’indiquer le marquage initial. Définir également les 6 transitions de ce RdP.

P5
P1

T5
T1 T3
P6 P7
P2 P3 P4

T6
T2 T4

Figure 1

Indications de places :
P1 : produits p1 en cours d’utilisation par le consommateur P5 : produits p2 en cours d’utilisation par le consommateur
P2 : produit p1 en cours de recyclage par M1 P6 : produit p2 en cours de recyclage par M2
P3 : machine M1 disponible P7 : machine M2 disponible
P4 : produit p2 en cours de recyclage par M1

Transitions :
T1 : T4 :
T2 : T5 :
T3 : T6 :

7
 II) Etude du RdP par Algèbre Linéaire

a) Déterminer les matrices d’incidence avant et arrière de ce RdP. En déduire la matrice

d’incidence.
Matrices d’incidence :

T1 T2 T3 T4 T5 T6 T1 T2 T3 T4 T5 T6 T1 T2 T3 T4 T5 T6
P1 P1 P1
P2 P2 P2
P3 P3 P3
W- = P4 W+ = W= P4
P4
P5 P5 P5
P6 P6 P6
P7 P7 P7

b) Déterminer les P-semi-flots de ce RdP.

c) En déduire les invariants de marquage minimaux et les interpréter.
d) Déterminer les T-semi-flots de ce RdP.
e) En déduire les séquences répétitives minimales de ce RdP et les interpréter.