Algorithme de Ricart et Agrawala
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
L’Algorithme Ricart-Agrawala est un algorithme d'exclusion mutuelle sur un système distribué. Cet algorithme est une extension et une optimisation de l'algorithme de Lamport, en supprimant la nécessité de communiquer un message de libération. Il a été développé par Glenn Ricart et Ashok Agrawala. Dans cet algorithme, les requêtes d'entrée sont totalement ordonnées grâce à l'utilisation de l'Horloge de Lamport.
Algorithme[modifier | modifier le code]
Il a pour but de diminuer le nombre de messages échangés par entrée en section critique et élimine les messages de type libération.
Deux types de message sont utilisés ici[1]:
- les messages REQUETE qui sont envoyés lorsqu'un site veut entrer en section critique
- les messages REPONSE qui sont envoyés soit immédiatement à la réception d'un message de type REQUETE, soit ultérieurement à la sortie de section critique du site.
Source[modifier | modifier le code]
/* invariant : Pi :EC==exclusion )8p; Pp:EC==candidat: Pi :drLoc < Pp:drLoc */
process P(i:0..N-1){
type État = {hors,candidat,exclusion};
EtatEC = hors;
Datehloc = newDate(i,1);
DatedrLoc;
Set<int>Att=newEnumSet<int>();Set<int>D=EnumSet.range(0,N-1).remove(i);
while (true) {
select {
when (EC == hors)) // hors -> candidat
EC = candidat; drLoc=hloc.Top() ;
for(intp:D) send Rq(i,drLoc) to Pp ;
[]when (EC == exclusion)) // exclusion ! hors
for(intp:Att) send Perm(i) to Pp ; Att.clear() ; EC=hors;
[]when (EC == candidat) ) receive Perm(p) // candidat ? -> exclusion
D.remove(p);
if(D.empty())
EC = exclusion;
[]receive Rq(p,dr);
hloc.Recaler(dr) ;
if(EC!=hors&& Date.pred(drloc,dr))Att.add(p);
elsesend Perm(i) to Pp ;
} // select
} // while
}
Lorsqu'un processus (ou un site) Pi désire entrer en section critique, il envoie un message du type Requete. Lorsqu'un processus Pj reçoit ce message, soit il accepte et renvoie un message de type Response, ou différer sa réponse. S’il ne désire pas entrer en section critique, il envoie un message Response.
Un processus entre en section critique seulement s'il a obtenu les permissions de tous les autres (à l'aide des requêtes Response).
Performance[modifier | modifier le code]
- le nombre total de messages est , N étant le nombre de sites que comprend ce système.
- Un seul message suffit pour la synchronisation.
Variantes de l'algorithme[modifier | modifier le code]
L'algorithme Carvalho et Roucairol : l'accord donné par un processus reste valable tant qu'il n'a pas fait lui-même une demande d'entrée en section critique.
Notes et références[modifier | modifier le code]
- Jean-Marie Rifflet, Algorithme de Ricart/Agrawala
Bibliographie[modifier | modifier le code]
- Jean-Marie Rifflet, « Exclusion mutuelle : algorithme de Ricart/Agrawala »,
- François Laroussinie, « Algorithme de Ricart-Agrawala (1981) »
- Sarah Benkouider, Souhila Labgaa, Mohamed Yagoubi, « Influence De La Taille Du Jeton Sur Les Performances De L’algorithme D'exclusion Mutuelle De Ricart - Agrawala »
