Citation preview

INTERBLOQUEOS EN SISTEMAS DISTRIBUIDOS Arturo Díaz Pérez [email protected] Centro de Investigación y de Estudios Avanzados del IPN Departamento de Ingeniería Eléctrica Sección de Computación RESUMEN La presencia de interbloqueos (deadlocks) es una característica no deseable para todo sistema concurrente. En sistemas centralizados el manejo de interbloqueos es o muy costoso o extremadamente restrictivo. En sistemas distribuidos debemos agregar el costo que se paga por tener a los elementos de procesamiento físicamente separados. En este capítulo se revisará el manejo de interbloqueos en sistemas distribuidos. Se revisarán los conceptos básicos y diversos mecanismos propuestos para su detección. 1. Introducción Todos los sistemas concurrentes (paralelos o distribuidos) están propensos a presentar interbloqueos (deadlocks1) en su estado global. Los interbloqueos son factores no deseables ya que cuando se presentan, el único medio para restablecerse de ellos, es reiniciando una o varias tareas participantes en el interbloqueo. Esto implica un gasto de trabajo en actividades no útiles. Más aún, tener la posibilidad de detectar si el sistema se encuentra en un deadlock es con frecuencia complicado. Particularmente en el caso de los sistemas distribuidos en donde los participantes en el interbloqueo pueden estar físicamente separados y conectados solo mediante algún sistema de comunicaciones. Muchos sistemas han optado por garantizar que nunca se presentarán deadlocks dentro de ellos. Esto se hace imponiendo restricciones en cuanto a la forma y orden de solicitar recursos administrados por el sistema. Esta estrategia no parece particularmente útil en los sistemas distribuidos pues el ordenamiento de eventos en los sistemas distribuidos es un problema complicado y costoso. Así, en los sistemas distribuidos la estrategia más utilizada es el detectar los deadlocks cuando estos se presenten y dar un mecanismo de ruptura de un deadlock. Tres tipos de estrategia se han propuesto para el manejo de deadlocks: centralizadas, distribuidas y jerárquicas. En este capítulo se revisarán algunas de las técnicas más representativas para el manejo de los deadlocks en sistemas distribuidos. En la sección 2 se revisan las condiciones para la 1En

el resto de este capítulo se utilizará el término interbloqueo y deadlock indiscriminadamente para referirse a lo mismo.

presencia de deadlocks, así como una herramienta para describir las relaciones que conducen a un deadlock. En la sección 3 se presentan las tres grandes estrategias para manejar deadlocks en sistemas distribuidos. Algoritmos de tipo centralizado, distribuido y jerárquico se revisan en las secciones 4, 5 y 6, respectivamente. Finalmente, en la sección 7 se discuten algunos de los factores que están relacionados con la presencia y manejo de deadlocks. 2. Conceptos Generales Los deadlocks están relacionados tanto a aspectos de sincronización como de administración de recursos. Con respecto a los recursos estos pueden ser propios de la aplicación como por ejemplo: señales o mensajes de sincronización, o parte del sistema completo como por ejemplo: servidores de bases de datos, servidores de llaves, etc. Los recursos propios de la aplicación deben ser administrados por la aplicación misma. Sin embargo, los recursos del sistema deben ser administrados por el propio sistema. En lo siguiente nos referiremos a recursos que deben ser administrados por el sistema. Sin embargo, es conveniente enfatizar que existen recursos de la aplicaciones que también pueden conducir a deadlocks. Un deadlock es una situación en donde un grupo de procesos se bloquea permanente como resultado de que cada proceso ha obtenido un subconjunto de los recursos necesarios para su terminación y se encuentra esperando indefinidamente por lo la liberación de otros recursos que están siendo ocupados por otros procesos los cuales también esperan por recursos ocupados por el primer proceso, haciendo imposible que cualquiera de los procesos pueda proceder. Los deadlocks ocurren en ambientes concurrentes como resultado de una concesión, sin control, de los recursos del sistema que solicitan los procesos. 2.1 Condiciones para la presencia de un deadlock Las condiciones necesarias para la presencia de deadlocks son las siguientes: 1. Exclusión mutua. Los recursos compartidos se obtienen y se usan en una forma mutuamente exclusiva, esto es, a lo más un proceso a la vez. 2. Hold and wait. Cada proceso continúa manteniendo el control de un recurso mientras espera obtener otros recursos. 3. No preemption. Los recursos concedidos a un proceso pueden ser liberados al sistema únicamente como resultado de una acción voluntaria de tal proceso; el sistema no puede liberar los recursos por la fuerza.

