Bloqueos en Sistemas Distribuidos
Son peores que los bloqueos en sistemas monoprocesado:
- 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:
- 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
Distribuida de Bloqueos
Cuando se detecta un bloqueo en un S. O. convencional se
resuelve eliminando uno o más procesos.
Cuando se detecta un bloqueo en un sistema basado en
transacciones atómicas se resuelve abortando una o más transacciones:
- El sistema
restaura el estado que tenía antes de iniciar la transacción.
- La
transacción puede volver a comenzar.
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.
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:
- Cada máquina
informa cada actualización al coordinador.
- Cada máquina
informa periódicamente las modificaciones desde la última actualización.
- El
coordinador requiere la información cuando la necesita.
La información de control incompleta o retrasada
puede llevar a falsos bloqueos:
- El
coordinador interpreta erróneamente que existe un bloqueo y elimina un
proceso.
- Una posible
solución es utilizar el algoritmo de Lamport para disponer de un tiempo
global.
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:
- Un proceso
puede esperar a uno o más recursos simultáneamente.
- Los recursos
que espera un proceso pueden ser locales o remotos (de otra
máquina).
Si el proceso “0” se bloquea debido al
proceso “1”:
- Se genera un mensaje
de exploración que se envía al proceso (o procesos) que detienen los
recursos necesarios.
- El mensaje
consta de tres números:
- El
proceso recién bloqueado, el proceso que envía el mensaje y el proceso al
cual se envía.
- Al llegar el
mensaje el receptor verifica si él mismo espera a algunos procesos, en
cuyo caso:
- El
mensaje se actualiza:
- Se
conserva el primer campo.
- Se
reemplaza el segundo por su propio número de proceso y el tercero por el
número del proceso al cual espera.
- El
mensaje se envía al proceso debido al cual se bloquea:
- Si se
bloquea debido a varios procesos les envía mensajes (diferentes) a todos
ellos.
- Si un mensaje
recorre todo el camino y regresa a su emisor original (el proceso
enlistado en el primer campo), entonces:
- Existe
un ciclo y el sistema está bloqueado.
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.
Prevención
Distribuida de Bloqueos
La prevención consiste en el diseño cuidadoso del sistema
para que los bloqueos sean imposibles estructuralmente.
Entre las distintas técnicas se incluye:
- Permitir a
los procesos que solo conserven un recurso a la vez.
- Exigir a los
procesos que soliciten todos sus recursos desde un principio.
- Hacer que
todos los procesos liberen todos sus recursos cuando soliciten uno nuevo.
En un sistema distribuido con tiempo global
y transacciones atómicas:
- Se puede
asociar a cada transacción una marca de tiempo global al
momento de su inicio.
- No pueden
haber parejas de transacciones con igual marca de tiempo asociada.
La idea es que cuando un proceso está a punto
de bloquearse en espera de un recurso que está utilizando otro proceso:
- Se verifica
cuál de ellos tiene la marca de tiempo mayor (es más joven).
- Se puede
permitir la espera solo si el proceso en estado de espera tiene una marca
inferior (más viejo) que el otro.
Al seguir cualquier cadena de procesos en
espera:
- Las marcas
aparecen en forma creciente.
- Los ciclos
son imposibles.
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:
- Se ha
invertido tiempo de proceso en ellos.
- Probablemente
conservan más recursos.