Sincronización en un Sistema Distribuido

Algoritmos para la Sincronización de Relojes

La sincronización de relojes en un sistema distribuido consiste en garantizar que los procesos se ejecuten en forma cronológica y a la misma vez respetar el orden de los eventos dentro del sistema. Para lograr esto existen varios métodos o algoritmos que se programan dentro del sistema operativo, entre los cuales tenemos:

1. Algoritmo de Cristian

Este algoritmo está basado en el uso del tiempo coordenado universal (siglas en inglés, UTC), el cual es recibido por un equipo dentro del sistema distribuido. Este equipo, denominado receptor de UTC, recibe a su vez solicitudes periódicas del tiempo del resto de máquinas del sistema a cada uno de los cuales les envía una respuesta en el menor plazo posible informando el tiempo UTC solicitado, con lo cual todas las máquinas del sistema actualicen su hora y se mantenga así sincronizado todo el sistema. El receptor de UTC recibe el tiempo a través de diversos medios disponibles, entre los cuales se menciona las ondas de radio, Internet, entre otros.

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

* El tiempo del receptor UTC no puede ser menor que el tiempo de la máquina que le solicitó el tiempo.

* El servidor de UTC debe procesar las solicitudes de tiempo con el concepto de interrupciones, lo cual incide en el tiempo de atención.

* El intervalo de transmisión de la solicitud y su respuesta debe ser tomado en cuenta para la sincronización. El tiempo de propagación se suma al tiempo del servidor para sincronizar al emisor cuando éste recibe la respuesta.

2. Algoritmo de Berkeley

Un sistema distribuido basado en el algoritmo de Berkeley no dispone del tiempo coordenado universal (UTC); en lugar de ello, el sistema maneja su propia hora. Para realizar la sincronización del tiempo en el sistema, también existe un servidor de tiempo que, a diferencia del algoritmo de Cristian, se comporta de manera activa. Este servidor realiza un muestreo periódico del tiempo que poseen algunas de las máquinas del sistema, con lo cual calcula un tiempo promedio, el cual es enviado a todas las máquinas del sistema a fin de sincronizarlo.

2. Distribuido

Este algoritmo fue desarrollado a fin de eliminar el problema latente en el algoritmo centralizado. Por lo tanto, su enfoque está basado en no disponer de un único coordinador para el control de acceso a las secciones críticas del sistema distribuido.

En este sentido, cada proceso que requiere acceso a una sección crítica, envía su solicitud a todos los procesos existentes en el sistema, identificándose así mismo y a la sección crítica que desea acceder. Cada proceso receptor envía su respuesta al proceso solicitante, indicando una de las siguientes posibles respuestas:

o Sección crítica no en uso por el proceso receptor. Mensaje de respuesta: OK.

o Sección crítica en uso por el proceso receptor. Mensaje de respuesta: no aplica, coloca al proceso emisor en cola de espera.

o Sección crítica no en uso pero solicitada por el proceso receptor.

+ Mensaje de respuesta: OK, si la solicitud es anterior a la del receptor.

+ Mensaje de respuesta: No aplica, si la solicitud es posterior a la del receptor, coloca al proceso de emisor en cola de espera.

Sin embargo, este algoritmo también contiene un problema, consistente en que si un proceso presenta una falla no podrá enviar su respuesta ante la solicitud de un proceso emisor, por lo cual esto será interpretado como una negación de acceso, bloqueando a todos los procesos que soliciten acceso a cualquier sección crítica.

1. De Anillo de Fichas (Token Ring)

Este algoritmo establece un anillo lógico de procesos, controlado por software, a través del cual se hace circular una ficha o testigo (token) entre cada proceso. Cuando un proceso recibe la ficha, puede entrar a una sección crítica si lo requiere, procesar todas sus tareas, abandonar la sección crítica y entregar la ficha al próximo proceso del anillo. Este proceso se repite continuamente en el anillo de procesos. Cuando un proceso recibe la ficha y no requiere entrar a una sección crítica, pasa la ficha inmediatamente al siguiente proceso.

Este algoritmo contiene una debilidad, asociada a la posible pérdida de la ficha de control para el acceso a las secciones críticas. Si esto ocurre, los procesos del sistema asumirán que la ficha está en uso por algún proceso que se encuentra en la sección crítica.

2. De Elección

Estos algoritmos están diseñados para elegir un proceso coordinador. En los mismos, se garantiza que una vez realizada la elección del proceso coordinador, la misma concluya con el acuerdo de todos los procesos el sistema en la elección de un nuevo coordinador.

3. Del Grandulón (García Molina)

Este algoritmo se inicia cuando un proceso cualquiera determina que no hay respuesta a las solicitudes hechas al proceso coordinador. En este momento, este proceso envía a todos los procesos mayores que él un mensaje de elección del nuevo coordinador, lo cual puede conllevar a los siguientes escenarios:

o Un proceso, con un número mayor que el proceso emisor del mensaje, responda OK, con lo cual queda elegido como coordinador del sistema.

o Ningún proceso responde el mensaje de elección, con lo cual el proceso emisor queda electo como proceso coordinador.

1. De Anillo

Este algoritmo opera de manera similar al algoritmo del Grandulón, con la diferencia que en este método se presenta las siguientes variantes:

El mensaje de elección se hace circular a todos los procesos del sistema, y no solo a los procesos mayores que el emisor.

Cada proceso inscribe en el mensaje su identificación.

Una vez que el mensaje completa el anillo y regresa a proceso emisor, quien establece como nuevo coordinador al proceso con el número mayor.

Se hace circular a través del anillo un nuevo mensaje indicando quién es el coordinador del sistema.

1. Transacciones Atómicas

Es un método de sincronización a alto nivel, que a diferencia de los métodos revisados hasta el momento, no ocupa al programador en los aspectos de exclusión mutua, prevención de bloqueos y recuperación ante fallos. Por el contrario, este método orienta el esfuerzo del programador a los verdaderos problemas y esencia de la sincronización de sistemas distribuidos.

El concepto de transacciones atómicas consiste en garantizar que todos los procesos que conforman una transacción deben ejecutarse en forma completa y satisfactoria. De producirse falla en alguno de los procesos, toda la transacción falla, revirtiéndose la misma y procediéndose a su reinicio.