Algoritmo de Naimi-Trehel

El algoritmo Naimi-Tréhel asegura la exclusión mutua en sistemas distribuidos . Este algoritmo reduce el número medio de mensajes introduciendo una estructura de árbol lógica y un token. El algoritmo inicial fue presentado por Naimi y Tréhel. logramo(no){\ registro de estilo de pantalla (n)}

Exclusión mutua

El problema con la exclusión mutua es asegurarse de que como máximo un sitio, en cualquier momento, pueda acceder a un recurso, generalmente denominado sección crítica. El planteamiento del problema fue dado por Dijkstra en 1965 en un sistema centralizado. Nos situamos en el contexto de una red distribuida, lo que significa que los procesos en cada sitio interactúan solo enviándose mensajes entre sí. Los algoritmos buscan reducir la cantidad de mensajes entre sitios. Para Lamport, si n es el número de sitios, el número de mensajes llega a 3 (n-1) En 1985, Maekawa define un algoritmo para el cual el número de mensajes es del orden de 2 * raíz (n). Este algoritmo reduce el número medio de mensajes a . Iniciar sesión⁡(no){\ Displaystyle \ log (n)}

Modelo general

Cada proceso tiene memoria local y puede enviar mensajes a cualquier otro utilizando un identificador único como dirección. Se supone que la comunicación entre los procesos es perfecta (sin pérdidas, duplicaciones o modificaciones de mensajes).

Descripción

El algoritmo que presentamos aquí se basa en el hecho de que un proceso envía su solicitud solo a otro proceso y espera su permiso. Sería un algoritmo centralizado si el proceso de recepción fuera siempre el mismo, pero cambiará en función de la evolución de las solicitudes

• Descripción simplificada

El permiso para ingresar a la sección crítica se materializa mediante un token; Uno y solo un proceso tiene el token. El proceso que posee este token puede ingresar a una sección crítica. Hay dos estructuras de datos:

• • El primero es una cola.

Cada proceso conoce el siguiente proceso en la cola, excepto cuando no hay un siguiente. La cabeza es el proceso al que pertenece el token. La cola es el último proceso que solicitó la cola (a menos que solo haya un proceso en esa cola). Una ruta está organizada de modo que cuando un proceso solicita la sección crítica, su solicitud se pasa a la cola. Cuando llega allí, hay dos casos:

• • • Si el proceso que está en la cola tiene el token y no está en la sección crítica, envía el token al solicitante, quien luego puede ingresar a la sección crítica.
    • si el proceso que está en la cola tiene el token y está en la sección crítica o lo está esperando, el solicitante pasa a ser el siguiente en esa cola y se convierte en la nueva cola.

- Cuando el proceso que encabeza la cola sale de la sección crítica, le da el token al siguiente, si es que hay otro.

• • La segunda estructura de datos da la ruta para ir al final de la cola. Es una estructura de árbol lógica. Un proceso que solicita ingresar a una sección crítica envía la solicitud al sitio principal. De padre a padre, se envía una solicitud a la raíz (proceso para el que padre = nulo), que también es la cola de la cola. Es una estructura distribuida, cada proceso solo conoce a su padre.

Además, si el proceso solicitante no es la raíz, la estructura del árbol se transforma: el proceso solicitante se convierte en la nueva raíz y los procesos ubicados entre el solicitante y la raíz tendrán la nueva raíz como padre.

• Consideración de los tiempos de transferencia de mensajes

La estructura del árbol se modifica de la siguiente manera: el solicitante transmite la solicitud a su padre y se considera la nueva raíz. Por tanto, la estructura del árbol se divide en dos: una asociada a la raíz antigua y la otra asociada a la nueva. De manera más general, si hay varias solicitudes en tránsito al mismo tiempo, hay varios árboles. Cuando han llegado todos estos mensajes en tránsito, estos árboles se agrupan para formar uno solo. La transformación del árbol tiene esta consecuencia: si la solicitud de i se envía en la dirección de la raíz j y si la solicitud de k llega antes de la solicitud de i, la solicitud de i se transmitirá a k.

Especificación de algoritmo

• variables de cada proceso:
  • token-present es un booleano que indica si el proceso tiene el token
  • request es un booleano que indica si el proceso está solicitando y permanece verdadero hasta que haya obtenido y luego salido de la sección crítica
  • siguiente y padre son enteros entre 1 yn donde n es el número de procesos o tienen el valor "nil"
• Mensajes usados
  • Req (k): solicitud enviada por el proceso k hacia la raíz
  • Token: transmisión de token
• Algoritmo de cada proceso
  • Inicialización

padre: = 1 siguiente: = nulo pregunta: = falso si padre = i entonces empieza token-presente: = verdadero; padre: = nulo final en caso contrario token-presente: = falso finsi

• • Solicite el tramo crítico por proceso i

solicitud: = verdadero si padre = nulo, entonces ingrese en la sección crítica; de lo contrario, comience a enviar Req (i) al padre; padre: = nil fin finsi

• • Procedimiento para terminar el uso de la sección crítica

preguntar: = falso; si el siguiente no es = nulo, comience a enviar el token al siguiente; token-presente: = falso; siguiente: = nil fin finsi

• • Recepción del mensaje Req (k) (k es la parte que llama)

si padre = nulo, entonces si solicitud, luego siguiente: = k de lo contrario, inicie token-present: = false; envíe el token a k end finsi; de lo contrario, envíe req (k) al padre finsi; padre: = k

• • Recibiendo el mensaje Token

token-presente: = verdadero

Rendimiento

• El número medio de mensajes intercambiados es del orden O (Log (n)) donde n es el número de procesos en el sistema distribuido. La demostración es compleja, pero intuitivamente podemos ver que solo tenemos que recorrer un camino desde un sitio hasta la raíz de un árbol.

Extensiones

1) Tolerancia a fallos Se han realizado varios trabajos para hacer que el algoritmo sea tolerante a fallos. Primero, hubo un trabajo realizado por los autores del algoritmo. http://lifc.univ-fcomte.fr/lifc/presentation/

Citemos también la contribución de Julien Sopena, Luciana Arantes, Pierre Sens Un algoritmo justo de exclusión mutua tolerando fallas Lip6, Universidad de París 6 http://www.lip6.fr/recherche/index.php

2) Solicitud por teleconferencia Mohammed OUZZIF - ENSIAS, Marruecos http://www.ensias.ma/ Prof. Mohammed Erradi - ENSIAS, Marruecos Prof. Jean-Pierre Courtiat - LAAS, Francia http://www.laas.fr/ Gestion Dinámica de grupo en un entorno de control de videoconferencia

Bibliografía

• M. Naimi, M. Tréhel, A. Arnold, "Un algoritmo de exclusión mutua distribuido log (N) basado en la inversión de la ruta", Journal of Parallel and Distributed Computing, 34, 1-13 (1996).
• M.Tréhel, M.Naimi: "Un algoritmo distribuido de exclusión mutua", TSI Vol 6, n o  2, p.  141-150 , (1987).
• M.Naimi, M. Tréhel: "Cómo detectar una falla y regenerar el token en el algoritmo distribuido Log (n) para la exclusión mutua", 2do Taller internacional sobre algoritmos distribuidos, Amsterdam, (julio de 1987), publicado en Lecture Notes en Ciencias de la Computación, n o  312, p.  149-158 , editado por J. Van Leeween.

Artículos relacionados

• Exclusión mutua
• Computación distribuída

Ver también

• Algoritmo de panadería
• Algoritmo de Maekawa
• Algoritmo de Suzuki-Kasami
• Algoritmo de Raymond