Sincronizacion

SINCRONIZACIÓN

Aquí revisaremos como pueden sincronizarse los procesos. Por ejemplo, es importante que varios procesos no accedan simultáneamente a un recurso compartido, digamos a una impresora, sino que cooperen para garantizar a cada uno el acceso exclusivo temporal al recurso. La sincronización en sistemas distribuidos es con frecuencia mucho más difícil comparada con la de sistemas de un procesador.

Ahora veamos el análisis de un asunto de sincronización basado en tiempo real, seguido de la sincronización en la que solo importan cuestiones de ordenamiento relativo en lugar del ordenamiento en tiempo absoluto.

Sincronización del reloj

En un sistema centralizado, el tiempo no es ambiguo. Cuando un proceso quiere saber la hora, realiza una llamada de sistema y el núcleo se la dice. Si un proceso A pregunta la hora, y después un proceso B pregunta lo hora, el valor que obtiene B será mayor que el valor que obtuvo A. en un sistema distribuido, lograr un acuerdo con respecto al tiempo no es algo trivial.

Relojes físicos

Casi todas las computadoras tienen un circuito para dar seguimiento al tiempo. A pesar del amplio de la palabra “reloj” para hacer referencia a estos dispositivos, en realidad no son relojes en el sentido usual. Tal vez cronómetro sea una mejor palabra con la cual designarlos. Un cronómetro de computadora, en general, es un cristal de cuarzo mecanizado con precisión. Cuando este dispositivo se mantiene sujeto a tensión los cristales de cuarzo oscilan en una frecuencia bien definida que depende del tipo de cristal, de la forma de su corte, y de la cantidad de tensión. Hay dos registros asociados con cada cristal, un contador y un registro de mantenedor. Cada oscilación del cristal disminuye el contador en uno. Cuando el contador llega a cero, se genera una interrupción y el contador se reinicia a partir del registro de mantenedor. De esta manera, es posible programar un cronómetro para programar una interrupción 60 veces por segundo, o a cualquier otra frecuencia deseada. A cada interrupción se le conoce como marca de reloj.

Aunque la frecuencia con la que oscila un cristal es en general bastante estable, resulta imposible garantizar que los cristales de los diferentes computadores funcionen exactamente con la misma frecuencia. En la práctica, cuando un sistema tiene n computadoras, los n cristales funcionaran a velocidades ligeramente diferentes, lo cual ocasiona que los relojes (software) se salgan gradualmente de sincronía y arrojen diferentes valores cuando se leen. Esta diferencia en valores se conoce como distorsión de reloj.

Sistema de posicionamiento global

Como un paso hacia la solución de problemas de sincronización de relojes, primero consideremos un problema relacionado, a saber, como determinar nuestra posición geográfica en cualquier parte del planeta. Este problema de posicionamiento se resuelve por sí mismo a través de un sistema distribuido altamente específico y dedicado llamado GPS que significa sistema de posicionamiento global. El GPS es un sistema distribuido basado en un satélite puesto en órbita en 1978. Aunque ha sido utilizado principalmente en aplicaciones militares, en años recientes ha encontrado su camino para muchas aplicaciones civiles, principalmente en la navegación.

El GPS utiliza 29 satélites que circulan cada uno en una órbita situada a una altura aproximada de 20000 km. Cada satélite tiene hasta cuatro relojes atómicos que son calibrados regularmente desde estaciones especiales ubicadas en la Tierra. Un satélite transmite su posición de manera continua, y registra el tiempo de cada mensaje con su tiempo local. Esta transmisión permite a cada receptor localizado en la Tierra calcular exactamente su propia posición, empleando en principio solo tres satélites.

Algoritmos de sincronización de relojes

Si una maquina tiene un receptor WWV, el objetivo es mantener todas las demás maquinas sincronizadas con tal receptor. Si ninguna maquina tiene un receptor WWV, cada máquina da seguimiento a su propio tiempo, y el objetivo es mantenerlas juntas en tanto sea posible. Se han propuesto muchos algoritmos para realizar esta sincronización.

Si dos relojes parten del UTC en la dirección opuesta, en un tiempo Dt después de ser sincronizados pueden estar, cuando mucho, a 2p ∆t de diferencia. Si los diseñadores del sistema operativo quieren garantizar que dos relojes nunca difieran por mas de δ, los relojes deben ser sincronizados nuevamente (en el software) al menos cada δ/2p segundos. Los diversos algoritmos difieren precisamente en como se lleva a cabo esta sincronización.

Protocolo de tiempo de red

