1Algorithmique distribue
Exclusion mutuelle
Eric Cariou
Master Technologies de l'Internet 1re anne
Universit de Pau et des Pays de l'AdourDpartement Informatique
2Exclusion 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
3Rappel 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
4Rappel exclusion mutuelle Diagramme d'tats de l'accs en exclusion mutuelle
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
Dehors Demandeur
Dedans
acqurir
librer < gr par le systme >
5Exclusion 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
6Contrle 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
7Contrle par serveur Mthode par serveur centralisateur, critiques Avantages Trs simple mettre en oeuvre Simple pour grer la concurrence d'accs la ressource
Inconvnients 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
8Mthode 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
9Mthode 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
10
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
11
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)
12
Mthode par jeton Algorithme de [ Ricart & Agrawala, 83 ] (suite) Le jeton est un tableau de taille N 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 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
Quand un site veut accder la ressource et n'a pas le jeton Envoie un message de requte tous les processus
13
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 Pj mmorise que Pi a demand avoir la ressource
Si Pj possde le jeton et est dans l'tat dehors Pj envoie le jeton Pi
Quand processus rcupre le jeton 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
14
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
15
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
16
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
17
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
18
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 = )
19
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
On lui enverra la permission quand on aura accd la ressource Si Pj est prioritaire : envoi permission Pj
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
20
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
21
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
22
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
23
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 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
i : | Ri | = K 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
24
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
25
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
26
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
27
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
28
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