Algoritmo de lamport para la sincronización de relojes

Solo disponible en BuenasTareas
  • Páginas : 6 (1353 palabras )
  • Descarga(s) : 0
  • Publicado : 16 de noviembre de 2010
Leer documento completo
Vista previa del texto
Algoritmo de Lamport para la Sincronización de Relojes Lógicos en Sistemas Distribuidos. Simulación en Java
Publicado por Rolando
La sincronización en sistemas distribuidos consiste en garantizar que los procesos se ejecuten en forma cronológica y a la misma vez respetar el orden de los eventos dentro del sistema. En el caso de sistemas de una sola CPU, este problema se resuelve usandosemáforos, pero en sistemas de múltiples CPUs la solución ya implica el uso de otros métodos o algoritmos, para garantizar no solo la comunicación entre procesos sino también la forma como estos cooperan entre sí.

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.

Lasincronizació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.

Las computadoras poseen un circuito para el registro del tiempo conocido como dispositivo reloj. Es un cronómetro consistente en un cristal de cuarzo de precisión sometido a una tensión eléctrica.

Para unacomputadora y un reloj no interesan pequeños desfasajes del reloj porque:

Todos los procesos de la máquina usan el mismo reloj y tendrán consistencia interna.
Importan los tiempos relativos.

Para varias computadoras con sus respectivos relojes:

Es imposible garantizar que los cristales de computadoras distintas oscilen con la misma frecuencia.
Habrá una pérdida de sincronía en losrelojes (de software), es decir que tendrán valores distintos al ser leidos.

La diferencia entre los valores del tiempo se llama distorsión del reloj y podría generar fallas en los programas dependientes del tiempo.

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 encomputació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. Unreloj 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 unarelació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 procesosesté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.

[pic]

Una vez descrito el algoritmo, pasaré a mostrar su implementación en java. La primera imágen corresponde a una simulación similar a lamostrada en la imágen anterior y que puede ayudarnos a comprender mejor el funcionamiento de este algoritmo.

[pic]

En la imágen siguiente, vemos que al querer enviar un mensaje del proceso 3 en un instante de tiempo 4 al proceso 2 en un instante de tiempo 3, el algoritmo exige la sincronización de los relojes logicos de los CPUs donde se encuentran los procesos anteriormente numerados. Basta dar...
tracking img