3.1.1 Relojes Lóicos

Las computadoras tienen todas un circuito electrónico de reloj, que funciona más como un cronómetro el cual se basa en un oscilador de cristal de cuarzo y se puede identificar en la computadora porque tiene una pequeña pila del tamaño de una moneda. Al aplicarle un voltaje al cristal, oscila con cierta frecuencia que depende del tamaño del cristal, el tipo de corte, la magnitud del voltaje y la temperatura. Es sumamente difícil garantizar que todas estas variables son iguales en todas las computadoras por lo cual cada reloj oscilará a su frecuencia particular. Al reloj se le asocian dos registros: Un contador y un registro mantenedor. Al comienzo del algoritmo del reloj, se carga el contenido del registro mantenedor en el contador, luego, cada vez que el cristal oscila, se disminuye en 1 el valor del contador. Cuando el contador llega a cero, se genera una interrupción denominada marca de reloj, se carga de nuevo el contador con el valor del registro mantenedor y se repite el ciclo. Así podemos programar el reloj para que genere la cantidad de marcas de reloj por segundo deseada.

Cuando el sistema inicia por primera vez, se pide al operador la fecha y la hora, entonces esta información se convierte a número de marcas de reloj ocurridas a partir de cierta fecha que es el inicio del tiempo. Cada vez que ocurre una marca de reloj, la rutina de interrupción suma 1 al valor del tiempo para mantener actualizado el reloj de software.

Cuando se trata de un sistema monoprocesador, no importa que este reloj se desfase un poco del tiempo real, lo que interesa es que la hora que solicitan todos los procesos proviene de una misma fuente. Así se garantiza que los eventos se mantienen ordenados en el tiempo, manteniendo las relaciones causa efecto de tal manera que las causas tienen horas inferiores a sus efectos.

Cuando consideramos un sistema distribuído, compuesto por muchas computadoras, surgen problemas que no teníamos antes, como el hecho de que cada reloj de computadora marcará una hora diferente, marchará a una velocidad diferente de los otros y entonces hay que tener mucho cuidado con la información del tiempo que manejan los diversos procesos del sistema. Las diferencias en tiempo de los relojes se llama distorsión del reloj y como consecuencia de ella podrían fallar programas que dependan del tiempo percibido por los procesos, como la orden MAKE.

Un brillante investigador en este campo es LAMPORT, quien concluyó que a pesar de que no se pueda garantizar que todos los relojes marquen el mismo tiempo, sí es posible sincronizarlos para que se cumpla el principio de causalidad, es decir, que las causas sean anteriores a sus efectos. Publicó un primer artículo en 1978 y otro en 1990.

Lamport indica que si dos procesos no interactúan, no interesa el valor que marque el reloj de sus computadoras, porque no habría nada que dependiera de la distorsión de reloj, y lo que importa verdaderamente es que todos los procesos perciban la misma secuencia de eventos en el tiempo. En el ejemplo de MAKE, lo que importaba era percibir que la edición de un programa fuente era posterior a la última compilación del programa.

Generalmente no es necesario que la hora de las computadoras coincida con la hora real, nuestro interés en este punto es que los diferentes relojes de un sistema distribuído estén sincronizados entre sí. Esto es lo que se denomina relojes lógicos. Cuando existe una exigencia de que los relojes de las computadoras no se alejen de la hora real más de cierta cantidad, entonces hablamos de relojes físicos.

EL ALGORITMO DE LAMPORT

Permite sincronizar un conjunto de relojes lógicos. Lampor definió la siguiente relación:

a → b que significa a ocurre antes que b e indica que para todos los procesos, el evento a ocurre antes del evento b. Esta relación se puede observar en dos casos:

1. Si a y b son eventos del mismo proceso y a ocurre antes que b, entonces a → b es verdadero.
2. Si a es el evento de enviar un mensaje y b es el evento de recibir ése mensaje, entonces a → b es verdadero por causalidad.
   

"Ocurre antes de" es una relación transitiva, lo cual significa que si a → b y b → c entonces a → c.
Si dos procesos no intercambian mensajes, ni siquiera por medio de terceros, entonces a → b no es verdadero ni tampoco lo es b → a. Se dice que estos procesos son CONCURRENTES y no se puede decir nada acerca de cual evento ocurre primero.

Teniendo en cuenta que en una computadora el tiempo es un contador de marcas de reloj, se define la función C(a) como aquella que entrega el tiempo en que ocurre el evento a. Así, tenemos que si a → b entonces C(a) <>

3.1 SINCRONIZACIÓN DE RELOJES

En un sistema distribuído existen muchos relojes porque cada máquina tiene su propio reloj. Cada uno de estos relojes marca el tiempo a una velocidad un poco diferente de los otros, por lo que se van descuadrando con respecto a sus compañeros y de aquí surge la necesidad de sincronizarlos.

