Sincronización en Sistemas Distribuidos


 

  1. Introducción a la Sincronización en Sistemas Distribuidos
  2. Sincronización de Relojes
  3. Relojes Lógicos
  4. Relojes Físicos
  5. Algoritmos Para la Sincronización de Relojes
    1. Algoritmo de Cristian
    2. Algoritmo de Berkeley
    3. Algoritmos con Promedio
    4. Varias Fuentes Externas de Tiempo
  6. Exclusión Mutua
    1. Un Algoritmo Centralizado
    2. Un Algoritmo Distribuido
    3. Un Algoritmo de Anillo de Fichas (Token Ring)
  7. Algoritmos de Elección
    1. El Algoritmo del Grandulón o de García-Molina
    2. Un Algoritmo de Anillo
  8. Transacciones Atómicas
  9. El Modelo de Transacción
    1. Almacenamiento Estable
    2. Primitivas de Transacción
    3. Propiedades de las Transacciones
    4. Transacciones Anidadas
  10. Implantación del Modelo de Transacción
    1. Espacio de Trabajo Particular
    2. Bitácora de Escritura Anticipada
    3. Protocolo de Compromiso de Dos Fases (Two - Phase Commit)
  11. Control de Concurrencia en el Modelo de Transacción
    1. Cerradura (locking)
    2. Control Optimista de la Concurrencia
    3. Marcas de Tiempo
    4. Resumen
  12. Bloqueos en Sistemas Distribuidos
  13. Detección Distribuida de Bloqueos
    1. Detección Centralizada de Bloqueos
    2. Detección Distribuida de Bloqueos
  14. Prevención Distribuida de Bloqueos
  15. Fin


Introducción a la Sincronización en Sistemas Distribuidos

Además de la comunicación, es fundamental la forma en que los procesos [25, Tanenbaum]:

Ejemplos: Los problemas relativos a las regiones críticas, exclusión mutua y la sincronización: Otro problema de gran importancia es el tiempo y la forma de medirlo, ya que juega un papel fundamental en algunos modelos de sincronización.

Inicio:   Fin:

Sincronización de Relojes

Generalmente los algoritmos distribuidos tienen las siguientes propiedades [25, Tanenbaum]:

Los primeros tres puntos indican que es inaceptable reunir toda la información en un solo lugar para su procesamiento, pero lograr la sincronización sin centralización requiere hacer las cosas distintas al caso de los sistemas operativos tradicionales.

El último punto también es crucial:

La pregunta es si es posible sincronizar todos los relojes en un sistema distribuido.

Inicio:   Fin:

Relojes Lógicos

Las computadoras poseen un circuito para el registro del tiempo conocido como dispositivo reloj [25, Tanenbaum].

Es un cronómetro consistente en un cristal de cuarzo de precisión sometido a una tensión eléctrica que:

Para una computadora y un reloj: Para varias computadoras con sus respectivos relojes: 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:

Para ciertos algoritmos lo que importa es la consistencia interna de los relojes: Los relojes físicos son relojes que: Para sincronizar los relojes lógicos, Lamport definió la relación ocurre antes de (happens-before): 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: 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 (ver Figura 9.1 [25, Tanenbaum]):


Ejemplo de tres procesos cuyos relojes corren a diferentes velocidades - El algoritmo de Lamport corrige los relojes.

Este algoritmo cumple nuestras necesidades para el tiempo global, si se hace el siguiente agregado:

Con este algoritmo se puede asignar un tiempo a todos los eventos en un sistema distribuido, con las siguientes condiciones:


Inicio:   Fin:

Relojes Físicos

El algoritmo de Lamport proporciona un orden de eventos sin ambigüedades, pero [25, Tanenbaum]:

La medición del tiempo real con alta precisión no es sencilla.

Desde antiguo el tiempo se ha medido astronómicamente.

Se considera el día solar al intervalo entre dos tránsitos consecutivos del sol, donde el tránsito del sol es el evento en que el sol alcanza su punto aparentemente más alto en el cielo.

