Sétif le 18-01-2014

Université Sétif 1
Faculté des sciences
Département d'Informatique

Module SD MTC
Documents personnels autorisés (Communication de documents entre étudiants est strictement interdite)
Question : Le temps logique est utilisé dans les horloges scalaires, les horloges vectorielles et les horloges
matricielles, citez pour chaque type d’horloge une utilisation pratique. 1,5 pts
Réponse : Horloges scalaires : exclusion mutuelle, horloges vectorielles : tolérance aux fautes, horloges
matricielles : Elimination des informations obsolètes (garbadge collection), détection interblocage.
Problème. Soient N (N=4) processus P1, P2, P3 et P4 situés respectivement sur les Machines M1, M2, M3 et M4
et évoluant selon le chronogramme suivant. En supposant qu’à l’initialisation les estampilles matricielles de ces
processus soient nulles,
P1 e11 e12

P2 e21 e22

P3 e31 e32

P4 e41 e42
a) Donnez les estampilles matricielles de tous les évènements représentés sur le chronogramme ; 02 pts
b) Pourquoi les horloges matricielles ne sont pas fréquemment utilisées (Inconvénient majeur) ? 01 pt
Réponse : Leur inconvénient majeur et leur encombrement, car les estampilles véhiculées dans les messages
occuperaient beaucoup d’espace n’en lassant que peu aux messages nets.
c) On suppose maintenant que les 4 processus (N=4) Pi, 1 ≤ i ≤ 4, soient organisés en anneau virtuel et
utilisent un fichier F en mode lecture ou écriture. L’accès à F peut être simultané en lecture, et exclusif en
écriture.
1. Ecrire le gestionnaire de F formé des procédures lire(F) et écrire(F) sachant qu’on ne peut autoriser que 03
lectures simultanées, et montrez que les propriétés de safety et liveness sont satisfaites. 04 pts
Réponse : On utilise 03 jetons de lecture et un jeton d’écriture.
Lire (F) Ecrire(F)
Begin begin
Attendre un jeton de lecture Attendre le jeton d’écriture
Prendre le jeton de lecture Prendre le jeton d’écriture
< lire > Attendre chaque jeton de lecture
Libérer jeton de lecture Prendre chaque jeton de lecture
End < Ecrire >
Libérer les jetons de lecture un à un
Libérer le jeton d’écriture
End
 Propriété de liveness satisfaite: Absence de blocage ou d’interblocage permet au système d’évoluer. Comme
toute écriture implique que tous les jetons (lecture et écriture) sont pris par un seul processus donc aucune
autre demande n’est possible, d’ou l’interblocage ne peut se produire.
Propriété de safety satisfaite : Un seul jeton d’écriture disponible implique qu’un seul processus au plus
peut avoir accès au fichier en écriture, donc l’exclusion mutuelle des accès à F est toujours satisfaite.
2. Proposez une solution pour Lire (F) et écrire (F) si le nombre N de processus est important (N=100) 2,5 pts
Réponse : Lorsque le nombre de processus devient important, associer un jeton à une lecture implique
l’utilisation d’un nombre inacceptable de jetons. On va donc utiliser un seul jeton qui portera le nombre de
lectures autorisées en cours, et écriture en cours. Lorsque le jeton arrive au niveau d’un processus si celui-ci
désire lire il consulte le jeton. Si nbrredacteur =0 et nbrlecteurs < nbmax alors il la décrémente nbrlecteurs
et fait suivre le jeton, puis lit F. Lorsque le jeton lui revient il l’incrémente nbrlecteurs et libère le jeton.
Pour écrire, un processus Pi attend le jeton, puis vérifie qu’aucun processus n’est en lecture (nbrlecteurs
nul) et aucun rédacteur n’est en écriture (nbrredacteurs=0), il positionne nbrredacteur =1, libère le jeton et
accède à F. lorsqu’il termine l’écriture, il attend le jeton et remet nbrredacteurs=0, puis fait suivre le jeton.
3. Supposons que P5 détecte que P10 (N=10), qui est élu avant leader, tombe en panne, quel serait alors le
nombre de messages émis pour élire un nouveau leader selon Bully algorithm 02 pts
Réponse : Lorsque P5 détecte que P10 (leader en panne), P5 lance une élection en appliquant Bully
algorithm. Le nombre de message sera donc de :
P5 : 4 messages d’élection (il n’envoie pas au leader car il sait qu’il est en panne), reçoit 04 OK = 8 msg
P6 : 4 msg d’élection (il ignore que P10 est e pannne), il reçoit 3 Ok = 7 msg
P7 : 3 msg d’élection, il reçoit 2 ok = 5 msg
P8 : 2 msg d’élection, il reçoit 1 OK= 3 msg
P9 : 1 msg d’élection+ 8 coordination = 9 msg
Total : 8 + 7 + 5 + 3 + 9 = 32 msg
d) Considérons que les horloges des 4 machines dérivent de 1 seconde toutes les 105 secondes, un intervalle de
104 millisecondes suffit– il à limiter leur inclinaison à 10 ms. 02 pts
Réponse : Dérive sur un intervalle de 104ms soit 10s : 1/105*10= 0,1 ms < 10ms donc OK
e) On considère N=6 processus d’une application distribuée et que l’un d’eux soit affecté par une faute
byzantine, quel serait le nombre de messages émis pour obtenir un consensus. 02 pts
Réponse : nombre de messages selon the théorème vu au cours : 6 + 5*4= 26 messages
f) Quel serait le nombre de messages nécessaires dans le cas d’une faute fail-stop 01 pt
Réponse : Un seul message puisqu’un processus soit il fonctionne correctement donc répond correctement
soit en panne il ne répondra pas.
g) On suppose que P1 et P2 jouent le rôle de producteurs, et P3 et P4 le rôle de consommateurs liés par un
buffer B (N=4)
Donnez l’expression abstraite de synchronisation de ce système et justifiez votre réponse 02 pts
Réponse : P1 et P2 consommateurs, P3 et P4 consommateurs. Pour pouvoir déposer un message dans B, il
faut qu’il y ait une case libre d’où l’expression abstraite : nbr_production – nbr_consommation < N. Pour
pouvoir consommer, il faut qu’il y ait au moins un message dans B d’où :
Nbr_production – nbr_consommation > 0.
Soit nbp = nombre de productions et nbc= nombre de consommations d’où l’expression :
nbp – nbc < N et
nbp _ nbc > 0 or nbp = nbp1 + nbp2 et nbc = nbc3 + nbc4 d’où pour produire il faut vérifier
l’expression : (nbp1+ nbp2) – (nbc3 + nbc4) < N et pour consommer il faut satisfaire l’expression :
 (nbp1 + nbp2) – (nbc3 + nbc4) > 0. Tout processus a connaissance d’une variable, il en obtient les trois
autres par transmissions : nbp1’, nbp2’, nbc3’, nbc4’ (voir démonstration dans le problème du parking vu
en cours).

1100 2222 0000 0000 0000 0000 0000 0000

0100 0200 0100 0200 0200 0200 0200 0200
é11 0000 e12 0222 e21 0000 e22 0000 e31 0212 e32 0222 e41 0000 e42 0000
0000 0202 0000 0000 0202 0202 0201 0202

N.B : 80% du contrôle a été déjà réalisé en cours et TD !!