4. Espera circular. Los procesos bloqueados en un deadlock están involucrados en una cadena circular tal que cada proceso mantiene uno o más recursos que están siendo solicitados por el siguiente proceso en la cadena. 2.2 La gráfica de estado del sistema La caracterización de deadlocks requiere una representación del estado las interacciones recurso-proceso. Este se modela por medio de una gráfica dirigido llamado la gráfica de asignación de recursos.

Figura 1. Gráfica del estado del sistema Un sistema se encuentra en un deadlock, si su gráfica de asignación de recursos contiene un ciclo dirigido en el cual cada arco de solicitud esta seguido por un arco de asignación. En sistemas de base de datos distribuidas la gráfica de asignación de recursos es conocida como la gráfica de transacciones en espera (TWF), en el cual, los vértices son transacciones y existe un arco de una transacción T1 a T2, si T1 está bloqueado y en espera de que T2 libere algún objeto de datos. 3. Estrategias para manejo de deadlocks en ambientes centralizados 3.1 Prevenir deadlocks La idea es prevenir que se presente alguna de las cuatro condiciones necesarias para la existencia de un deadlock. Las estrategias que se pueden seguir son: •

hacer que cada proceso adquiera de antemano los recursos que va a utilizar.



retirarle el uso de un recurso al conceder una nueva solicitud.

Las desventajas son: • • •

decrementa la concurrencia del sistema. los procesos puede entrar en un deadlock en la fase de adquisición. el uso de los recursos tiene un caracter dinámico que no se puede predecir fácilmente.

3.2 Evitación de deadlocks La idea es conceder un recurso no únicamente basándose en su disponibilidad, sino también, basándose en el hecho de si la concesión nos conduce a un estado global seguro. Un estado es seguro si existe una secuencia de solicitudes-asignamientos que permiten que los procesos que ya han adquirido recursos van a terminar. Los inconvenientes de esta estrategia es sistemas distribuidos son: • •



requiere una gran capacidad de almacenamiento para el estado global en cada parte del sistema distribuido. el proceso que verifica la seguridad del estado global debe trabajar en forma mutuamente exclusiva; esto limita severamente la concurrencia y “throughput” del sistema. la verificación de la seguridad del estado global es computacionalmente cara.

3.3 Detección de deadlocks La idea de la detección de deadlocks es conceder los recursos sujeto únicamente a su disponibilidad y verificar periódicamente si el sistema ha entrado o no a un deadlock. Cuando se detecta un deadlock se elige alguna estrategia para romperlo. Tiene las siguientes ventajas: •

una vez que un ciclo se ha formado en la gráfica del estado global, éste persiste hasta que es detectado y resuelto.



la detección de deadlocks puede proceder concurrentemente con las actividades normales del sistema.

Por las razones anteriores, los trabajos para el manejo de deadlocks en sistemas distribuidos se han enfocado fundamentalmente hacia la detección.

Los algoritmos de detección de deadlocks fundamentalmente incluyen dos actividades:

1. el mantenimiento de la gráfica de estados, y 2. la búsqueda de ciclos en la gráfica

3.4 Algoritmo para detección de deadlocks Sean ASIGNADOS y SOLICITADOS estructuras de datos para mantener la información sobre los recursos asignados y solicitados y aún no obtenidos por un proceso, respectivamente. Sea DISPONIBLES la estructura de datos en la cual se almacena la información sobre los recursos disponibles. 1. Identificar el estado del sistema. Actualizar la información de las estructuras, ASIGNADOS, SOLICITADOS y DISPONIBLES, de acuerdo con el estado del sistema. Poner a todos los procesos activos como no marcados. 2. Encontrar un proceso no marcado i, tal que, SOLICITADOSi T1 T3 -> T2

Tk -> Tk-1

Figura 8. Funcionamiento del algoritmo Menasce-Muntz.

Cuando T1 hace su solicitud y es bloqueada por Tk, se genera el par bloqueante (T1, Tk), lo cual general el par bloqueante (T1, Tk-1), y así sucesivamente, hasta general el par bloqueante (T1, T2). Dado que ya existía un arco (T2, T1), entonces se detecta un ciclo. 6 Algoritmos jerárquicos para detección de deadlocks 6.1 Algoritmo de Menasce y Muntz Todos los controladores de recursos se arreglan en una estructura de árbol. Los controladores en el nivel más bajo, llamados controladores hoja, manejan exclusivamente recursos; todos los demás, son responsables de detectar deadlocks. Un controlador hoja mantiene la parte de la gráfica global de transacciones en espera que concierne con el asignamiento de recursos controlados por él. Un controlador no hoja mantiene la parte de la gráfica global de transacciones en espera que se expande sobre todos sus descendientes y es responsable de detectar deadlocks que involucran únicamente a los recursos en las hojas. Un cambio en el estado global puede ocurrir debido a un asignamiento, liberación o espera por un recurso. El controlador correspondiente propaga el cambio hacia su padre, el cual hace los ajustes necesarios en su gráfica, detecta ciclos, y propaga los cambios hacia su padre, si es necesario.

