El algoritmo de Maekawa es un algoritmo que se emplea para crear exclusión mutua en un sistema distribuido. Para una red de N nodos, el algoritmo utilizará únicamente un total de c*√N mensajes para crear esta exclusión mutua, siendo 'c' una constante que puede variar entre los valores 3 y 5. En esta red supuesta, también se supone que todos los nodos se comunican solamente mediante mensajes y no tienen memoria compartida, así como que los mensajes se reciben en el mismo orden que han sido enviados.
Como aproximación, este algoritmo requerirá 3*√N mensajes en cada exclusión mutua que se cree: √N mensajes para realizar la petición, √N mensajes para obtener el permiso necesario para acceder a la sección crítica y √N mensajes para salir de la sección crítica y desbloquear la exclusión mutua para que otros procesos puedan acceder posteriormente.
Para entender el algoritmo hay que pensar en la red como un subconjunto de nodos (Si), y que para que un nodo pueda acceder a la sección crítica este debe haber bloqueado anteriormente a los demás pertenecientes al mismo subconjunto. Cuando el nodo i trate de bloquear a todos los demás nodos, si lo consigue podrá acceder a la sección crítica, pero si no tendrá que esperar a que todos los demás nodos estén libres para poder volver a intentarlo.
Para evitar el posible interbloqueo de los nodos debido a varias peticiones simultáneas de distintos nodos se utilizará una prioridad de dicha petición para dar el permiso a un nodo o a otro. Esta prioridad será una marca de tiempo o número de secuencia (timestamp), que cuanto más baja sea, mayor prioridad le otorgará a la petición.
Cuando un nodo desea acceder a una sección crítica envía un mensaje de tipo REQUEST a todos los nodos pertenecientes a su subconjunto para tratar de bloquearlos. Este mensaje llevará asociada una prioridad, que será una marca de tiempo o número de secuencia (timestamp) y que será siempre mayor que cualquier otra prioridad que el nodo haya enviado o recibido.
Algoritmo de Maekawa 1.Cuando un nodo j recibe un mensaje de tipo REQUEST de un nodo i comprobará si ya se encuentra bloqueado por otra petición anterior de un nodo k. En caso de que no lo esté, se bloquea y responde al nodo i del que recibió la petición con un mensaje de tipo LOCKED, y si por el contrario sí que se encuentra bloqueado, añadirá la petición recibida de i a una cola de espera. Cuando haya añadido esta última petición a la cola comprobará si la petición con la que se encuentra bloqueado o alguna de las que ya tiene en la cola de espera tiene mayor prioridad que la petición que acaba de añadir. Si esto sucede, responderá al nodo i con un mensaje de tipo FAILED. Si ninguna de las peticiones tiene una prioridad mayor, el nodo bloqueado enviará un mensaje de tipo INQUIRE al nodo que le envió la petición para comprobar si este último ha conseguido bloquear a los demás nodos del subconjunto. Si ya se había enviado previamente un mensaje de tipo INQUIRE y todavía no se ha obtenido respuesta, no es necesario enviarlo. Algoritmo de Maekawa 2.
Cuando un nodo recibe un mensaje de tipo INQUIRE tiene dos posibles respuestas: Si ya sabe que no va a ser capaz de bloquear todos los demás nodos por haber recibido ya un mensaje de tipo FAILED de cualquier otro nodo, puede responder con un mensaje de tipo RELINQUISH. De esta forma libera al nodo para aceptar otra petición con mayor prioridad cancelando el mensaje LOCKED recibido. (Esto sirve para evitar interbloqueos). La otra respuesta es el mensaje de tipo RELEASE, que se produce si el nodo que recibe el INQUIRE ha conseguido bloquear todos los demás nodos del subconjunto y está por tanto en la sección crítica y que se envía cuando el nodo completa la sección crítica. Si el mensaje INQUIRE ha llegado cuando ya se ha mando un mensaje de tipo RELEASE se ignorará, y si se recibe cuando aún no se sabe si ha habido éxito al bloquear los demás nodos se pospone el envío de su respuesta.
Cuando un nodo recibe un mensaje de tipo RELINQUISH se libera del estado bloqueado y se vuelve a bloquear pero esta vez con la petición de mayor prioridad que tenga en su cola de espera, independientemente de que petición haya originado el envío del mensaje INQUIRE anterior. La petición que había obligado el envío del INQUIRE se añade a la cola de espera, mientras que la petición con mayor prioridad se elimina de esta y se le envía un mensaje de tipo LOCKED al nodo que generó dicha petición.
Si todos los miembros del subconjunto han respondido a las peticiones de un nodo con un mensaje de tipo LOCKED este nodo ya puede acceder a la sección crítica y cuando la complete enviará un mensaje de tipo RELEASE a todos y cada uno de los miembros del subconjunto.
Cuando un nodo recibe un mensaje de tipo RELEASE se desbloquea de la petición que lo mantenía bloqueado y se vuelve a bloquear con la petición de mayor prioridad de su cola si no está vacía, enviando un mensaje de tipo LOCKED al nodo que envío la petición que genera el nuevo bloqueo. Si la cola está vacía, este nodo se marca como desbloqueado.
Los subconjuntos de voto son grupos de nodos que se utilizan para tomar decisiones de exclusión mutua. Cada nodo pertenece a varios subconjuntos de voto y solo puede acceder al recurso compartido si es el único nodo en al menos uno de estos subconjuntos. De esta manera, cada nodo tiene múltiples subconjuntos de voto que se superponen con los de otros nodos, lo que garantiza que solo un nodo a la vez pueda obtener el recurso compartido. Los subconjuntos de voto son una parte esencial del algoritmo de Maekawa para garantizar la exclusión mutua en un sistema distribuido.
Para construir los subconjuntos de voto, el algoritmo de Maekawa utiliza la idea de "triángulos". Un triángulo es un subconjunto de tres nodos en el que cada par de nodos tiene un camino directo entre ellos. En un sistema distribuido, cada nodo puede ver los nodos que están directamente conectados a él, y los nodos que están a una distancia de dos saltos (es decir, los nodos que están conectados a los nodos que están conectados directamente al nodo). Utilizando esta información, cada nodo puede construir una lista de triángulos a los que pertenece.
Ejemplo de los Subconjuntos de Voto
Una vez que se han identificado todos los triángulos, el algoritmo de Maekawa utiliza una fórmula para construir los subconjuntos de voto. Cada subconjunto de voto incluye el nodo actual y dos nodos de cada triángulo en el que está presente el nodo. Por ejemplo, si un nodo pertenece a cuatro triángulos, se construirán cuatro subconjuntos de voto, cada uno de ellos con el nodo actual y dos nodos diferentes de cada triángulo.
De esta manera, cada nodo tiene múltiples subconjuntos de voto que se superponen con los de otros nodos, lo que garantiza que solo un nodo a la vez pueda obtener el recurso compartido. Los subconjuntos de voto son una parte clave del algoritmo de Maekawa para garantizar la exclusión mutua en un sistema distribuido.
A diferencia del algoritmo de Ricart y Agrawala, no necesitamos que todos los procesos nos permitan el acceso para entrar a la sección crítica, únicamente será necesario obtener el permiso de un subconjunto de N procesos. De esta manera, se logra conseguir una mayor tolerancia a fallos.
Su funcionalidad tiene una alta capacidad de escalado ya que a mayor número de nodos aumenta la cantidad de subconjuntos de voto, sin embargo esto no afecta al rendimiento ni a la escalabilidad del algoritmo.
Inicialmente se tienen que crear los subconjuntos de voto, tarea que puede ocasionar una gran carga computacional del sistema, además de ser necesaria un sistema de red fiable.
No cumple con la pervivencia, pues puede producir interbloqueos. Este inconveniente se soluciona con una versión posterior creada por Sanders en el año 1987.
En general, este algoritmo sigue siendo una solución eficiente y funcional para garantizar la exclusión mutua entre procesos; sin embargo, es importante conocer sus limitaciones para implementarlo de manera correcta.
Considerando N el número de nodos en el sistema distribuido, este algoritmo se mide en términos de retraso de entrada √N; retraso en el relevo √N y ancho de banda 3√N.
El retraso de entrada hace referencia al tiempo necesario para solicitar el acceso a un recurso compartido y obtener una respuesta de acceso al recurso compartido. Para este algoritmo el retraso de entrada es proporcional a la raíz cuadrada de N. Esto se debe a que cada nodo necesita contactar con al menos un subconjunto de voto para obtener el acceso, y además cada subconjunto tiene un tamaño mínimo de 3 nodos N.
El retraso en el relevo se refiere al tiempo necesario para que un nodo que tiene el acceso al recurso, lo libere y se lo ceda a otro nodo. Al igual que en el retraso de entrada, este valor también es proporcional a la raíz cuadrada de N, ya que el nodo que tiene acceso a la sección crítica, tiene que notificar a los otros nodos en sus subconjuntos de voto correspondientes.
El ancho de banda se refiere a la cantidad de mensajes que tienen que intercambiar los diferentes nodos para conseguir la exclusión mutua. Cada nodo tiene que comunicarse con al menos 3 subconjuntos de voto para solicitar y conceder acceso.
Cuando a mejora de rendimiento se refiere, el algortimo de Maekawa mejora cuando es mayor que 4. En el caso de N=4, ambos algoritmos tienen el mismo rendimiento, pero cuando N es mayor, el algoritmo de Maekawa es más eficiente. Se debe a que el algoritmo de Ricart-Agrawala necesita que cada nodo se comunique con todos los demás nodos para lograr la exclusión mutua, lo que requiere un ancho de banda proporcional a N^2. En cambio el ancho de banda en Maekawa se reduce a 3 veces la raíz cuadrada de N.
Datos: Q1883604