Un método común en muchos protocolos es dejar a los clientes contactar a un servidor de tiempo. El ultimo puede proporcionar exactamente el tiempo actual, por ejemplo, debido a que está equipado con un receptor WWV o un reloj exacto. Por supuesto, el problema cuando se contacta al servidor es que los retrasos del mensaje ocasionaran que el tiempo reportado no este actualizado. El truco reside en encontrar una buena estimación para estos retrasos.

El caso del protocolo de tiempo de red (NTP, por sus siglas en ingles), este se configura en pares entre servidores. En otras palabras, B también sondeara a A en cuanto a su tiempo actual.

Al aplicar el NTP simétricamente debe, en principio, permitir también a B ajustar su reloj con el de A. sin embargo, si se sabe que el reloj de B es más exacto, entonces tal ajuste sería imprudente. Para resolver este problema, el NTP divide a los servidores en estratos. Un servidor con un reloj de referencia, tal como como receptor WWV o un reloj atómico, se conoce como servidor de estado 1 (se dice que el propio reloj opera en el estado 0). Cuando A contacte a B, solo ajustara su tiempo si su propio estrato es más alto que el de B. además, después de la sincronización, el estado de A será un nivel más alto que el de B.

Existen muchas características importantes del NTP, de las cuales una gran cantidad se relaciona con identificación y enmascaramiento de errores, pero también con ataques a la seguridad. Mills (1992) describe al NTP, y es reconocido por lograr una exactitud en el rango de 1 a 50 ms.

Algoritmo de Berkeley

En Berkeley UNIX el servidor de tiempo (de hecho un demonio de tiempo) es cativo, ya que cada cierto tiempo pregunta a cada máquina sobre la hora ahí registrada. Basado en las respuestas, calcula un tiempo promedio y les indica a todas las maquinas que adelanten o trasen sus relojes, según la nueva hora. Este método es conveniente para un sistema en el que ninguna maquina tiene un receptor WWV. El operador debe configurar manualmente y de manera periódica la hora del demonio de tiempo.

Sincronización de relojes en redes inalámbricas

En redes de monitoreo, los nodos son recursos restringidos, y el enrutamiento multisaltos es caro. Además, con frecuencia es importante optimizar algoritmos para el consumo de energía. Estas y otras observaciones han dado pie al diseño de muchos diferentes algoritmos de sincronización de relojes para redes inalámbricas.

La sincronización de transmisión de referencias (RBS, por sus siglas en inglés) es un protocolo de sincronización de relojes que difiere mucho de otras propuestas (Elson y Cols., 2002). El protocolo no asume que hay un solo nodo con una cuenta exacta del tiempo real disponible. En lugar de ayudar a proporcionar a todos los nodos el tiempo UTC, este protocolo ayuda simplemente a sincronizar internamente los relojes, justo como el algoritmo de Berkeley. El SBS hace que solo los receptores se sincronicen, y manteniendo al emisor fuera del ciclo. En el RBS, un emisor transmite un mensaje de referencia que permitirá a sus receptores ajustar sus relojes.

Relojes lógicos

La sincronización de relojes esta naturalmente relacionada con el tiempo real. También hemos visto que puede ser suficiente que cada nodo coincida con un tiempo actual, sin que el tiempo sea necesariamente el mismo que el tiempo real.

Lamport (1978) señaló que lo generalmente importante no es que todos los procesos coincidan exactamente en el tiempo, sino que coincidan en el orden en que ocurren los eventos.

Relojes lógicos Lamport

Para sincronizar los relojes lógicos, Lamport definió una relación llamada ocurrencia anterior. La expresión a ---> b se lee como “a ocurre antes que b”, y significa que todos los procesos coinciden en que ocurre el primer evento a y, después de eso, ocurre el evento b. la relación ocurrencia anterior puede observarse directamente en dos situaciones:

1. Si a y b son eventos del mismo proceso, y a ocurre antes que b, entonces a  b es verdadera.

2. Si a es el evento en el que un proceso envía un mensaje, y b es el evento de recepción del mensaje por otro proceso, entonces a b también es verdadero. Un ejemplo no puede recibirse antes de ser enviado, o incluso al mismo tiempo en que es enviado, ya que necesita cierta cantidad de tiempo finita, diferente a cero, para llegar.

Relojes vectoriales

Los relojes de Lamport no se puede decir nada sobre la relación entre dos eventos a y b por mera comparación de sus valores de tiempo C(a) y C(b), respectivamente. En otras palabras, si C(a) < C(b), entonces esto no necesariamente implica que a realmente ocurrió antes que b; se necesita algo más para afirmar eso.

El problema es que los relojes de Lamport no capturan la casualidad. La casualidad puede capturase mediante los relojes vectoriales. Un reloj vectorial, VC(a), asignado a un evento a, tiene la propiedad de que si VC(a) < VC(b) para algún evento b, entonces se sabe que el evento

...