-
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 metodos o algoritmos que
se programan dentro del sistema
operativo, entre los cuales tenemos:
Este algoritmo está basado en el uso del tiempo
coordenado universal (siglas en ingles 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 maquinas 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 atencion.
- 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.
Algoritmo de Cristian
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 periodico 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.
Algoritmo con Promedio
Este algoritmo no dispone de un servidor que controle,
centralice y mantenga la sincronización del tiempo en el sistema. A diferencia
de ello, cada máquina del sistema informa su hora local con cada mensaje que
requiera enviar a otra máquina o maquinas del sistema. A partir de ese momento,
cada máquina inicializa localmente un cronómetro, cuya duración es de intervalo
y longitud fija. A partir de ese momento, cada máquina promedia su hora local
con el uso de las horas que le informan el resto de las máquinas que
interactúan con ella.
Algoritmos para la Exclusión Mutua
Estos algoritmos están definidos para asegurar el
cumplimiento de exclusión mutua entre procesos que requieren acceder a una
región crítica del sistema.
Este algoritmo simula la filosofía de operación de
exclusión mutua utilizada en sistemas monoprocesadores. Para ello, existe una
máquina en el sistema distribuido que se encarga de controlar el acceso a las
diferentes secciones críticas, la cual es denominada coordinador. Cada proceso
del sistema que requiera acceso a una sección crítica, debe solicitar acceso al
coordinador, el cual lo otorgará en caso que la sección crítica esté
disponible; caso contrario, colocará en una cola de espera al proceso
solicitante. Cuando un proceso que recibió acceso a la sección crítica culmina
su tarea, informa por igual al coordinador a fin de que éste pueda otorgar
acceso a un próximo proceso solicitante o que se encuentre en cola de espera.
Este algoritmo presenta una gran limitante, consistente en que el coordinador
representa un único punto de control para el acceso a las diferentes secciones
críticas del sistema distribuido, lo cual se convierte en un cuello de botella
que puede afectar la eficiencia de los procesos que se ejecutan en el sistema.
Igualmente, cualquier falla que presente el coordinador ocasionará la
paralización de los procesos.
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:
- Sección crítica no en uso por el proceso receptor. Mensaje de respuesta: OK.
- Sección crítica en uso por el proceso receptor. Mensaje de respuesta: no aplica, coloca al proceso emisor en cola de espera.
- 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.
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.
De Anillo
Este algoritmo opera de manera
similar al algoritmo del Grandulón, con la diferencia que en este metodos 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.
Transacciones Atómicas
Es un método de sincronización a alto nivel, que a
diferencia de los metodos 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.
No hay comentarios:
Publicar un comentario