Unidad 3.- Sincronización
3.1.- Análisis del tiempo
La sincronización es más compleja en los sistemas distribuidos que en los centralizados, puesto que los primeros deben utilizar algoritmos distribuidos. Por lo general, no es posible (o recomendable) reunir toda la información relativa al sistema en un lugar y después dejar que cierto proceso la examine y tome una decisión, como se hace en el caso centralizado. En un sistema centralizado!; el tiempo no tiene ambigüedades. Cuando un proceso desea conocer la hora, llama al sistema y el núcleo se la dice. Si el proceso A pide la hora y un poco después, el proceso B también la pide, el valor obtenido por B es mayor o igual que el valor obtenido por A
En general, los algoritmos distribuidos tienen las siguientes propiedades:
1. La información relevante se distribuye entre varias máquinas.
2. Los procesos toman las decisiones sólo con base en la información disponible en forma local.
3. Debe evitarse un punto de fallo en el sistema.
4. No existe un reloj común o alguna otra fuente precisa del tiempo global.
Los primeros tres puntos indican que es inaceptable reunir toda la información en un lugar para su procesamiento.
3.1.1.- Introducción
Puesto que el tiempo es fundamental para la forma de pensar de la gente y el efecto de carecer de sincronización en los relojes puede ser muy drástico.
3.1.2.- Relojes lógicos y físicos
Relojes lógicos: Casi todas las computadoras tienen un circuito para el registro del tiempo. A pesar del uso generalizado de la palabra “reloj” para hacer referencia a dichos dispositivos, en realidad no son relojes en el sentido usual. Cronómetro sería una mejor palabra. Un cronómetro de computadora es por lo general un cristal de cuarzo trabajado con precisión. Cuando se mantiene sujeto a tensión, un cristal de cuarzo oscila con frecuencia bien definida, que depende del tipo de 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 cronómetro de modo que genere una interrupción 60 veces por cada segundo o con cualquier frecuencia que se desee. Cada interrupción recibe el nombre de m arca de reloj.
En el caso de una computadora y un reloj, no importa si éste se desfasa un poco. Puesto que todos los procesos de la máquina utilizan el mismo reloj, tendrán consistencia interna. En la práctica, cuando un sistema tiene n computadoras, los n cristales correspondientes oscilarán a tasas un poco distintas, lo que provoca una pérdida de sincronía en los relojes (de software) y que al leerlos tengan valores distintos. La diferencia entre los valores del tiempo se llama distorsión del reloj. Como consecuencia de esta distorsión, podrían fallar los programas que esperan que el tiempo asociado a un archivo, objeto, proceso o mensaje sea correcto e independiente del sitio donde haya sido generado (es decir, del reloj utilizado).
Cuando existe la restricción adicional de que los relojes no sólo deben ser iguales, sino que además no se desvíen del tiempo real más allá de cierta magnitud, los relojes reciben el nombre de relojes físicos.
Para sincronizar los relojes lógicos, 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 del envío de un mensaje por un proceso y ó 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 envía, puesto que tarda en llegar 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 y, están en procesos diferentes que no intercambian mensajes (ni siquiera en forma indirecta por medio de un tercero), entonces x —» y no es verdadero, ni tampoco lo es y —» x. Se dice que estos eventos son concurrentes, lo que significa que nada se puede decir (o se necesita decir) acerca del momento en el que ocurren o cuál de ellos es el primero.
Relojes físicos: En ciertos sistemas (por ejemplo, los sistemas de tiempo real), es importante la hora real del reloj. Para estos sistemas se necesitan relojes físicos externos. Por razones de eficiencia y redundancia, por lo general son recomendables varios relojes físicos.
Los físicos retomaron de los astrónomos la tarea de medir el tiempo y definieron el segundo como el tiempo que tarda el átomo de cesio 133 en hacer exactamente 9 192 631 770 transiciones. La elección de 9 192 631 770 fue hecha para que el segundo atómico fuera igual al segundo solar promedio en el año de su introducción.
Actualmente, cerca de 50 laboratorios en el mundo tienen relojes de cesio 133. En forma periódica, cada laboratorio le indica a la oficina internacional de la hora en París (BIH) el número de marcas de su reloj. La oficina hace un promedio de estos números para producir el tiempo atómico internacional, que se abrevia TAI. Así, TAI es el promedio de las marcas de los relojes de cesio 133 a partir de la medianoche del primero de enero de 1958 (principio del tiempo), dividido entre 9 192 631 770.
La BIH resolvió el problema mediante la introducción de segundos de salto, siempre que la discrepancia entre TAI y el tiempo solar creciera hasta 800 milisegundos. El uso de los segundos de salto se ilustra en la figura 3-4. Esta corrección da lugar a un sistema de tiempo basado en los segundos constantes TAI, pero que permanece en fase con el movimiento aparente del Sol. Se le llama tiempo coordenado universal, UTC. UTC es la base de todo el sistema de mantenimiento moderno de la hora. En lo esencial, ha remplazado al estándar anterior, el tiempo del meridiano de Greenwich, que es un tiempo astronómico.
3.2.- Estudio de algoritmos de sincronización
Todos los algoritmos tienen el mismo modelo subyacente del sistema. Se supone que cada máquina tiene un cronómetro, el cual provoca una interrupción H veces por cada segundo. Cuando este cronómetro se detiene, el controlador de interrupciones suma 1 a un reloj en software, el cual mantiene el registro del número de marcas (interrupciones) a partir de cierta fecha acordada en el pasado. Llamaremos al valor de este reloj C. Más precisamente, cuando el tiempo UTC es t, el valor del reloj en la máquina p es Cp(t). En un mundo perfecto, tendríamos Cp(t) = t para to d ap y toda t. En otras palabras, dC/dt debería ser 1. Los cronómetros reales no realizan interrupciones exactamente //v e c e s por cada segundo. En teoría, un cronómetro con H = 60 generaría 216 000 marcas por hora.
Algoritmo de Cristian
Comenzaremos con un algoritmo adecuado para los sistemas en los que una máquina tiene un receptor WWV y el objetivo es hacer que todas las máquinas se sincronicen con ella. Llamaremos a la máquina con el receptor WWV un servidor del tiempo. Nuestro algoritmo se basa en el trabajo de Cristian (1989) y trabajos anteriores. En forma periódica, en un tiempo que no debe ser mayor que 5/2p segundos, cada máquina envía un mensaje al servidor para solicitar el tiempo actual. Esa máquina responde tan pronto como puede con un mensaje que contiene el tiempo actual, CUTC. Como primera aproximación, cuando el emisor obtiene la respuesta, puede hacer que su tiempo sea CUTC.
Sin embargo, este algoritmo tiene dos problemas, uno mayor y otro menor. El problema mayor es que el tiempo nunca debe correr hacia atrás. Si el reloj del emisor es rápido, CUTC será menor que el valor actual de C del emisor. El simple traslado de CUTC podría provocar serios problemas, tales como tener un archivo objeto compilado justo después del cambio de reloj y que tenga un tiempo anterior al del archivo fuente, modificado justo antes del cambio del reloj.
El algoritmo de Berkeley
En el algoritmo de Cristian, el servidor de tiempo es pasivo. Otras máquinas le piden el tiempo de manera periódica y todo lo que hace es responder a sus solicitudes. En este caso, el servidor de tiempo (en realidad, un demonio para el tiempo) está activo y realiza un muestreo periódico de todas las máquinas para preguntarles el tiempo. Con base en las respuestas, calcula un tiempo promedio y les indica a todas las demás máquinas que avancen su reloj a la nueva hora o que disminuyan la velocidad del mismo hasta lograr cierta reducción específica. Este método es adecuado para un sistema donde no exista un receptor de WWV. La hora del demonio para el tiempo debe ser establecida en forma manual por el operador, de manera periódica.
Algoritmos con promedio
Una clase de algoritmos descentralizados trabaja al dividir el tiempo en intervalos de re sincronización de longitud fija.
El i-ésimo intervalo inicia en Ta + iR y va hasta T0 + (i+l)R, donde T0 es un momento ya acordado en el pasado y R es un parámetro del sistema. Al inicio de cada intervalo, cada máquina transmite el tiempo actual según su reloj, Puesto que los relojes de las diversas máquinas no funcionan con exactamente la misma velocidad, estas transmisiones no ocurrirán en forma simultánea. Después de que una máquina transmite su hora, inicia un cronómetro local para reunir las demás transmisiones que lleguen en cierto intervalo S. Cuando llegan todas las transmisiones, se ejecuta un algoritmo para calcular una nueva hora para ellos. El algoritmo más sencillo consiste en promediar los valores de todas las demás máquinas.
3.3.- Exclusión mutua de un sistema distribuido
Con frecuencia, los sistemas con varios procesos se programan más fácil mediante las regiones críticas. Cuando un proceso debe leer o actualizar ciertas estructuras de datos compartidas, primero entra a una región crítica para lograr la exclusión mutua y garantizar que ningún otro proceso utilice las estructuras de datos al mismo tiempo. En los sistemas con un procesador, las regiones críticas se protegen mediante semáforos, monitores y construcciones similares.
Un algoritmo centralizado
La forma más directa de lograr la exclusión mutua en un sistema distribuido es similar a la forma en que se lleva a cabo en un sistema con un procesador. Se elige un proceso como el coordinador (por ejemplo, aquel que se ejecuta en la máquina con la máxima dirección en la red). Siempre que un proceso desea entrar a una región crítica, envía un mensaje de solicitud al coordinador, donde indica la región crítica a la que desea entrar y pide permiso. Si ningún otro proceso está por el momento en esa región crítica, el coordinador envía una respuesta otorgando el permiso.
Un algoritmo distribuido
Con frecuencia, el hecho de tener un punto de falla es inaceptable, por lo cual los investigadores han buscado algoritmos distribuidos de exclusión mutua.
El algoritmo funciona como sigue. Cuando un proceso desea entrar a una región crítica, construye un mensaje con el nombre de ésta, su número de proceso y la hora actual. Entonces envía el mensaje a todos los demás procesos y de manera conceptual a él mismo. Se supone que el envío de mensajes es confiable; es decir, cada mensaje tiene un reconocimiento.
El proceso 0 envía a todos una solicitud con la marca de tiempo 8, mientras que al mismo tiempo, el proceso 2 envía a todos una solicitud con la marca de tiempo 12. El proceso 1 no se interesa en entrar a la región crítica, por lo que envía OK a ambos emisores. Los procesos 0 y 2 ven el conflicto y comparan las marcas. El proceso 2 ve que ha perdido, por lo que otorga el permiso a 0 al enviar un mensaje OK. El proceso 0 forma ahora la solicitud de 2 en una fila para posterior procesamiento y entra a la región crítica, como se muestra en la figura (b). Cuando termina, retira la solicitud de 2 de la fila y envía un mensaje OK al proceso 2, lo que permite a éste entrar a su región crítica.
Un algoritmo de anillo de fichas
En software, se construye un anillo lógico y a cada proceso se le asigna una posición en el anillo. Las posiciones en el anillo se pueden asignar según el orden numérico de las direcciones de la red o mediante algún otro medio. No importa cómo sea el orden. Lo importante es que cada proceso sepa quién es el siguiente en la fila después de él. Al iniciar el anillo, se le da al proceso 0 una ficha, la cual circula en todo et anillo. Se trasfiere del proceso al proceso k+ 1 (módulo el tamaño del anillo) en mensajes puntuales. Cuando un proceso obtiene la ficha de su vecino, verifica si intenta entrar a una región crítica. En ese caso, el proceso entra a la región, hace todo el trabajo necesario y sale de la región. Después de salir, pasa la ficha a lo largo del anillo. No se permite entrar a una segunda región crítica con la misma ficha. Si un proceso recibe la ficha de $u vecino y no está interesado en entrar a
una región crítica, sólo la vuelve a pasar. En consecuencia, cuando ninguno de los procesos desea entrar a una región crítica, la ficha sólo circula a gran velocidad en el anillo.
Comparación de los tres algoritmos
3.4.- Problemas de concurrencia
Cuando se ejecutan varias transacciones de manera simultánea en distintos procesos (o distintos procesadores), se necesita cierto mecanismo para mantener a cada uno lejos del camino del otro. Este mecanismo se llama algoritmo de control de concurrencia.
Cerradura
El algoritmo más antiguo y de más amplio uso es la cerradura. En su forma más sencilla, cuando un proceso necesita leer o escribir en un archivo (u otro objeto) como parte de una transacción, primero cierra el archivo. La cerradura se puede hacer mediante un controlador centralizado de cerraduras, o bien con un controlador local de cerraduras en cada máquina, que maneje los archivos locales. En ambos casos, el controlador de cerraduras mantiene una lista de los archivos cerrados y rechaza todos los intentos de otro proceso por cerrarlos. Puesto que los procesos bien comportados no intentan tener acceso a un archivo antes de ser cerrado, el establecimiento de una cerradura en un archivo mantiene a todos lejos de éste, lo cual garantiza que no será modificado durante la transacción. El sistema de transacciones es el que por lo general adquiere y libera las cerraduras y no necesita acción alguna por parte del programador.
Control optimista de la concurrencia
Un segundo método para el manejo de varias transacciones al mismo tiempo es el control optimista de la concurrencia (Kung y Robinson, 1981). La idea detrás de esta técnica sorprende por sencilla: sólo se continúa y se hace todo lo que se deba llevar a cabo, sin prestar atención a lo que hacen los demás. Si existe un problema, hay que preocuparse por él después. (También muchos políticos utilizan este algoritmo.) En la práctica, los conflictos son sumamente raros, por lo que la mayoría del tiempo todo funciona muy bien. Aunque los conflictos pueden ser raros, no son imposibles, por lo que se necesita manejarlos de alguna forma. Lo que hace el control optimista de la concurrencia es mantener un registro de los archivos leídos o en los que se ha escrito algo. En el momento del compromiso, se verifican todas las demás transacciones para ver si alguno de los archivos ha sido modificado desde el inicio de la transacción. SÍ esto ocurre, la transacción aborta. Si no, se realiza el compromiso. El control optimista de la concurrencia se ajusta mejor a la implantación con base en espacios de trabajo particulares. De esa manera, cada transacción modifica sus archivos en forma privada, sin interferencia de los demás. Al final, los nuevos archivos quedan comprometidos o liberados.
Marcas de tiempo
Un método por completo distinto al control de la concurrencia consiste en asociar a cada transacción una marca de tiempo, al momento en que realiza BEGIN TRANSACTION (Reed, 1983). Mediante el algoritmo de Lamport, podemos garantizar que las marcas son únicas, lo cual es importante en este caso. Cada archivo del sistema tiene asociadas una marca de tiempo para la lectura y otra para la escritura, las cuales indican la última transacción comprometida que realizó la lectura o la escritura, respectivamente. Si las transacciones son breves y muy espaciadas con respecto del tiempo, entonces ocurrirá de manera natural que cuando un proceso intente tener acceso a un archivo, las marcas de tiempo de lectura y escritura sean menores (más antiguas) que la marca de la transacción activa. Este orden quiere decir que las transacciones se procesan en el orden adecuado, por do que todo funciona bien.
