Exclusion mutuelle de groupe basée sur les quorums

Algorithme d’exclusion mutuelle de groupe basé sur les quorums

Dans [Jou01b], Joung présente le système de quorum de surface (surficial quorum system) pour l’exclusion mutuelle de groupe. Il présente aussi une modification de l’algorithme de Maekawa [Mae85] de sorte que le nombre de processus qui peuvent accéder à une ressource en un temps fini ne soit pas limité à la structure du système de quorums. Il ne distingue pas les processus et les ressources, c’est-à-dire qu’un processus peut appartenir à un ou plusieurs groupes. Le processus doit identifier un unique groupe dans lequel il appartient quand il veut entrer en section critique. Dans ce travail, nous avons fait une différence entre les processus et les ressources. Nous présentons aussi une modification de l’algorithme de Maekawa. Notre algorithme d’exclusion mutuelle de groupe est basé sur les quorums. Le nombre de processus qui peuvent entrer en section critique n’est pas limité [TN06]. Exclusion mutuelle de groupe basée sur les quorums Exclusion mutuelle de groupe basée sur les quorums Le problème est de proposer un algorithme pour un système satisfaisant les conditions suivantes : • Exclusion mutuelle (Surêté) : À tout moment, deux sessions de différents groupes ne peuvent être ouvertes simultanément. • Absence de blocage (Vivacité) : Une session demandée sera accessible au bout d’un temps fini. • Entrée concurrente (Efficacité) : Si un groupe g de processus demandent une session et aucun autre groupe de processus n’est intéressé d’une session différente, alors les processus du groupe g peuvent accéder en section critique de façon concurrente [Jou98, KM01, Had01]. Notons que la dernière propriété est une conséquence triviale de la deuxième. Nous considérons un système de processus asynchrones P1, ·, Pn, chacun d’entre eux tourne à travers les trois états suivants, avec NSC (non section critique) étant l’état initial du système. • Non Section Critique : Le processus est en dehors de SC (section critique) et ne souhaite pas entrer en section critique. • Attente : Le processus attend d’entrer en section critique mais n’est pas encore entré. • Section Critique : Le processus est en section critique. 

Algorithme basé sur les quorums pour l’exclusion mutuelle de groupe

Dans cette section, nous présentons un algorithme utilisant les quorums pour résoudre le problème de l’exclusion mutuelle de groupe. Le réseau est supposé complet et fiable. Dans le chapitre 2, les définitions formelles sur les quorums et coteries ont été présentés.

Motivation et Contribution

La difficulté majeure dans le problème de l’exclusion mutuelle de groupe est d’éviter une situation d’interblocage, c’est-à-dire le blocage mutuel de plusieurs processus du système. Le problème est de gérer la propriété d’entrée concurrente pour les processus désirant entrer en section critique, qui a été définie ci-dessus.  Dans [Jou01b], Joung a présenté les quorums de surface pour résoudre le problème de l’exclusion mutuelle de groupe. Il a ensuite présenté deux modifications de l’algorithme de Maekawa [Mae85]. Dans notre travail, nous nous sommes intéressés au problème de l’exclusion mutuelle de groupe basé un système ordinaire de quorums. Notre but a été de présenter une solution au problème de l’exclusion mutuelle de groupe, qui est aussi une modification de l’algorithme de Maekawa, qui réduit le nombre de messages pas entrée en section critique, par rapport à l’algorithme de Joung [Jou01b], en O( √ n + |Q|), où n est le nombre de processus et |Q|, la taille du quorum choisi. L’algorithme que nous avons présenté dans cette section permet aux processus non seulement d’occuper la section critique en même temps, mais aussi d’y entrer sans surplus de synchronisation. Dans notre solution proposée, les requêtes sont envoyées simultanément par p aux noeuds de Q pour minimiser le délai de synchronisation, qui est le délai entre le temps qu’un processus souhaite entrer en section critique et celui d’entrée en section critique. Cependant, en raison du fait que le système est asynchrone, un processus doit garder une requête tout en attendant qu’un autre processus libére la session. Ceci peut créer un blocage. L’algorithme de Maekawa résout le phénomène de blocage en exigeant une relation d’ordre d’exécution entre les processus de basse priorité et les processus de haute priorité. 

Principe de l’algorithme

