Tema 4: Sincronización en Sistemas Distribuidos

SINCRONIZACIÓN DE RELOJES

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

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 dei tipo de cristal, la foriina 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 a 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 intenrupción recibe el nombre de marca de reloj.

ALGORITMOS PARA LA SINCRONIZACIÓN DE RELOJES

• Algoritmo de Lamport

El algoritmo de la panadería toma su nombre de la costumbre de las panaderías y tiendas en general, donde las personas al entrar al local obtienen un número de turno (único) y lo utilizan para que el dependiente les vaya atendiendo en orden de llegada. El cliente obtiene su número de turno usando una cinta de papel que ofrece boletos con números consecutivos.

El dependiente sólo puede atender a una persona al mismo tiempo, lo que concuerda con el uso de un recurso de forma exclusiva: el recurso es el dependiente y la sección crítica de un cliente es lo que realiza mientras es atendido.

El sistema mantiene un número (variable global) que refleja el número de turno del cliente que se está atendiendo en el instante actual. Los clientes deben esperar en una cola hasta que llega su turno. Una vez que se acaba con un cliente, la variable global se incrementa en uno y el cliente que tenga un boleto con ese número pasa a ser atendido. Cuando termina una compra, el cliente se desprende de su boleto y se dedica a realizar cualquier otra actividad libremente (guardar el dinero en la billetera, retirarse, etc.), ya que no se encuentra más en su sección crítica. Si más tarde quiere volver a comprar, tendrá que obtener un nuevo número.

En el modelo algorítmico que se propone, cada cliente es un hilo, identificado con un número único i. Los hilos se deben coordinar para decidir en cada momento qué hilo tiene derecho a ejecutar su código de sección crítica.

En la vida real, el sistema de los boletos funciona perfectamente, pero en un sistema informático la obtención del boleto es problemática: varios hilos pueden obtener el mismo número de turno. En el algoritmo de Lamport se permite que varios hilos obtengan el mismo número. En este caso, se aplica un algoritmo de desempate, que garantiza que sólo un hilo entra en sección crítica. El desempate se realiza así: si dos o más hilos tienen el mismo número de turno, tiene más prioridad el hilo que tenga el identificador con un número más bajo. Como no puede haber dos hilos con el mismo identificador, nunca se da el caso de que dos hilos evalúen al mismo tiempo que tienen derecho a ejecutar su sección crítica.

• Algoritmo de Cristian

Es un método para la sincronización de relojes que se puede usar en muchos campos de la computación distribuida. El algoritmo es probabilístico, es decir sólo puede sincronizar si el RTT es bajo en comparación con la precisión deseada. También tiene problemas en funciones donde se usa un solo servidor. Tampoco es adecuado para numerosas aplicaciones distribuidas donde la redundancia sería importante.

ALGORITMO DE ELECCIÓN Y ACTUALIZACIÓN DE HORA

Son algoritmos que realizan elección de procesos para coordinar, iniciar y realizar secuencias que garantizan que al momento de iniciar una elección esta concluya con el acuerdo de todos los procesos con respecto a la identidad de nuevo coordinador.

USOS DE LOS RELOJES SINCRONIZADOS

• —Hasta hace poco, se dispone del hardware y software necesarios para la sincronización de relojes a gran escala (es decir, en todo Internet).
• —Todo esto ya lo estamos viendo con productos como relojes o cámaras que incorporan android.
• —Android es un sistema operativo móvil basado en Linux, que junto con aplicaciones middleware está enfocado para ser utilizado en dispositivos móviles como teléfonos inteligentes, y  otros dispositivos. 

—Un ejemplo claro es el reloj de Sony con Android que está completamente sincronizado con nuestro móvil. Cada cosa que ocurre en el móvil también aparece en el reloj.

EXCLUSIÓN MUTUA

La exclusión mutua no es mas que una serie de algoritmos que se utilizan en la programación concurrente para con esta programación poder evitar el ingreso a las secciones criticas por mas de un proceso simultaneo.

Algunos ejemplos de algoritmos clásicos de exclusión mutua son:

• El algoritmo de Dekker.
• El algoritmo de Peterson.

ALGORITMOS BASADOS EN  PASO DE MENSAJE

  Comparten un token único entre todos los nodos el cual permite que un nodo entre en la sección critica (SC) si posee al token, este utiliza números de secuencia en lugar de marcas de tiempo. Cada partición de un token contiene un numero de secuencias del resto de los nodos donde un nodo incrementa el contador de numero secuencia cada vez que realiza una petición para poseer a token.

ALGORITMOS NO BASADOS EN EL  PASO DE MENSAJE

BLOQUEOS EN SISTEMAS DISTRIBUIDOS

Son peores que los bloqueos en sistemas monoprocesador:

• Son más difíciles de evitar, prevenir, detectar y solucionar.
• Toda la información relevante está dispersa en muchas máquinas.

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

Las estrategias usuales para el manejo de los bloqueos son:

• Algoritmo del avestruz:
• Ignorar el problema.
• Detección:
• Permitir que ocurran los bloqueos, detectarlos e intentar recuperarse de ellos.
• Prevención:
• Hacer que los bloqueos sean imposibles desde el punto de vista estructural.
• Evitarlos:
• Evitar los bloqueos mediante la asignación cuidadosa de los recursos.

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:

• Se requiere saber de antemano la proporción de cada recurso que necesitará cada proceso.
• Es muy difícil disponer de esta información en forma práctica.

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

• Detección.
• Prevención.