Algorithme de Naimi-TrehelL'algorithme de Naimi-Tréhel assure l'exclusion mutuelle dans les systèmes distribués. Cet algorithme réduit le nombre moyen de messages à en introduisant une structure arborescente logique et un jeton. L'algorithme initial a été présenté par Naimi et Tréhel. Exclusion mutuelleLe problème de l’Exclusion mutuelle consiste à s’assurer qu’au plus un site, à un moment donné, peut accéder à une ressource, généralement appelée section critique. L’énoncé du problème a été donné par Dijkstra en 1965 dans un système centralisé. Nous nous plaçons dans le contexte d’un réseau distribué, ce qui signifie que les processus de chaque site interagissent seulement en se transmettant des messages. Les algorithmes cherchent à diminuer le nombre de messages entre les sites. Pour Lamport, si n est le nombre de sites, le nombre de messages atteint 3(n-1) En 1985, Maekawa définit un algorithme pour lequel le nombre de messages est de l’ordre de 2*racine(n). Cet algorithme réduit le nombre moyen de messages à . Modèle généralChaque processus a une mémoire locale et peut envoyer des messages à n'importe quel autre en utilisant un identificateur unique comme adresse. La communication entre les processus est supposée être parfaite (pas de pertes ni duplications ni modifications de messages). DescriptionL'algorithme que nous présentons ici est basé sur le fait qu'un processus envoie sa requête à seulement un autre processus et attend sa permission. Ce serait un algorithme centralisé si le processus qui reçoit était toujours le même, mais il changera en fonction de l'évolution des demandes
La permission d'entrer en section critique est matérialisée par un jeton; Un et seulement un processus a le jeton. Le processus qui possède ce jeton peut entrer en section critique. Il y a deux structures de données:
Chaque processus connaît le processus suivant dans la file d'attente sauf quand il n'y a pas de suivant. La tête est le processus qui possède le jeton. La queue est le dernier processus qui a demandé la file d'attente, (sauf s'il y a un seul processus dans cette file). Un chemin est organisé de sorte que, quand un processus demande la section critique, sa demande est transmise à la queue. Quand elle y arrive, il y a deux cas:
- Quand le processus en tête de la file d'attente quitte la section critique, il donne le jeton à son suivant, s'il y a un suivant.
De plus, si le processus demandeur n'est pas la racine, l'arborescence est transformée : le processus demandeur devient la nouvelle racine et les processus situés entre le demandeur et la racine auront la nouvelle racine comme père.
L'arborescence est modifiée comme suit : le demandeur transmet la requête à son père et se considère comme la nouvelle racine. L'arborescence est donc coupée en deux : une associée à l'ancienne racine, l'autre associée à la nouvelle. Plus généralement, s'il y a plusieurs demandes en transit en même temps, il y a plusieurs arborescences. Quand tous ces messages en transit sont arrivés, ces arborescences sont regroupées pour n'en former plus qu'une. La transformation de l'arborescence a cette conséquence : si la demande de i est envoyée en direction de la racine j et si la demande de k arrive à j avant la demande de i, la demande de i sera transmise à k. Spécification de l'algorithme
père := 1 suivant := nil demande := faux si père = i alors debut jeton-présent := vrai;père := nil fin sinon jeton-présent :=faux finsi
demande := vrai si père = nil alors entrée en section critique sinon début envoyer Req(i) à père; père := nil fin finsi
demande := faux; si suivant not= nil alors début envoyer token à suivant; jeton-présent := faux; suivant := nil fin finsi
si père = nil alors si demande alors suivant := k sinon début jeton-présent := faux; envoyer token à k fin finsi sinon envoyer req(k) à père finsi; père := k
jeton-présent := vrai Performance
Prolongements1) Tolérance aux fautes Différents travaux ont été faits pour rendre l’algorithme tolérant aux fautes. Il y a d’abord eu des travaux réalisés par les auteurs de l’algorithme. http://lifc.univ-fcomte.fr/lifc/presentation/ Citons en outre l’apport de Julien Sopena, Luciana Arantes, Pierre Sens Un algorithme équitable d’exclusion mutuelle tolérant les fautes Lip6, Université de Paris 6 http://www.lip6.fr/recherche/index.php 2) Application en téléconférence Mohammed OUZZIF – ENSIAS, Maroc http://www.ensias.ma/ Pr. Mohammed Erradi – ENSIAS, Maroc Pr. Jean-Pierre Courtiat - LAAS, France http://www.laas.fr/ Gestion Dynamique de Groupe dans un Environnement de Contrôle de Visioconférence Bibliographie
Articles connexesVoir aussi |