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
  1. Riflet,2008
  2. thibault,p2, 2010

Bibliographie
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.