El Reloj De Lamport

RELOJES LÓGICOS (ALGORITMO DE LAMPORT)

Un reloj lógico de Lamport es un contador software que se incrementa monótonamente, cuyos valores no necesitan tener ninguna relación con un reloj físico.

• Útiles para ordenar eventos en ausencia de un reloj común.

– Cada proceso P mantiene una variable entera LCP (reloj lógico)

– Cuando un proceso P genera un evento, LCP=LCP+1

– Cuando un proceso envía un mensaje incluye el valor de su reloj

– Cuando un proceso Q recibe un mensaje m con un valor t:

• LCQ=max(LCQ,t)+1

• El algoritmo asegura:

– Que si a  b entonces LCa < LCb

– Pero LCa < LCb no implica a  b (pueden ser concurrentes)

• Relojes lógicos sólo representan una relación de orden parcial.

• Orden total entre eventos si se añade el número del procesador.

CONCLUSIÓN:

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.

Este algoritmo nos da una forma de obtener un orden total de todos los eventos en el sistema. Muchos otros algoritmos distribuidos necesitan tal orden para evitar problemas las ambigüedades.

Por medio de este método, tenemos ahora una forma de asignar un tiempo a todos los eventos en un sistema distribuido.

No sincronizado Sincronizado

RELOJES DE VECTORES (MATTERN Y FIDGE)

Mattern y Fidge desarrollaron relojes vectoriales para vencer la deficiencia de los relojes de Lamport, del hecho que no podemos deducir que un reloj vectorial para un sistema de N procesos es un vector de N enteros.

Para evitar los casos en los que LCa < LCb no implica a  b.

Cada reloj es un array V de N elementos siendo N el número de procesadores (nodos) del sistema.

– Inicialmente Vi[j]=0 para todo i,j

– Cuando el proceso i genera un evento Vi[i]=Vi[i]+1

– Cuando en el nodo i se recibe un mensaje del nodo j con un vector de tiempo t entonces:

• para todo k: Vi[k]=max(Vi[k],t[k]) (operación de mezcla) y

• Vi[i]=Vi[i] + 1

CONCLUSIÓN: Por medio de este mecanismo siempre es posible evaluar si dos marcas de tiempo tienen o no relación de precedencia.

DESVENTAJA:Los vectores de marcas de tiempo tienen la desventaja, comparados con las marcas de tiempo de Lamport, de precisar una cantidad de almacenamiento y de carga real de mensajes que es proporcional a N, el número de procesos.

Uso de los Relojes Lógicos

La

...