4.2.13.

Exemples divers

Exercice 1
Réseaux de Petri : TD2
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 1

P1 P1 2 P1 3

T1 T4 T1 T4 T1 T4

P2 P3 P2 P3 P2 P3

T3 T3 T3
T2 T2 T2

a. b. Exercises 4 1c.5

Exercice
Pour 2 chacun
marking is asdesfollows:
RdP deitlaisfigure
a longsuivante,
time since
dontthere havesont
certains been
desany
RdPrequests
généralisés, répondre aux
Deux calculateurs
from utilisent
downsteam;
questions une mémoire
there are
: est-il borné? commune.
4 parts
Vivant? On
in Bblocage?
Sans suppose que
i-1 and 4 Justifier chaque
parts in votre
Bi ([Link]
a complete
réponse. peut avoir
trois états
batch: plus one part).
- il n’a pas besoin de la mémoire
Chapter
- Exercice2 2 mais ne l’utilise pas encore
il la demande
- Les
il l’utilise
réseaux de Petri de la figure suivante sont-ils répétitifs ou répétitifs croissants :
2.1 For each of the PNs, A, B, C, D and E of Figure E 2.1, answer the
questions: is it bounded? live? deadlock
Mémoire
free?
Calculateur 1 commune Calculateur 2
T1 P1
1T
Modéliser le fonctionnement
P de ce système par unT1RdP ou un Grafcet.
1 P1 P1 T1
P1
Exercice 3 T1
T2 P2
A B C D E
On considère le protocole suivant de gestion des cabines et des paniers d’une piscine. À
l’entrée, un client
Figure E 2.1 qui a trouvé une cabine libre y entre et se change en posant ses
vêtements dans 3la cabine. Il demande ensuite un panier qu’il remplit pour libérer la
2 . 2 Exercice
For each of the PNs A to F of Fig. E 2.2, certain of which are generalized
cabine. Après la baignade le client rentre dans une cabine avec son panier, le vide et le
PNs, answer the following questions: ispour
it bounded?
le réseaulive? deadlock
de : free?
libè[Link]
Ensuite les
il seinvariants
rhabille etdelibère
marquages
la cabine. de Petri
Soient- Nc Ple
1 nombre
Deux programmesde cabines et PNp
1 le nombre
qui partagent de panier.
une2mémoire commune.
P1 3
1. - Décrire
Système ceproducteur
protocole
T4
par un RdP/ ou
/ magasin un Grafcet
consommateur
T4
avec Nc=3 et Np=5. T4
T1 T1 T1
2. Montrer qu’il y a un état de blocage. Y-a-t-il blocage pour toute valeurs de Nc et
dePNp? P2 P2
Exercice
2 4
3. Définir un protocole tel qu’il n’y ait pas de blocage et donner le RdP ou le Grafcet
On considère
T2
correspondant. leT3protocole
P3 suivant
T2 T3
de gestion Pdes
3 cabines T3
T2 et des paniers P3 d’une piscine. À l’entrée, un
A B C
client qui a trouvé une cabine libre y entre et se change en posant ses vêtements dans la cabine. Il
demande
P1 ensuite un panier qu’il P1 remplit2 pour libérer la P1 cabine. Après
3 la baignade le client rentre
Chapitredans une cabine
IV- Annexe avec son panier,
- CEG4566/CSI4541 le vide
– RNM et le
– SITE libère. Ensuite
– uOttawa il se rhabille et libère 15
– Hiver 2013 la cabine.
T4 T4 T4
Soient
T1 Nc le nombre de cabines T1 et Np le nombre de panier. T1
1. Décrire ce protocole par un RdP avec Nc=3 et Np=5.
P2 P P
2. Montrer qu’il y a un état de2 blocage. Y-a-t-il blocage2 pour toute valeurs de Nc et de Np?
T2
3. Définir T3
un protocole P3 tel qu’ilT2 n’y ait pasT3 de P3blocageT2et donnerTle 3 RdPP3 correspondant.
D E F
4. Modifier le RdP de 2. pour modéliser le nombre de clients qui attendent une cabine pour entrer à
la piscine.
Figure E 2.2
2.3 Are the PNs in Figure E 2.1 repetitive or increasing repetitive?
2.4 For both PNs in Figs. S 1.4 and S 1.6, answer the following questions:
a) Is it a strongly connected event graph?
 >?-6&)2*.7-?2-8&+5(-,@;-
85$45(&+&)-

Exercice 1
,!':1'*+,%*),(/5!+(!/3),%*,.!+<1!0*),,2$1+,'*,+&)*!1,%*,7&3+(,%*,+,,
Exercice 5
• 9*1>,2+$0+!..*),<1(,2!+3!0*/3,1/*,.&.$(+*,:$..1/*8,
Une administration fait entrer des clients puis ferme la porte d’entrée avant de commencer le
• I-)3E.*,2+$%1:3*1+,J;,.!0!)(/,J;,:$/)$..!3*1+8,
service. Au fur et à mesure qu’ils sont servis les clients sortent par une autre porte. La porte d’entrée
ne sera rouverte que lorsque tous les clients qui étaient entrés seront sortis.
Exercice 2
Donner le RdP correspondant.
,$/)3+1(+*,'*,+&)*!1,%*,7&3+(,%-1/*,2('*,<4<.,"<(+)3,4/213,<(+)3,.13213$,(,<1!3+*,&'&.*/3)8,=1*',*)3,)$/,
Conseil : Utiliser la notion d’arc inhibiteur.
(/5!+(!/3,%*,.!+<1!0*,Q,
Exercice 6
Exercice 3
Comme l'indique la figure ci-contre, quatre philosophes
,$..*,'>(/%(<1*,'!,A(01+*,:(J:$/3+*B,<1!3+*,2S('$)$2S*),7S('!,(,7S('/,
)$/3, !13$1+,Phil1
%>1/*,à 3!*'*B,
Phil4%()2$)!/3,
sont autour d'une table,
%*), *!01*33*), disposant
*!, (, des
*/, %()2$)&*),
*/3+*,*1>8, baguettes b1 à b4 disposées entre eux.
,
Un philosophe peut avoir quatre états:
0/,2S('$)$2S*,2*13,!5$(+,<1!3+*,&3!3)+,
1. il n'a pas de baguette et il pense.
!8 (',/>!,2!),%*,*!01*33*,*3,(',2*/)*8,
2. il a une baguette et s'apprête à prendre la deuxième.
#8 (',!,1/*,*!01*33*,*3,)>!22+33*,(,2+*/%+*,'!,%*1>(E.*8,
3. il a les deux baguettes et il mange.
)8 (',!,'*),%*1>,*!01*33*),*3,(',.!/0*8,
4. il a déposé une baguette et n'en a plus qu'une seule
/8 (',!,%&2$)&,1/*,*!01*33*,*3,/>*/,!,2'1),<1>1/*,)*1'*,<1>(',
qu'il s'apprête à déposer pour recommencer à penser.
)>!22+33*,(,%&2$)*+,2$1+,+*:$..*/:*+,(,2*/)*+8,
A l'état initial tous les philosophes pensent et les baguettes
2, '>&3!3, (/(3(!', 3$1), '*), 2S('$)$2S*), 2*/)*/3, *3, '*), *!01*33*), )$/3,
sont posées sur la table.
2$)&*),)1+,'!,3!*'*8,
,
! , 9&:+(+*, 2!+, 1/, :97, '*, 2+$3$:$'*, )1(5!/3+, '$+)<1>1/, 2S('$)$2S*,
1. Décrire par un RDP le protocole suivant: lorsqu'un
%&)(+*, .!/0*+B, (', 2+*/%, '!, *!01*33*, (, )!, %+$(3*B, 21(), :*''*, <1(, *)3, (, )!, 0!1:S*, *3, )*, .*3, (, .!/0*+8,
philosophe désire manger, il prend la baguette à sa droite,
=1!/%,(',!,A(/(B,(',+*2$)*,'!,*!01*33*,%*,%+$(3*,21(),:*''*,%*,0!1:S*8,2,'-&3!3,?,(,@,%1,2S('$)$2S*,?,/,@,
puis celle qui est à @sa*3,(',2$1++!,33+*,13('*,%*,+*2+&)*/3*+,'!,%()2$/(*('(3&,%*,'!,*!01*33*,?,*
)*+!,!))$:(&*,1/*,2'!:*,?,7 gauche et se met à manger. Quand il a fini, il repose la baguette de droite
/(, , A,@,
puis celle @,.!+<1&*,$1,/$/8,,$.23*,3*/1,%*,'!,)-.&3+(*,&5(%*/3*,%1,2+$*'E.*,$/,2*13,)*,
2!+,1/*,2'!:*,?,7 de gauche. A l’état « i » du philosophe « n » sera associée une place « Pni » et il pourra
*A,
être utile de représenter la disponibilité de la baguette « bj » par une place « Pbj » marquée ou
:$/3*/3*+,%*,+*2+&)*/3*+,'!,.$(3(&,%1,:97,:$/:*+/!/3,%*1>,2S('$)$2S*)8,
non. Compte tenu de la symétrie évidente du problème on peut se contenter de représenter la
; , 4/%(<1*+,%*),(/5!+(!/3),%*,.!+<1!0*8,F*,+&)*!1,*)3J(',*$+/&,Q,
moitié
! , $/3+*+, <1-(', du1/,
-, !, RDP concernant
*'$:!0*B, deux
%$//*+, philosophes.
1/*, )&<1*/:*, %*, A+!/:S())*.*/3), <1(, -, :$/%1(3, *3, *>2'(<1*+,
2. Indiquer des invariants de marquage.
2$1+<1$(, (', )*, 2+$%1(38, F*, +&)*!1, *)3J(', 5(5!/3,Q, Le réseau est-il borné ?7$1+, &5(3*+, :*33*, )(31!3($/B, /$1),
<1!)(J5(5!/3,Q,
3. Montrer
%&A(/())$/), qu’il y2+$3$:$'*+,
1/, /$15*!1, a un blocage, donner
:S!<1*, une séquence
2S('$)$2S*, />!, 2'1),de
<1*,franchissements qui(',y/>!,
%*1>, &3!3)+, )$(3, conduit
2!), %*,et
expliquer
*!01*33*, *3, (', 2*/)*B,pourquoi
)$(3, (', !,il'*),
se%*1>,
produit. Le réseau
*!01*33*), *3, (', est-il
.!/0*8, vivant ? quasi-vivant
F$+)<1>1/, 2S('$)$2S*,? Pour éviter5*13,
<1(, 2*/)*, cette
situation, nous définissons un nouveau protocole: chaque philosophe n'a plus que
.!/0*+B, (', 2+*/%, )(.1'3!/&.*/3, '*), %*1>, *!01*33*), %$/3, (', !, **)$(/, *3, (', '*), +*)3(31*, )(.1'3!/&.*/3,deux états:
!2+E),!5$(+,.!/0&8,9&:+(+*,2!+,1/,:97,:*,/$15*!1,2+$3$:$'*8,
soit il n'a pas de baguette et il pense, soit il a les deux baguettes et il mange. Lorsqu'un
philosophe qui pense veut manger, il prend simultanément les deux baguettes dont il a besoin et
il les restitue simultanément après avoir mangé. Décrire par un RDP ce nouveau protocole.
Donner le RdP correspondant.
Conseil : Utiliser la notion d’arc inhibiteur.

Solutions
Solutions des exercices 1 à 4

Exercice 1
Solution Exercice 1

P1 P1 2 P1 3

T1 T4 T1 T4 T1 T4

P2 P3 P2 P3 P2 P3

T3 T3 T3
T2 T2 T2

a. b. c.

Borné Borné Pas borné

Pas vivant Vivant Vivant
Sans blocage Sans blocage Sans blocage

Solution Exercice 2
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
A) Yes. The sequence S = T1 is increasing repetitive, thus the PN is increasing repetitive.
Mémoire
B)Calculateur 1
No. The sequence S = T1 is Calculateur
not repetitive. C) Yes.
commune 2
The sequence S = T1 is repetitive.

D) Y es. The sequence S = T 1T 2 is repetitive. It contains all the transitions (T2T1 is also
repetitive).

E) No. The sequence S = T1 is not repetitive.

Exercice 3
Chapitre IV- Annexe - CEG4566/CSI4541 – RNM – SITE – uOttawa – Hiver 2013 16
1. Deux programmes qui partagent une mémoire commune
Solutions to Exercises 455

Memory
P1 free P4
P7
CP1 CP2
requests T1 T4 requests
CP1 CP2 T6
T3 P2 P6
uses uses
CP1 P3 T2 T5 P5 CP2
does not does not
need need

Figure S 1.5
1.6 The generalized PN is presented in Fig. S 1.6. For the initial marking
2. indicated, only transition T1 is enabled. When it is fired, a token is deposited
Producteur/magasin/consommateur
in place P 2: execution of an instruction from task 1. Then (firing of T 2),
task 1 is placed in stand-by (token in place P7) and a second execution of an
- Les invariants de marquage : M(P1)+M(P
instruction from task 1 is authorized, 2)=1 ; M(P3)+M(P4)=1 ; M(P5)+M(P6)=1
etc. The initial marking is such that 3
;
instructions from task 1 can be performed (3 tokens in place P1). The firing
- Les séquences
sequence répétitives
T1T 2 must be: carried
T1 T2outT4 3T3times
ou Tin1 aTrow
4 T3before
T4 T3another
T2 T1 transition
T2
becomes enabled. In fact, after the firing sequence T1T 2T 1T 2T 1T 2, place P1 is
empty and 3 tokens have been deposited in P3. Transition T 3 is then enabled.
Its firing consists of removing the 3 tokens from P3 and of adding 5 tokens to
P4. We shall thus be able to perform 5 instructions from task 2, etc.
 c) The solution is presented in Fig. S 1.3c. ArcstoP'Exercises
Solutions 2 T 4 and T 4 P
4 5' 2 9
have a weight 4. Transition T 4 is only enabled if there are 4 tokens in P'2,
therefore 0 token in P2. When T4 is fired, marking of P'2 is not changed. The
D) Yes. The sequence S = T T 2 is repetitive. It contains all the transitions
initial marking (for the 3 cases) 1corresponds to the case when the door is open
(T2T 1 is also repetitive).
and no customer has come in since it was opened.
E) No. The sequence S = T1 is not repetitive.
P1 P1 P1
2.4 A)
T1 For the PN in Fig. S 1.4.T1 T1
a) As each place has exactly one input transition and one4 output transition,
P’2 P’2
and 2 all Pthe
P’ 2 arc
T4
weights
T3
are 1, Pit2 is Tan event T
graph. Since
P2 the path
T4 T3
4 3
P1T 2P4T 3P5T 4P6T 3P3T 2P2T 1P1 passes through all the nodes, the event graph is
strongly connected. 4
b) AccordingPto 3 Property 2.8, there is Pa3 P-invariant for each elementary
P3
T2 namely x = (1, 1, 0, 0,T20, 0), x = (0, 0, 1, 1, 0,T20), and x = (0, 0,
circuit, 1 2 3
0, 0, 1, 1), and a single T-invariant y1 = (1, 1, 1, 1).
Marking(a) invariants: m + m = 1(b)(states of the producer), (c) m + m = 3
1 2 3 4
(number
Figure S of1.3places in the buffer), and m5 + m 6 = 1 (states of the consumer).
Examples of repetitive sequences: T1T 2T 4T 3 or T 1T 4T 3T 4T 3T 2T 1T 2 (same y1).
1 . 4 c) The PN is indicated
According in Fig.
to Property S 1.4.
2.8c, Theisproducer
the PN hasthere
live since two is
possible
at leaststates: a
a token
"production"
in state oncircuit.
every elementary the one hand and a "ready to deposit" state on the other.
Similarly,
d) Firingthe consumer
sequence T1T 2has
T 4Ttwo possible states. Capacity 3 of the buffer is
3 is complete and repetitive from m 0. Hence, the
the sum
PN of the numbers of parts in the buffer and free places: m3 + m 4 = 3.
is consistent.
Ready to Places
B) Form0 the PN in Fig. S 1.6. in the buffer
deposit Consumption
a) It has the structure
P1 of an Pevent
3 graph, Pbut
5 it is not an event graph
because all the arc weights are Tnot 1. T3
Production T1 2 T
b) Building
complete the graph of markings shows
Deposit Taking
that, out
for each4 Consumption
reachable
complete
marking
there is only one transition enabled (no concurrency). The firing sequence
S = (TSolution3 Exercice5P 3 P4 m S P6 m . It corresponds to the
1T 2) T 3(T4T 5) T 2 6 is such that 0 0

