Algorithmique distribue
Exclusion mutuelle
Eric Cariou
Master Technologies de l'Internet 1re anne
Universit de Pau et des Pays de l'Adour
Dpartement Informatique
[Link]@[Link]
1
Exclusion mutuelle distribue
Exclusion mutuelle
Contexte de plusieurs processus s'excutant en parallle
Accs une ressource partage par un seul processus la fois
Exclusion mutuelle en distribu
Accs une ressource partage distante par un seul
processus la fois
Processus distribus
Requtes et gestion d'accs via des messages changs entre
les processus
Ncessit de mettre en oeuvre des algorithmes grant ces
changes de messages pour assurer l'exclusion mutuelle
Algorithmes d'exclusion mutuelle dcrits dans ce cours : plus de
dtails dans Synchronisation et tat global dans les systmes
rpartis, Michel Raynal, Eyrolles, 1992
2
Rappel exclusion mutuelle
Exclusion mutuelle
Une ressource partage ou une section critique n'est
accde que par un processus la fois
Un processus est dans 3 tats possibles, par rapport
l'accs la ressource
Demandeur : demande utiliser la ressource, entrer dans la section
Dedans : dans la section critique, utilise la ressource partage
Dehors : en dehors de la section et non demandeur d'y entrer
Changement d'tat par un processus
De dehors demandeur pour demander accder la ressource
De dedans dehors pour prciser qu'il libre la ressource
Le passage de l'tat demandeur l'tat dedans est gr par le
systme et/ou l'algorithme de gestion d'accs la ressource
3
Rappel exclusion mutuelle
Diagramme d'tats de l'accs en exclusion mutuelle
Dehors
librer
acqurir
Dedans
Demandeur
< gr par le systme >
L'accs en exclusion mutuelle doit respecter deux
proprits
Sret (safety) : au plus un processus est la fois dans la
section critique (dans l'tat dedans)
Vivacit (liveness) : tout processus demandant entrer dans
la section critique ( passer dans l'tat dedans) y entre en un
temps fini
4
Exclusion mutuelle distribue
Plusieurs grandes familles de mthodes
Contrle par un serveur qui centralise les demandes
d'accs la ressource partage
Contrle par jeton
Un jeton circule entre les processus et donne l'accs la
ressource
La gestion et l'affectation du jeton et donc l'accs la
ressource est faite par les processus entre eux
Deux approches : jeton circulant en permanence ou affect la
demande des processus
Contrle par permission
Les processus s'autorisent mutuellement accder la
ressource
5
Contrle par serveur
Principe gnral
Un serveur centralise et gre l'accs la ressource
Algorithme
Un processus voulant accder la ressource (quand il passe
dans l'tat demandeur) envoie une requte au serveur
Quand le serveur lui envoie l'autorisation, il accde la
ressource (passe dans l'tat dedans)
Il informe le serveur quand il relche la ressource (passe dans
l'tat dehors)
Le serveur reoit les demandes d'accs et envoie les
autorisations d'accs aux processus demandeurs
Avec par exemple une gestion FIFO : premier processus
demandeur, premier autoris accder la ressource
Contrle par serveur
Mthode par serveur centralisateur, critiques
Avantages
Inconvnients
Trs simple mettre en oeuvre
Simple pour grer la concurrence d'accs la ressource
Ncessite un lment particulier pour grer l'accs
Potentiel point faible, goulot d'tranglement
Suppression du serveur centralisateur
Via par exemple une mthode jeton : le processus qui
a le jeton peut accder la ressource
La gestion et l'affectation du jeton est faite par les
processus entre eux
Pas de besoin de serveur centralisateur
Mthode par jeton
Principe gnral
Un jeton unique circule entre tous les processus
Le processus qui a le jeton est le seul qui peut accder
la section critique
Respect des proprits
Sret : grce au jeton unique
Vivacit : l'algorithme doit assurer que le jeton circule bien
entre tous les processus voulant accder la ressource
Plusieurs versions
Anneau sur lequel circule le jeton en permanence
Jeton affect la demande des processus
8
Mthode par jeton
Algorithme de [Le Lann, 77]
Un jeton unique circule en permanence entre les processus
via une topologie en anneau
Quand un processus reoit le jeton
S'il est dans l'tat demandeur : il passe dans l'tat dedans et
accde la ressource
S'il est dans l'tat dehors, il passe le jeton son voisin
Quand le processus quitte l'tat dedans, il passe le jeton
son voisin
Respect des proprits
Sret : via le jeton unique qui autorise l'accs la ressource
Vivacit : si un processus lche le jeton (la ressource) en un
temps fini et que tous les processus appartiennent l'anneau
9
Mthode par jeton
Algorithme de [Le Lann, 77], critiques
Inconvnients
Ncessite des changes de messages (pour faire circuler le
jeton) mme si aucun site ne veut accder la ressource
Temps d'accs la ressource peut tre potentiellement
relativement long
Si le processus i+1 a le jeton et que le processus i veut accder la
ressource et est le seul vouloir y accder, il faut quand mme
attendre que le jeton fasse tout le tour de l'anneau
Avantages
Trs simple mettre en oeuvre
Intressant si nombreux processus demandeurs de la ressource
Jeton arrivera rapidement un processus demandeur
quitable en terme de nombre d'accs et de temps d'attente
Aucun processus n'est privilgi
10
Mthode par jeton
Variante de la mthode du jeton
Au lieu d'attendre le jeton, un processus diffuse tous le
fait qu'il veut obtenir le jeton
Le processus qui a le jeton sait alors qui il peut l'envoyer
vite les attentes et les circulations inutiles du jeton
Algorithme de [ Ricart & Agrawala, 83 ]
Soit N processus avec un canal bi-directionnel entre
chaque processus
Canaux fiables mais pas forcment FIFO
Localement, un processus Pi possde un tableau nbreq,
de taille N
Pour Pi, nbreq [ j ] est le nombre de requtes d'accs que le processus
Pj a fait et que Pi connat (par principe il les connat toutes)
11
Mthode par jeton
Algorithme de [ Ricart & Agrawala, 83 ] (suite)
Le jeton est un tableau de taille N
Initialisation
Pour tous les sites Pi : j [ 1 .. N ] : nbreq [ j ] = 0
Jeton : j [ 1 .. N ] : jeton [ j ] = 0
Un site donn possde le jeton au dpart
jeton [ i ] est le nombre de fois o le processus Pi a accd la
ressource
La case i de jeton n'est modifie que par Pi quand celui-ci accde
la ressource
Quand un site veut accder la ressource et n'a pas le jeton
Envoie un message de requte tous les processus
12
Mthode par jeton
Algorithme de [ Ricart & Agrawala, 83 ] (suite)
Quand processus Pj reoit un message de requte venant de Pi
Pj modifie son nbreq localement : nbreq [ i ] = nbreq [ i ] + 1
Si Pj possde le jeton et est dans l'tat dehors
Pj envoie le jeton Pi
Quand processus rcupre le jeton
Pj mmorise que Pi a demand avoir la ressource
Il accde la ressource (passe dans l'tat dedans)
Quand Pi libre la ressource (passe dans l'tat dehors)
Met jour le jeton : jeton [ i ] = jeton [ i ] + 1
Parcourt nbreq pour trouver un j tel que : nbreq [ j ] > jeton [ j ]
Une demande d'accs la ressource de Pj n'a pas encore t
satisfaite : Pi envoie le jeton Pj
Si aucun processus n'attend le jeton : Pi le garde
13
Mthode par jeton
Algorithme de [ Ricart & Agrawala, 83 ], respect des
proprits
Sret : seul le processus ayant le jeton accde la
ressource
Vivacit : assure si les processus distribuent
quitablement le jeton aux autres processus
Mthode de choix du processus qui va rcuprer le jeton lorsque
l'on sort de l'tat dedans
Pi parcourt nbreq partir de l'indice i+1 jusqu' N puis continue de
1 i-1
Chaque processus teste les demandes d'accs des autres processus
en commenant un processus spcifique et diffrent de la liste
vite que par exemple tous les processus avec un petit identificateur
soient servis systmatiquement en premier
14
Mthodes par permission
Mthodes par permission
Un processus doit avoir l'autorisation des autres
processus pour accder la ressource
Principe gnral
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
Les sous-ensembles sont conus alors tel qu'au moins un processus
soit commun 2 sous-ensembles : il joue le rle d'arbitre
15
Permission individuelle
Algorithme de [Ricart & Agrawala, 81]
Permission individuelle
Chaque processus demande l'autorisation tous les
autres (sauf lui par principe)
Liste des processus interroger par le processus Pi pour
accder la ressource : Ri = { 1, ... , N } { i }
Se base sur une horloge logique (Lamport) pour garantir
le bon fonctionnement de l'algorithme
Ordonnancement des demandes d'accs la ressource
Si un processus ayant fait une demande d'accs reoit une
demande d'un autre processus avec une date antrieure la
sienne, il donnera son autorisation l'autre processus
Et passera donc aprs lui puisque l'autre processus fera le contraire
16
Permission individuelle
Algorithme de [Ricart & Agrawala, 81], fonctionnement
Chaque processus gre les variables locales suivantes
Une horloge Hi
Une variable dernier qui contient la date de la dernire demande
d'accs la ressource
L'ensemble Ri
Un ensemble d'identificateurs de processus dont on attend une
rponse : attendu
Un ensemble d'identificateurs de processus dont on diffre le
renvoi de permission si on est plus prioritaire qu'eux : diffr
Initialisation
Hi = dernier = 0
diffr = , attendu = Ri
17
Permission individuelle
Algorithme de [Ricart & Agrawala, 81], fonctionnement (suite)
Si un processus veut accder la ressource, il excute
Hi = Hi + 1
dernier = Hi
attendu = Ri
Envoie une demande de permission tous les processus de Ri
avec estampille ( Hi, i )
Se met alors en attente de rception de permission de la part de
tous les processus dont l'identificateur est contenu dans attendu
Quand l'ensemble attendu est vide, le processus a reu la
permission de tous les autres processus
Accde alors la ressource partage
Quand accs termin
Envoie une permission tous les processus dont l'id est dans diffr
diffr est ensuite rinitialis (diffr = )
18
Permission individuelle
Algorithme de [Ricart & Agrawala, 81], fonctionnement (suite)
Quand un processus Pi reoit une demande de permission
de la part du processus Pj contenant l'estampille (H, j)
Met jour Hi : Hi = max (Hi, H)
Si Pi pas en attente d'accs la ressource : envoie permission Pj
Sinon, si Pi est en attente d'accs la ressource
Si Pi est prioritaire : place j dans l'ensemble diffr
Si Pj est prioritaire : envoi permission Pj
On lui enverra la permission quand on aura accd la ressource
Pj doit passer avant moi, je lui envoie ma permission
La priorit est dfinie selon la datation des demandes d'accs la
ressource de chaque processus
Le processus prioritaire est celui qui a fait sa demande en premier
Ordre des dates : l'ordre << de l'horloge de Lamport :
( dernier, i ) << ( H, j ) si ( ( dernier < H ) ou ( dernier = H et i < j ) )
19
Permission individuelle
Algorithme de [Ricart & Agrawala, 81], fonctionnement (fin)
Quand processus Pi reoit une permission de la part du
processus Pj
Supprime l'identificateur de Pj de l'ensemble attendu :
attendu = attendu { j }
Respect des proprits
Sret : vrifie (et prouvable...)
Vivacit : assure grce aux datations et aux priorits
associes
Inconvnient principal de cet algorithme
Nombre relativement important de messages changs
20
Permission individuelle
Permission individuelle, amlioration de l'algorithme
de [Ricart & Agrawala, 81]
[Carvalho & Roucairol, 83]
Si Pi veut accder plusieurs fois de rang la ressource partage
et si Pj entre 2 accs (ou demandes d'accs) de Pi n'a pas
demand accder la ressource
Pas la peine de demander l'autorisation Pj car on sait alors qu'il donnera
par principe son autorisation Pi
Limite alors le nombre de messages changs
[Chandy & Misra, 84], amliorations tel que
Les processus ne voulant pas accder la ressource et qui ont dj
donn leur permission ne reoivent pas de demande de permission
Horloges avec des datations bornes (modulo m)
Pas d'identification des processus
21
Permission par arbitre
Permission par arbitre
Un processus ne donne qu'une permission la fois
Il redonnera sa permission un autre processus quand le
processus a qui il avait donn prcdemment la permission lui a
indiqu qu'il a fini d'accder la ressource
La sret est assure car
Les sous-ensemble de processus qui un processus demande
la permission sont construits tel qu'ils y ait toujours au moins un
processus commun 2 sous-ensemble
Un processus commun 2 sous-ensembles est alors arbitre
Comme il ne peut donner sa permission qu' un seul processus, les
processus de 2 sous-ensembles ne peuvent pas tous donner
simultanment la permission 2 processus diffrents
C'est donc ce processus commun qui dtermine qui donner la
ressource
22
Permission par arbitre
Algorithme de [ Maekawa, 85 ]
Chaque processus Pi possde un sous-ensemble Ri
d'identificateurs de processus qui Pi demandera
l'autorisation d'accder la ressource
i,j [ 1..N ] : Ri Rj
i : | Ri | = K
Deux sous-ensembles de 2 processus diffrents ont obligatoirement
au moins un lment en commun (le ou les arbitres)
Cela rend donc inutile le besoin de demander la permission tous
les processus, d'o les sous-ensembles Ri ne contenant pas tous
les processus
Pour une raison d'quit, les sous-ensembles ont la mme taille
pour tous les processus
i : i est contenu dans D sous-ensembles
Chaque processus joue autant de fois le rle d'arbitre qu'un autre
processus
23
Permission par arbitre
Algorithme de [ Maekawa, 85 ] (suite)
Solution optimale en nombre de permissions demander
et de messages changs
K N et D = K
Fonctionnement de l'algorithme
Chaque processus possde localement
Une variable vote permettant de savoir si le processus a dj
vot (a dj donn sa permission un processus)
Une file file d'identificateurs de processus qui ont demand la
permission mais qui on ne peut la donner de suit
Un compteur rponses du nombre de permissions reues
Initialisation
tat non demandeur, vote = faux et file = , rponses = 0
24
Permission par arbitre
Algorithme de [Maekawa, 85], fonctionnement (suite)
Quand processus Pi veut accder la ressource
rponses = 0
Envoie une demande de permission tous les processus de Ri
Quand rponses = | Ri |, Pi a reu une permission de tous, il
accde alors la ressource
Aprs l'accs la ressource, envoie un message tous les
processus de Ri pour les informer que la ressource est libre
Quand processus Pi reoit une demande de permission
de la part du processus Pj
Si Pi a dj vot (vote = vrai) ou accde actuellement la
ressource : place l'identificateur de Pj en queue de file
Sinon : envoie sa permission Pj et mmorise qu'il a vot
vote = vrai
25
Permission par arbitre
Algorithme de [Maekawa, 85], fonctionnement (suite)
Quand Pi reoit de la part du processus Pj un message
lui indiquant que Pj a libr la ressource
Si file est vide, alors vote = faux
Pi a dj autoris tous les processus en attente d'une
permission de sa part
Si file est non vide
Retire le premier identificateur (disons k) de la file et
envoie Pk une permission d'accs la ressource
vote reste vrai
26
Permission par arbitre
Algorithme de [Maekawa, 85], problme
La vivacit n'est pas assure par cet algorithme car des
cas d'interblocage sont possibles
Pour viter ces interblocages, amliorations de
l'algorithme en dfinissant des priorits entre les
processus
En datant les demandes d'accs avec une horloge logique
En dfinissant un graphe de priorits des processus
27
Tolrance aux fautes
Tolrance aux fautes
Les algorithmes dcrits dans ce cours ne supportent pas
des pertes de messages et/ou des crash de processus
Mais adaptation possibles de certains algorithmes pour rsister
certains problmes
Ex. pour la mthode par serveur : lection d'un nouveau serveur en
cas de crash
Peut aussi amliorer la tolrance aux fautes en utilisant des
dtecteurs de fautes associs aux processus pour dtecter les
processus morts
28