El segundo solar se define como 1 / 86.400 de un día solar.

Como el período de rotación de la tierra no es constante, se considera el segundo solar promedio de un gran número de días.

Los físicos definieron al segundo como el tiempo que tarda el átomo de cesio 133 para hacer 9.192.631.770 transiciones:

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:

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


Inicio:   Fin:

Algoritmos Para la Sincronización de Relojes

Si una máquina tiene un receptor de UTC, todas las máquinas deben sincronizarse con ella [25, Tanenbaum].

Si ninguna máquina tiene un receptor de UTC:

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)”:

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


Inicio:   Fin:

Algoritmo de Cristian

Es adecuado para sistemas en los que:

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

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

El cambio del reloj se debe introducir de manera global: La corrección por el tiempo del servidor y el tiempo de transmisión se hace midiendo en el emisor: El tiempo de propagación del mensaje será (T1 - T0) / 2.

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

Para mejorar la precisión: El tiempo de propagación se suma al tiempo del servidor para sincronizar al emisor cuando éste recibe la respuesta.

Inicio:   Fin:

Algoritmo de Berkeley

En el algoritmo de Cristian el servidor de tiempo es pasivo.

En el algoritmo de Berkeley el servidor de tiempo:

Es adecuado cuando no se dispone de un receptor UTC.

Inicio:   Fin:

Algoritmos con Promedio

Los anteriores son algoritmos centralizados.

Una clase de algoritmos descentralizados divide el tiempo en intervalos de resincronización de longitud fija:

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.

Inicio:   Fin:

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:

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.

Inicio:   Fin:

Exclusión Mutua

Cuando un proceso debe leer o actualizar ciertas estructuras de datos compartidas [25, Tanenbaum]:

En sistemas monoprocesadores las regiones críticas se protegen con semáforos, monitores y similares.

En sistemas distribuidos la cuestión es más compleja.

Inicio:   Fin:

Un Algoritmo Centralizado

La forma más directa de lograr la exclusión mutua en un sistema distribuido es simular a la forma en que se lleva a cabo en un sistema monoprocesador.

Se elige un proceso coordinador.

Cuando un proceso desea ingresar a una región crítica:

Si un proceso pide permiso para entrar a una región crítica ya asignada a otro proceso: Cuando un proceso sale de la región crítica envía un mensaje al coordinador para liberar su acceso exclusivo: Es un esquema sencillo, justo y con pocos mensajes de control.

La limitante es que el coordinador puede ser un cuello de botella y puede fallar y bloquear a los procesos que esperan una respuesta de habilitación de acceso.

Inicio:   Fin:

Un Algoritmo Distribuido

El objetivo es no tener un único punto de fallo (el coordinador central).

Un ej. es el algoritmo de Lamport mejorado por Ricart y Agrawala.

Se requiere un orden total de todos los eventos en el sistema para saber cuál ocurrió primero.

Cuando un proceso desea entrar a una región crítica:

Si el receptor no está en la región crítica y no desea entrar a ella, envía de regreso un mensaje o.k. al emisor.

Si el receptor ya está en la región crítica no responde y encola la solicitud.

Si el receptor desea entrar a la región crítica pero aún no lo logró, compara:

Luego de enviar las solicitudes un proceso: Cuando un proceso sale de la región crítica: La exclusión mutua queda garantizada sin bloqueo ni inanición.

El número de mensajes necesarios por entrada es “2(n - 1)”, siendo “n” el número total de procesos en el sistema.

No existe un único punto de fallo sino “n”:

Se incrementa la probabilidad de fallo en “n” veces y también el tráfico en la red.

Se puede solucionar el bloqueo si:

Otro problema es que: Un importante problema adicional es que: Una mejora consiste en permitir que un proceso entre a una región crítica con el permiso de una mayoría simple de los demás procesos (en vez de todos):


Inicio:   Fin:

Un Algoritmo de Anillo de Fichas (Token Ring)