Figura 9. Funcionamiento del algoritmo Menasce-Muntz jerárquico.

6.2. Algoritmo de Ho y Ramamoorthy

Figura 10. Funcionamiento del algoritmo Ho-Ramamoorthy. Los nodos del sistema distribuido se dividen en grupos, clusters. El algoritmo realiza los pasos siguientes: 1. Periódicamente se elige un nodo de control central (para todo el sistema). Este realiza las siguientes acciones: a) Elige dinámicamente un nodo de control para cada cluster. b) Envía mensajes a todos los nodos de control solicitándoles la información del estado de las transacciones entre clusters y las relaciones de en-espera-por dentro de cada cluster. c) Construye una gráfica de demanda para todo el sistema con la información recibida. 2. Cada vez que un nodo de control de un cluster recibe una solicitud para reportar el estado de las transacciones dentro del cluster, realiza las siguientes operaciones: a) Envía un mensaje a todos los nodos del cluster solicitándoles sus tablas de estado y de espera.

b) Construye una gráfica de demanda para el cluster utilizando únicamente transacciones dentro del cluster. c) Calcula la cerradura transitiva de la gráfica de demanda. Si existe un ciclo en el gráfica de demanda, el sistema está en un deadlock. d) Deriva las relaciones en-espera-por dentro del mismo cluster a partir de la cerradura transitiva del gráfica de demanda. e) Envía la información del estado de las transacciones que involucran a otro cluster al nodo de control central. 7. Factores relacionados con la detección de deadlocks 7.1 Resolución de deadlocks Un deadlock se resuelve abortando uno o más procesos (transacciones) involucrados en un ciclo y concediendo los recursos liberados a otros procesos en el ciclo. Para resolver eficientemente un deadlock se requiere conocer a todos los procesos en el ciclo y los recursos que controlan cada uno de ellos. En los algoritmos existen se presenta una de las siguientes condiciones: •

No se conocen a todos los procesos en el ciclo.



La detección del mismo ciclo puede ser hecha por más de un proceso. ¿Quién resuelve el deadlock?

7.2 Deadlocks falsos En ambientes donde un proceso puede simultáneamente esperar por recursos múltiples, la resolución del deadlock es aún más compleja debido a que un arco puede ser compartido por dos o más ciclos, y al borrar ese arco borrará esos deadlocks. Sin embargo, ya que la búsqueda de cada ciclo se realiza en forma independiente, la detección de deadlocks iniciada para algunos ciclos puede no darse cuenta que un arco ha sido borrado, resultando en la detección de deadlocks falsos. Detección de deadlocks involucra detectar una condición estática, mientras que la resolución de ellos es un proceso dinámico.

Figura 11. Detección de deadlocks falsos 7.3 Correctitud de los algoritmos Existe una escasez de métodos formales para probar la correctitud de los algoritmos para detectar deadlocks. La dificultad para probar la correctitud de un algoritmo se debe a varias razones: •

la gráfica de transacciones en espera y los ciclos de los deadlocks se forman en diversas maneras, haciendo difícil imaginar y estudiar exhaustivamente todas las situaciones concebibles.



los deadlocks son muy sensibles al tiempo en que se realizan las solicitudes.



en sistemas distribuidos, los retardos de los mensajes son impredecibles y no existe memoria global.

7.4 Probabilidad de los deadlocks La frecuencia con que ocurren los deadlocks es un factor crucial en el diseño de un sistema distribuido. Esto determina con qué periodicidad lanzar el algoritmo para detección de deadlocks. Las estrategias que se pueden utilizar son: 1. Periodos fijos. 2. Periodos de gracia. Cuando el tiempo que espera un proceso por un recurso excede un tiempo predefinido.

7.5 Eficiencia de los algoritmos Muchos autores han elegido el número de mensaje para detectar un deadlock como una medida de la eficiencia del algoritmo. Sin embargo, estrictamente no es una medida fiel ya que algunos algoritmos intercambian largos mensajes mientras otros intercambian mensajes cortos. Factores importantes a considerar para la evaluación de los algoritmos de detección de deadlocks son: • • • • •

