- 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].
Sommaire
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 possedes 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 priorit = faux booleen si i prioritaire ou non Demande d entree en section critique etat = E last = h + 1 for all j Dans Rj do Envoi msg(dem(lasti, i) a j end for while R différent de l 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 differe = ensemble de sites qui retardent l'envoi d'une permission Reception de msg(dem, (h', j)) de j h = max(hi, h') priorit (etat = SC)<math> \bigwee </math>[(etat = E) \bigwedge (last; i) < (h 0 ; i)] if priorit 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 », 2008
- Joyce El Haddad et Serge Haddad, « Cours d’algorithmique réparti »
- Thibault BERNARD, « Liste d'Algorithmes »
Catégorie :- Algorithme d'exclusion mutuelle
Wikimedia Foundation. 2010.
