Condiciones para el interbloqueo y estrategias de resolución

Condiciones

Según Coffman, para que se pueda producir un interbloqueo se tienen que dar la siguientes cuatro condiciones:

• Exclusión mutua: cada recurso está asignado a un único proceso de manera exclusiva.
• Retención y espera: los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos.

• No apropiación: los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita.

• Espera circular: debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena. Esta condición es una consecuencia potencial de las tres primeras, es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble.

Las tres primeras condiciones son necesarias, pero no suficientes para que exista interbloqueo. Sólo las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.

Estrategias

Existen diversas estrategias frente a los interbloqueos, que se pueden agrupar en:

• Omisión
• Detección y recuperación
• Prevención
• Predicción

Omisión

Considera que la probabilidad de un interbloqueo es muy baja, de modo que se confía en que no se van a producir. Por sorprendente que parezca, los sistemas operativos modernos convencionales suelen aplicar esta estrategia. Por justificar la decisión de los fabricantes de sistemas operativos cabe incidir en que las estrategias de resolución y prevención de interbloqueos tienen un coste alto desde el punto de vista del consumo de recursos de procesamiento y memoria.

Detección y Recuperación

Esta estrategia permite la detección de una situación de interbloqueo y su consiguiente resolución. De entre las medidas de detección consideramos las siguientes:

• Grafo de relación recursos-procesos: Consiste en la representación gráfica de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.

• Matrices de relación recursos-procesos: Consiste en la representación matricial de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.

Tras la detección de un interbloqueo, se pueden aplicar algunas de las siguientes estrategias para resolverlo:

• Eliminación: El sistema operativo selecciona a uno de los procesos que forma parte del interbloqueo y elimina el ciclo acabando con la ejecución de dicho interbloqueo. La selección del proceso se realiza en base a un cierto criterio, por ejemplo, aquel proceso que lleve menos tiempo en ejecución o aquel que sea más voraz consumiendo recursos. Aunque parezca una medida drástica, es la empleada en sistemas operativos convencionales.

• Apropiación temporal: Se retira la asignación de un recurso a un proceso para deshacer el interbloqueo.

• Puntos de conformidad o checkpoints: Consiste en tomar una imagen del estado del proceso, ya sea periódicamente o a instancia del propio proceso, de manera que si se produce un interbloqueo se vuelve a un estado de la ejecución anterior. Son muy poco usados ya que tienen un elevado coste en memoria y existe la posibilidad de que un proceso permanezca indefinidamente sin progresar.

Prevención

La prevención apunta a una serie de estrategias que eviten el interbloqueo. Concretamente, son cuatro las estrategias de prevención posibles en base a los principios que Coffman estableció como interbloqueo. Dichas estrategias son:

• Supresión de exclusión mutua: un proceso no puede tener acceso exclusivo a un recurso.
• Supresión de retención y espera (1ª estrategia de Havender): El proceso debe tener asignado todos los recursos necesarios al inicio y no liberarlos hasta que éste finalice. Esto presenta un inconveniente: si un recurso sólo se utiliza al final, estará ocupado durante toda la ejecución, no permitiendo ser usado por otros procesos.
• Supresión de no apropiación (2ª estrategia de Havender): Si un proceso está en ejecución y no puede obtener un recurso, dicho proceso libera todos los recursos que está usando y espera a que todos los que necesita estén disponibles. Problemas: se puede perder trabajo, además de presentar una carga extra la realización de peticiones
• Supresión de espera circular (3ª estrategia de Havender): Si todos los recursos comunes a varios procesos se solicitan siempre en el mismo orden no se producen interbloqueos.

Predicción

El sistema operativo observa la evolución que siguen los procesos, y predice una posible situación de interbloqueo. Si detecta una alta probabilidad de que sucede, adopta una trayectoria de ejecución de los procesos involucrados en el posible interbloqueo de manera que se garantice que no va a suceder.