L’algorithme présenté ici peut être directement adapté à l’exclusion mutuelle de groupe comme suit. Un processus P ∈ P qui veut entrer en section critique chosit un groupe g, selectionne un quorum arbitraire Q, et entre en section critique seulement s’il reçoit la permission de tous les membres du quorum Q. Notre algorithme fonctionne de la manière suivante : quand un processus Pi veut participer à une session x, il envoie un message REQ() à x afin d’obtenir un message OK() de la part de ce dernier. La session x à son tour envoie un message Open_Session() à tous les membres de son groupe. Si x reçoit tous les messages Aut_Session() de son groupe, elle envoie un message OK() au processus Pi . Lors de la sortie de la section critique, le processus Pi envoie un message de libération REL() à la session x. Supposons qu’un membre du quorum donne la permission à un seul processus à la fois. Alors, par la propriété d’intersection, deux processus ayant demandé différents groupes ne 47 Exclusion mutuelle de groupe basée sur les quorums peuvent entrer en section critique simultanément. La propriété de minimalité est utilisée plutôt pour améliorer l’efficacité. Les groupes sont en compétition pour l’entrée en section critique et sont de priorité égale (aucun n’est privilégié). Le nombre de messages requis pour entrer en section critique est indépendant du quorum choisi par un processus. Chaque noeud partage la même responsabilité dans le système. Pour la simplicité, nous ne donnerons pas ici le code explicite pour manipuler les horloges logiques. L’estampille pour la requête courante est maintenant par une variable Hi . Une relation d’ordre notée « < » sur les estampilles est définie de la façon suivante : hPi , Hii < hPj , Hj i si et seulement si (Hi < Hj ) ou ((Hi = Hj ) ∧ (Pi < Pj )). Les priorités sont implémentées par les horloges logiques qui ont été définies par [Lam78b]. Plus l’estampille est petite, plus la priorité de la requête est haute. Spécifiquement, si un noeud i reçoit une requête par un noeud p après avoir donné une permission à q et que la priorité de p est plus haute que celle de q, alors i envoie un message d’investigation (message Interrogation) à q. Le processus q alors retourne à i sa requête (en lui envoyant un message de refus) s’il ne peut pas avoir une permission de tous les noeuds du quorum Q choisi. Alors le noeud i donne à p sa permission après avoir reçu la requête de q. Quand p sort de la section critique et libère la requête de i, il retourne la requête à q (vraisemblablement aucun autre processus de plus haute priorité que q est en attente de la permission du noeud i).

Messages echangés par processus/session et session/session

Les messages échangés entre les processus et les sessions d’une part et entre les sessions d’autre part dans l’algorithme sont : Open_Session(x, Hx) : message de demande d’ouverture de la session x. Aut_Session(x, Hx) : message d’autorisation de l’ouverture de la session x. End_Session(x, Hx) : message de fermeture de la session x. REQ(P, x) : message envoyé par P pour demander la participation à la session x. OK(x) : messade d’autorisation envoyé par P afin de participer à la session x. REL(x) : message signifiant que P a fermé la session x.

Variables locales à la session x

Les variables locales utilisées dans l’algorithme pour la session x sont : Hx : un nombre d’ordre utilisé pour implémenter la requête logique de la session x. Il est initialisé à 0.Hr : un nombre d’ordre utilisé pour implémenter la requête logique de la session x. Il est utilisé pour estampiller la requête afin d’ouvrir la session x. Il est initialisé à 0. Nextx : groupe de sessions en attente de participation à la session x. Initialement Nextx = Nil pour toute session x. HATx : boolean, True si la session x recoit un message Aut_Session() de son groupe. W Sx : groupe de processus en attente de participation à la session x. Initialement, W Sx = ∅ pour toute session x. Nrelx : désigne le nombre de messages de libération que la session x attend de l’ensemble des processus. Initialement, Nrelx = 0 pour toute session x. X : où X = {x, y, z, · · · } est un ensemble dynamique de m sessions dans le réseau. Q : quorum sélectionné par le processus P. g : le groupe dans lequel P appartient. status : le statut du processus P. lockednodes: ensemble de noeuds ayant donné la permission à P. Initialement lockenodes = ∅. Add() : ajoute un noeud demandeur i dans la file Nextx telle que le noeud précédent i dans Nextx est tel que (j, Hj ) < (i, Hi) et le noeud après i dans Nexts est tel que (k, Hk) > (i, Hi). Remove() : enlève le noeud à la tête de la file Nextx. Head() : retourne le premier noeud de la file Nextx. SC : désigne la section critique.