Los algoritmos que se ejecutan en sistemas distribuídos deben ser a su vez algoritmos distribuídos los cuales debe cumplir ciertas características:

1. La información relevante debe estar distribuída en varias máquinas, de tal manera que ninguna de ellas sea necesaria. Esto significa que no deben existir porcesos administradores únicos o servidores únicos para alguna labor. No debe existir un administrador de procesos o de recursos no sólo porque es un punto de falla sino porque limita el crecimiento del sistema, es un problema de escalabilidad.
   
2. Cada proceso toma decisiones con la información que tiene disponible localmente, para que sea eficiente porque la red es lenta comparada con la velocidad interna de la máquina.
3. Se debe evitar un punto de falla en el sistema, es decir, no habrá centralización, así que el sistema debe ser tolerante a la falla de una o varias de sus máquinas.
4. No existe un reloj común o alguna otra fuente precisa de tiempo global, esto acepta la realidad de que todos los relojes marcan horas diferentes y aún así, los algoritmos deben funcionar.
   

Un sistema distribuído debería ser más confiable que uno centralizado, así que el fallo de algunas máquinas no debe inutilizar al sistema distribuído, como sucede con el centralizado cuando falla el servidor central.

El punto 4 es el que se va a discutir aquí. En un sistema centralizado el reloj de la máquina central es la que pone la hora para todo el sistema, cuando un proceso necesita la hora, se la pregunta al único reloj central y no tiene ambigüedades o incertidumbres acerca del tiempo. En el sistema distribuído existen muchos relojes que caminan a veolicidades ligeramente diferentes, es de esperarse entonces que cada reloj marque una hora diferente. Esto origina problemas nuevos. Por ejemplo, cuando hay una relación de causalidad entre dos eventos, se supone que el evento que toma el rol de "causa" debe ocurrir en un tiempo anterior que el evento que toma el rol de "efecto", pues las causas anteceden a lo efectos según la lógica o el sentido común. Pero si los relojes están descuadrados, no se puede garantizar que se cumpla lo que la lógica indica.

Hay aplicaciones que trabajan con base en el tiempo. En UNIX existe la orden make la cual se utiliza para compilar una aplicación que consta de muchos programas fuentes. Make compila cada programa fuente (un .c) generando un programa objeto (un .o) y al final enlaza todos los objetos con las librerías para generar el programa ejecutable (el .exe). Pero make es inteligente, verifica si la fecha y hora de modificación del programa fuente es posterior a la fecha y hora de creación del programa objeto; si esto se cumple, compila el programa fuente, de lo contrario, no lo hace, ahorrando un tiempo considerable. El problema es que si estamos en un sistema distribuído, los relojes de las máquinas donde se editan los programas fuente y de la máquina donde se compila, pueden estar muy descuadrados, por lo que make podría no compilar un programa fuente que se acaba de modificar, generando traumatismos para el programador que no entiende los errores que le salen.

Entonces, una vez que entendemos los problemas que se pueden originar por la falta de sincronización, nos hacemos esta pregunta:

Es posible sincronizar todos los relojes de un sistema?

3 Sincronización en Sistemas Distribuídos

Un sistema tiene recursos únicos que necesitan ser compartidos entre los procesos. Generalmente, sólo un proceso puede accesar el recurso a la vez. Es necesario entonces sincronizar el acceso a estos recursos. Otras veces se requiere sincronizar el tiempo, la comunicación, el orden de los eventos de un algoritmo, etc.

En los sistemas monoprocesador, la sicronización era fácil porque todos los procesos comparten el mismo reloj, y el acceso a regiones críticas se hace con mecanismos como los semáforos y los monitores, los cuales presuponen la existencia de una memoria compartida. Entonces el núcleo del sistema operativo se encarga de mantener el semáforo o monitor y los procesos acceden a él por medio de señalamientos al núcleo. Esto es rápido porque todo se realiza sobre la misma memoria RAM.

Cuando se trata de un sistema distribuído, ya no hay memoria compartida y toda comunicación entre procesos supone un mensaje sobre la red, que es costoso en tiempo. Estas nuevas circunstancias requieren algoritmos y mecanismos diferentes. Igualmente, los errores que se presentan en el sistema son distintos.

El libro de texto

Recuerden que estamos utilizando como guía el libro SISTEMAS OPERATIVOS DISTRIBUIDOS de Andrew S. Tanenbaum.
Actualmente vamos a leer el capítulo 3 que habla de SINCRONIZACIÓN. Como no podemos tener clases presenciales, durante esta semana los estudiantes deben leer este capítulo.