Systèmes Répartis
Chapitre V:
Élection & Consensus
Amine DHRAIEF 1ère année Master Pro Data Science
Contexte
● Coordination et accord (agreement) entre processus :
C’est une famille de problèmes en algorithmique distribuée :
● Catégories de problèmes de cette famille
– Accord sur un processus jouant un rôle particulier : Élection d'un
maître
– Accord sur une valeur commune : Consensus
– Accord sur l'accès à une ressource partagée : Exclusion
mutuelle
– Accord sur une action à effectuer par tous ou personne :
Transaction
– Accord sur l'ordre d'envoi de messages à tous :Diffusion
atomique
ÉLECTION
Introduction
● De nombreux algorithmes distribués requièrent qu'un processus agisse en tant que coordinateur, initiateur ou ayant tout rôle spécifique.
● En général, peu importe le processus qui assume cette responsabilité particulière, l’un d’eux doit le faire.
→ Nous examinons les algorithmes permettant de choisir/élire un tel coordinateur.
19/12/2019
Systèmes Répartis
4
Exemple#1
● Les détails de votre compte bancaire sont répliqués sur plusieurs serveurs, mais l’un de ces serveurs est responsable de la réception de toutes les lectures et écritures, c’est-à-dire qu’il est le «coordinateur» parmi les autres serveurs.
– Et s'il y a deux coordinateurs par client?
– Que se passe-t-il si les serveurs ne sont pas d'accord sur l'identité du
coordinateur?
– Et si le coordinateur se bloque?
⇒ Chacun des scénarios ci-dessus mène à une incohérence
19/12/2019
Systèmes Répartis
5
Objectifs
● Dans un groupe de processus, élire un responsable/coordinateur pour
effectuer des tâches spéciales
● Ensuite, informer tous les membres du groupe de l’identité du
responsable/coordinateur
– Que se passe-t-il lorsqu'un responsable/coordinateur échoue?
– Certains processus le détectent (à l'aide d'un détecteur de panne !)
– alors en suite quoi?
● Objet : proposer un algorithme d’élection
– Élire un seul responsable/coordinateur parmi les processus non défaillants
– Tous les processus non défaillants s'accordent pour déterminer qui est le
responsable/coordinateur
19/12/2019
Systèmes Répartis
6
Le modèle
● Un système distribué de N Processus.
● Chaque processus a un identifiant (ID) unique.
● Les messages arrivent aux destinataires (même après
retransmissions).
● Des pannes peuvent se produire durant le processus de
l’élection.
19/12/2019
Systèmes Répartis
7
Appel à une élection
● Tout processus peut appeler à une élection.
● Un processus peut appeler au plus à une élection à la fois.
● Plusieurs processus sont autorisés à appeler une élection
simultanément.
– Ensemble, ils ne doivent élire qu’un seul coordinateur
● Le résultat d'une élection ne devrait pas dépendre du
processus qui la lance.
19/12/2019
Systèmes Répartis
8
Le problème d’élection
● À la fin d’une élection
⇒
Le « meilleur»
processus est élu.
– Meilleur → ayant le plus grand/le petit ID
– Meilleur → ayant la plus grande adresse IP, le
plus de CPU, de RAM d’espace disque
19/12/2019
Systèmes Répartis
9
The bully algorithm (Garcia-Molina 1982)
● Hypothèses :
– N processus {P0,. . . , PN - 1} – id(Pk) = k.
● Principes :
– Lorsqu'un processus constate que la coordinateur ne répond plus aux demandes, il déclenche une élection.
19/12/2019
Systèmes Répartis
10
The bully algorithm (Garcia-Molina 1982)
Un processus Pk, lance une élection comme suit:
1.Pk envoie un message ELECTION à tous les processus ayant des
identificateurs supérieurs:
Pk+1, Pk+2,. . . , PN-1.
2.Si personne ne répond, Pk remporte les élections et devient coordinateur.
3.Si l’un des niveaux supérieurs répond, il prend le relais et le travail de Pk
est terminé.
19/12/2019
Systèmes Répartis
11
The bully algorithm (Garcia-Molina 1982)
● À tout moment, un processus peut recevoir un message ELECTION d'un de ses
collègues dont le numéro est inférieur.
● Lorsqu'un tel message arrive, le destinataire renvoie un message OK à l'expéditeur
pour indiquer qu'il est en vie et qu'il prendra la relève.
● Le récepteur lance alors une élection, sauf s'il a déjà lancé une élection.
● En fin de compte, tous les processus abandonnent sauf un seul, et ce dernier est
le nouveau coordinateur.
● Il annonce sa victoire en envoyant à tous les processus un message leur indiquant
qu’il est le nouveau coordinateur.
19/12/2019
Systèmes Répartis
12
The bully algorithm (Garcia-Molina 1982)
● Si un processus qui était précédemment inactif revient, il lance
une élection.
● S'il s'agit du processus ayant le plus grand ID en cours, il remportera les élections et assumera les fonctions de coordinateur.
● Ainsi, le plus grand ID gagne toujours, d’où le nom «algorithme
du tyran».
– A bully : a person who uses strength or power to harm or intimidate
those who are weaker.
19/12/2019
Systèmes Répartis
13
Exemple
● Un groupe est constitué de huit
processus, avec des identificateurs numérotés de 0 à 7.
● Auparavant, le processus P7 était le coordinateur, mais il vient de tomber en panne. Le processus P4 est le premier à le remarquer, il envoie donc des messages ELECTION à tous les processus supérieurs, à savoir P5, P6 et P7.
19/12/2019
Systèmes Répartis
14
Exemple
● Les processus P5 et P6 répondent tous deux par OK.
● Dès qu’il obtient la première de ces réponses, P4 sait que son travail est terminé, sachant que l’un des P5 ou P6 prendra la relève et deviendra le coordinateur.
19/12/2019
Systèmes Répartis
15
Exemple
● P5 et P6 envoient des messages uniquement aux processus dont l'identificateur est supérieur à lui- même.
● P6 indique à P5 qu'il prendra le
relais. À ce stade, P6 sait que P7 est mort et qu’il est le vainqueur.
● Lorsqu'il est prêt à prendre le relais, il annonce la prise de contrôle en envoyant un message COORDINATOR à tous les processus en cours d'exécution.
19/12/2019
Systèmes Répartis
16
Élection sur un anneau unidirectionnel
● Hypothèses :
– le nombre de processus n’est pas connu a priori
– chaque processus Pi est identifié par un identifiant unique (unique identifier
UID)
– les processus sont rangés de façon quelconque sur un anneau logique
– Les nœuds communiquent dans le sens contraire d’une montre
● Objectif : élire le processus ayant le plus grand ID.
– Pour cela, chaque processus Pi transmet son UID à son voisin de gauche Pj
– celui-ci, à la réception d’un tel message, compare son propre UID (j) au
numéro reçu (i)
● si ce dernier est plus grand, il le transmet à son voisin de gauche ; ● sinon il transmet son propre numéro
⇒ principe d’extinction sélective des messages.
19/12/2019
Systèmes Répartis
17
Élection sur un anneau unidirectionnel
● Initialement, chaque processus de l'anneau est marqué comme non-
participant.
● Un processus qui constate une absence de coordinateur commence
une élection.
– Il envoie un message ELECTION contenant son UID. Il envoie ensuite ce
message dans le sens des aiguilles d'une montre (ou l’inverse mais toujours le même) à son voisin.
● Chaque fois qu'un processus envoie ELECTION ou transmet un message ELECTION, le processus se marque également en tant que participant.
19/12/2019
Systèmes Répartis
18
Élection sur un anneau unidirectionnel
● Lorsqu'un processus reçoit un message ELECTION, il compare l'UID
dans le message à son propre UID.
– Si l'UID dans le message d'élection est plus grand, le processus transfère
le message d'élection dans le sens des aiguilles d'une montre.
– Si l'UID dans le message d'élection est plus petit et si le processus n'est pas encore participant, le processus remplace l'UID dans le message par son propre UID et envoie le message d'élection mis à jour dans le sens des aiguilles d'une montre.
– Si l'UID dans le message d'élection est plus petit et que le processus est déjà un participant (c'est-à-dire, le processus a déjà envoyé un message d'élection avec un UID au moins égal à son propre UID), le processus détruit le message d’élection.
– Si l'UID dans le message d'élection entrant est identique à l'UID du
Publicité
processus, ce processus commence à agir en tant que coordinateur.
19/12/2019
Systèmes Répartis
19
Élection sur un anneau unidirectionnel
● Lorsqu'un processus commence à agir en tant que
coordinateur, il commence la deuxième étape de l'algorithme.
– Le processus coordinateur se définit comme non-participant
et envoie un message ÉLU à son voisin en lui annonçant son élection et son UID.
– Lorsqu'un processus reçoit un message ÉLU, il se marque
comme non-participant, enregistre l'UID de l’élu et le transmet sous forme inchangée.
– Lorsque le message ÉLU parvient au nouveau coordinateur
élu, celui-ci le rejette et les élections sont terminées.
19/12/2019
Systèmes Répartis
20
CONSENSUS
19/12/2019
Systèmes Répartis
21
Introduction
● Objectif : Les processus s'accordent sur une valeur après qu'un ou plusieurs processus ont proposé ce que cette valeur devrait être.
19/12/2019
Systèmes Répartis
22
Introduction
● Exemple :
– Guerre 6 Octobre /10 Ramadan/Yom Kippour 1973
– Égypte → Heure de l’attaque 18:00
● dernière lumières du jours pour profiter de la nuit et protéger les soldats du génie
lors de la constructions des ponts sur le canal de suez
– Syrie → Heure de l’attaque 06:00
● première lumières du jours pour que les chars syrien pénètrent dans le Golan et
que les chars Israélien soient aveuglé par le soleil ⇒ Consensus (Égypte/Syrie) → attaque à 14:00
● Exemple dans la littérature : Problème des généraux
byzantins
19/12/2019
Systèmes Répartis
23
Problème des généraux byzantins
● « Des généraux de l'armée byzantine campent autour d'une cité
ennemie. Ils ne peuvent communiquer qu'à l'aide de messagers et doivent établir un plan de bataille commun, faute de quoi la défaite sera inévitable. Cependant un certain nombre de ces messagers peuvent s'avérer être des traîtres, qui essayeront donc de semer la confusion parmi les autres. Le problème est donc de trouver un algorithme pour s'assurer que les généraux loyaux arrivent tout de même à se mettre d'accord sur un plan de bataille. »
– Source : www.wikipedia.fr
– Problème formulé dans : Leslie Lamport, Robert Shostak et Marshall Pease, « The Byzantine Generals Problem », ACM Transactions on Programming Languages and Systems, vol. 4, no 3, juillet 1982.
19/12/2019
Systèmes Répartis
24
Modélisation d’un consensus
● Soit un ensemble de (n) processus (P1,…,Pn) reliés par des canaux de communication et s’envoyant des messages.
● Le consensus doit être atteint même en présence de fautes.
– Nous supposons, que les communications sont fiables mais les processus
peuvent crasher.
● Initialement : chaque processus Pi est indécis et propose une
valeur vi
● A la terminaison de l’algorithme : chaque Pi décide d’une valeur
di
19/12/2019
Systèmes Répartis
25
Modélisation d’un consensus
● Les exigences d'un algorithme de consensus :
– Accord : la valeur décidée est la même pour tous les processus
corrects.
– Intégrité : tout processus décide au plus une fois (sa décision est
définitive).
– Validité : la valeur décidée est l’une des valeurs proposées.
– Terminaison : tout processus correct décide au bout d’un temps fini.
19/12/2019
Systèmes Répartis
26
Modélisation d’un consensus Démarrage
● Quand un processus démarre-t-il
l’algorithme de consensus ?
– Démarrage simultanée
– Démarrage initié par l’un des processus : diffusion
d’un message d’initialisation de l’algorithme.
– Sur réception d’un 1er message de l’algorithme.
● Les trois formes sont équivalentes.
19/12/2019
Systèmes Répartis
27
Modélisation d’un consensus
● Considérons un système dans lequel les processus ne peuvent
pas échouer.
– Il est alors simple de résoudre le consensus.
● Par exemple, nous pouvons collecter les processus dans un groupe et faire en sorte que chaque processus diffuse de manière fiable la valeur proposée aux membres du groupe.
● Chaque processus attend d'avoir collecté toutes les N valeurs
(y compris les siennes).
● Il évalue ensuite la fonction majority(v1,v2,...vN), qui renvoie la
valeur qui apparaît le plus souvent parmi ses arguments.
19/12/2019
Systèmes Répartis
28
Modélisation d’un consensus
● Chaque processus reçoit le même ensemble de valeurs
proposées et chaque processus évalue la même fonction de ces valeurs.
● Donc, ils doivent tous être d'accord, et si chaque processus propose la même valeur, ils décident tous de cette valeur.
● majority() n'est qu'une fonction possible que les processus pourraient utiliser pour convenir d'une valeur à partir des valeurs candidates.
– Par exemple, si les valeurs sont ordonnées, les fonctions minimum() et
maximum() peuvent être appropriées.
19/12/2019
Systèmes Répartis
29
Modélisation d’un consensus : Variantes
● Consensus uniforme
– Accord uniforme : la valeur décidée est la même pour tous les processus
(corrects ou ultérieurement fautifs) qui décident.
– Un processus peut décider puis devenir incorrect.
● K-consensus
– k-Accord : au plus k-valeurs distinctes sont décidées pour l’ensemble des
processus corrects
– Consensus basique :k= 1
● Consensus approximatif
– ε-Accord : les valeurs décidés par les processus corrects doivent à distance ε
maximale l’une de l’autre
19/12/2019
Systèmes Répartis
30
Modélisation d’un consensus : Modèle temporel
● Synchrone
● Asynchrone
– borne supérieure connue
sur le temps de transmission et sur l’avancement des processus.
– Usuellement, algorithmes fonctionnant par tours, synchronisés sur tous les processus.
– Pas de borne connue :
avancement arbitrairement lent des processus et du réseau.
– Modèle moins contraint, plus réaliste (mais plus difficile)
P1
P2
P3
Tour n
Tour n+1
19/12/2019
Systèmes Répartis
31
Modélisation d’un consensus Défaillance d’un processus
● Arrêt (crash failure ou panne) :
– le processus fonctionne correctement jusqu’à
un point où il cesse définitivement d’agir.
Arrêt
● Omission
– omission en émission : le processus omet certaines émissions qu’il aurait dû faire,ou cesse définitivement.
– omission en réception : le processus
ignore certains messages en réception,ou cesse définitivement.
● Arbitraire (byzantine failure) :
– Le processus ment (par omission ou par
contenu arbitraire des messages envoyés)
Omission en émission
Omission en réception
Omission en générale
Arbitraire
19/12/2019
Systèmes Répartis
32
Modélisation d’un consensus Communications
● Défaillance
– Réseau fiable : tout message finit par arriver
– Perte : certains messages n’arrivent jamais
– Ordre : respect de l’ordre d’émission ou d’un autre ordre
– Arbitraire : duplication, modification du contenu. . .
● Hypothèse de réseau fiable
– Les défaillances réseau en asynchrone peuvent être modélisées
par des défaillances de site
⇒ On suppose le réseau fiable
19/12/2019
Systèmes Répartis
33
The Byzantine Generals Problem
● Métaphore utilisé par Lamport en 1982
● Trois généraux ou plus doivent accepter d'attaquer ou de se
retirer.
– L'un, le commandant, donne l'ordre. Les autres, lieutenants du commandant,
doivent décider d’attaquer ou de se retirer.
● Mais un ou plusieurs des généraux peuvent être "traîtres" -
(processus défectueux).
– Si le commandant est perfide, il propose d'attaquer à un général et de se
retirer vers un autre.
– Si un lieutenant est perfide, il dit à l'un de ses pairs que le commandant lui a
dit d'attaquer et un autre qu'ils doivent se retirer.
19/12/2019
Systèmes Répartis
Publicité
34
The Byzantine Generals Problem
● Le problème des généraux byzantins diffère du consensus en ce qu'un processus distingué fournit une valeur sur laquelle les autres doivent s'entendre, au lieu que chacun d'entre eux propose une valeur.
● Les exigences pour résoudre ce problème sont les suivants :
– Accord : la valeur décidée est la même pour tous les processus corrects.
– Terminaison : tout processus correct décide au bout d’un temps fini.
– Intégrité: si le commandant est correct, tous les processus corrects décident
de la valeur proposée par le commandant.
19/12/2019
Systèmes Répartis
35
The Byzantine generals problem in a synchronous system
● On suppose que les processus peuvent subir une défaillance
arbitraire.
– C'est-à-dire qu'un processus défectueux peut envoyer n'importe quel message
avec n'importe quelle valeur à tout moment et il peut omettre d’envoyer un message.
● Jusqu'à (f) des (N) processus peuvent être défectueux.
● Des processus corrects peuvent détecter l’absence de message
pendant une période donnée; mais ils ne peuvent pas conclure que l'expéditeur est tombé en panne, car il peut rester silencieux pendant un certain temps, puis envoyer à nouveau des messages.
19/12/2019
Systèmes Répartis
36
The Byzantine generals problem in a synchronous system
● Nous supposons que les canaux de
communication entre des paires de processus sont privés.
● Nous supposons qu'aucun processus
défaillant ne peut injecter des messages dans le canal de communication entre les processus corrects.
19/12/2019
Systèmes Répartis
37
The Byzantine generals problem in a synchronous system
● Lamport a examiné le cas de trois processus qui envoient des messages non signés entre eux.
● Il a montré qu’il n’existait aucune solution garantissant
le respect des les conditions du problème des généraux byzantins si un processus peut échouer.
● Il a généralisé ce résultat pour montrer qu'aucune
solution n'existe si N ≤ 3f et a proposé une solution pour N ≥ 3f +1.
19/12/2019
Systèmes Répartis
38
The Byzantine generals problem in a synchronous system Impossibilité avec trois processus
● Dans la configuration de gauche, l’un des lieutenants, p3, est défectueux; à droite le commandant, p1, est défectueux.
19/12/2019
Systèmes Répartis
39
The Byzantine generals problem in a synchronous system Impossibilité avec trois processus
● Chaque scénario présente deux séries de messages: les valeurs envoyées par le commandant et les valeurs que les lieutenants s’envoient ensuite.
● Les préfixes numériques servent à spécifier les sources des messages
et à afficher les différents tours. Lisez le symbole ":" dans les messages sous la forme "dit"; Par exemple, "3: 1: u" est le message "3 dit 1 dit u".
19/12/2019
Systèmes Répartis
40
The Byzantine generals problem in a synchronous system Impossibilité avec trois processus
● Dans le scénario de gauche, le commandant envoie correctement la même valeur v à chacun des deux autres processus, et p2 le renvoie correctement à p3. Cependant, p3 envoie une valeur u≠v à p2.
● Tout ce que p2 sait à ce stade, c’est qu’il a reçu des valeurs
différentes; il ne peut pas dire lesquels ont été envoyés par le commandant..
19/12/2019
Systèmes Répartis
41
The Byzantine generals problem in a synchronous system Impossibilité avec trois processus
● Dans le scénario de droite, le commandant est fautif et
envoie des valeurs différentes aux lieutenants.
● Une fois que p3 a correctement répercuté la valeur x
reçue, p2 se trouve dans la même situation que lorsque p3 était défectueux: il a reçu deux valeurs différentes.
19/12/2019
Systèmes Répartis
42
The Byzantine generals problem in a synchronous system Impossibilité avec trois processus
● Si une solution existe, alors le processus p2 est tenu de choisir la valeur v lorsque le commandant est correct, en fonction de la condition d'intégrité.
● Si nous acceptons qu’aucun algorithme ne peut éventuellement
distinguer les deux scénarios, p2 doit également choisir la valeur envoyée par le commandant dans le scénario de droite.
19/12/2019
Systèmes Répartis
43
The Byzantine generals problem in a synchronous system Impossibilité avec trois processus
● Suivant exactement le même raisonnement pour p3, en supposant qu'il soit correct, nous sommes obligés de conclure (par symétrie) que p3 choisit également la valeur envoyée par le commandant comme valeur de décision.
● Mais cela contredit la condition d’accord (le commandant envoie des valeurs différentes s’il est défectueux). Donc, aucune solution n'est possible.
19/12/2019
Systèmes Répartis
44
The Byzantine generals problem in a synchronous system Solution avec un processus défectueux
● N=4 et f=1
● Les généraux corrects parviennent à un accord en deux tours de
messages:
– Au premier tour, le commandant envoie une valeur à chacun des lieutenants.
– Au deuxième tour, chacun des lieutenants envoie la valeur qu’il a reçue à ses
pairs.
19/12/2019
Systèmes Répartis
45
The Byzantine generals problem in a synchronous system Solution avec un processus défectueux
● Dans le cas de gauche, les deux processus de lieutenant correct sont d’accord, décidant de la valeur du commandant:
– p2 décide de la majorty(v,u,v) = v
– p4 décide de la majorty(v,v,w) = v
19/12/2019
Systèmes Répartis
46
The Byzantine generals problem in a synchronous system Solution avec un processus défectueux
● Dans le cas de droite, le commandant est
défectueux, mais les trois processus corrects s’accordent:
– p2, p3 et p4 décident de la majorty(u,v,w) = {} pas de
majorité.
19/12/2019
Systèmes Répartis
47
Exclusion mutuelle
19/12/2019
Systèmes Répartis
48
Contexte
● La concurrence et la collaboration entre plusieurs processus
sont fondamentales pour les systèmes distribués.
● Dans de nombreux cas, cela signifie que les processus devront accéder simultanément aux mêmes ressources.
● Pour éviter que de tels accès simultanés ne corrompent la ressource ou la rendent incohérente, des solutions sont nécessaires pour accorder un accès exclusif mutuel par processus.
19/12/2019
Systèmes Répartis
49
Contexte
● Un processus est dans les trois états
possibles, par rapport à l'accès à la ressource:
– demandeur
– dedans
– dehors
DEHORS
Acquérir
Libérer
DEDANS
DEMANDEUR
Gestion par le middelware
19/12/2019
Systèmes Répartis
50
Aperçu
● Les algorithmes d'exclusion mutuelle
distribués peuvent être classés en plusieurs catégories :
– Approches centralisées.
– Contrôle basées sur des jetons.
– Contrôle par permission.
19/12/2019
Systèmes Répartis
51
Exclusion mutuelle Approches centralisées
19/12/2019
Systèmes Répartis
52
Approches centralisées
● Mécanisme centralisé de synchronisation en système distribué regroupe les algorithmes qui utilisent un coordinateur pour gérer l'exclusion mutuelle.
● Le coordinateur :
– centralise les requêtes des différents processus de l'application
– réalise l'exclusion mutuelle en accordant la permission d'entrée
en Section Critique
– gère une file des requêtes en attente de Section Critique.
19/12/2019
Systèmes Répartis
53
Approches centralisées : L’algorithme
● Quand un processus Pi veut entrer en Section Critique, il
envoie au coordinateur un message de "demande d'entrée en Section Critique". Il attend la permission du coordinateur, avant d'entrer en Section Critique.
● Lorsque Pj reçoit la permission, il entre en Section Critique.
● Quand Pi quitte la Section Critique, il envoie un message
de sortie de Section Critique au coordinateur.
19/12/2019
Systèmes Répartis
54
Approches centralisées : Rôle du Coordinateur
● Si personne en Section Critique, à la réception d'une demande
d'accès de Pi , il retourne « permission d'accès » à Pi .
● Si un processus Pj est déjà en Section Critique. Le coordinateur
refuse l'accès. La méthode dépend de l'implantation :
– soit il n'envoie pas de réponse, le processus Pj est bloqué. – soit il envoie une réponse : « Permission non accordée ».
→ Dans les deux cas, le coordinateur dépose la demande de Pj dans une file d'attente.
● A la réception d'un message de sortie de Section Critique, le
coordinateur prend la première requête de la file d'attente de la Section Critique et envoie au processus un message de permission d'entrée en Section Critique.
19/12/2019
Systèmes Répartis
55
Approches centralisées
● (a) Le processus P1 demande l'autorisation d'accéder à une ressource partagée. La
permission est accordée.
● (b) Le processus P2 demande la permission d'accéder à la même ressource mais ne
reçoit aucune réponse.
● (c) Lorsque P1 libère la ressource, le coordinateur répond à P2.
Publicité
19/12/2019
Systèmes Répartis
56
Approches centralisées : Les Avantages
● Algorithme garantit l'exclusion mutuelle
● Algorithme juste (les demandes sont accordées
dans l'ordre de réception)
● Pas de famine (aucun processus ne reste bloqué)
● Solution facile à implanter
● Pas de supposition sur l'ordre des messages
● Complexité : maximum 2 ou 3 messages
19/12/2019
Systèmes Répartis
57
Approches centralisées : Les Inconvénients
● Si le coordinateur a un problème, tout le système
s’effondre.
● Si les processus sont bloqués lors de demande
d'accès à une Section Critique occupée : impossibilité de détecter la panne du coordinateur.
● Dans de grands systèmes, le coordinateur = goulet
d'étranglement.
19/12/2019
Systèmes Répartis
58
Exclusion mutuelle Contrôle basées sur des jetons
19/12/2019
Systèmes Répartis
59
Contrôle basées sur des jetons
● Dans les solutions basées sur des jetons, l'exclusion mutuelle est obtenue
en transmettant un message spécial entre les processus, appelé jeton.
– Un jeton circule entre les processus et donne l'accès à la ressource
● Deux approches : jeton circulant en permanence ou affecté à la demande
des processus.
● La gestion et l'affectation du jeton – et donc l'accès à la ressource – est
faite par les processus entre eux
– Un seul jeton est disponible et celui qui en possède est autorisé à accéder à la ressource
partagée.
– Une fois terminé, le jeton est transmis à un processus suivant.
– Si un processus ayant le jeton n'est pas intéressé par l'accès à la ressource, il le transmet.
19/12/2019
Systèmes Répartis
60
Contrôle basées sur des jetons
● Lorsque l'anneau est initialisé, le processus P
0 reçoit un jeton.
● Le jeton circule autour de l'anneau.
● En supposant qu'il y ait N processus, le jeton est passé du processus Pk au processus P(k + 1)mod N en messages point à point.
19/12/2019
Systèmes Répartis
61
Contrôle basées sur des jetons : algorithme de Le Lann
● Lorsqu'un processus acquiert le jeton auprès de son voisin, il vérifie s'il doit
accéder à la ressource partagée.
● Si tel est le cas, le processus accède à la ressource ensuite il la libère. Une fois
terminé, il passe le jeton le long de l'anneau.
● Si un processus reçoit le jeton de son voisin et qu'il n'est pas intéressé par la
ressource, il le fait simplement passer.
● En conséquence, lorsque aucun processus n'a besoin de la ressource, le jeton
ne fait que circuler autour de l'anneau.
● Pour des raisons d'équité, un processus ne peut pas entrer deux fois de suite en
Section Critique
19/12/2019
Systèmes Répartis
62
Contrôle basées sur des jetons : algorithme de Le Lann
● Avantages
– Simple à mettre en œuvre
– Intéressant si nombreux demandeurs de la
ressource
– Équitable en terme de nombre d'accès et de temps
d'attente
19/12/2019
Systèmes Répartis
63
Contrôle basées sur des jetons : algorithme de Le Lann
● Inconvénients
– Nécessite des échanges de messages même si aucun
processus ne veut accéder à la Section Critique
– Temps d'accès à la Section Critique peut être long
– Perte du jeton :
● difficulté de détecter un tel cas ● impossibilité de prendre en compte le temps écoulé entre deux passages du jeton (temps passé en Section Critique est très variable)
● des algorithmes gèrent ce problème de perte et régénération de
jeton sur un anneau
19/12/2019
Systèmes Répartis
64
Contrôle basées sur des jetons : algorithme de Le Lann
● Problème de la panne d'un processus
– plus facile à gérer que dans les algorithmes
précédents
– envoi d'un acquittement à la réception du jeton :
permet de détecter la panne de l'un des processus
– le processus mort peut être retiré de l'anneau et le
suivant prend alors sa place
– pour implanter ceci : chaque processus doit connaître
la configuration courante de l'anneau.
19/12/2019
Systèmes Répartis
65
Exclusion mutuelle Contrôle par permission
19/12/2019
Systèmes Répartis
66
Méthodes par permission
● Un processus doit avoir l'autorisation des autres
processus pour accéder à la ressource.
● Principe général
– Un processus demande l'autorisation à un sous-ensemble donné de
tous les processus
● Deux modes
– Permission individuelle : un processus peut donner sa permission à
plusieurs autres à la fois
– Permission par arbitre : un processus ne donne sa permission qu'à
un seul processus à la fois
19/12/2019
Systèmes Répartis
67
Permission individuelle : Algorithme de Ricart & Agrawala
● Algorithme de [Ricart & Agrawala, 81]
– Permission individuelle
– Chaque processus demande l'autorisation à tous les autres (sauf lui par
principe)
● Se base sur une horloge logique (Lamport) pour garantir le
bon fonctionnement de l'algorithme
– Ordonnancement des demandes d'accès à la ressource
– Si un processus ayant fait une demande d'accès reçoit une demande d'un
autre processus avec une date antérieure à la sienne, il donnera son autorisation à l'autre processus ● Et passera donc après lui puisque l'autre processus fera le contraire
19/12/2019
Systèmes Répartis
68
Permission individuelle : Algorithme de Ricart & Agrawala
● Lorsqu'un processus souhaite accéder à une
ressource partagée, il crée un message contenant le nom de la ressource, son numéro de processus et l'heure (logique) actuelle.
● Il envoie ensuite le message à tous les autres
processus
● L’envoi de messages est supposé fiable; c'est-à-dire
qu'aucun message n'est perdu.
19/12/2019
Systèmes Répartis
69
Permission individuelle : Algorithme de Ricart & Agrawala
● Lorsqu'un processus reçoit un message de demande d'un autre
processus, l'action qu'il entreprend dépend de son propre état par rapport à la ressource nommée dans le message.
● Trois cas différents doivent être clairement distingués:
– Si le destinataire n'est pas entrain d’accéder à la ressource et ne veut pas y
accéder → il renvoie un message OK à l'expéditeur.
– Si le destinataire est entrain d’accèder à la ressource → il ne répond tout
simplement pas. Au lieu de cela, il met la demande en file d'attente.
– Si le destinataire souhaite également accéder à la ressource mais ne l'a pas encore
fait :
● il compare l'horodatage du message entrant à celui contenu dans le message qu'il a envoyé
à tous → Le plus bas gagne.
● Si l'horodatage du message entrant est inférieur → le destinataire renvoie un message OK. ● Si son propre message a un horodatage inférieur → le destinataire met en file d'attente la
demande entrante et n'envoie rien.
19/12/2019
Systèmes Répartis
70
Permission individuelle : Algorithme de Ricart & Agrawala
● Après avoir envoyé des demandes demandant une
autorisation, un processus est suspendu et attend que tous les autres aient donné leur autorisation.
● Dès que toutes les autorisations sont entrées, le
processus peut acquérir la ressource.
● Une fois l'opération terminée, le processus envoie des messages OK à tous les processus de sa file d'attente et les supprime tous de la file d'attente.
19/12/2019
Systèmes Répartis
71
Permission individuelle : Algorithme de Ricart & Agrawala
● (a) Deux processus veulent accéder à une ressource partagée en même temps
moment.
● (b) P0 a l'horodatage le plus bas, donc il gagne.
● (c) Lorsque le processus P0 libère la ressource, un message OK est envoyé, de sorte
que P2 peut maintenant accéder à la ressource.
19/12/2019
Systèmes Répartis
72
The End !
19/12/2019
Systèmes Répartis
73