Algorithme de Naimi-Trehel
Un article de Wikipédia, l'encyclopédie libre.
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 |
[modifier] Algorithme
[modifier] 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.
- Pj racine de l'arborescence:
Dans tous ces deux cas, le processus Pj pointe sur le processus Pi
[modifier] Performance
- Le nombre moyen de messages échanés est de l'ordre O(Log(n)) où n est le nombre de processus du système distribué.
[modifier] Voir aussi
- Lamport's Bakery Algorithm
- Lamport's Distributed Mutual Exclusion Algorithm
- Maekawa's Algorithm
- Suzuki-Kasami's Algorithm
- Raymond's Algorithm