Algorithme Carvalho et Roucairol
L'Algorithme Carvalho et Roucairol est un algorithme d'exclusion mutuelle sur un système distribué. Il est une amélioration possible de l'algorithme de Ricart et Agrawala[1].
Principe de l’algorithme
Il est identique à l'algorithme de Ricart et Agrawala. Il a été optimisé sur un point : une fois qu'un site a reçu un message de réponse à partir d'un autre site, le premier site peut entrer en section critique sans avoir reçu la permission de l'autre jusqu'à ce qu'il ait envoyé un message de réponse à l'autre.
Source[2]
R = {j \in V tel que i ne possede pas perm(i; j)}
etat = S E, SC, S etat du site i
h = 0 entier date des demandes
last = 0 entier date de la derniere demande
differe = ensemble de sites qui retardent l envoi d une permission
priorite = faux booleen si i prioritaire ou non
<Demande d'entrée en section critique>
etat = E
last = h + 1
for all j in Rj do
Envoi msg(dem(lasti, i) a j
end for
while R != <ensemble vide> do
Reception msg(perm(i, j)) de j
R = R j
end while
etat = SC
Sortie
etat = S
for all j dans differe do
Envoi msg(perm(i, j)) a j
end for
R = differe
Reception de msg(dem, (h', j)) de j
h = max(hi, h')
priorite (etat = SC)<math> \bigwee </math>[(etat = E) \bigwedge (last; i) < (h0; i)]
if priorite then
differe differe [ j
else
Envoi msg(perm(i; j)) a j
R R [ j
if etat = E then
Envoi msg(dem, (last, i)) a j
end if
end if
Notes et références
- Riflet,2008
- thibault,p2, 2010
Bibliographie
- jean-Marie Rifflet, « Exclusion mutuelle : algorithme de Ricart/Agrawala »,
- Joyce El Haddad et Serge Haddad, « Cours d’algorithmique réparti »
- Thibault BERNARD, « Liste d'Algorithmes »
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.