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.

Sommaire

Algorithme

Description de l'algorithme

Demande de la section critique:

  • Un processus demandeur:
    • Pi a le jeton il peut entrer dans sa section critique.
    • Pi 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 Pj:
    • Pj racine de l'arborescence:
      • si Pj est demandeur de la section critique, la requête de sera dans la file d'attente de Pj
      • si Pj n'est pas demandeur, il envoie le jeton au processus Pi
    • Pj 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 Pj pointe sur le processus Pi

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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Naimi-Trehel de Wikipédia en français (auteurs)

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”