3.4 ALGORITMOS DE SINCRONIZACION Y CONTROL

 

Algoritmos de Sincronización.

 

La sincronización es mas compleja en los sistemas distribuidos que en los centralizados, puesto que los primeros deben utilizar algoritmos distribuidos, no es posible reunir toda la información relativa al sistema en un lugar y después dejar que cierto proceso lo examine.

 

Más compleja que en los centralizados

 

• Propiedades de algoritmos distribuidos:

– La información relevante se distribuye entre varias máquinas.

– Se toman decisiones sólo en base a la información local.

– Debe evitarse un punto único de fallo.

– No existe un reloj común.

 

• Problemas a considerar:

– Tiempo y estados globales.

– Exclusión mutua.

– Algoritmos de elección.

 

Tiempo y Estados Tiempo y Estados

•Relojes Distribuidos

•Relojes Lógicos                        

•Estados Globales.

 

Sincronización de Relojes Físicos

 

Relojes lógicos.

Casi todas las computadoras tienen un circuito para el registro de tiempo. Un cronometro de computadora es por lo general un cristal de cuarzo trabajando con precisión, cuando se mantiene sujeto a tensión, un cristal oscila con frecuencia bien definida,que depende del tiempo del cristal, la forma en que se corte y la magnitud de la tensión. A cada cristal se le asocian dos registros, un contador y un registro mantenedor. Cada oscilación del cristal disminuye en 1 al contador. Cuando el contador toma el valor 0, se genera una interrupción y el contador se vuelve a cargar mediante el registro mantenedor. De esta forma, es posible programar un cronometro de modo que genere una interrupción 60 veces por cada segundo o con cualquier frecuencia que desee. Cada interrupción recibe el nombre de marca de reloj.

 

Cuando se arranca por vez primera el sistema, por lo general se pide al operador que escriba la fecha y la hora, las cuales se convierten al número de marcas después de cierta fecha conocida y se guardan en la memoria. En cada marca de reloj, el procedimiento de servicio de interrupciones añade un 1 al tiempo guardado en memoria.

 

Tan pronto se comienzan a trabajar con varias maquinas, cada una con su propio reloj, la situación es distinta. Aunque la frecuencia de un oscilador de cristal es muy estable, es imposible garantizar que los cristales de computadoras distintas oscilen precisamente con la misma frecuencia. La diferencia entre los valores del tiempo se llama distorsión de reloj. Como consecuencia, podrían fallar los programas que esperan que el tiempo asociado en un archivo, objeto. Proceso o mensaje sea correcto e independiente del sitio donde haya sido generado.

 

Pero esto nos dice es posible sincronizar todos los relojes para obtener una estandarización del tiempo único, sin ambigüedades.

 

Para esto Lamport señalo que la Sincronización de relojes no tiene que ser absoluta. Si dos procesos no interactúan, no es necesario que sus relojes estén sincronizados, puesto que la carencia de sincronización no seria observable y por tanto no podría provocar problemas, Además señalo que lo que importa ,no es que todos los procesos concuerden de manera exacta en la hora, si no que coincidan en el orden en que ocurren los eventos.

 

Algoritmo de Lamport.

 

Para sincronizar los relojes físicos Lamport Definió una relación llamada Ocurre antes de la expresión a à b se lee: “a ocurre antes de b” e indica que todos los procesos coinciden en que primero ocurre el evento a y después el evento b. La relación “ ocurre antes de “ se puede observar de manera directa en dos situaciones:

 

1.- Si a y b son eventos en el mismo proceso y a ocurre antes de b, entonces aàb es verdadero.

 

2.- Si a es el evento de un mensaje por un proceso y b es el evento de la recepción del mensaje por otro proceso, entonces  aàb también es verdadero. Un mensaje no se puede recibir antes de ser enviado o al mismo tiempo en que se envia,puesto que tarda una cantidad finita de tiempo en que se envía, puesto que tarda una cantidad finita de tiempo.

 

Ocurre antes de  es una relación transitiva, de modo que si a àb y bàc entonces aàc. si dos eventos ,x, y z están en procesos diferentes que no intercambian mensajes , entonces en xàz no es verdadero , ni tampoco lo es  y à z. Se dice que estos eventos son concurrentes, lo que significa que nada se puede decir acerca del momento  en el que ocurren o cual de ellos es el primero.

 

Lo que necesitamos es 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. Estos valores del tiempo deben tener la propiedad de que si aàb, entonces C(a) < C(b). En otros terminos, si a y b son dos procesos dentro del mismo evento y a ocurre antes de b, entonces C(a) < C(b).

 

 

 

 

 

 

 

 

 

 

Relojes Físicos.

 

