Université Mohamed Khider– Biskra
Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie
Département d'informatique
Niveau: M1 Module: Systèmes distribués Date du contrôle: 09.01.2019
Correction du contrôle
Exercice n° 1 (5 points)
1. Schéma doit contenir non respect de délivrance causale pour expliquer le problème (1 point). Datation (1 point).
2. Principe des horloges matricielles: Signification des éléments + Màj des horloges locales selon le type d’évènements: (2 points)
La modification des horloges des différents sites est réalisée de la manière suivante :
• lorsqu’un événement local se produit sur le site Si : HMi [i,i] est incrémenté;
• lorsqu’un message est expédié à partir du site Si vers le site Sj : HMi [i,i] et HMi [i,j] sont incrémentés ;
• lorsqu’un message m en provenance du site Sj est reçu sur le site Si, Cela correspond aux conditions suivantes (à vérifier
dans l’ordre):
1. HMm [j,i] = HMi [j,i] + 1 (ordre FIFO sur le canal (j,i))
2. pour tout k ≠ i et j, HMm [k,i] ≤ HMi [k,i] (tous les messages en provenance des sites différents de Sj ont été
reçus).
• Si toutes ces conditions sont vérifiées, le message est délivrable et l’horloge du site Si est mise à jour :
1. HMi [ i,i ] ++ (incrémentation);
2. HMi [ j,i ] ++ (incrémentation);
3. pour le reste de la matrice : HMi [k,l] = max (HMi [k,l], EMm [k,l] )
Si les conditions ne sont pas toutes vérifiées, la délivrance du message est différée jusqu’à ce qu’elles le deviennent et l’horloge
n’est pas mise à jour.
3. S’il y a un non respect de protocole de délivrance causale, les horloges matricielles le corrigent par la vérification des deux
conditions dans le cas d’un évènement de réception. Si l’une d’elles ou les deux n’est/pas vérifiée (s) l’évènement concerné sera
décalé (1 points).
Exercice n° 2 (7 points)
1. La cohérence de chacune des deux coupures C1 et C2
C1 : coupure non cohérente (message ip) (1 point)
C2 : coupure cohérente (1 point)
2. Le tableau les estampilles scalaires (1 point) et vectorielles (1 point) des différents évènements
Evènement a b c d e f g h i j k l m n o p q r
Estampille Scalaire 1 2 3 6 7 1 2 3 4 5 6 7 1 2 3 5 6 7
Estampille Vectoriel 1 2 3 4 5 0 1 1 1 1 1 1 0 0 0 1 1 1
0 1 1 5 5 1 2 3 4 5 6 7 0 0 0 4 4 4
0 0 0 0 0 0 0 0 0 0 0 2 1 2 3 4 5 6
3. Deux événement a et b sont dits conçurent si l’exécution de l’un n’influe pas sur l’exécution de l’autre = il n’y a aucune précédence
causale entre eux. a || b ((a b) (ba)) (0.5 point)
Les paires d’évènements concurrents dans le schéma (1 point): (a || f), (a || m), (f || m), (b || g), (b || n), (g || n), (c || h), (c || o),
(h || o), (d || k), (d || q), (k || q), (e || l), (e || r), (l || r), (j || p)
4. (1.5 point)
Exercice n° 3
A. Quelles sont les contraintes à respecter par un algorithme d’exclusion mutuelle ?
Réponse
Sûreté: au plus un processus est à la fois dans la section critique (0.5 pt)
Vivacité: tout processus demandant à entrer dans la section critique y entre en un temps fini (0.5 pt)
B. On considère un système réparti à trois sites S1, S2, S3. S1 a émis une requête pour entrer en Section Critique (SC) à H1=2, et S2
a émis une requête pour utiliser la SC à l'instant H2=5. La figure représente uniquement les évènements datés après Hi=10.
B. Q1/ Quel est le type du message marqué par "?" sur la figure?
Réponse :
Le message est de type ACK (Réponse/ OK/ Permission) (1 pt)
Q2/ Quel est l'algorithme utilisé dans ce cas pour la gestion de la SC ? Justifiez.
Réponse:
Il s'agit de l'algorithme Ricart-Agrawala. Justification: Si c'était l'algorithme Lamport, S1aurait diffusé, à sa sortie de SC,
un message REL à S2 et S3. Ce n'est pas le cas. C'est donc bien l'algorithme Ricart-Agrawala qui est utilisé et le message marqué par
? est bien un ACK (1 pt)
Q3/ Donnez la valeur de toutes les structures de données utilisées par S2 à l'instant A.
Réponse: (1 pt)
File d’attente pour sauvegarder les requêtes reçues et non servies: FA=.
Liste des sites récepteurs (Tous les sites sauf l’émetteur de la requête): Liste_Site=.
Horloge locale: H2=12.
Etat du site par rapport à demande d’accès à la section critique: Etat=Dedans.
Q4/ Que fera S2 à l'instant B ?
Réponse: (1 pt)
Il n'envoie aucun message. Il remet: Demandeur à faux ou Etat à Dehors.
Q5/ Quel est le nombre de messages échangés avant (Hi=10) ? et après ? Justifiez.
Réponse
Avant, Il y'a 7 messages : 2 REQ (de S1 vers S2 et S3), 2 REQ (de S2 vers S1 et S3), 2 ACK (de S3 vers S1 et S2), 1 ACK (de
S2 vers S1) (1.5 pt).
Après, Il y'a 1 seul message : 1 ACK de S1 vers S2 (0.5 pt).
Q6/ S2 fait une nouvelle demande pour entrer en SC à l'instant C. Représentez l'enchainement des messages qui en découlent, l'entrée
et la sortie de la SC.
Réponse: (1 pt)