T-invariant Production
y2 = (3, 3, 1, 5, 5, 1). in Parts
There is no otherReady to
minimal repetitive firing
1. the buffer consume
sequence.
Figure
ThereS 1.4
is a marking invariant for each elementary circuit: m 2 + m 7 = 1,
Exercice 4
1 . 5m 5 Figure
+ m8 = S1, 1.5
andpresents
5 m 1 + 5them 2 PN,
+ 5m 3 + 3
with anminitial
4 + 3m 5 + 3 m 6 The
marking. = 15,three
corresponding
states of
to
computer CP1 corresponds to P 1, P 2, and P 3 (and similarly for CP2).1),The
1.P-invariants x 4 = (0, 1, 0, 0, 0, 0, 1, 0), x 5 = (0, 0, 0, 0, 1, 0, 0, and
xmemory
6 = (5, 5,
has5,also
3, 3, 3, 0,states:
three 0). idle (P ), used by CP (P ), and used by CP (P ).
7 1 2 2 6
c) According to b) above, m0 is a home state. Since S is complete, the PN
is live according to Property 2.10. (Property 2.11 is also verified).
d) The PN is consistent since S is complete and repetitive from m0.
2.5 a) P-invariants: x1 = (0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0) and x 2 = (0, 0, 0, 1,
0, 0, 1, 1, 0, 0, 0, 1). The PN is not conservative since P1, P3, P9, and P11,
are not in the support of a P-invariant. These places are unbounded.
b) Since there is no conflict, the PN is persistent. From m 0 the firing
sequence T1T 2T 3T 4T 5T 6T 7T 8T 9T 10 is possible. This is a complete repetitive
sequence and thus the PN is live according to Property 2.11.
2.6 a) The PN is presented in Figure S 2.6a. The initial state corresponds to the
case where all the philosophers are thinking. Places P17 to P 20 correspond to

