SINCRONIZACIÓN

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

     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. 

 RELOJES LOGICOS

     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:

·         Al forma en que se corte el cristal.

·         El tipo de cristal.

·         La magnitud de la tensión.

·         A cada cristal se le asocian dos registros:

Registro contador.

Registro mantenedor.

·         Cada oscilación del cristal decrementa en “1” al contador.

·         Cuando el contador llega a “0”:

Se genera una interrupción.

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:

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

Importan los tiempos relativos.

·         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:

·         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.

·         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.

     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.

     Las computadoras poseen un circuito para el registro del tiempo conocido como dispositivo reloj.

Para varias computadoras con sus respectivos relojes:

RELOJES FISICOS 

El algoritmo de Lamport proporciona un orden de eventos sin ambigüedades, pero:

Los valores de tiempo asignados a los eventos no tienen porqué ser cercanos a los tiempos reales en los que ocurren.

En ciertos sistemas (ej.: sistemas de tiempo real ), 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í.

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

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.