el "overhead" de comunicaciones la persistencia del deadlock, el tiempo que transcurre desde que se presenta hasta que se detecta y se resuelve las necesidades de almacenamiento de cada algoritmo el tiempo de procesamiento que se requiere para detectar los ciclos el tiempo de procesamiento para resolver un deadlock

Figura 12. Tabla comparativa de algoritmos para detectar deadlocks. 8 Conclusiones Los deadlocks aparecen en cualquier tipo de sistema concurrente (paralelo o distribuido) provocados por factores de sincronización y administración de recursos. El desarrollador de

aplicaciones es responsable de tener en cuenta la presencia de deadlocks al administrar recursos propios de la aplicación. En contraste con la prevención de deadlocks, la técnica de detección y recuperación parece más adecuada para sistemas distribuidos. Sin embargo, debido a los retrasos de comunicación existe la posibilidad de detectar deadlocks falsos. Así que técnicas más formales se requieren para garantizar la no existencia de deadlocks. Para el caso de los sistemas distribuidos existen tres estrategias para detección de deadlocks: centralizadas, distribuidas y jerárquicas. Los factores que se utilizan para evaluar el rendimiento de los algoritmos propuestos son: tamaño y número de mensajes, y el tiempo de retraso que existe para que el algoritmo detecte un deadlock. 9 Bibliografia [Chandy 83] Chandy, K.M., Misra, J. and Haas, L.M. "Distributed Deadlock Detection," ACM Trans. on Computer Systems, May 1983, pp. 144-156. [Ho 82]

Ho, G.S. and Ramamoorthy, C. V. "Protocols for Deadlock Detection in Distributed Database Systems," IEEE Trans. Software Engineering, Nov. 1982, pp. 554-557.

[Isloor 80]

Isloor, S. S. and Marsland, T. A. "The Deadlock Problem: An overview," Computer, Sept. 1980, pp. 58-77/

[Menasce 79] Menasce, D. E. and Muntz, R. R. "Locking and Deadlock Detection in Distributed Database Systems," IEEE Trans. Software Engineering, May 1979, pp. 195-202. [Singhal 94]

Mukesh Singhal, "Deadlock Detection in Distributed Systems," in Reading in Distributed Computing Systems, Thomas L. Casavant and Mukesh Singhal eds. IEEE Computer Society Press, Los Alamitos, Calif. 1994.

10 Ejercicios 1. Considere un sistema que corre 5000 trabajos por mes y no tiene ninguna estrategia para prevenir o evitar deadlocks. Los deadlocks ocurren 2 veces por mes y requieren que un operador termine y reinicie 10 trabajos por deadlock. Cada trabajo cuesta 2 dólares de tiempo de CPU y los trabajos terminados en promedio se encuentran a la mitad de su camino cuando ellos son reiniciados. Un programador de sistemas ha estimado que con un algoritmo para evitar deadlocks se incrementaría el tiempo de ejecución por trabajo en promedio del 10%. Ya que la máquina tiene actualmente el 30% de su tiempo ocioso, los 5000 trabajos por mes aún pueden ejecutarse, aunque el tiempo de reciclaje se incrementa en promedio en 20%.

Basándose en los parámetros indicados indique cuantitiva y cualitativamente los argumentos a favor y en contra de la instalación del algoritmo para evitar deadlocks. 2. Considere un sistema distribuido que controla cuatro recursos del mismo tipo los cuales son compartidos por tres procesos. Cada proceso solicita un recurso a la vez y a lo más pide dos recursos. Demuestre que en este sistema nunca se pueden presentar deadlocks. 3. Suponga que en un sistema operativo distribuido existen 4 tipos de recursos: A, B, C y D y que se atienden a los procesos P, Q, R, S y T, los cuales declararon al inicio sus siguientes necesidades de recursos: A 0 1 2 0 0

P Q R S T

B 0 7 3 6 6

C 1 5 5 5 5

D 2 0 6 2 6

En un momento dado se detecta la siguiente situación: Asignados A 0 1 1 0 0

P Q R S T

B 0 0 3 6 0

C 1 0 5 3 1

D 2 0 4 2 4

Disponibles A 1

B 5

C 2

D 0

a) ¿Se encuentra el sistema en un estado seguro? Explique. b) Si el proceso Q solicita los siguientes recursos A = 0, B = 4. C = 2 y D = 0, ¿Se le pueden conceder inmediatamente? Explique. 4. Describa un escenario en el cual el algoritmo de dos fases de Ho y Ramammorthy para detectar deadlocks falla. 5. Desarrolle un programa para implementar el algoritmo jerárquico para detección de deadlocks de Menasce y Muntz.