16 Ago
Sistemas Distribuidos: Problemas de Sincronización y Exclusión Mutua
Problemas en Regiones Críticas
Los problemas relacionados con las regiones críticas, la exclusión mutua y la sincronización, que generalmente se resuelven en sistemas de una sola CPU con métodos como semáforos y monitores, presentan desafíos en sistemas distribuidos. Esto se debe a que:
- Se basan en la memoria compartida.
- No son directamente aplicables a sistemas distribuidos.
Propiedades de Sincronización de Relojes en Algoritmos Distribuidos
En sistemas distribuidos, la información relevante se distribuye entre varias máquinas. Los procesos toman decisiones basándose únicamente en la información disponible localmente. Es crucial evitar un único punto de fallo. Además, no existe un reloj común o una fuente precisa de tiempo global.
Relojes Lógicos vs. Relojes Físicos
Relojes Lógicos
Un reloj lógico es un contador de software que se incrementa monótonamente. Su valor no necesita estar relacionado con ningún reloj físico. Generalmente, se asocia un reloj lógico a cada proceso.
Relojes Físicos
Un reloj físico, como un cronómetro, se basa en un cristal de cuarzo que oscila a una frecuencia específica. Esta frecuencia depende de:
- La forma en que se corta el cristal.
- El tipo de cristal.
- La magnitud de la tensión aplicada.
A cada cristal se le asocian dos registros:
- Contador
- Mantenedor
Cada interrupción se denomina marca de reloj.
Importancia de la Sincronización
En una sola computadora, las pequeñas diferencias en el reloj no son cruciales porque:
- Todos los procesos de la máquina usan el mismo reloj y mantienen la consistencia interna.
- Lo importante son los tiempos relativos.
Sin embargo, en un sistema con varias computadoras, es imposible garantizar que los cristales de diferentes PCs oscilen a la misma frecuencia. Esto provoca una pérdida de sincronía en los relojes, resultando en valores distintos.
El Algoritmo de Lamport
Lamport demostró que la sincronización de relojes es posible y presentó un algoritmo para lograrlo. Señaló que la sincronización no tiene que ser absoluta. Para ciertos algoritmos, lo importante es la consistencia interna de los relojes, no su cercanía al tiempo real (oficial). Estos relojes se denominan relojes lógicos.
Ocurre Antes De
Lamport utiliza la relación «ocurre antes de»:
- Si un evento C sale en el tiempo 60, debe llegar en el tiempo 61 o posterior.
- Cada mensaje lleva consigo el tiempo de envío, según el reloj del emisor.
- Cuando un mensaje llega y el reloj del receptor muestra un valor anterior al tiempo de envío, el receptor adelanta su reloj una unidad más que el tiempo de envío.
Limitaciones del Algoritmo de Lamport
Aunque el algoritmo de Lamport proporciona un orden de eventos sin ambigüedades, los valores de tiempo asignados a los eventos no necesariamente se acercan a los tiempos reales en los que ocurren.
Exclusión Mutua (Mutex)
La exclusión mutua (mutex) se utiliza en programación concurrente para evitar el acceso simultáneo a recursos comunes, como variables globales, por parte de fragmentos de código conocidos como secciones críticas.
Técnicas para la Exclusión Mutua
Una técnica común para lograr la exclusión mutua es inhabilitar las interrupciones durante la ejecución de la sección crítica, evitando así la corrupción de la estructura compartida.
Algoritmos de Sincronización de Relojes
Algoritmo de Cristian
El algoritmo de Cristian es un método para la sincronización de relojes que se puede usar en diversos campos de la computación distribuida. Su principal desventaja es que todo el sistema depende de un servidor de tiempo, lo cual no es ideal en un sistema distribuido fiable.
Algoritmo de Berkeley
El algoritmo de Berkeley utiliza la hora de todos los ordenadores para calcular una media, que se reenvía para que cada equipo actualice su propia hora, ya sea ralentizando el reloj o adoptando la nueva hora.
Algoritmos de Exclusión Mutua
Algoritmo Centralizado
La forma más directa de lograr la exclusión mutua en un sistema distribuido es similar a la de un sistema monoprocesador. Sin embargo, el inconveniente es que el coordinador puede convertirse en un cuello de botella y, si falla, puede bloquear los procesos.
Algoritmo con Promedio
Este algoritmo no tiene un servidor que controle, centralice y mantenga la sincronización del tiempo en el sistema. Cada máquina informa su hora local con cada mensaje que envía.
Algoritmo Distribuido
En este algoritmo, el proceso que desea entrar en su sección crítica envía un mensaje a todos los procesos y solo entra si recibe una confirmación de todos ellos.
Pasos del Algoritmo Distribuido
- El proceso construye un mensaje con el nombre de la región crítica, su número de proceso y la hora actual.
- Envía el mensaje a todos los procesos, incluyéndose a sí mismo.
- Si el receptor no está en la región crítica ni desea entrar, envía un mensaje de confirmación al emisor.
- Si el receptor ya está en la región crítica, no responde y encola la solicitud.
- El proceso espera hasta recibir todos los permisos para entrar en la región crítica.
- Al salir de la región crítica, envía mensajes de confirmación a todos los procesos en su cola y la vacía.
Este algoritmo garantiza la exclusión mutua sin bloqueos ni inanición.
Transacciones Atómicas
Las técnicas de sincronización vistas anteriormente son de bajo nivel. El programador debe lidiar directamente con la exclusión mutua, el manejo de regiones críticas, la prevención de bloqueos y la recuperación de fallos.
Cluster
Un cluster es un grupo de múltiples ordenadores interconectados mediante una red de alta velocidad, de forma que el conjunto se percibe como un único ordenador, más potente que los equipos de escritorio convencionales.
Deja un comentario