Apuntes_Leccion4_Deadlock.pdf

CE4303 – Principios de Sistemas Operativos Deadlock PROFESOR: ING. LUIS BARBOZA ARTAVIA Agenda • Introducción. • Definición. • Detección de un deadlock. • Evasión de un deadlock. • Prevención de un deadlock. Introducción • ¿Cómo logramos la concurrencia? • ¿Qué podemos asegurar del paralelism...

CE4303 – Principios de Sistemas Operativos Deadlock PROFESOR: ING. LUIS BARBOZA ARTAVIA Agenda • Introducción. • Definición. • Detección de un deadlock. • Evasión de un deadlock. • Prevención de un deadlock. Introducción • ¿Cómo logramos la concurrencia? • ¿Qué podemos asegurar del paralelismo de procesos? • ¿Cómo ayudan los semáforos? Introducción • ¿Cuántos recursos tenemos en la computadora? • Si damos un mismo recurso va a provocar desórdenes. • Para solucionar esta situación, el SO da permiso de acceso exclusivo a ciertos recursos. Introducción • Hay aplicaciones que requieren acceso exclusivo a más de un recurso a la vez. • Queremos escanear un documento y guardarlo en un CD. • Proceso A pide el escáner y el B el grabador. • Proceso A requiere el grabador, pero B lo tiene. • Proceso B no devuelve el grabador hasta tener el escáner. • Situación conocida como deadlock. Introducción Introducción • Puede suceder de forma local o en red. • Ejemplo: bases de datos • Sucede en recursos de software o hardware. Introducción Introducción Recursos • Algo que puede ser adquirido, utilizado y devuelto en el tiempo. • Tipos: • Apropiativo. • No apropiativo. Recursos apropiativos • Puede ser quitado al proceso que lo tiene como dueño y no tiene efecto dañino para el sistema. • Ejemplo: procesador. Proceso A Proceso B Recursos no apropiativos • Recurso que NO puede ser quitado de su dueño porque puede provocar fallos en el sistema. • Ejemplo: impresora, disco. Recursos • Un recurso es apropiativo dependiendo del contexto. • Los deadlocks involucran recursos no apropiativos. • Deadlocks con recursos apropiativos son más sencillos de manejar. Secuencia para utilizar un recurso 1. Solicitar el recurso. 2. Utilizar el recurso. 3. Liberar el recurso. • Si el recurso no está disponible, es forzado a esperar. • Esta implementación varía según el SO. Deadlock • Conjunto de procesos están con deadlock si cada proceso en el grupo está esperando por un evento que sólo otro proceso en el grupo puede causarlo. • Todos los procesos están en espera, por lo que ninguno va a poder causar un evento para despertar a otro miembro del grupo y todos los procesos estarán esperando para siempre. • Ningún proceso puede correr, liberar un recurso y ser despertado. Adquisición de recursos • Ceder el control a usuario para que se encargue del control del mismo. • Dejar esta tarea al sistema operativo sería ineficiente. ¿Por qué? • Entonces, ¿Cómo puede controlar el acceso un programador a los recursos y con ello adquirirlos? Adquisición de recursos • Dependiendo del tipo queda para el proceso de usuario. • Se pueden utilizar semáforos. Condiciones Coffman Las siguientes condiciones son necesarias para un deadlock: • Exclusión mutua. • Contención y espera. • No apropiativa. • Espera circular. Condiciones Coffman Las siguientes condiciones son necesarias para un deadlock: • Exclusión mutua: cada recurso o es asignado a exactamente un proceso o está disponible. • Contención y espera. • No apropiativa. • Espera circular. Condiciones Coffman Las siguientes condiciones son necesarias para un deadlock: • Exclusión mutua. • Contención y espera: procesos que actualmente contienen recursos que fueron otorgados anteriormente pueden solicitar nuevos recursos. • No apropiativa. • Espera circular. Condiciones Coffman Las siguientes condiciones son necesarias para un deadlock: • Exclusión mutua. • Contención y espera. • No apropiativa: recursos que antes fueron otorgados no pueden ser quitados a la fuerza de otro proceso. Deben ser liberados por el proceso. • Espera circular. Condiciones Coffman Las siguientes condiciones son necesarias para un deadlock: • Exclusión mutua. • Contención y espera. • No apropiativa. • Espera circular: debe existir una lista circular de dos o más procesos. Cada uno está en espera por un recurso que lo tiene el siguiente de la cadena. Modelado de deadlock • Holt propone utilizar grafos. • Recurso R es asignado al proceso A. • Proceso B está a la espera del recurso S. ¿Por qué sucede deadlock? ¿Cuáles son las condiciones de Coffman? Lidiando con deadlocks • Ignorar el problema. • Detección y recuperación. • Evitarlos de manera dinámica. • Prevención. Algoritmo del avestruz • Metemos la cabeza en la arena y pretendemos que no hay problema. • Matemáticos vs Ingenieros. Detección y recuperación • Deja que ocurra, trata de detectarlo cuando ocurre y toma acción para recuperarse. • Detección para un tipo de recurso o varios tipos. Detección con un tipo • Se construye un grafo con los recursos. • Si hay más de un ciclo es porque hay un deadlock. • Cualquier proceso dentro del ciclo está con deadlock. Detección con un tipo 1. Proceso A tiene R pero quiere S. 2. Proceso B no tiene nada pero quiere T. 3. Proceso C no tiene nada, pero quiere S. 4. Proceso D tiene U y quiere S y T. 5. Proceso E tiene T y quiere V. 6. Proceso F tiene W y quiere S. 7. Proceso G tiene V y quiere U. Detección con múltiples tipos • Algoritmo basado en matrices para detectar deadlock en n procesos. • Vector recursos existentes 𝐸. • Vector de recursos disponibles 𝐴. • Matriz de asignación actual 𝐶. • Matriz de solicitudes 𝑅. Detección con múltiples tipos Detección con múltiples tipos Detección con múltiples tipos • Este algoritmo detecta deadlocks (solicitudes adelantadas estáticas). • Revisar cada vez que una solicitud es hecha (buscando detectar lo más pronto posible). • Es caro en uso. • Se puede esperar a que el uso de CPU baje sobre algún medidor. Referencias • Tanenbaum, A. and Bos, H., 2015. Modern Operating Systems. 4th ed. Pearson. • Stallings, W., 2012. Operating systems: internals and design principles. Boston: Prentice Hall. CE4303 – Principios de Sistemas Operativos Deadlock PROFESOR: ING. LUIS BARBOZA ARTAVIA