El algoritmo de Maekawa

• Un sitio es cualquier dispositivo informático que ejecuta el algoritmo de Maekawa.
• Para cualquier solicitud de acceso a la sección crítica :
  • El sitio solicitante es el sitio que solicita acceder a la sección crítica.
  • El sitio receptor es cualquier otro sitio que reciba la solicitud del sitio solicitante.
• ts se refiere a la marca de tiempo local del sistema según su reloj lógico.

Sitio solicitante :

• Un sitio solicitante${\displaystyle P_{i}}$envía un mensaje${\displaystyle {\text{solicitud}}(ts,i)}$a todos los sitios en su conjunto de quórum${\displaystyle R_{i}}$.

Sitio receptor :

• Al recibir un${\displaystyle {\text{solicitud}}(ts,i)}$mensaje, el sitio receptor${\displaystyle P_{j}}$voluntad:
  • Si el sitio${\displaystyle P_{j}}$no tiene un sobresaliente${\displaystyle {\text{subvención}}}$mensaje (es decir, un${\displaystyle {\text{subvención}}}$mensaje que no ha sido publicado), entonces el sitio${\displaystyle P_{j}}$envía un${\displaystyle {\text{grant}}(j)}$mensaje al sitio${\displaystyle P_{i}}$.
  • Si el sitio${\displaystyle P_{j}}$tiene una excepcional${\displaystyle {\text{subvención}}}$mensaje con un proceso con mayor prioridad que la solicitud, luego sitio${\displaystyle P_{j}}$envía un${\displaystyle {\text{falló}}(j)}$mensaje al sitio${\displaystyle P_{i}}$y sitio${\displaystyle P_{j}}$pone en cola la solicitud del sitio${\displaystyle P_{i}}$.
  • Si el sitio${\displaystyle P_{j}}$tiene una excepcional${\displaystyle {\text{subvención}}}$mensaje con un proceso de menor prioridad que la solicitud, luego el sitio${\displaystyle P_{j}}$envía un${\displaystyle {\text{inquire}}(j)}$mensaje al proceso al que actualmente se le ha concedido acceso a la sección crítica por parte del sitio${\displaystyle P_{j}}$. (Es decir, el sitio con la destacada${\displaystyle {\text{subvención}}}$mensaje.)
• Al recibir un${\displaystyle {\text{inquire}}(j)}$mensaje, el sitio${\displaystyle P_{k}}$voluntad:
  • Enviar un${\displaystyle {\text{rendimiento}}(k)}$mensaje al sitio${\displaystyle P_{j}}$si y solo si el sitio${\displaystyle P_{k}}$ha recibido un${\displaystyle {\text{fallido}}}$mensaje de algún otro sitio o si${\displaystyle P_{k}}$ha enviado un rendimiento a otro sitio pero no ha recibido uno nuevo${\displaystyle {\text{subvención}}}$.
• Al recibir un${\displaystyle {\text{rendimiento}}(k)}$mensaje, sitio${\displaystyle P_{j}}$voluntad:
  • Enviar un${\displaystyle {\text{grant}}(j)}$Mensaje dirigido a la solicitud que se encuentra en la parte superior de su propia cola de solicitudes. Tenga en cuenta que las solicitudes que se encuentran en la parte superior tienen la máxima prioridad.
  • Lugar${\displaystyle P_{k}}$en su cola de solicitudes.
• Al recibir un${\displaystyle {\text{liberar}}(i)}$mensaje, sitio${\displaystyle P_{j}}$voluntad:
  • Borrar${\displaystyle P_{i}}$de su cola de solicitudes.
  • Enviar un${\displaystyle {\text{grant}}(j)}$mensaje a la solicitud que se encuentra en la parte superior de su cola de solicitudes.

Sección crítica :

• Sitio${\displaystyle P_{i}}$entra en la sección crítica al recibir una${\displaystyle {\text{subvención}}}$mensaje de todos los sitios en${\displaystyle R_{i}}$.
• Al salir de la sección crítica,${\displaystyle P_{i}}$envía un${\displaystyle {\text{liberar}}(i)}$mensaje a todos los sitios en${\displaystyle R_{i}}$.

Conjunto de quórum (${\displaystyle R_{x}}$) : Un conjunto de quórum debe cumplir las siguientes propiedades:

1. ${\displaystyle \forall i\,\forall j\,[R_{i}\bigcap R_{j}\neq \emptyset ]}$
2. ${\displaystyle \forall i\,[P_{i}\in R_{i}]}$
3. ${\displaystyle \forall i\,[|R_{i}|=K]}$
4. Sitio${\displaystyle P_{i}}$está contenido exactamente${\displaystyle K}$conjuntos de solicitudes

Por lo tanto:${\displaystyle |R_{i}|\geq {\sqrt {N-1}}}$

• Número de mensajes de red;${\displaystyle 3{\sqrt {N}}}$a${\displaystyle 6{\sqrt {N}}}$
• Retraso de sincronización: 2 retrasos en la propagación de mensajes
• El algoritmo puede bloquearse si no se implementan protecciones. ^{[ 1 ] [ 2 ]}