2. Montrer qu’il y a un état de blocage. Y-a-t-il blocage pour toute valeurs de Nc et de

Np?
2. Montrer qu’il y a un état de blocage. Y-a-t-il blocage pour toute valeurs
de Nc et de Np?

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.
Np Nc
En général : ∀ Nc et Np, la séquence 5 (T
3 1T2T3) T1 conduit
La séquence de franchissement (T1T2T3) T1 conduit au marquage
à un blocage.
(3,0,5,0,0,0,0) qui
3. Définir
est unun protocole
blocage : Il y a 5tel qu’il qui
personnes n’ysont
aitàpas de blocage
la baignade etlesdonner
et 3 dans cabines le
en RdP ou
attentecorrespondant.
le Grafcet de paniers qui ne se libéreront jamais.
Np Nc
En général : ∀ Nc et Np, la séquence (T1T2T3) T1 conduit à un blocage.
Le client qui entre a besoin de deux ressources qui sont une cabine et un
3. Définir
panier, s’il un
lesprotocole
prend tel qu’il n’y ait pas de
simultanément blocageles
quand et donner
deux lesont
RdP libres
ou le Grafcet
il n’y a pas
correspondant.
de blocage. Le RdP (b) modifié montre que la transition T1 en amont de P1
Le client qui entre a besoin de deux ressources qui sont une cabine et un panier, s’il
ne seralesfranchise que si un
prend simultanément panier
quand ETsont
les deux unelibres
cabine
il n’y sont libre
a pas de simultanément.
blocage. Le RdP
(b) modifié montre que la transition T1 en amont de P1 ne sera franchise que si un
4. Modifier le une
panier ET RdP ou le
cabine sontGrafcet de 2. pour modéliser le nombre de clients
libre simultanément.
qui attendent une cabine pour entrer à la piscine.
4. Modifier le RdP ou le Grafcet de 2. pour modéliser le nombre de clients qui attendent
On une cabineune
ajoute pourtransition
entrer à la piscine.
T0 et une place P0 (en pointillés sur le RdP (b)) :
On ajoute une transition
Le franchissement de T0T0 et une place
(arrivée d’unP0 (en pointillés
client) sur leun
ajoute RdP (b)) : dans
jeton Le P0
franchissement de T0 (arrivée d’un client) ajoute un jeton dans P0 (nombre de clients
(nombre de clients en attente).
en attente).
 Solution Exercice 4
