Département Informatique
FEI, USTHB
M1 Master RSD
Série d’Exercices 01
Exercice 1 Soit le réseau de Petri suivant:
p1 p0 p2
t1 t5 t2
p3 p5 p4
t3 t4
1. Donner les matrices P ré, P ost et la matrice d’incidence.
2. Construire le graphe des marquages accessibles.
Exercice 2 Propriétés des réseaux de Petri
Construire les graphes de couverture des réseaux de Petri ci-dessous, puis donner les
propriétés de chacun.
p1
p1 a
p2 p4
a
p2 c p3 c b
p4 p3 p5
b d
Exercice 3 Feux de circulation
1. Modeliser à l’aide d’un réseau de Petri l’activité d’un feu de circulation tri-colors
2. Modeliser à l’aide d’un réseau de Petri le fonctionnement de deux feux coordonnant
la circulation à l’intersection de deux routes. Un feu de circulation ne peut être au vert
que si l’autre se trouve au rouge. On suppose qu’à l’état initial l’un des feux est au vert
l’autre est au rouge.
3. Donner les matrices P ré et P ost puis le graphe des marquages de ce réseau de Petri
Exercice 4 Partage d’un ressource
Deux processus utilisent une ressource commune mais qui constitue une ressource cri-
tique. Chaque processus peut se trouver dans l’un des états: Pas besoin de la ressource,
demande la ressource mais ne l’a pas encore ou utilise la ressource.
1. Modeliser un tel système à l’aide d’un réseau de Petri.
2. Construire le graphe des marquages accéssibles
Exercice 5 Protocole de connexion/déconnexion
On considère un système constitué de 02 processus qui peuvent se connecter et se décon-
necter selon le protocole:
• La connexion se fait par rendez-vous.
• La déconnexion se fait selon les étapes:
– L’un des processus peut envoyer un demande de déconnexion
– Lorsqu’un processus reçoit un demande de déconnexion, il renvoie un acquit-
tement et se déconnecte
– Lorsqu’un processus reçoit un acquittement, il se déconnecte.
1. Modéliser ce protocole à l’aide d’un réseau de Petri
2. Donner le graphe des marquages.
3. Etudier les propriétés: états de blocage, vivacité. Que peut-on déduire ? Proposer
une correction de ce protocole afin d’enlever cette anomalie.
Solutions
Exercice 1 Les matrices:
t1 t2 t3 t4 t5 t1 t2 t3 t4 t5
p0 1 1 0 0 0 p0 0 0 0 0 1
1
p1 0 0 0 0 0
p1 0 1 0 0
p 0 1 0 0 0 p 0 0 0 1 0
P ré = 2 P ost = 2
0
p3 0 1 0 0 1
p3 0 0 0 0
p4 0 0 0 1 0 p4 0 1 0 0 0
p5 0 0 0 0 1 p5 0 0 1 1 0
La matrice d’incidence
t1 t2 t3 t4 t5 Le graphe des marquages
p0 −1 −1 0
0 1
−1
p1 0 1 0 0
p 0 −1 0 1 0
C = 2
1
p3 0 −1 0 0
p4 0 1 0 −1 0
p5 0 0 1 1 −1
Exercice 2 Les Graphes de couvertures:
10000
1001 a
t1 01010
0101 c b
t2 00110 01001
1010 t3 b c
t1 00101
0110 d
1ω000
c a
Le graphe de couverture du 1er RdP c 1ω010 0ω010 c
a c b
d c 0ωω10 0ω001
b
c 0ωω01
Graphe de couverture du 2ème RdP
Les propriétés :
- Le 1er RdP est borné, vivant, pas d’états de blocage, non réinitialisable.
- Le 2ème RdP n’est pas borné.
Exercice 3 Feux tricolores
1. Le cas d’un seul feu 2. Le cas de deux feux tri- Le GMA:
tricolore: colore:
v v1 v2 v1 , r2
t1
t1 t1 t01
j1 , r2
t3 j j1 j2 t2 t02
t2 t2 t02 r1 , v2
r r1 r2 t01
r1 , j2
Exercice 4 Partage d’une ressource critiques
Le réseau de Petri modélisant le problème Le Graphe des marquages:
de partage d’une ressource critique:
idle1 r idle2
idle1 idle2 ask1 ask2
end1 end2
ask1 ask2
r wait1 r idle2 idle1 r wait2
wait1 wait2 get1 ask2 ask1 get2
end1 end2
get1 get2
use1 idle2 wait1 r wait2 idle1 use2
use1 use2 ask2 get1 get2 ask1
end1 end2
use1 wait2 wait1 use2
Exercice 5 Protocole de connexion-déconnexion
1. Le réseau de Petri :
idle1 idle2
Conn_req1 Conn_req2
wait1 wait2
Connection
con1 con2
Dec_req1 Dec_req2
wAck1 wAck2
rr1 rr2
send_ack1 send_ack2
ar1 ar2
Dec1 Dec2
2. Le Graphe des marquages:
idle1 idle2
Conn_res1 Conn_res2
wait1 idle2 idle1 wait2
Conn_res1 Conn_res2
Dec1 wait1 wait2 Dec2
Connection1
con1 con2
Dec_req1 Dec_req2
wAck1 rr2 con2 con1 rr1 wAck2
send_ack1 Dec_req 2 send_ack2
Dec_req1
wAck1 ar2 wAck1 rr1 rr2 wAck2 ar1 wAck2
3. Les propriétés du réseau de Petri:
- Il est borné
- Il admet un état de blocage, il n’est donc pas vivant.
Le problème de blocage se produit lorsque les deux processus demandent une déconnex-
ion au même moment.
Pour éviter cela, il suffit de rajouter une place (partagée) pour rendre la demande de
déconnexion réalisable que par un seul processus. Cette place sera relié en entré des deux
transitions Dec_reqi et en sortie de Connection.
