Système de Quorum Dans Les Grilles

7/23/2019 Système de Quorum Dans Les Grilles

http://slidepdf.com/reader/full/systeme-de-quorum-dans-les-grilles 1/6

Système de quorum dans les grilles

République Algérienne Démocratique et Populaire

Université Dr Tahar Moulay Saida

Faculté de technologie

Département d’Informatique

1ère

année master RISR

2014 - 2015

Préparé par :

Awad Samir

Haddi Mohamed Reda

Bouras Bouhaous



Table des matières

1. Introduction ........................................................................... 2

2. Définition ............................................................................... 2

3. Algorithme de Maekawa ......................................................... 2

3.1. Différents types de messages échangés ................................ 2

3.2. Algorithme ............................................................................. 3

4. Conclusion .............................................................................. 4

Références ..................................................................................... 5



2

1. Introduction:Les systèmes de quorums sont des constructions bien connus qui

permettent d’améliorer les performances et la disponibilité des systèmes

distribués. Ils sont aussi utilisés comme un moyen pour améliorer le temps

de réponse de services déployés sur des grilles de calcul. Ils ont été

employés pour mettre en application beaucoup de problèmes de

coordination dans les systèmes répartis tels que l’exclusion mutuelle.

2.

Définition:Un système de quorum Q sur un univers U est un ensemble sur U tel que

pour tout Q i, Q j ∈ Q, la propriété d’intersection Q i ∩ Q j ≠ ∅ est vérifiée. Par

exemple Q = {{P1, P2}, {P2, P3}, {P3, P1}} est un système de quorum.

3.

Algorithme de Maekawa:L'algorithme de Maekawa est un algorithme d'exclusion mutuelle sur un

système distribué. Dans cet algorithme, chaque composant appelé « site » ne

peut donner de permission d'entrée dans une section critique qu'à un seul

autre composant à la fois. Chaque site a la charge d'arbitrer les éventuels

conflits qui apparaîtront entre différents autres sites. Cela impose au

participant à qui cette permission a été donnée de rendre la main sur la section

critique une fois qu'il a fini son travail, c'est-à-dire lorsqu'il sort de sa section

critique.

3.1. Différents types de messages échangés:

Les types de messages échangés lors de l'exécution de l'algorithme sont :

DEMANDE : un message de demande d'entrée en section critique.

ACCORD : un message d'acceptation d'entrée en section critique.

ÉCHEC : un message de refus d'entrée en section critique.

SONDAGE : un message envoyé pour résoudre les problèmes

d’interblocage.

RESTITUTION : une réponse à un message SONDAGE.

LIBÉRATION : un message de sortie de section critique.



3

3.2. Algorithme:

Site demandeur: Un site Pi demandant envoie un message de demande (ts, i)

à tous les sites dans son quorum Ri.

Site receveur:

Lors de la réception d'un message de demande (ts, i), le site de réception P j:

Si le site P j n'a pas un accord en cours (c'est-à-dire, un message

d'accord qui n'a pas été relâché), alors le site P j envoie un message

d'accord (j) sur le site Pi.

Si le site P j a un accord en cours pour un processus avec une priorité

plus élevée que la demande, alors le site P j envoie un message d'échec

(j) sur le site Pi et P j ajoute à sa file d'attente la demande du site Pi.

Si le site P j a un accord en cours pour un processus avec une priorité

inférieure à la demande, alors le site P j envoie un message de sondage

(j) au processus qui est actuellement autorisé à accéder à la section

critique par le site P j (c'est-à-dire le site avec le message d'accord en

cours).

Lors de la réception d'un message de sondage (j), le site Pk:

Envoie un message de restitution (k) sur le site P j si et seulement si le

site Pk a reçu un message d'échec d'un autre site, ou si Pk a envoyé un

message de restitution à un autre site, mais n'a pas reçu un nouvel

accord.

Lors de la réception d'un message de restitution (k), le site P j:

Envoie un message d'accord à la première demande de sa file

d'attente. Notez que les requêtes au sommet sont celles de plus haute

priorité.

Place Pk dans sa file d'attente.

Lors de la réception d'un message de libération (i), le site P j:

Supprime Pi de sa file d'attente.

Envoie un message d'accord à la première demande de sa file

d'attente.



4

Section critique:

Un site Pi entre dans la section critique lorsqu'il reçoit un message

d'accord de tous les sites du quorum Ri.

A la sortie de la section critique, Pi envoie un message de libération(i) à tous les sites de Ri.

Quorum: Un quorum doit respecter les propriétés suivantes:

1)

∈ { } ∅

2) ∈ { } ∈ 3)

∈ { } 4)

Le site Pi est contenu dans exactement K ensembles de requêtes ce

qui implique: √

4. Conclusion:La complexité de l'algorithme de Maekawa en fonction du nombre de

messages sur le réseau est en O(√ ) mais le problème de cette approche est

la complexité de construction des quorums qui rend difficile sa mise en oeuvre

sur un système composé d'un grand nombre de sites.



5

Références

[1]. Ousmane Thiare

« Exclusion mutuelle de groupes dans les systèmes distribués»

Disponible sur : https://tel.archives-ouvertes.fr/tel-00198862/document

[2]. Vincent Gramoli

« Mémoire partagée distribuée pour systèmes dynamiques à grande échelle»

Disponible sur : ftp://ftp.irisa.fr/techreports/theses/2007/gramoli-f.pdf

[3]. « Algorithme de Maekawa»

Disponible sur : http://fr.wikipedia.org/wiki/Algorithme_de_Maekawa

[4]. Julien Sopena

« Algorithmes d'exclusion mutuelle: tolérance aux fautes et adaptation aux

grilles»

Disponible sur:

http://julien.sopena.fr/recherche/these/These-Sopena-Manuscrit.pdf

http://fr.wikipedia.org/wiki/Algorithme_de_Maekawa

http://fr.wikipedia.org/wiki/Algorithme_de_Maekawa

Documents

Système de Quorum Dans Les Grilles