Exercice 5
Le Rdp est le suivant :

Exercice 6
a) The PN is presented in Figure S 2.6a. The initial state corresponds to the case where all
the philosophers are thinking. Places P17 to P20 correspond to the availability of rods B1 to B4.
There are four marking invariants corresponding to each of the philosophers. For example,
m 1 + m 2 + m 3 + m 4 =1 for Phil1. There are equally four marking invariants each
corresponding to arod,e.g.m18 +m1 +m2 +m5 +m8 =[Link] B2 is
either available (P18) or picked up by Phil1 (P1 and P2) or picked up by Phil2 (P8 and P5).

The net is not live. Indeed, the firing sequence T3T7T11T15 results in a deadlock: there is a
token in each of places P4, P8, P12 and P16 and only in these places. This comes about
because each philosopher has picked up the rod on his right-hand side and is waiting for the
one on his left to be freed. This will never occur since each of them needs two rods in order
to eat. In order to avoid this unfortunate situation in which the philosophers would
inevitably die of hunger, we shall propose another protocol.

b) We note that philosopher Phili needs two resources in order to eat: rod Bi and rod Bi+1(mod.
4). Since the possession of just one of these is of no use, both resources must be taken up
simultaneously, in order to avoid taking up one which might have been useful to someone
else. The PN of Figure S 2.6b is obtained, if each philosopher simultaneously takes up the
two rods he needs and simultaneously puts them back.

Chapitre IV- Annexe - CEG4566/CSI4541 – RNM – SITE – uOttawa – Hiver 2013 19

 avoid this unfortunate situation in which the philosophers would inevitably
die of hunger, we shall propose another protocol.
b) We note that philosopher Phili needs two resources in order to eat: rod Bi
and rod Bi+1(mod. 4). Since the possession of just one of these is of no use, both
resources must be taken up simultaneously, in order to avoid taking up one
which might have been useful to someone else. The PN of Figure S 2.6b is
obtained, if each philosopher simultaneously takes up the two rods he needs
and simultaneously puts them back.

Phil1 Phil2 Phil3 Phil4

eats eats eats eats
P1 P5 P9 P13

T1 T5 T9 T13

P2 P6 P10 P14

T2 T6 T10 T14
P17 P18 P19 P20

(a) P3 P7 P11 P15

thinks thinks thinks thinks
T3 T7 T11 T15

P4 P8 P12 P16

T4 T8 T12 T16

Phil1 Phil2 Phil3 Phil4

eats eats eats eats
P1 P3 P5 P7

P9 T1 P10 T3 P11 T5 P12 T7

(b) P2 P4 P6 P8 thinks

T2 thinks T4 thinks T6 thinks T8

Figure S 2.6