Algoritmo de Lamport para exclusión mutua en sistemas distribuidos

Requisito previo: Exclusión mutua en sistemas distribuidos
El Algoritmo de Exclusión Mutua Distribuida de Lamport es un algoritmo basado en permisos propuesto por Lamport como una ilustración de su esquema de sincronización para sistemas distribuidos.
La marca de tiempo basada en permisos se utiliza para ordenar requests de secciones críticas y para resolver cualquier conflicto entre requests.

En el algoritmo de Lamport, las requests de sección crítica se ejecutan en el orden creciente de las marcas de tiempo, es decir, una solicitud con una marca de tiempo más pequeña tendrá permiso para ejecutar la sección crítica primero que una solicitud con una marca de tiempo más grande.

En este algoritmo:

• Se utilizan tres tipos de mensajes ( SOLICITUD , RESPUESTA y LIBERACIÓN ) y se supone que los canales de comunicación siguen el orden FIFO.
• Un sitio envía un mensaje de SOLICITUD a todos los demás sitios para obtener su permiso para ingresar a la sección crítica.
• Un sitio envía un mensaje de RESPUESTA al sitio que solicita permiso para ingresar a la sección crítica.
• Un sitio envía un mensaje de LIBERACIÓN a todos los demás sitios al salir de la sección crítica.
• Cada sitio Si _, mantiene una cola para almacenar requests de secciones críticas ordenadas por sus marcas de tiempo.
  request_queue _i denota la cola del sitio S _i
• Se asigna una marca de tiempo a cada solicitud de sección crítica utilizando el reloj lógico de Lamport.
• La marca de tiempo se utiliza para determinar la prioridad de las requests de secciones críticas. La marca de tiempo más pequeña tiene alta prioridad sobre la marca de tiempo más grande. La ejecución de la solicitud de sección crítica siempre está en el orden de su marca de tiempo.

Algoritmo:

• Para ingresar a la sección Crítica:
  • Cuando un sitio S _i desea ingresar a la sección crítica, envía un mensaje de solicitud Request(ts _i , i) a todos los demás sitios y coloca la solicitud en request_queue _i . Aquí, Ts _i denota la marca de tiempo del sitio S _i
  • Cuando un sitio S _j recibe el mensaje de solicitud SOLICITUD (ts _i , i) del sitio S _i , devuelve un mensaje de RESPUESTA con marca de tiempo al sitio S _i y coloca la solicitud del sitio S _i en request_queue _j

  .

• Para ejecutar la sección crítica:
  • Un sitio S _i puede ingresar a la sección crítica si ha recibido el mensaje con una marca de tiempo mayor que (ts _i , i) de todos los demás sitios y su propia solicitud está en la parte superior de request_queue _i
• Para liberar la sección crítica:
  • Cuando un sitio S _i sale de la sección crítica, elimina su propia solicitud de la parte superior de su cola de requests y envía un mensaje de LIBERACIÓN con marca de tiempo a todos los demás sitios.
  • Cuando un sitio S _j recibe el mensaje de LIBERACIÓN con marca de tiempo del sitio S _i , elimina la solicitud de S _i de su cola de requests

Complejidad del mensaje:
el algoritmo de Lamport requiere la invocación de 3 (N – 1) mensajes por ejecución de sección crítica. Estos 3(N – 1) mensajes implican

• (N – 1) mensajes de solicitud
• (N – 1) mensajes de respuesta
• (N – 1) mensajes de liberación

Inconvenientes del algoritmo de Lamport:

• Enfoque poco confiable: la falla de cualquiera de los procesos detendrá el progreso de todo el sistema.
• Alta complejidad de mensajes: el algoritmo requiere 3 (N-1) mensajes por invocación de sección crítica.

Actuación:

• El retraso de sincronización es igual al tiempo máximo de transmisión del mensaje
• Requiere 3 (N – 1) mensajes por ejecución de CS.
• El algoritmo se puede optimizar para 2 (N – 1) mensajes omitiendo el mensaje RESPONDER en algunas situaciones.