Esta sincronización, en sistemas distribuidos, se hace más compleja que en los sistemas centralizados puesto que la información y el procesamiento se mantienen en diferentes nodos. La sincronización de relojes en sistemas distribuidos nos permite garantizar que los procesos se ejecutan cronológicamente y además respetar el orden de los eventos dentro del sistema.
Luego de esta pequeña introducción a la sincronización vamos a hablar acerca del Algoritmo de Lamport. Y es que en este post hablaremos de la propuesta que hizo el científico en computación Dr Leslie Lamport.
Lamport señaló que la sincronización de relojes no tiene que ser absoluta.
Si 2 procesos no interactúan no es necesario que sus relojes estén sincronizados.
Generalmente lo importante no es que los procesos estén de acuerdo en la hora, pero sí importa que coincidan en el orden en que ocurren los eventos.
Y es aquí dónde aparece el concepto de reloj lógico. Un reloj lógico de Lamport es un contador software que se incrementa monótonamente, cuyos valores no necesitan tener ninguna relación particular con ningún reloj físico.
Para sincronizar los relojes lógicos, Lamport definió la relación ocurre antes de(happens-before):
Si “a” y “b” son eventos en el mismo proceso y “a” ocurre antes de “b”, entonces “a –> b” es verdadero.
“Ocurre antes de” es una relación transitiva:
Si “a –> b” y “b –> c”, entonces “a –> c”.
Si dos eventos “x” e “y” están en procesos diferentes que no intercambian mensajes, entonces “x –> y” no es verdadero, pero tampoco lo es “y –> x”:
Se dice que son eventos concurrentes.
Necesitamos una forma de medir el tiempo tal que a cada evento “a”, le podamos asociar un valor del tiempo “C(a)” en el que todos los procesos estén de acuerdo:
Se debe cumplir que:
o Si “a –> b” entonces “C(a) < C(b)”.
o El tiempo del reloj, “C”, siempre debe ir hacia adelante (creciente), y nunca hacia atrás (decreciente).
El algoritmo de Lamport asigna tiempos a los eventos.
Para la implementación se ejemplifica con el paso de mensajes entre 3 "procesos, con un tiempo especifico cada uno, dando como resultado el envio de un mensaje con su tiempo de envio.
En la interfaz, observamos el "time", que es tiempo que transcurre desde que inicia el proceso, el "message" que es el mensaje que queremos enviar, "to:" en esta area seleccionamos a que proceso queremos enviar el mensaje, "received" que es la variable que escucha el mensaje enviado por cualquier otro proceso, aqui es donde recibimos el mensaje y el tiempo en el cual fue enviado el mensaje.
Otras referencias:
http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO9.htm
http://rubmarin.galeon.com/algoritmolamport.htm
http://blog.rolandopalermo.com/2009/12/algoritmo-de-lamport-para-la.html
http://tele.informatik.uni-freiburg.de/lehre/ws01/dsys/Lectures/Lecture10.pdf
