Université de Manouba

Ecole Nationale des Sciences

de l’Informatique Session : 01 Décembre 2011

Section : II3 A.U. : 2011 /2012.

Module : Informatique Répartie

Signatures des

Surveillants

Total

feuilles

remises

Nom : ……………………… Prénom :……………………..

N° CIN : …………………………………………………….

N° d’inscription : ……………………………………………

Salle n° :…………………. Place n° :…………………..

Signature de

l’étudiant

- - - - - - - - - - - - - -- - - - - - - - - - - - - -- - - - - - - - - - - - - -- - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - -

Note

EXAMEN de RATTRAPAGE

Documents non autorisés

Appréciations du correcteur

Exercice 1- Interblocage (5pts)

1. Comment se traduit la sureté pour les algorithmes de gestion d’interblocage ? (1pt)

…………………………………………………………………………………………………

2. Comment se traduit la vivacité pour les algorithmes de gestion d’interblocage ? (1 pt)

…………………………………………………………………………………………………

3. Expliquez la différence entre l’évitement et la prévention de l’interblocage. (1pt)

…………………………………………………………………………………………………...

4. Tous les algorithmes de détection d’interblocage partent d’un même principe. Expliquer

brièvement ce principe (ne citer pas les algorithmes eux-mêmes). (1pt)

…………………………………………………………………………………………………...

5. Expliquez l’impact de la détection d’un faux interblocage.

…………………………………………………………………………………………………

Ne rien écrire ici

- - - - - - - - - - - - - -- - - - - - - - - - - - - -- - - - - - - - - - - - - -- - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - -

…………………………………………………………………………………………………...

Exercice 2 : Election (5pts)

On utilise les variables suivantes :

M : initialisée à 0

mon_numero : identificateur du nœud

Texte de l’algorithme en Pi:

Si la condition { M=0 } est vérifiée

Alors

M := mon_numero

envoie < M > au suivant dans l’anneau

Si la condition { message <j> arrivé } est vérifiée

Alors Si M < j

Alors

M := j

envoie <M> au suivant dans l’anneau

Si j = i alors

“Je suis le leader”

On suppose que “Je suis le leader” déclenche un algorithme de diffusion sur l’anneau pour

en informer les autres, qui remettra toutes les variables M à 0.

1. Appliquez, sur un schéma, cet algorithme sur un exemple sur un anneau d'au moins 4

sites sachant qu'un seul processeur initie l'élection. On suppose que les sites sont disposés

dans l’ordre suivant : 2,1,4,3 et que l’élection est initiée par le processus 2. (3pts)

Ne rien écrire ici

- - - - - - - - - - - - - -- - - - - - - - - - - - - -- - - - - - - - - - - - - -- - - - - - - - - - - - - -- - - - - - - - - - - - - - - - - -

1. Comparez cet algorithme à celui de Chang et Roberts vu en cours : regardez ce qui se

produit dans les cas où tous les processus se réveillent spontanément et dans les cas où

seulement une portion d’entre eux se réveille spontanément. Expliquez. (2pts)

Exercice 3 – Horloges logiques (5pts)

2. Si on élimine la composante site des horloges de Lamport, quelle propriété est perdue par

rapport aux horloges de Lamport ? L’horloge, ainsi modifiée, respecte-elle toujours la

condition de validité faible des observations ? Justifiez votre réponse. (2pts)

3. Les horloges de vectorielles de Mattern permettent de dater les événements d’un calcul

réparti en assurant la propriété fondamentale exprimée sous forme de l’équivalence

Pour tous e et e’, ee’  Ve ≤ Ve’

On suppose que, pour une application donnée, seuls les événements internes aux sites et

les émissions ont besoin d’être datés. On envisage donc de ne plus comptabiliser les

événements de réception (pas d’incrémentation de la composante correspondant au site

récepteur lors de la réception d’un message).

Cette modification garde-t-elle la propriété fondamentale des horloges de Mattern ?

Illustrez votre réponse avec un exemple. (3pts)

Exercice 4 – Exclusion mutuelle (5pts)

On considère l’algorithme de Lamport vu en cours.

1. Appliquez cet algorithme sur le diagramme suivant (les flèches représentent les messages

du type (Demandei;Hi), (Ack,Hi) et (Liberation,Hi) ; Hi valeur de l’horloge de Lamport

lors de l’émission du message correspondant) et déterminer l’ordre d’entrée des processus

en section critique. Préciser le contenu des files d’attente des différents processus. (3pts)

2. Expliquez pourquoi les communications doivent-elles être FIFO. (2pt)

………………………………………………………………………………………………………........

…………………………………………………………………………………………………………..

………………………………………………………………………………………………………..........