Sincronización en Sistemas Distribuidos



SINCRONIZACIÓN

     Se habla de sincronización cuando varios procesos se ejecutan a la vez con el propósito de completar una tarea y evitar así condiciones de carrera, que pudieran desembocar en un estado inesperado. También se habla de sincronización de datos cuando dos dispositivos se actualizan de forma que contengan los mismo datos.



SINCRONIZACIÓN DE RELOJES

     Un sistema distribuido debe permitir el apropiado uso de los recursos, debe encargarsede un buen desempeño y de la consistencia de los datos, además de mantener seguras todas estas operaciones

La sincronización de procesos en los sistemas distribuidos resulta más compleja que en los centralizados, debido a que la información y el procesamiento se mantienen en diferentes nodos. Un sistema distribuido debe mantener vistas parciales y consistentes de todos los procesos cooperativos y de cómputo. 

Tales vistas pueden ser provistas por los mecanismos de sincronización.
El término sincronización se define como la forma de forzar un orden parcial o total en cualquier conjunto de eventos, y es usado para hacer referencia a tres problemas distintos pero relacionados entre sí:
1.La sincronización entre el emisor y el receptor.
2.La especificación y control de la actividad común entre procesos cooperativos.
3.La serialización de accesos concurrentes a objetos compartidos por múltiples procesos.

Haciendo referencia a los métodos utilizados en un sistema centralizado, el cual hace uso de semáforos y monitores; en un sistema distribuido se utilizan algoritmos distribuidos para sincronizar el trabajo común entre los procesos y estos algoritmos.



RELOJES FÍSICOS

      La idea es proveer de un único bloque de tiempo para el sistema. Los procesos pueden usar la marca física del tiempo provista o leída de un reloj central para expresar algún orden en el conjunto de acciones que inician. La principal ventaja de este mecanismo es la simplicidad, aunque existen varios inconvenientes: el correcto registro del tiempo depende en la posibilidad de recibir correctamente y en todo momento, el tiempo actual desplegado por el reloj físico; los errores de transmisión se convierten en un impedimento para el orden deseado, el grado de exactitud depende de las constantes puestas en el sistema.

*Los valores de tiempo asignados a los eventos no tienen porqué ser cercanos alos tiempos reales en los que ocurren.
*En ciertos sistemas es importante la hora real del reloj:
        *Se precisan relojes físicos externos (más de uno).
        *Se deben sincronizar:
               *Con los relojes del mundo real.
               *Entre sí.
Desde antiguo el tiempo se ha medido astronómicamente. 
Se considera el día solar al intervalo entre dos tránsitos consecutivos del sol, donde el tránsito del sol es el evento en que el sol alcanza su punto aparentemente más alto en el cielo. 
El segundo solar se define como 1 / 86.400 de un día solar.
Como el período de rotación de la tierra no es constante, se considera el segundo solar promedio de un gran número de días.
Los físicos definieron al segundo como el tiempo que tarda el átomo de cesio 133 para hacer 9.192.631.770 transiciones:
        •Se tomó este número para que el segundo atómico coincida con el segundo solar promedio de 1958. :
        •Operan estaciones de radio de onda corta o satélites de comunicaciones.
        •Transmiten pulsos UTC con cierta regularidad establecida (cada segundo, cada 0,5 mseg, etc.).
        •Se deben conocer con precisión la posición relativa del emisor y del receptor:
                   o Se debe compensar el retraso de propagación de la señal.
                   o Si la señal se recibe por módem también se debe compensar por la ruta de la señal y                       la velocidad del módem.
                   o Se dificulta la obtención del tiempo con una precisión extremadamente alta.



ALGORITMOS PARA LA SINCRONIZACIÓN DE RELOJES





ALGORITMO DE LAMPORT


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:
    • 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:
    • Si “a –> b” entonces “C(a) < C(b)”.
    • 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:
  • 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”:
    • Si “c” sale en “60” debe llegar en “61” o en un tiempo posterior.
    • Cada mensaje acarrea el tiempo de envío, de acuerdo con el reloj del emisor.
    • 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)”.

ALGORITMO DE CRISTIAN

Es adecuado para sistemas en los que:
  • Una máquina tiene un receptor UTC, por lo que se la llama despachador del tiempo.
  • El objetivo es sincronizar todas las máquinas con ella.
Cada máquina envía un mensaje al servidor para solicitar el tiempo actual, periódicamente, en un tiempo no mayor que d / 2 r segundos.El despachador del tiempo responde prontamente con un mensaje que contiene el tiempo actual “CUTC”.
Cuando el emisor obtiene la respuesta puede hacer que su tiempo sea “CUTC”.
Un gran problema es que el tiempo no puede correr hacia atrás:
  • “CUTC” no puede ser menor que el tiempo actual “C” del emisor.
  • La atención del requerimiento en el servidor de tiempos requiere un tiempo del manejador de interrupciones.
  • También se debe considerar el tiempo de transmisión.
El cambio del reloj se debe introducir de manera global:
  • Si el cronómetro genera 100 interrupciones por segundo:
    • Cada interrupción añade 10 mseg al tiempo.
    • Para atrasar solo agregaría 9 mseg.
    • Para adelantar agregaría 11 mseg.
La corrección por el tiempo del servidor y el tiempo de transmisión se hace midiendo en el emisor:
  • El tiempo inicial (envío) “T0”.
  • El tiempo final (recepción) “T1”.
  • Ambos tiempos se miden con el mismo reloj.
El tiempo de propagación del mensaje será (T1 - T0) / 2.Si el tiempo del servidor para manejar la interrupción y procesar el mensaje es “I”:
  • El tiempo de propagación será (T1 - T0 - I) / 2.
Para mejorar la precisión:
  • Se toman varias mediciones.
  • Se descartan los valores extremos.
  • Se promedia el resto.
El tiempo de propagación se suma al tiempo del servidor para sincronizar al emisor cuando éste recibe la respuesta.

ALGORITMO DE BERKELEY

En el algoritmo de Berkeley el servidor de tiempo:
  • Es activo.
  • Realiza un muestreo periódico de todas las máquinas para preguntarles el tiempo.
  • Con las respuestas:
    • Calcula un tiempo promedio.
    • Indica a las demás máquinas que avancen su reloj o disminuyan la velocidad del mismo hasta lograr la disminución requerida.
Es adecuado cuando no se dispone de un receptor UTC.

ALGORITMOS CON PROMEDIOS

Los anteriores son algoritmos centralizados.
Una clase de algoritmos descentralizados divide el tiempo en intervalos de resincronización de longitud fija:
  • El i -ésimo intervalo:
    • Inicia en “T0 + i R” y va hasta “T0 + (i + 1) R”.
    • “T0” es un momento ya acordado en el pasado.
    • “R” es un parámetro del sistema.
Al inicio de cada intervalo cada máquina transmite el tiempo actual según su reloj.
Debido a la diferente velocidad de los relojes las transmisiones no serán simultáneas.
Luego de que una máquina transmite su hora, inicializa un cronómetro local para reunir las demás transmisiones que lleguen en cierto intervalo “S”.
Cuando recibe todas las transmisiones se ejecuta un algoritmo para calcular una nueva hora para los relojes.
Una variante es promediar los valores de todas las demás máquinas.
Otra variante es descartar los valores extremos antes de promediar (los “m” mayores y los “m” menores).
Una mejora al algoritmo considera la corrección por tiempos de propagación.
Publicado por