Td4: RDP - Révision: Exercice 1
Td4: RDP - Révision: Exercice 1
Td4: RDP - Révision: Exercice 1
Exercice 1 :
Pour chacun des RdP de la figure suivante, dont certains sont des RdP généralisés,
répondre aux questions : est-il borné ? Vivant ? Sans blocage ? Justifier votre réponse.
Exercice 2 :
Deux calculateurs utilisent une mémoire commune. On suppose que chaque
calculateur peut avoir trois états :
• - il n’a pas besoin de la mémoire
• - il la demande mais ne l’utilise pas encore
• - il l’utilise
Exercice 3 :
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 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. Soit Nc le nombre de cabines et Np le
nombre de paniers.
1. 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é ? Justifier votre réponse.
3. Montrer qu'il y a un état de blocage. Y-a-t-il blocage pour toutes valeurs de Nc et
de Np ?
4. Définir un protocole tel qu'il n'y aurait plus de blocage. Donner le Réseau de Petri
correspondant.
Exercice 4 :
On considère un système de production composé de quatre machines (de capacité
unitaire chacune), chaque machine ayant un stock d’entrée. Ce système produit trois
types de pièces : p1, p2 et p3.
La gamme de fabrication des pièces p1 correspond au passage sur la machine 1,
ensuite sur la machine 2 et enfin sur la machine 4. La gamme de fabrication d’une pièce
p2 correspond au passage sur la machine 1, puis sur la machine 3 et enfin sur la
machine 4. La gamme de fabrication d’une pièce p3 correspond au passage sur la
machine 1, puis sur la machine 3 et enfin sur la machine 4.
Les machines 1 et 4 étant des ressources partagées, on impose l’ordonnancement
suivant sur ces machines : une pièce p1, puis une pièce p3 et enfin une pièce p2. Seules
les pièces p1 passent sur la machine 2. Sur la machine 3, les pièces passent
systématiquement dans l’ordre suivant : une pièce p3, puis une pièce p2.
Les stocks en amont des machines sont supposés infinis. Les pièces sont portées par
des palettes recyclées à chaque fin de cycle. On dispose de n palettes pour les pièces
p1, n palettes pour les pièces p2 et n palettes pour les pièces p3. Ces palettes sont
initialement dans le stock ST1 en amont de la machine 1.
En prenant les couleurs <pi,mj> où pi représente une pièce et mj représente une
machine, construire le RdP coloré décrivant ce système de production. On définira avec
soin les ensembles de couleurs associées aux transitions et les fonctions associées aux
arcs.
Exercice 5 :
§ Deux chariots, C1 et C2, se déplacent indépendamment sur deux voies
distinctes.
§ Le contact M1 commande, si C1 est en A1, le cycle A1 – B1 – A1 avec chargement
en A1 et déchargement en B1.
§ Le contact M2 commande, si C2 est en A2, le cycle A2 – B2 – A2 avec chargement
en A2 et déchargement en B2.
§ L’opération de déchargement est ecectuée par un pont roulant unique, qui est
une ressource partagée entre C1 et C2.
§ Lorsque l’un des chariots, noté Ci, arrive en Bi, la procédure suivante est
appliquée : si la ressource est libre, elle est alors occupée, le chariot est
déchargé, puis la ressource est libérée. Si la ressource est occupée, le
chariot est mis en attente jusqu'à ce que la ressource se libère.
Modéliser par RdPIC la partie opérative de ce système.
§ Ne jamais tester un capteur et prendre une ressource en même temps.
§ Priorité statique à C1.
Exercice 6 :
Nous considérons le Réseau de Petri P-temporisé (RdP P-temporisé) suivant.
1. Construire son graphe de marquage des états stables en indiquant les durées
d’indisponibilité des jetons.
2. Calculer les fréquences de franchissement pour un fonctionnement à vitesse
maximale.
Solutions
1.
2.
3.
La séquence de franchissement (T1T2T3)5T13 conduit au marquage (3,0,5,0,0,0,0)
qui est un blocage : Il y a 5 personnes qui sont à la baignade et 3 dans les cabines en
attente de paniers qui ne se libéreront jamais.
En général : ∀ Nc et Np, la séquence (T1T2T3)NpT1Nc conduit à un blocage.
Le client qui entre a besoin de deux ressources qui sont une cabine et un panier, s’il
les prend simultanément quand les deux sont libres il n’y a pas de blocage. Le RdP
(b) modifié montre que la transition T1 en amont de P1 ne sera franchise que si un
panier ET une cabine sont libre simultanément.
On ajoute une transition T0 et une place P0 (en pointillés sur le RdP (b)) : Le
franchissement de T0 (arrivée d’un client) ajoute un jeton dans P0 (nombre de
clients en attente).
4.
5.
6.
M0 : [(0;0;0;) () () (0;) (0;) ]^T
M1 : after firing of T1 T3 / 0 / : [(0;) (3;) (4;) () () ]^T
M2 : after firing of T2 T1 / 3 / : [(1;) (3;) (1;) () () ]^T
M3 : after firing of T4 T3 / 1 / : [(1;) (2;) (4;) () () ]^T
M4 : after firing of T2 T1 / 2 / : [(1;) (3;) (2;) () () ]^T
M5 : after firing of T4 T3 / 2 / : [(1;) (1;) (4;) () () ]^T
M6 : after firing of T2 T1 / 1 / : [(1;) (3;) (3;) () () ]^T
M7 : after firing of T2 T4 T1 / 3 / : [(1;1;) (3;) () () (0;) ]^T
M8 : after firing of T3 / 1 / : [(0;) (2;) (4;) () () ]^T
M4 : after firing of T2 T1 / 2 / : [(1;) (3;) (2;) () () ]^T
P = 2+2+1+3+1=9 u.t.
f1=3/9 fr/u.t.
f2= 3/9 fr/u.t.
f3=2/9 fr/u.t.
f4=2/9 fr/u.t.