Algorithme de Naimi-Trehel

Chaque 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).

L'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

• Description simplifiée

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:

• • La première est une file d'attente.

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:

• • • si le processus qui est à la queue a le jeton et n'est pas en section critique, il envoie le jeton au demandeur, qui est alors autorisé à entrer en section critique.
    • si le processus qui est à la queue soit a le jeton et est en section critique soit l'attend, le demandeur devient le suivant de cette queue et devient la nouvelle queue.

- 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.

• • La seconde structure de données donne le chemin pour aller à la queue de la file d'attente. C'est une arborescence logique. Un processus qui demande à entrer en section critique envoie la requête au site père. De père en père, une requête est transmise à la racine (processus pour lequel père= nil), qui est aussi la queue de la file d'attente. C'est une structure distribuée, chaque processus connaît seulement son père.

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.

• Prise en compte des temps de transfert des messages

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.

• variables de chaque processus :
  • jeton-présent est un booléen qui indique si le processus a le jeton
  • demande est un booléen qui indique si le processus est demandeur et reste vrai tant qu'il n'a pas obtenu puis quitté la section critique
  • suivant et père sont soit des entiers entre 1 et n où n est le nombre de processus soit ont la valeur "nil"
• Messages utilisés
  • Req(k) : demande envoyée par le processus k en direction de la racine
  • Token : transmission du jeton
• Algorithme de chaque processus
  • Initialisation

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 de la section critique par le processus i

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

• • Procédure de fin d'utilisation de la section critique

demande := faux; si suivant not= nil alors début envoyer token à suivant; jeton-présent := faux; suivant := nil fin finsi

• • Réception du message Req (k)(k est le demandeur)

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

• • Réception du message Token

jeton-présent := vrai

• Le nombre moyen de messages échangés est de l'ordre O(Log(n)) où n est le nombre de processus du système distribué. La démonstration est complexe, mais on voit intuitivement qu'on n'a à parcourir qu'un chemin d'un site jusqu'à la racine d'une arborescence.

1) 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

• M. Naimi, M. Tréhel, A. Arnold, "A Log(N) Distributed Mutual Exclusion Algorithm Based on the Path Reversal", Journal of Parallel and Distributed Computing, 34, 1-13 (1996).
• M.Tréhel, M.Naimi: "Un algorithme distribué d'exclusion mutuelle", TSI Vol 6, n^o 2, p. 141–150, (1987).
• M.Naimi, M. Tréhel : "How to detect a failure and regenerate the token in the Log(n) distributed algorithm for mutual exclusion" , 2nd International Workshop on Distributed Algorithms, Amsterdam, (Juill. 1987), paru dans Lecture Notes in Computer Science, n^o 312, p. 149-158, édité par J. Van Leeween.

• Exclusion mutuelle
• Calcul distribué