Los procesos se organizan por software formando un anillo lógico asignándose a cada proceso una posición en el anillo.

Cada proceso sabe cuál es el siguiente luego de él.

Al inicializar el anillo se le da al proceso “0” una ficha (token) que circula en todo el anillo, que se transfiere del proceso “k” al “k + 1” en mensajes puntuales.

Cuando un proceso obtiene la ficha de su vecino verifica si intenta entrar a una región crítica:

En un instante dado solo un proceso puede estar en una región crítica.

Si la ficha se pierde debe ser regenerada, pero es difícil detectar su perdida:

La falla de un proceso es detectada cuando su vecino intenta sin éxito pasarle la ficha:


Inicio:   Fin:

Algoritmos de Elección

Son los algoritmos para la elección de un proceso coordinador, iniciador, secuenciador, etc. [25, Tanenbaum].

El objetivo de un algoritmo de elección es garantizar que iniciada una elección ésta concluya con el acuerdo de todos los procesos con respecto a la identidad del nuevo coordinador.

Inicio:   Fin:

El Algoritmo del Grandulón o de García-Molina

Un proceso “P” inicia una elección cuando observa que el coordinador ya no responde a las solicitudes.

“P” realiza una elección de la siguiente manera:

Un proceso puede recibir en cualquier momento un mensaje elección de otros procesos con un número menor: En cierto momento todos los procesos han declinado ante uno de ellos, que será el nuevo coordinador, que envía un mensaje coordinador a todos los procesos para anunciarlo.

Si un proceso inactivo se activa realiza una elección:


Inicio:   Fin:

Un Algoritmo de Anillo

Se supone que los procesos tienen un orden físico o lógico, es decir que cada proceso conoce a su sucesor.

Cuando algún proceso observa que el coordinador no funciona:


Inicio:   Fin:

Transacciones Atómicas

Las técnicas de sincronización ya vistas son de bajo nivel [25, Tanenbaum]:

Se precisan técnicas de abstracción de mayor nivel que: Tal abstracción la llamaremos transacción atómica, transacción o acción atómica.

La principal propiedad de la transacción atómica es el “todo o nada”:


Inicio:   Fin:

El Modelo de Transacción

Supondremos que [25, Tanenbaum]:


Inicio:   Fin:

Almacenamiento Estable

Se puede implantar con una pareja de discos comunes.

Cada bloque de la unidad 2 es una copia exacta (espejo) del bloque correspondiente en la unidad 1.

Cuando se actualiza un bloque:

Si el sistema falla luego de actualizar la unidad 1 y antes de actualizar la unidad 2: Si se detecta el deterioro espontáneo de un bloque, se lo regenera partiendo del bloque correspondiente en la otra unidad.

Un esquema de este tipo es adecuado para las aplicaciones que requieren de un alto grado de tolerancia de fallos, por ej. las transacciones atómicas.

Inicio:   Fin:

Primitivas de Transacción

Deben ser proporcionadas por el sistema operativo o por el sistema de tiempo de ejecución del lenguaje.

Ejemplos:

Las operaciones entre Begin y End forman el cuerpo de la transacción y deben ejecutarse todas o ninguna de ellas:


Inicio:   Fin:

Propiedades de las Transacciones

Las propiedades fundamentales son:

La serialización garantiza que si dos o más transacciones se ejecutan al mismo tiempo: La atomicidad garantiza que cada transacción no ocurre o bien se realiza en su totalidad: La permanencia se refiere a que una vez comprometida una transacción:


Inicio:   Fin:

Transacciones Anidadas

Se presentan cuando las transacciones pueden contener subtransacciones (procesos hijos) que:


Inicio:   Fin:

Implantación del Modelo de Transacción

Existen varios métodos de implantación [25, Tanenbaum].

Inicio:   Fin:

Espacio de Trabajo Particular

Consiste en que cuando un proceso inicia una transacción se le otorga un espacio de trabajo particular:

