TD3 SD [PDF]

Zitiervorschau

Université constantine2, Faculté NTIC Master 1 GL – module SD

2020/2021

Travaux Dirigés N° 3 : Exclusion mutuelle distribuée basée permission Exercice 1 Compléter l’exécution de l’algorithme de Ricart et Agrawala de la figure ci-dessous, par montrer l’évolution des variables : étati, hi, attendus i et les messages échangés.

S1 h1=0

S2 h2=0

S3 h3=0

Requête Permission Exercice 2 Soit l’exécution de l’algorithme de Carvalho et Roucairol de la figure suivante. -

Donnez les valeurs initiales des ensembles Ri et la distribution initiale des permissions. montrez l’évolution de : l’horloge, le contenu des messages échangés et l’état des processus.

pi hi=0

pj hj=1

pk hk=0

Requête Permission

Exercice 3 Compléter l’exécution de l’algorithme de Lamport de la figure suivante, par montrer l’évolution des variables : hi, file-requêtei et les messages échangés. P1 h1=2

P2 h2=1

P3 h3=0

Requête Acquittement Libérer

Exercice 4 Soit l’exécution de l’algorithme Chandy et Misra montrée sur la figure 1. 1. Donnez la valeur initiale des ensembles Ri. 2. Donnez la distribution initiale des permissions.

3. Compléter l’exécution de la figure 1, vous préciserez les étiquettes des permissions, les valeurs des variables étati et différéi. 4. Donner l’état de toutes les permissions de P2 entre les évènements c et d et entre les évènements g et i.

P1

P2

P3

a b

c d e f

g

h i j

m l o

n p q

r s

Corrigé type Exercice 1

S1

diff1= {} att1= {s2,s3} demandeur h1=1 last1=1

diff1= {s3} h1=1

diff1= {s3,s2} h1=1

att1= {s2}

dedans att1= {}

dehors diff1= {}

h1=0 dehors

S2

diff2= {} att2= {s1,s3} demandeur h2=1 last2=1

diff2= {s3} h2=1

diff2= {} dehors

att2= {s1}

h2=1

att2= {} dedans

h2=0 dehors

S3 h3=0 dehors

att3= {s1,s2} demandeur h3=1 last2=1 diff3= {}

h3=1

h3=1

att3= {s2}

att3= { }

Requête Permission

Exercice 2

hi=1 demandeur

pi

diffi={} dedans Ri={}

hi=2 diffi={pj}

Ri={pj} demandeur dehors hi=3

dedans Ri={}

hi=0 dehors Ri={pk} diffi={}

Rj={pi}

pj hj=1 hj=2 dehors demandeur Rj={pi,pk} diffj={}

pk

hk=0 dehors Rk={} diffk={}

Exercice 3

Exercice 4 1) Ri ={pk}, Rj={pi, pk} et Rk={}.

hj= 3 diffj={pi}

Rj={} dehors dedans Rj={pi} diffj={}

hk=2 Rk={pj}

hk=2 Rk={pj,pi}

Requête Permission

initialement : pemission(pi, pj) se trouve sur le site pi, permission(pi, pk) est chez le site pk et permission(pj, pk) est sur le site pk. 2) RP1={}, RP2={P1}, RP3={P1,P2}. 3) entre les évènements c et d, perm(p1, p2) et perm(p2, p3) sont à l’état utile. entre les évènements g et i, perm(p1, p2) et perm(p2, p3) sont à l’état utile.

b

P1

j

f

Dehors

o

r

Demandeur

s

Dedans

différé2 =p1

P2

a

d

c

g

e

Dehors Demandeur Dedans Dehors

i

l

Dedans

Dehors

h

P3 Dehors

m

n

Demandeur Différé3 =p1

1

p

q

Dedans

Dehors

Dehors