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 :
Cest 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, lun deux 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 lun de ces serveurs est responsable de la r ception de toutes les
lectures et critures, cest- -dire quil 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 lidentit 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 quun 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 dune 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 despace 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 lun 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
quil 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, do 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 quil obtient la
premi re de ces
r ponses, P4 sait que son
travail est termin ,
sachant que lun 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 quil est le vainqueur.
Lorsqu'il est pr t prendre le
relais, il annonce la prise de
contr le en envoyant un message
Publicité
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 nest 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 nSuds communiquent dans le sens contraire dune 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 dun 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 dextinction 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 linverse 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
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 lattaque 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 lattaque 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 dun consensus
Soit un ensemble de (n) processus (P1,&,Pn) reli s par des
canaux de communication et senvoyant 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 lalgorithme : chaque Pi d cide dune valeur
di
19/12/2019
Syst mes R partis
25
Mod lisation dun 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 lune des valeurs propos es.
Terminaison : tout processus correct d cide au bout dun temps fini.
19/12/2019
Syst mes R partis
26
Mod lisation dun consensus
D marrage
Quand un processus d marre-t-il
lalgorithme de consensus ?
D marrage simultan e
D marrage initi par lun des processus : diffusion
dun message dinitialisation de lalgorithme.
Sur r ception dun 1er message de lalgorithme.
Les trois formes sont quivalentes.
19/12/2019
Syst mes R partis
27
Mod lisation dun 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 dun 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 dun 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.
Publicité
Un processus peut d cider puis devenir incorrect.
K-consensus
k-Accord : au plus k-valeurs distinctes sont d cid es pour lensemble des
processus corrects
Consensus basique :k= 1
Consensus approximatif
-Accord : les valeurs d cid s par les processus corrects doivent distance
maximale lune de lautre
19/12/2019
Syst mes R partis
30
Mod lisation dun consensus : Mod le temporel
Synchrone
Asynchrone
borne sup rieure connue
sur le temps de transmission
et sur lavancement 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 dun consensus
D faillance dun processus
Arr t (crash failure ou panne) :
le processus fonctionne correctement jusqu
un point o il cesse d finitivement dagir.
Arr t
Omission
omission en mission : le processus omet
certaines missions quil 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 dun consensus
Communications
D faillance
R seau fiable : tout message finit par arriver
Perte : certains messages narrivent jamais
Ordre : respect de lordre d mission ou dun 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 dattaquer 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
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 dun 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 denvoyer un
message.
Jusqu' (f) des (N) processus peuvent tre d fectueux.
Des processus corrects peuvent d tecter labsence 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 quil nexistait 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 d 3f et a propos une solution
pour N e 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, lun 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
senvoient 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, cest quil 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
Publicité
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 quaucun 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 daccord (le commandant envoie des
valeurs diff rentes sil 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 quil 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 daccord, 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
saccordent:
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 : Lalgorithme
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.
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
seffondre.
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
Publicité
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 Suvre
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
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
Lenvoi 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 dacc der la ressource et ne veut pas y
acc der il renvoie un message OK l'exp diteur.
Si le destinataire est entrain dacc 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