Cuando un proceso inicia una transacción, basta crear un espacio de trabajo particular para él que sea vacío excepto por un apuntador de regreso al espacio de trabajo de su proceso padre.

Para una transacción del nivel superior el espacio de trabajo del padre es el sistema de archivos “real”.

Cuando el proceso abre un archivo para lectura, se siguen los apuntadores de regreso hasta localizar el archivo en el espacio de trabajo del padre (o algún antecesor).

Cuando se abre un archivo para escritura:

La lectura por medio del índice particular (del espacio de trabajo particular) no es problemática, pues las direcciones en disco a las que referencia son las originales.

La modificación de un bloque de un archivo requiere:

La modificación sobre la copia no afecta al bloque original.

Un tratamiento similar se da al agregado de bloques; los nuevos bloques se llaman bloques sombra (shadow blocks).

El proceso que ejecuta la transacción ve el archivo modificado pero los demás procesos ven el archivo original.

Si la transacción aborta (termina anormalmente):

Si la transacción se compromete (termina normalmente):


Inicio:   Fin:

Bitácora de Escritura Anticipada

Este método también se denomina lista de intenciones.

Los archivos realmente se modifican pero antes de cambiar cualquier bloque:

Si la transacción tiene éxito y se hace un compromiso: Si la transacción aborta: Por medio de la bitácora se puede:


Inicio:   Fin:

Protocolo de Compromiso de Dos Fases (Two - Phase Commit)

Uno de los procesos que intervienen funciona como el coordinador.

El coordinador escribe una entrada en la bitácora para indicar que inicia el protocolo.

El coordinador envía a cada uno de los procesos relacionados (subordinados) un mensaje para que estén preparados para el compromiso.

Cuando un subordinado recibe el mensaje:

Cuando el coordinador ha recibido todas las respuestas sabe si debe establecer el compromiso o abortar:


Inicio:   Fin:

Control de Concurrencia en el Modelo de Transacción

Los algoritmos de control de concurrencia son necesarios cuando se ejecutan varias transacciones de manera simultánea [25, Tanenbaum]:

Los principales algoritmos son:


Inicio:   Fin:

Cerradura (locking)

Cuando un proceso debe 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:

El manejador de cerraduras: El sistema de transacciones generalmente adquiere y libera las cerraduras sin acción por parte del programador.

Una mejora consiste en distinguir las cerraduras para lectura de las cerraduras para escritura.

Una cerradura para lectura no impide otras cerraduras para lectura:

Una cerradura para escritura sí impide otras cerraduras (de lectura o de escritura): El elemento por cerrar puede ser un archivo, un registro, un campo, etc. y lo relativo al tamaño del elemento por cerrar se llama la granularidad de la cerradura.

Mientras más fina sea la granularidad:

Generalmente se utiliza la cerradura de dos fases: Se deben evitar situaciones de aborto en cascada: Las cerraduras comunes y de dos fases pueden provocar bloqueos cuando dos procesos intentan adquirir la misma pareja de cerraduras pero en orden opuesto, por lo tanto se deben utilizar técnicas de prevención y de detección de bloqueos para superar el problema.

Inicio:   Fin:

Control Optimista de la Concurrencia

La idea es muy sencilla:

Se mantiene un registro de los archivos leídos o grabados.

En el momento del compromiso:

Las principales ventajas son: La principal desventaja es:


Inicio:   Fin:

Marcas de Tiempo

Se asocia a cada transacción una marca de tiempo al iniciar (begin_transaction).

Se garantiza que las marcas son únicas mediante el algoritmo de Lamport.

Cada archivo del sistema tiene asociadas una marca de tiempo para la lectura y otra para la escritura, que indican la última transacción comprometida que realizó la lectura o escritura.

Cuando un proceso intente acceder a un archivo, lo logrará si las marcas de tiempo de lectura y escritura son menores (más antiguas) que la marca de la transacción activa.

Si la marca de tiempo de la transacción activa es menor que la del archivo que intenta acceder:

