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.

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

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

Bibliographie

• jean-Marie Rifflet, « Exclusion mutuelle : algorithme de Ricart/Agrawala », 2008
• Joyce El Haddad et Serge Haddad, « Cours d’algorithmique réparti »
• Thibault BERNARD, « Liste d'Algorithmes »