INTERBLOQUEO
(SISTEMA OPERATIVO)
En sistemas operativos, el bloqueo mutuo
(también conocido como interbloqueo, traba mortal, deadlock, abrazo mortal) es el bloqueo
permanente de un conjunto de procesos o hilos de
ejecución en un sistema concurrente que compit
en por recursos
del sistema o bien se comunican entre ellos. A diferencia de otros problemas de
concurrencia de procesos, no existe una solución general para los
interbloqueos.
Todos los interbloqueos surgen de necesidades que no pueden ser satisfechas, por parte de dos o más procesos. En la vida real, un ejemplo puede ser el de dos niños que intentan jugar al arco y flecha, uno toma el arco, el otro la flecha. Ninguno puede jugar hasta que alguno libere lo que tomó.
En el siguiente ejemplo, dos procesos compiten por dos recursos que necesitan para funcionar, que sólo pueden ser utilizados por un proceso a la vez. El primer proceso obtiene el permiso de utilizar uno de los recursos (adquiere el lock sobre ese recurso). El segundo proceso toma el lock del otro recurso, y luego intenta utilizar el recurso ya utilizado por el primer proceso, por lo tanto queda en espera. Cuando el primer proceso a su vez intenta utilizar el otro recurso, se produce un interbloqueo, donde los dos procesos esperan la liberación del recurso que utiliza el otro proceso.
Todos los interbloqueos surgen de necesidades que no pueden ser satisfechas, por parte de dos o más procesos. En la vida real, un ejemplo puede ser el de dos niños que intentan jugar al arco y flecha, uno toma el arco, el otro la flecha. Ninguno puede jugar hasta que alguno libere lo que tomó.
En el siguiente ejemplo, dos procesos compiten por dos recursos que necesitan para funcionar, que sólo pueden ser utilizados por un proceso a la vez. El primer proceso obtiene el permiso de utilizar uno de los recursos (adquiere el lock sobre ese recurso). El segundo proceso toma el lock del otro recurso, y luego intenta utilizar el recurso ya utilizado por el primer proceso, por lo tanto queda en espera. Cuando el primer proceso a su vez intenta utilizar el otro recurso, se produce un interbloqueo, donde los dos procesos esperan la liberación del recurso que utiliza el otro proceso.
Interbloqueo
Se dice que dos o más procesos están bloqueados, cuando están
suspendidos en espera de un evento que sólo puede ser activado por uno de los procesos
bloqueados, y por lo tanto dicho evento nunca sucederá
Se dice que uno o más
procesos están en postergación indefinida cuando la política de planificación
del sistema permite que un proceso quede en espera de un evento por un tiempo
indefinido. Esto puede suceder, por ejemplo, cuando la asignación de recursos
se realiza por prioridad. De este modo un proceso de baja prioridad estará
suspendido mientras existan otros procesos de mayor prioridad.
Envejecimiento: aumentar la prioridad de los procesos conforme pasa el tiempo
iberación del recurso que utiliza el otro proceso.
Envejecimiento: aumentar la prioridad de los procesos conforme pasa el tiempo
iberación del recurso que utiliza el otro proceso.
Clasificación
de recursos
Para el estudio del interbloqueo, los recursos se pueden clasificar en:
· Compartido/exclusivos:
Se dice que un recursos es compartido si puede ser utilizado por más de un
proceso al mismo tiempo. Son exclusivos los que pueden ser utilizados sólo por
un proceso a la vez
· Apropiativos/inapropiativos:
Son apropiativos los recursos asignados a un proceso, que pueden ser desasignados
del proceso, por al sistema para asignarlos a otro proceso.
Condiciones
necesarias para el interbloqueo
Coffman, Elphuck y Shoshani, establecieron cuatro condiciones, necesarias y suficientes, para que se dé un interbloqueo:
Exclusión mutua
Si dos procesos solicitan un recurso exclusivo, uno de los dos quedará
suspendido hasta que el favorecido libere el recurso.
Contención
o retención y espera
Si un proceso necesita más de un recurso para realizar su trabajo,
conservará en su poder los recursos exclusivos ya asignados, mientras espera
por otro recurso adicional.
Inapropiatividad
Los recursos asignados a un proceso, sólo pueden ser liberados por el
proceso mismo y no pueden ser desasignados por el sistema, cuando otro proceso
los necesite.
Espera
circular
Dependencia: Si un proceso P1 está suspendido en
espera de un recurso exclusivo que está asignado a otro proceso P2, entonces
decimos que P1 depende de P2 (P1 <= P2).
Espera circular: Existe una cadena circular de procesos en espera de un recurso, si existe una cadena de dependencias entre procesos de la forma P1 <= P2 <= P3 <= ... <= Pn <= P1
Ejemplos:
Asignación de recursos sin ciclos
Espera circular: Existe una cadena circular de procesos en espera de un recurso, si existe una cadena de dependencias entre procesos de la forma P1 <= P2 <= P3 <= ... <= Pn <= P1
Ejemplos:
Asignación de recursos sin ciclos
Formas de enfrentar los interbloqueos
Existen varias políticas y estrategias que el sistema operativo puede
tomas, para tratar con los interbloqueos:
- Indiferencia:Problema
del usuario y del programador, lograr que no se dé el interbloqueo.
- Prevención:Consisten
en condicionar el sistema con una serie de restricciones a los
programadores, para que no se den al menos una de las condiciones del
interbloqueo, por lo que éste nunca sucederá.
- Evitación o predicción:
Esta estrategia consiste en dejar que las condiciones para el interbloqueo
se puedan dar, pero en el momento de asignar recursos, y se detecte que puede
ocurrir un interbloqueo, deniega la asignación del recurso que puede
desencadenar el interbloqueo.
- Detección y recuperación:
En esta política, el sistema deja que suceda el interbloqueo, pero se
implementan procesos encargados de revisar el estado de asignación de los
procesos, para detectar los interbloqueo. Una vez detectado, se pueden
implementar políticas de recuperación de interbloqueo, que básicamente consisten
en matar procesos.
Condiciones
necesarias para la detección
1. Conocer los procesos:
acceso al PCB
2. Conocer los recursos: acceso a la tabla de recursos del sistema
3. Conocer la asignación: debemos poder saber qué recursos está asignado a cada proceso
4. Conocer la espera: debemos poder saber en que recursos está esperando (suspendido) un proceso
2. Conocer los recursos: acceso a la tabla de recursos del sistema
3. Conocer la asignación: debemos poder saber qué recursos está asignado a cada proceso
4. Conocer la espera: debemos poder saber en que recursos está esperando (suspendido) un proceso
Recuperación
Una vez que se
detecta un interbloqueo, corresponde la decisión sobre la recuperación del
sistema sobre ese interbloqueo, que básicamente se trata de matar un proceso y
recuperar sus recursos.
Esta recuperación puede ser manual o automática. La recuperación automática es un tema difícil, ya que no se pueden establecer, fácilmente, condiciones determinísticas para saber cuál es el proceso más adecuado de eliminar. Existen algunas posibilidades:
Esta recuperación puede ser manual o automática. La recuperación automática es un tema difícil, ya que no se pueden establecer, fácilmente, condiciones determinísticas para saber cuál es el proceso más adecuado de eliminar. Existen algunas posibilidades:
- El proceso con más recursos: se libera la
mayor cantidad cantidad de recursos, lo que permite continuar a la mayor
cantidad de procesos. Se deshace el "nudo" principal. Sin
embargo tiene la desventaja que normalmente será el proceso más
importante, lo que implica el mayor daño, o el mayor tiempo de repetición.
- El proceso con menos recursos: se busca el
menor daño, pero puede ser que pocos procesos puedan continuar.
- El proceso que esté involucrado en más ciclos
o interbloqueos: se deshace el mayor número de interbloqueos.
Sin embargo, hay que tomar en cuenta un criterio
subjetivo: la
importancia del proceso, lo cual no está dado ni por la cantidad de
recursos que tiene asignados el proceso ni el número de interbloqueos en que
está involucrado. Lo cuál hace de la recuperación manual, una forma muy
recomendable, siempre y cuando se cuente con un operador entrenado en el
funcionamiento de los procesos del usuario.
Herramientas para
el interbloqueo en los sistemas operativos existentes
SOLARIS
Utiliza la herramienta CAT (Crash Analysis Tool), que es parte del
entorno del sistema, y ayuda a analizar los archivos centrales del sistema.
Esta herramienta consiste en analizar la salida del desplome o error que se
dio. Esta herramienta genera archivos de salida en los cuales se describen las
causas que provocaron este estado en el sistema.
LINUX
Utiliza las siguientes herramientas:
GDB: Es una herramienta de rastreo y debugeo del kernel, con la información obtenida en un error en el sistema.
INGO: Es un “perro guardián” que sirve para detectar y reportar los interbloqueos.
SYSREQ: Permite observar las tareas, procesos y registros dentro del kernel en caso de fallo.
KDB: Es un debugeador del kernel en línea de comando que sirve para inspeccionar el estado de los procesos.
GDB: Es una herramienta de rastreo y debugeo del kernel, con la información obtenida en un error en el sistema.
INGO: Es un “perro guardián” que sirve para detectar y reportar los interbloqueos.
SYSREQ: Permite observar las tareas, procesos y registros dentro del kernel en caso de fallo.
KDB: Es un debugeador del kernel en línea de comando que sirve para inspeccionar el estado de los procesos.
WINDOWS
Utiliza las siguientes herramientas:
WINDBG:
DBGMON:
I386KD: Es utilizado para cargar el archivo MEMORY.DMP, el que fue generado por una computadora con WINDOWS NT. Este archivo contiene información que puede ser observada para verificar la integridad del sistema.
KD:
En general, la mayoría de herramientas sirven para observar el estado del sistema, ya sea por el kernel o por archivos generados conteniendo la información, y así poder saber el estado del sistema y que situaciones, procesos y recursos se encuentran involucrados en llevar al sistema a su estado actual.
Verifier.exe:a partir de WinXp, detecta interbloqueos en drivers
En Windows® XP La detección se presentó por medio del control orientado a excepciones, que permite interceptar la cadena de control de excepciones con propósitos de registro y diagnóstico. En Windows Vista™ Windows Vista tiene una nueva API muy interesante denominada Cruce encadenado con esperas (WCT). API Cruce permite determinar cuándo y por qué se produce interbloqueo en un proceso. WCT notifica exactamente en qué objeto de sincronización se encuentra el interbloqueo. Pero esta sólo notifica un conjunto limitado de primitivas de sincronización. Aun con esta limitante, resulta una API muy útil y que deseará tener en su kit de herramientas de depuración. API de WCT Uso y sus limitaciones Uso examina si un subproceso se encuentra en espera en una llamada de bloqueo. Si el subproceso se encuentra en una llamada de bloqueo, busca el objeto que el subproceso bloquea y determina, si es apropiado, el nombre del objeto y qué subprocesos o procesos poseen ese objeto. Por ejemplo, si el subproceso A espera que el proceso B complete la ejecución y el proceso B invoca SendMessage para el proceso A, existe un interbloqueo que WCT puede detectar y notificar. Limitaciones El único problema que observo con la API de WCT es que no notifica interbloqueos cuando se usa WaitForMultipleObjects, lo que reduce su utilidad en muchas aplicaciones.
WINDBG:
DBGMON:
I386KD: Es utilizado para cargar el archivo MEMORY.DMP, el que fue generado por una computadora con WINDOWS NT. Este archivo contiene información que puede ser observada para verificar la integridad del sistema.
KD:
En general, la mayoría de herramientas sirven para observar el estado del sistema, ya sea por el kernel o por archivos generados conteniendo la información, y así poder saber el estado del sistema y que situaciones, procesos y recursos se encuentran involucrados en llevar al sistema a su estado actual.
Verifier.exe:a partir de WinXp, detecta interbloqueos en drivers
En Windows® XP La detección se presentó por medio del control orientado a excepciones, que permite interceptar la cadena de control de excepciones con propósitos de registro y diagnóstico. En Windows Vista™ Windows Vista tiene una nueva API muy interesante denominada Cruce encadenado con esperas (WCT). API Cruce permite determinar cuándo y por qué se produce interbloqueo en un proceso. WCT notifica exactamente en qué objeto de sincronización se encuentra el interbloqueo. Pero esta sólo notifica un conjunto limitado de primitivas de sincronización. Aun con esta limitante, resulta una API muy útil y que deseará tener en su kit de herramientas de depuración. API de WCT Uso y sus limitaciones Uso examina si un subproceso se encuentra en espera en una llamada de bloqueo. Si el subproceso se encuentra en una llamada de bloqueo, busca el objeto que el subproceso bloquea y determina, si es apropiado, el nombre del objeto y qué subprocesos o procesos poseen ese objeto. Por ejemplo, si el subproceso A espera que el proceso B complete la ejecución y el proceso B invoca SendMessage para el proceso A, existe un interbloqueo que WCT puede detectar y notificar. Limitaciones El único problema que observo con la API de WCT es que no notifica interbloqueos cuando se usa WaitForMultipleObjects, lo que reduce su utilidad en muchas aplicaciones.
No hay comentarios:
Publicar un comentario