[PDF] Examen semestriel Algorithmique et Systèmes distribués (Corrigé) 1

View - Download Examen semestriel Algorithmique et Systèmes distribués (Corrigé) 1

Previous PDF

Next PDF

1/6

Université de Chlef Mai 2017

Département Informatique

Filière : Master 1 - IL

Examen semestriel

Algorithmique et Systèmes distribués

(Corrigé) 1 H30

Exercice 1 (08 points)

: La figure suivante montre une partie des messages échangés entre 3 processus (P1, P2, P3) d"un système réparti pour utiliser une section critique (SC). Nous savons que P3

accède à la SC au point B; le contenu de sa file de requêtes et son ensemble des réponses

ACK sont précisés sur la figure.

Question 1

: D"après-vous l"algorithme utilisé est celui de Lamport ou de Ricart-Agrawala ? Justifiez.

Réponse :

L"algorithme utilisé est celui de Lamport. Justification : dans la file des requêtes au point B, on voit que

P3 a sa propre requête en tête de file. L"algorithme Ricart-Agrawala ne fonctionne pas de cette manière.

(1 pt)

Question 2

: En supposant que A=10, identifiez le type de chaque message marqué par "?" et datez le.

Réponse :

2/6 Le message envoyé de P2 vers P3 est : (ACK, 10, 2) Le message envoyé de P3 vers P1 et P2 est : (REL, 12, 3) Le message envoyé de P2 vers P1 et P3 est : (REL, 14, 2) (2 pt)

Question 3

: A partir des informations de la figure, peut-on connaitre à quel moment P2 peut-il entrer en

SC ? . Justifiez. Quelle est la valeur de X ?.

Réponse :

P2 entre en SC lorsque sa valeur d"horloge H2 est égale à 13. Justification : Le message envoyé à

