Resumen Breve
Este video explica los conceptos de deadlock y starvation en sistemas operativos, proporcionando ejemplos y estrategias para prevenir, evitar y detectar deadlocks. Se discuten las condiciones necesarias para que ocurra un deadlock, así como diferentes enfoques para lidiar con ellos, incluyendo la prevención mediante la asignación anticipada de recursos, la evitación a través del algoritmo del banquero, y la detección con la posterior recuperación.
- Deadlock ocurre cuando dos o más procesos están bloqueados indefinidamente, esperando por recursos que otros procesos tienen.
- Starvation es cuando un proceso no puede acceder a los recursos que necesita debido a la continua asignación de esos recursos a otros procesos.
- Hay tres estrategias principales para lidiar con deadlocks: prevención, evitación y detección.
Introducción al Deadlock y Starvation
El video introduce los temas de deadlock y starvation, explicando que se profundizará en estos escenarios y se explorarán medidas y mecanismos para abordar los problemas de concurrencia que estos generan. El objetivo es entender cómo los procesos pueden quedar bloqueados esperando recursos y cómo evitar o resolver estas situaciones.
¿Qué es un Deadlock?
Un deadlock ocurre cuando un proceso necesita un recurso que otro proceso tiene asignado, y este último a su vez necesita un recurso que el primero tiene, creando un ciclo de espera mutua. Ninguno de los procesos puede liberar sus recursos, resultando en un ciclo muerto donde ningún proceso puede avanzar. Se ilustra con el ejemplo de una intersección de tráfico donde los carros se bloquean mutuamente.
Visualización de Deadlocks con Diagramas
Para visualizar y evitar deadlocks, se pueden usar diagramas de procesos (JPDs) que muestran cómo los procesos se relacionan y solicitan recursos. Estos diagramas ayudan a identificar posibles escenarios de deadlock y a tomar medidas preventivas. Se explica cómo las rutas en estos diagramas pueden ayudar a evitar situaciones donde múltiples procesos compiten por los mismos recursos simultáneamente.
Tipos de Recursos: Reutilizables vs. Consumibles
Existen dos tipos de recursos que los procesos pueden solicitar: reutilizables y consumibles. Los recursos reutilizables, como la memoria o los dispositivos de entrada/salida, pueden ser usados repetidamente. Los recursos consumibles, como los mensajes o las señales, se "gastan" después de ser utilizados. Se dan ejemplos de cómo cada tipo de recurso puede llevar a un deadlock.
Ejemplo de Deadlock con Recursos Reutilizables
Se presenta un ejemplo de deadlock utilizando recursos reutilizables, específicamente la memoria. Dos procesos solicitan memoria en un sistema con capacidad limitada. Si ambos procesos solicitan una cantidad de memoria que excede la capacidad total y se esperan mutuamente para liberar memoria, se produce un deadlock.
Ejemplo de Deadlock con Recursos Consumibles
Se explica un ejemplo de deadlock con recursos consumibles, como mensajes entre procesos. Dos procesos necesitan información del otro para continuar, pero ambos están esperando un mensaje del otro, creando un ciclo de espera que impide que ambos avancen.
Gráficos de Asignación de Recursos
Se introducen los gráficos de asignación de recursos, donde los procesos se representan con círculos y los recursos con rectángulos. Las flechas indican si un proceso requiere un recurso o si un recurso está asignado a un proceso. Se muestra cómo una espera circular en estos gráficos indica un deadlock.
Espera Circular y Soluciones
Se explica la condición de espera circular, donde cada proceso en un ciclo está esperando un recurso que otro proceso en el ciclo tiene asignado. Una solución simple es agregar más instancias del recurso para romper el ciclo de espera. Se enfatiza que la definición de deadlock involucra dos o más procesos en espera circular.
Condiciones Necesarias para un Deadlock
Para que ocurra un deadlock, deben cumplirse cuatro condiciones: exclusión mutua, mantener y esperar, no apropiación y espera circular. Se explica cada una de estas condiciones y cómo su eliminación puede prevenir el deadlock.
Estrategias para Lidar con Deadlocks
Se describen tres enfoques para lidiar con deadlocks: prevención (asegurar que nunca ocurran), evitación (permitir que el sistema funcione pero tomar decisiones para evitar deadlocks) y detección (permitir que ocurran y luego recuperarse). Cada enfoque tiene sus propias técnicas y compromisos.
Prevención de la Exclusión Mutua
Para prevenir la exclusión mutua, se pueden emplear técnicas como solicitar todos los recursos al inicio del programa o liberar todos los recursos si un proceso se bloquea. Estas estrategias son estrictas y buscan evitar cualquier posibilidad de deadlock.
Prevención de la No Apropiación
Si se permite la capacidad de apropiación del sistema operativo, se pueden liberar los recursos originales de un proceso, guardando su estado en un "snapshot" y permitiendo que otros procesos utilicen los recursos. Esto requiere que el sistema operativo tenga la capacidad de apropiarse de los recursos.
Prevención de la Espera Circular
Para prevenir la espera circular, se puede definir un orden total de los tipos de recursos y hacer que los procesos los soliciten en orden ascendente. Esto evita que se formen ciclos de espera. Esta técnica es más adecuada para procesos batch donde se conoce el uso de los recursos de antemano.
Evitación de Deadlocks
La evitación de deadlocks implica tomar decisiones basadas en el conocimiento del futuro para evitar que ocurran. Esto se puede hacer denegando la asignación de un recurso o evitando que un proceso inicie si se prevé que causará un deadlock.
Algoritmo del Banquero
El algoritmo del banquero es una técnica para evitar deadlocks que utiliza matrices y vectores para determinar si un estado es seguro. Se analiza la matriz de solicitud (claim matrix), la matriz de asignación, y los vectores de recursos disponibles y totales para encontrar una ruta segura de asignación de recursos.
Ventajas y Limitaciones de la Evitación
La evitación de deadlocks no requiere la capacidad de apropiación del sistema operativo y es menos restrictiva que la prevención. Sin embargo, requiere monitorear matrices y tener una cantidad fija de recursos, lo que puede ser costoso y complicado.
Detección de Deadlocks
La detección de deadlocks implica permitir que ocurran y luego identificarlos. Esto requiere preguntar constantemente si hay deadlocks y tomar medidas para resolverlos. Los algoritmos de detección utilizan matrices similares a las del algoritmo del banquero.
Algoritmos para la Detección de Deadlocks
Los algoritmos de detección de deadlocks utilizan matrices de peticiones (Q), matrices de asignación y vectores de recursos reales y disponibles. A diferencia de la evitación, no se busca una ruta segura, sino identificar si existe un ciclo de espera que cause un deadlock.
Estrategias de Recuperación
Una vez detectado un deadlock, se pueden usar estrategias de recuperación como abortar todos los procesos o realizar una terminación selectiva de procesos para liberar los recursos y romper el ciclo de espera. Se pueden crear puntos de recuperación para restaurar los procesos a un estado anterior.
Resumen Comparativo de Enfoques
Se presenta un resumen comparativo de los tres enfoques: prevención, evitación y detección. La prevención es la más conservadora e ineficiente, la evitación requiere conocimiento futuro de los recursos, y la detección es la más liberal pero requiere monitoreo constante y acciones de recuperación.
El Problema de los Filósofos Cenando
Se presenta el problema clásico de los filósofos cenando, donde cinco filósofos necesitan dos palillos chinos para comer, pero solo hay cinco palillos en total. Se discuten soluciones como tener un mesero que arbitre quién come o asignar un número a cada palillo y que los filósofos sigan una regla para evitar el deadlock.
