Las computadoras poseen un circuito para el registro del tiempo conocido como dispositivo reloj [25, Tanenbaum].

Es un cronómetro consistente en un cristal de cuarzo de precisión sometido a una tensión eléctrica que:

  • Oscila con una frecuencia bien definida que depende de: 
          o Al forma en que se corte el cristal.
          o El tipo de cristal.
          o La magnitud de la tensión.
  • A cada cristal se le asocian dos registros: 
          o Registro contador.
          o Registro mantenedor.
  • Cada oscilación del cristal decrementa en “1” al contador.
  • Cuando el contador llega a “0”: 
          o Se genera una interrupción.
          o El contador se vuelve a cargar mediante el registro mantenedor.
  • Se puede programar un cronómetro para que genere una interrupción “x” veces por segundo.
  • Cada interrupción se denomina marca de reloj.

Para una computadora y un reloj:

  • No interesan pequeños desfasajes del reloj porque: 
          o Todos los procesos de la máquina usan el mismo reloj y tendrán consistencia interna.
          o 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 los relojes (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.

Lamport demostró que la sincronización de relojes es posible y presentó un algoritmo para lograrlo.

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.

Para ciertos algoritmos lo que importa es la consistencia interna de los relojes:

  • No interesa su cercanía particular al tiempo real (oficial).
  • Los relojes se denominan relojes lógicos.

Los relojes físicos son relojes que:

  • Deben ser iguales (estar sincronizados).
  • No deben desviarse del tiempo real más allá de cierta magnitud.

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: 
          o 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”: 
          o 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.

Consideramos tres procesos que se ejecutan en diferentes máquinas, cada una con su propio reloj y velocidad (ver Figura 9.1 [25, Tanenbaum]):

  • El proceso “0” envía el mensaje “a” al proceso “1” cuando el reloj de “0” marca “6”.
  • El proceso “1” recibe el mensaje “a” cuando su reloj marca “16”.
  • Si el mensaje acarrea el tiempo de inicio “6”, el proceso “1” considerará que tardó 10 marcas de reloj en viajar.
  • El mensaje “b” de “1” a “2” tarda 16 marcas de reloj.
  • El mensaje “c” de “2” a “1” sale en “60” y llega en “56”, tardaría un tiempo negativo, lo cual es imposible.
  • El mensaje “d” de “1” a “0” sale en “64” y llega en “54”.
  • Lamport utiliza la relación “ocurre antes de”: 
          o Si “c” sale en “60” debe llegar en “61” o en un tiempo posterior.
          o Cada mensaje acarrea el tiempo de envío, de acuerdo con el reloj del emisor.
          o Cuando un mensaje llega y el reloj del receptor muestra un valor anterior al tiempo en que se envió el mensaje:
                + El receptor adelanta su reloj para que tenga una unidad más que el tiempo de envío.

Ejemplo de tres procesos cuyos relojes corren a diferentes velocidades - El algoritmo de Lamport corrige los relojes.

Este algoritmo cumple nuestras necesidades para el tiempo global, si se hace el siguiente agregado:

  • Entre dos eventos cualesquiera, el reloj debe marcar al menos una vez.
  • Dos eventos no deben ocurrir exactamente al mismo tiempo.

Con este algoritmo se puede asignar un tiempo a todos los eventos en un sistema distribuido, con las siguientes condiciones:

  • Si “a” ocurre antes de “b” en el mismo proceso, “C(a) < C(b)”.
  • Si “a” y “b” son el envío y recepción de un mensaje, “C(a) < C(b)”.
  • Para todos los eventos “a” y “b”, “C(a)” es distinto de “C(b)”.

Búsqueda personalizada

GFDL