5.1 Definiciones Previas

5.2 Casos de Interbloqueos

5.3 Condiciones Necesarias para Producir un Interbloqueo

5.4 Estrategias para Resolver Interbloqueos

5.5 Interbloqueos: Sistemas Actuales/Sistemas Futuros

Cuando un proceso de un sistema de multiprogramación espera en balde a que se presente un evento específico, se dice que se encuentra en un estado de interbloqueo o bloqueo mutuo. Los procesos que pueden encontrase en esta situación pueden ser uno o varios.

En los sistemas de multiprogramación, compartir recursos es uno de los principales objetivos del sistema operativo. Cuando se comparten recursos entre una población de usuarios o procesos, cada uno de los cuales mantiene un control exclusivo sobre ciertos recursos asignados a él, es posible que se produzcan bloqueos mutuos que impedirán la terminación de algunos de los procesos del sistema.

Todos los interbloqueos suponen demandas contradictorias de recursos por parte de dos o más procesos. La figura 5.1 ilustra este conflicto de forma abstracta en el caso de dos procesos y dos recursos. Los dos ejes del diagrama representan el avance de los dos procesos en términos de instrucciones ejecutadas. El avance conjunto de los dos procesos se representa entonces con una secuencia discreta de puntos en el espacio. Las líneas horizontales o verticales representan el intervalo de tiempo en el que sólo uno de los procesos está ejecutándose (intercalado); una línea diagonal significa ejecución simultánea (solapamiento). Supóngase que existe un punto en la ejecución de cada proceso en el que se requiere el uso exclusivo de ambos recursos, R1 y R2, para continuar. En el ejemplo, llega un punto en el que el proceso P1 ha adquirido el recurso R1 y el proceso P2 ha adquirido el recurso R2, y cada proceso necesita el otro recurso. Este es el punto de interbloqueo.

  En este tema se analizará el problema del interbloqueo y las distintas alternativas de solución que se pueden adoptar clasificadas en las siguientes cuatro áreas : prevención, evitación, detección y recuperación del bloqueo mutuo. Para cada una de las estrategias adoptadas, se analizará el equilibrio entre la sobrecarga debida a los mecanismos de corrección del interbloqueo y los beneficios que reportan. En algunos casos es excesivo el precio (gasto extra) que hay que pagar para conseguir a toda costa que no se produzcan interbloqueos. Sin embargo, en algunos casos, como en los sistemas de tiempo real, no hay más alternativa que pagar el precio, ya que puede resultar catastrófico permitir la posibilidad de un bloqueo mutuo.

En cualquier sistema que mantenga los procesos en espera mientras se les asigna un recurso o se toman decisiones de planificación, la programación de un proceso puede postergarse indefinidamente mientras otro recibe la atención del sistema. Tal situación se conoce con varios nombres, entre los que se incluyen aplazamiento indefinido, bloqueo indefinido e inanición, y puede resultar tan peligrosa como el interbloqueo.

El aplazamiento indefinido puede ocurrir debido a predisposiciones en las políticas de planificación de recursos del sistema. Cuando los recursos se planifican por prioridad, es posible que un proceso dado espere de forma indefinida un recurso porque siguen llegando otros procesos con mayor prioridad. Los sistemas deben diseñarse para administrar los procesos en espera de manera justa además de eficiente. En algunos sistemas, el aplazamiento indefinido se evita aumentando la prioridad del proceso mientras espera (técnica de envejecimiento). En algún momento la prioridad de ese proceso superará la prioridad de los entrantes y el proceso en espera será atendido.

El caso más simple de interbloqueo sería el de un sólo proceso que espera la ocurrencia de un evento y, sin embargo, el sistema no incluye la posibilidad de señalar dicha ocurrencia. Es muy difícil detectar los bloqueos mutuos de esta naturaleza. La mayor parte de los bloqueos mutuos implican una competencia entre varios procesos por varios recursos.

Holt (1972) utilizó grafos dirigidos para representar situaciones de interbloqueo. Estos grafos tienen dos tipos de nodos : procesos, que se representan con círculos, y recursos, representados por cuadrados. Si in proceso está utilizando un recurso, previamente solicitado y concedido, se traza un arco desde el nodo del recurso (cuadrado) hasta el proceso (círculo). En la figura 2, el recurso R está en ese momento asignado al proceso A. En b), el proceso B está solicitando el recurso s. Por último en c) se representa un situación de interbloqueo : el proceso C está a la espera del recurso T, que está asignado al proceso D. El proceso D no ha dejado T, porque está esperando a que quede libre el recurso U, que, a su vez, está siendo utilizado por C. Ambos esperarán indefinidamente.

  El siguiente ejemplo servirá para ilustrar el empleo de grafos de recursos. Supongamos que tenemos tres procesos, A, B y C, y tres recursos, R, S, y T. La figura 5.2 representa las secuencias de petición y liberación que realizan los tres procesos. El sistema operativo tiene en todo momento completa libertad para ejecutar cualquiera de los procesos que no estén bloqueados, así que, por ejemplo, podría decidirse a ejecutar A hasta que éste terminara su trabajo, después B hasta que acabe y, finalmente C.

Este secuenciamiento no produce interbloqueo, ( ya que no se compite por los recursos), pero suprime completamente el paralelismo. Además de pedir y liberar recursos, los procesos también realizan E/S y procesamiento de datos. Si se ejecutan uno tras otro, se elimina completamente la posibilidad de que, mientras uno de ellos está esperando que acabe una E/S, otro pueda utilizar el procesador.

Supongamos, sin embargo, que los procesos realizan tanto E/S como procesamiento de datos, de forma que la planificación por turno rotatorio es la más adecuada. En este caso, la secuencia de petición de recursos podría ser la representada en la figura 3 (d). Si las seis peticiones se llevan a cabo en ese orden, se producirían los seis grafos de los casos (e)-(j). Después de la petición 4, A está bloqueado en espera de captar S, como se muestra en (h). Los procesos B y C se bloquean en las dos etapas siguientes, lo que conduce finalmente a un bucle cerrado y al correspondiente interbloqueo representado en (j).

El sistema operativo no está obligado a ejecutar los procesos en ningún orden en particular. En concreto, si la concesión de un recurso a un proceso determinado puede provocar interbloqueo, el sistema operativo es muy libre de suspender al proceso y no atender su petición hasta que esté seguro de que esto no conduce a una situación problemática. En la figura 5.3, por ejemplo, si el sistema operativo supiera que se avecinaba un interbloqueo, podría decidir suspender al proceso B antes de concederle el recurso S. La ejecución sólo de los procesos A y C produciría las secuencias de petición y liberación de la figura 5.3 (k), en lugar de las de la figura 5.3 (d). Esta secuencia de ejecución produce los grafos de recursos (l)-(q), y no produce interbloqueo.

Después de la etapa (q), no hay ningún problema en conceder S a B, ya que A ha terminado y C tiene todo lo que necesita. Aunque B se bloqueara al solicitar T, no se produciría interbloqueo; B simplemente esperaría hasta que terminara C.