Aunque el algoritmo de Lamport proporciona un orden de ambigüedades, los valores de tiempo asignados a los eventos no tienen que ser cercanos a los tiempos reales en los que ocurren. En ciertos sistemas es importante la hora de Reloj. Para estos sistemas se necesitan relojes físicos externos. Por razones de eficiencia y redundancia. Pero como se mide el tiempo en realidad no es tan sencillo como uno pudiese pensar, en particular cuando se requiere de alta precisión. Desde la Invención de los relojes mecánicos, el tiempo se ha medido de manera astronómica. Cada día, el sol parece levantarse en el horizonte desde el este, sube hasta una altura máxima en el cielo y desciende en el oeste. El evento en que el sol alcanza su punto aparentemente mas alto en el cielo se llama transito del sol. Este evento ocurre aproximadamente a las doce del día de cada día. El intervalo entre dos tránsitos consecutivos del sol se llama día solar. Puesto que existen 24 horas en un día, cada una de las cuales contiene 3600 segundos, el segundo solar se define exactamente como 1/86400 de un día solar. 

 

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.

 

La Oficina Internacional de la Hora en París (BIH) recibe las indicaciones de cerca de 50 relojes atómicos en el mundo y calcula el tiempo atómico internacional (TAI).

 

Como consecuencia de que el día solar promedio (DSP) es cada vez mayor, un día TAI es 3 mseg menor que un DSP:

 

La BIH introduce segundos de salto para hacer las correcciones necesarias para que permanezcan en fase:

 

El sistema de tiempo basado en los segundos TAI.

El movimiento aparente del sol.

Surge el tiempo coordenado universal (UTC).

El Instituto Nacional del Tiempo Estándar (NIST) de EE. UU. y de otros países:

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:

Se debe compensar el retraso de propagación de la señal.

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.

Se dificulta la obtención del tiempo con una precisión extremadamente alta.

 

 

 

 

Algoritmos Para la Sincronización de Relojes

Si una máquina tiene un receptor de UTC, todas las máquinas deben sincronizarse con ella

Si ninguna máquina tiene un receptor de UTC:

• Cada máquina lleva el registro de su propio tiempo.
• Se debe mantener el tiempo de todas las máquinas tan cercano como sea posible.

Se supone que cada máquina tiene un cronómetro que provoca una interrupción “h” veces por segundo.

Cuando el cronómetro se detiene, el manejador de interrupciones añade “1” a un reloj en software.

El reloj en software mantiene un registro del número de marcas (interrupciones) a partir de cierta fecha acordada antes; al valor de este reloj se lo llama “C”.

Cuando el tiempo UTC es “t”, el valor del reloj en la máquina “p” es “Cp(t)”:

• Lo ideal sería que “Cp(t)” = “t” para toda “p” y todo “t”:
• “dC/dt” debería ser “1”.
• Lo real es que los cronómetros no realizan interrupciones exactamente “h” veces por segundo:
• Poseen un error relativo de aproximadamente 10^{-5 .}
• El fabricante especifica una constante “ r ” llamada tasa máxima de alejamiento que acota el error.
• El cronómetro funciona dentro de su especificación si existe una constante “ r ” y se cumple:
• 1 - r £dC / dt £ 1 + r.

Si dos relojes se alejan de UTC en la dirección opuesta:

• En un instante Dt luego de la sincronización podrían estar tan alejados como: 2 rDt.
• Para garantizar que no difieran más de d:
• Se deben volver a sincronizar (en software) al menos cada d / 2 r segundos

 

 

 

 

   

 

 

 

 

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

Cuando el emisor obtiene la respuesta puede hacer que su tiempo sea “C_UTC”.

Un gran problema es que el tiempo no puede correr hacia atrás:

• “C_UTC” 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) “T₀”.
• El tiempo final (recepción) “T₁”.
• Ambos tiempos se miden con el mismo reloj.

El tiempo de propagación del mensaje será (T₁ - T₀) / 2.

Si el tiempo del servidor para manejar la interrupción y procesar el mensaje es “I”:

• El tiempo de propagación será (T₁ - T₀ - 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 Cristian el servidor de tiempo es pasivo.

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 Promedio

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 “T₀ + i R” y va hasta “T₀ + (i + 1) R”.
• “T₀” 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

 

 

 

Varias Fuentes Externas de Tiempo

Los sistemas que requieren una sincronización muy precisa con UTC se pueden equipar con varios receptores de UTC.

Las distintas fuentes de tiempo generaran distintos rangos (intervalos de tiempo) donde “caerán” los respectivos UTC, por lo que es necesaria una sincronización.

Como la transmisión no es instantánea se genera una cierta incertidumbre en el tiempo.

Cuando un procesador obtiene todos los rangos de UTC:

• Verifica si alguno de ellos es ajeno a los demás y de serlo lo descarta por ser un valor extremo.
• Calcula la intersección (en el tiempo) de los demás rangos.
• La intersección determina un intervalo cuyo punto medio será el UTC y la hora del reloj interno.

Se deben compensar los retrasos de transmisión y las diferencias de velocidades de los relojes.

Se debe asegurar que el tiempo no corra hacia atrás.

Se debe resincronizar periódicamente desde las fuentes externas de UTC.