En el método de las marcas no preocupa que las transacciones concurrentes utilicen los mismos archivos, pero sí importa que la transacción con el número menor esté en primer lugar.

Las marcas de tiempo tienen propiedades distintas a las de los bloqueos:

Las marcas de tiempo son libres de bloqueos, lo que es una gran ventaja.

Inicio:   Fin:

Resumen

Los diferentes esquemas ofrecen distintas ventajas pero el problema principal es la gran complejidad de su implantación.

Inicio:   Fin:

Bloqueos en Sistemas Distribuidos

Son peores que los bloqueos en sistemas monoprocesador [25, Tanenbaum]:

Son especialmente críticos en sistemas de bases de datos distribuidos.

Las estrategias usuales para el manejo de los bloqueos son:

El algoritmo del avestruz merece las mismas consideraciones que en el caso de mono-procesador.

En los sistemas distribuidos resulta muy difícil implantar algoritmos para evitar los bloqueos:

Las técnicas más aplicables para el análisis de los bloqueos en sistemas distribuidos son:


Inicio:   Fin:

Detección Distribuida de Bloqueos

Cuando se detecta un bloqueo en un S. O. convencional se resuelve eliminando uno o más procesos [25, Tanenbaum].

Cuando se detecta un bloqueo en un sistema basado en transacciones atómicas se resuelve abortando una o más transacciones:

Las consecuencias de la eliminación de un proceso son mucho menos severas si se utilizan las transacciones que en caso de que no se utilicen.

Inicio:   Fin:

Detección Centralizada de Bloqueos

Cada máquina mantiene la gráfica de recursos de sus propios procesos y recursos.

Un coordinador central mantiene la gráfica de recursos de todo el sistema, que es la unión de todas las gráficas individuales.

Cuando el coordinador detecta un ciclo elimina uno de los procesos para romper el bloqueo.

La información de control se debe transmitir explícitamente, existiendo las siguientes variantes:

La información de control incompleta o retrasada puede llevar a falsos bloqueos:


Inicio:   Fin:

Detección Distribuida de Bloqueos

Un algoritmo típico es el de Chandy-Misra-Haas.

Los procesos pueden solicitar varios recursos (por ejemplo cerraduras) al mismo tiempo, en vez de uno cada vez.

Se permiten las solicitudes simultáneas de varios procesos:

Si el proceso “0” se bloquea debido al proceso “1”: Una forma de romper el bloqueo es que el proceso que inició la exploración se comprometa a suicidarse y, si varios procesos se bloquean al mismo tiempo e inician exploraciones, todos ellos se suicidarán.

Una variante es eliminar solo al proceso del ciclo que tiene el número más alto.

Inicio:   Fin:

Prevención Distribuida de Bloqueos

La prevención consiste en el diseño cuidadoso del sistema para que los bloqueos sean imposibles estructuralmente [25, Tanenbaum].

Entre las distintas técnicas se incluye:

En un sistema distribuido con tiempo global y transacciones atómicas: La idea es que cuando un proceso está a punto de bloquearse en espera de un recurso que está utilizando otro proceso: Al seguir cualquier cadena de procesos en espera: Otra posibilidad es permitir la espera de procesos solo si el proceso que espera tiene una marca mayor (es más joven) que el otro proceso; las marcas aparecen en la cadena en forma descendente.

Es más sabio dar prioridad a los procesos más viejos:


Inicio:   Fin:
 
 

Para mayor información, seleccione una opción:

Número de visitas efectuadas desde el 17/12/2001: 
 
Estadísticas diarias desde el 10/07/2002:   Free counter and web stats  

Número de visitantes actuales disponible desde el 14/07/2002:

 

AddFreeStats.com Free Web Stats in real-time !  

 

 

Autor: lrmdavid@exa.unne.edu.ar

Ó FACENA - http://exa.unne.edu.ar

Servicios WEB: webmaster@exa.unne.edu.ar