H2=14 (qui ne peut être qu"un REL) a fait supprimer la requête (REQ, X, 2) qui était dans la file de P3.

P2 entre en SC après P3 et avant P1. La date de sa requête X doit donc être postérieure à la date de la

requête de P3 ( "1" ) et antérieure à la date de la requête de P1( "4" ). X est donc égal à 2 ou 3.

(2 pt)

Question 4

: On suppose que l"ensemble des réponses ACK de P1, au point C, est ACK={2, 3}. A quel moment P1 entre-t-il en SC ? .

Réponse :

P1 entre en SC lorsque H1=15 : il a tous les ACK des autres sites et sa requête est la seule qui reste

dans sa file. (1 pt)

Question 5

: Compléter la figure en ajoutant tous les messages manquants , à partir du point A. Donnez l"évolution du contenu des files de requêtes et d"ACK de chaque site. 3/6

Evolution des sites :

P1 P2 P3

H1=13

REQ,4,1 REQ,X,2

ACK={ 2, 3}

H1=15

REQ,4,1

ACK={ 2, 3}

H1=16 H2=10

REQ,4,1 REQ,X,2 REQ,1,3

ACK={ 1, 3}

H2=13

REQ,4,1 REQ,X,2

ACK={ 1, 3}

H2=14

REQ,4,1

H2=17 H3=11

REQ,4,1 REQ,X,2 REQ,1,3

ACK={ 1, 2}

H3=12

REQ,4,1 REQ,X,2

H3=15

REQ,4,1

H3=17 4/6 (2 pt)

Question 6

: Combien y"a-t-il de message échangés entre les sites avant le point A , qui sont nécessaires à

la gestion de la SC ? Justifiez.

Réponse :

Il y"a 11 messages échangés avant le point A :

2 REQ envoyés par P1

2 REQ envoyés par P2

2 REQ envoyés par P3

2 ACK envoyés par P1

2 ACK envoyé par P3

1 ACK envoyé par P2 (l"autre a été envoyé après le point A).

(1 pt)

Exercice 2 (06 points)

: On propose la méthode suivante pour l"élection d"un processus dans un système réparti : les processus sont organisés en un anneau virtuel. Chaque processus a un numéro

distinct. Le processus i qui initie la procédure d"élection lance un message élire(i) à son

voisin.

Question 1

: Que doit faire un processus j qui reçoit un message élire(i) ?.

Réponse :

Un site j recevant élire(i) de son prédécesseur (j-1) regarde si son propre numéro j est plus grand que le

numéro reçu i. Si oui, il envoie élire(j) au site successeur j+1. Sinon, il renvoie le même message élire(i).

Procédure exécutée par un processus j qui reçoit élire(i) : Si j>i alors envoyer(élire(j)) au site voisin (j+1) sinon envoyer (élire(i)) au site voisin finsi (1.5 pt)

Question 2

: Quand un processus peut-il savoir qu"il est le nouveau coordinateur ? .

Réponse :

Un site peut savoir qu"il est le nouveau coordinateur lorsque le message élire qu"il a envoyé fait un tour

complet sur l"anneau et lui revient. (1.5 pt)

Question 3

: Que doit faire le nouveau coordinateur ?. Réponse : Il doit envoyer un message de proclamation à travers l"anneau. 5/6 (1 pt)

Exercice 3 (06 points)

: Le consensus est l"un des problèmes étudiés dans les systèmes répartis.

Question 1

: Donnez la définition du problème.

Réponse :

Le problème du consensus dans un système réparti consiste à faire prendre une décision commune par

un ensemble de processus. Concrètement, chaque processus peut proposer une valeur vi. Le calcul du

consensus doit aboutir à une même valeur v attestée par tous les processus. (1 pt) Question 2 : Expliquez en quelques lignes les difficultés de ce problème.

Réponse :

L"obtention du consensus peut devenir complexe dans les cas suivants :

· Arrêt d"un site

· Omission : Un site omet d"envoyer ou de recevoir certains message indispensables au calcul du consensus. · Fonctionnement arbitraire (ou byzantin) : Un site peut avoir un comportement douteux et envoie des messages arbitraires. (1 pt)

Question 3

: On utilise un coordinateur responsable du calcul du consensus entre N Sites. Donnez un schéma expliquant l"établissement du consensus. Combien de messages sont nécessaires ?. Quels sont les avantages et les inconvénients de cette méthode ?.

Réponse :

6/6

Il y"a 2*N messages en tout : N messages envoyés par les N processus pour proposer une valeur, et N

messages pour diffuser la valeur décidée. Avantage : La fiabilité du consensus est assurée par le coordinateur.

Inconvénient : Panne du coordinateur.

(2 pt)

Question 4

: On utilise maintenant la méthode des messages symétriques : Chaque site diffuse sa valeur à

tous les sites, y compris à lui-même. Après avoir reçu toutes les valeurs , chaque site calcule le

min des valeurs reçues. Combien de messages sont nécessaires pour avoir un consensus ?. Quels sont les avantages et les inconvénients de cette méthode ?.

Réponse :

Le nombre de message nécessaires est N*(N-1) : chaque site diffuse la valeur qu"il propose aux N-1

autres sites.

Avantage : Il n"ya pas de coordinateur .

Inconvénient : Nombre élevé de messages. De plus, si le mode de messages n"est pas synchrone, nous

n"avons aucune idée sur le délai que doit prendre le calcul. (2 pt)quotesdbs_dbs4.pdfusesText_8

[PDF] exercice corrigé algorithme matrice

[PDF] exercice corrigé ancc

[PDF] exercice corrigé anova à un facteur

[PDF] exercice corrigé antenne

[PDF] exercice corrigé arbre de défaillance pdf

[PDF] exercice corrigé architecture des ordinateurs memoire

[PDF] exercice corrigé augmentation de capital pdf

[PDF] exercice corrigé automatique asservissement

[PDF] exercice corrigé avantage comparatif

[PDF] exercice corrigé balanced scorecard

[PDF] exercice corrigé bassin versant

[PDF] exercice corrigé bassin versant pdf

[PDF] exercice corrigé bordereau d'escompte

[PDF] exercice corrigé bras de levier

[PDF] exercice corrigé budget dapprovisionnement pdf