Algorithme de Naimi-Trehel

L'algorithme de Naimi-Trehel assure l'exclusion mutuelle dans les systèmes distribués. Cet algorithme réduit le nombre moyen de messages à log(n)en introduisant une structure arborescente logique et un jeton. L'algorithme a été présenté en 1987 par Naimi et Tréhel.

Algorithme

Description de l'algorithme

Demande de la section critique:

• Un processus demandeur:
  • P_i a le jeton il peut entrer dans sa section critique.
  • P_i n'a pas le jeton, il envoie une requête vers la racine de l'arborescence.

• A la réception de la requête:
• request(i) message, par le processus P_j:
  • P_j racine de l'arborescence:
    • si P_j est demandeur de la section critique, la requête de sera dans la file d'attente de P_j
    • si P_j n'est pas demandeur, il envoie le jeton au processus P_i
  • P_j n'est pas racine de l'arborescence: il achemine la requête vers la racine de l'arborescence.

Dans tous ces deux cas, le processus P_j pointe sur le processus P_i

Performance

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

Voir aussi

• Lamport's Bakery Algorithm
• Lamport's Distributed Mutual Exclusion Algorithm
• Maekawa's Algorithm
• Suzuki-Kasami's Algorithm
• Raymond's Algorithm

• Portail de l’algorithmique