[PDF] Examen de rattrapage (Corrigé) Algorithmique et Systèmes répartis

View - Download Examen de rattrapage (Corrigé) Algorithmique et Systèmes répartis

Previous PDF

Next PDF

1/1

Université de Chlef Mai 2017

Département Informatique

Filière : Master 1 - IL

Examen de rattrapage (Corrigé)

Algorithmique et Systèmes répartis

1 H30

Exercice 1 (7 points) : On considère un système réparti à trois (3) sites : 1, 2 et 3. Les horloges scalaires

sont initialisées à 0.On fera l"hypothèse suivante : le délai de propagation des messages entre les sites est

connu, comme le montre le tableau suivant :

Site 1 Site 2 Site 3

Site 1 0 1 1

Site 2 2 0 2

Site 3 3 3 0

Le délai de propagation des messages en partance du site 1 vers les autres sites est égal à 1. Pour le site 2,

il est égal à 2. Pour les site 3, il est égal à 3.

Les sites 1 et 3 émettent des requêtes pour entrer en section critique quand leurs horloges logiques sont

égales à 0.

Question 1 : En appliquant l"algorithme de synchronisation de Lamport, faire un diagramme (dessin) qui

décrit la trace d"exécution des transferts de messages entre les sites , l"entrée et la sortie de la

SC, en prenant soin de dater les événements. Montrez également l"évolution des files de

messages au niveau de chaque site. Comptez le nombre de messages total.

Réponse :

2/1 (1.5 pt)

Evolution des sites :

S1 S2 S3

H1=0

REQ, 0, 1

Ack={}

H1=2

REQ, 0, 1

Ack={2}

H1=4

REQ, 0, 3 REQ, 0, 1

Ack={2}

H1=6

REQ, 0, 3 REQ, 0, 1

H2=1

REQ, 0, 1

H2=3

REQ, 0, 3 REQ, 0, 1

H2=8

REQ, 0, 3

H1=10 H3=0

REQ, 0, 3

Ack={}

H3=1

REQ, 0, 3 REQ, 0, 1

Ack={}

H3=6

REQ, 0, 3 REQ, 0, 1

Ack={1}

H3=7

REQ, 0, 3 REQ, 0, 1

3/1

Ack={2, 3}

H1=7

REQ, 0, 3

H1=10

Ack={1, 2}

H3=8

REQ, 0, 3

Ack={1, 2}

H3=9 (1.5 pt)

Nombre de messages = 12 (4 REQ + 4 ACK + 4 REL)

(0.5 pt) Question 2 : Refaire le même travail avec l"algorithme Ricart-Agrawala.

Réponse :

4/1 (1.5 pt)

Evolution des sites :

S1 S2 S3

H1=0 , Etat=Ready ,

Demande=(REQ, 0, 1)

Ack={}

H1=3 , Etat=Ready ,

Demande=(REQ, 0, 1)

Ack={2}

H1=4 , Etat=Ready ,

Demande=(REQ, 0, 1)

REQ, 0, 3

Ack={2}

H3=0 , Etat=Ready ,

Demande=(REQ, 0, 3)

Ack={}

H3=5 , Etat=Ready ,

Demande=(REQ, 0, 1)

Ack={2}

H3=7 , Etat=IN ,

Demande=(REQ, 0, 1)

Ack={1, 2}

5/1

H1=5 , Etat=IN ,

Demande=(REQ, 0, 1)

REQ, 0, 3

Ack={2, 3}

H1=6 H3=8 (1.5 pt)

Nombre de messages = 08 (4 REQ + 4 ACK )

(0.5 pt)

Exercice 2 (7 points): On considère un système réparti à N sites (numérotés de 1 à N). On utilise

l"algorithme de synchronisation de Lamport. Le site 1 est le seul à solliciter l"entrée à la SC. Il émet des

requêtes REQ de façon itérative : après chaque sortie de la SC , il émet une nouvelle requête.

Question 1 : Faire un diagramme général montrant l"entrée et la sortie de la SC, ainsi que les messages

échangés.

6/1 (2 pt)

Question 2 : Pensez-vous qu"il y"a des messages qui peuvent être considérés comme inutiles ? Lesquels ? .

Que proposez-vous ?

Réponse :

En effet, pour chaque passage à la SC , le site 1 doit réitérer le message de Requête aux autres sites et

doit attendre les Accusés de réception de tous ces sites. Ces messages (REQ et ACK) peuvent paraitre

inutiles. (2.5 pt) 7/1

L"idée (Algorithme de Cavalho et Roucairol) est donc de permettre au site 1 d"entrer directement à la SC

s"il a déjà obtenu un Ack des autres sites tant qu"il n"ya aucun de ces sites qui zn"a émis une requête

pour entrer en SC. On revient à l"algorithme original lorsque l"un des sites souhaite de nouveau

l"utilisation de la SC. (2.5 pt)

Exercice 3 (6 points)

: Dans les systèmes répartis, on peut utiliser trois stratégies pour la gestion de

l"allocation des ressources . Donnez le principe de chaque stratégie, ses avantages et ses inconvénients.

Réponse :

1/ Centraliser la gestion des ressources : On charge un site coordinateur de gérer toutes les allocations

des ressources. Toutes les requêtes doivent parvenir à ce coordinateur , et c"est à lui de décider si une

requête peut être satisfaite ou non , en fonction de l"état d"allocation des ressources qu"il détient. Le

coordinateur reçoit aussi les avis de libération des ressources émanant des processus.

Avantage : Le fait de centraliser l"allocation des ressources rend aisé le maintien de l"état global des

ressources.

Inconvénient : Le coordinateur peut devoir affronter une surcharge puisque toutes les requêtes et avis

de libération des ressources arrivent chez lui. De plus, la panne du coordinateur affectera la gestion des

allocations. Il faudra , en cas de panne, faire une élection d"un nouveau coordinateur. (2 pt)

2/ Répartition totale de la gestion des ressources : Avec cette stratégie, nous n"avons pas un seul

allocateur mais plusieurs. Chaque allocateur doit pouvoir répondre aux différentes requêtes concernant

toutes les ressources du système.

Avantage : La fonction d"allocation étant répartie, il n"ya plus de surcharge d"un allocateur particulier. Il

y"a aussi plus de fiabilité, puisque la panne d"un allocateur n"affecte pas le fonctionnement des autres

allocateurs.

Inconvénient : Difficulté pour les allocateurs d"avoir un état global des ressources cohérent . Chaque

allocateur peut avoir une image différente de l"état d"allocation des ressources détenu par les autres

allocateurs (en raison des délais d"acheminement des messages qui peut différer d"un site à un autre).

(2 pt)

2/ Répartition partielle de la gestion des ressources : On désigne un allocateur pour un groupe de

ressources : par exemple un allocateur gère uniquement les ressources disponibles sur un site .

Avantage : L"allocateur n"aura pas de difficultés à constituer son propre état d"allocation des ressources

qui font partie de son "domaine".

Inconvénient : La répartition de l"allocation est partielle, et chaque allocateur n" a d"autorité que sur un

nombre restreint de ressources. (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