Interbloqueos

Concepto:

Un Interbloqueo supone un bloqueo permanente de un conjunto de procesos que compiten por recursos o bien se comunican o sincronizan si.

Los procesos de los sistemas no solo son independientes, sino que compiten en el uso exclusivo de recursos, se comunican y se sincronizan entre si. El sistema operativo debe encargarse de asegurar que estas interacciones se llevan a cabo aproximadamente proporcionando la exclusión mutua requerida por las mismas. La necesidad de los algunos procesos pueden entrar en conflicto entre si causando que estos se bloqueen indefinidamente.

El Interbloqueo surge debido a que produce un conflicto entre las necesidades de los procesos y el recurso que necesita cada proceso lo posee el otro.

Se caracteriza por la existencia de un conjunto de entidades activas que utilizan un conjunto de recursos para llevar a cabo su labor.

Entidades: activas que corresponden con los procesos existentes en el sistema. Un SO proporciona threads que representan las entidades activas y son la unidad de ejecución del sistema.

Recursos existentes en el sistema: son utilizados por los procesos para llevar a cabo su valor.

Tipos de recursos:

1-Recursos reutilizables o consumibles:

Se caracteriza por que el recurso  existiendo después de que un proceso lo use queda disponible para otros procesos. El recurso es independiente de su utilización.

2-Recursos consumibles:

Estos se caracterizan por que dejan de existir una vez que los usa.

3-Recursos compartidos o exclusivos:

Estos recursos no se ven afectados por Interbloqueos ya que los procesos que quieran usarlos pueden hacerlo inmediatamente sin posibilidad de quedarse bloqueados.

4-Recursos con un único ejemplar o con múltiples:

Una solicitud de este recurso por parte de un proceso podría satisfacerse con cualquier ejemplar del mismo.

 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

 

Asignación de recursos con espera circular e interbloqueados

Modelado del Interbloqueo

Los interbloqueos pueden describirse utilizando un grafo dirigido y bipartito G(N,A) llamado grafo de asignación de recursos que consta en un conjunto de N nodos (vértices) y E arcos.

2 tipos de nodos

Procesos y Recursos

2 tipos de arcos

Arco de solicitud. Es un arco que parte de un proceso P hacia un tipo de recurso R j y se representa por P i → R j (o (P i, R j i)). Significa que el proceso P solicitó una instancia del recurso R y se encuentra esperándolo.

Arco de asignación. Es un arco que sale de un tipo de recurso R y se dirige a un proceso P i (representado por R que se ha asignado un ejemplar del tipo de recurso R j→ P i j o (R j, P i al proceso P j)). Significa i.

Gráficamente, se representa cada proceso con un círculo y cada tipo de recurso con un rectángulo.  

Si de algún tipo de recurso existe más de un ejemplar, se representa cada uno con un punto dentro del rectángulo. 

Un arco de solicitud parte entonces de un círculo y apunta a un rectángulo.

Un arco de asignación parte desde un punto dentro del rectángulo y señala hacia un círculo.

Grafo de asignación de recursos

Estados de los procesos:

El proceso P 1 tiene asignado un recurso de tipo R 2, y espera un recurso de tipo R.

El proceso P 2 tiene asignado un recurso de tipo R 1 y otro de tipo R, y espera un recurso de tipo R.

El proceso P 3 3 tiene asignado un recurso de tipo R 3. 2 1

Si el grafo de asignación de recursos no contiene ciclos, entonces ningún proceso del sistema se encuentra en interbloqueo.  

Si existe un ciclo, puede haber interbloqueo.

La presencia de un ciclo es condición necesaria pero no suficiente para la existencia de interbloqueo.

Si de cada tipo de recurso existe un único ejemplar, entonces la presencia de un ciclo determina que existe interbloqueo.  

En este caso la existencia de un ciclo si es condición necesaria y suficiente para la existencia de interbloqueo.

Grafo de asignación de recursos con un interbloqueo

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.
• 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.
• 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.

Indiferencia (algoritmo del avestruz)

• Simple y eficiente, dado que el sistema operativo no gasta procesador ni recursos en el manejo del interbloqueo. Usualmente es la política preferida en los sistemas actuales
• El costo esperado de un interbloqueo suele ser muy bajo
• Costo esperado = Probabilidad (desastre) * Costo (desastre)
• Sólo se deben proporcionar herramientas para revisar el estado de los procesos
• complica el trabajo del operador

Detección y recuperación

• El sistema no impone ninguna clase de reglas para prevenir o evitar el interbloqueo
• Se puede tener un proceso de fondo o de activación manual que analice las estructuras del sistema operativo y determine si existe o no un interbloqueo.
• Una vez detectado el interbloqueo se procede a la recuperación, que puede ser automática o manual. Básicamente consiste en matar un proceso

Podría utilizar si no es muy costoso que haya un interbloqueo (el costo es menor que el costo de implementar una de las otras políticas de interbloqueo.

Normalmente sería utilizado como herramienta de diagnóstico y recuperación

Detección por ciclos de espera

La técnica más sencilla para detectar un interbloqueo es deducir un grafo dirigido de dependencias entre proceso por medio de las colas de espera en cada recurso y determinar si existen un ciclo en dicho proceso.

Por ejemplo, en la siguiente gráfica, al lado izquierdo, se tiene un grafo del estado actual de asignación de recursos y a la derecha vemos el grafo de espera entre procesos. Como se puede apreciar, existe un ciclo en en grafo de espera, por lo tanto existe un interbloqueo.

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

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:

• 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.

Evitación o Predicción ( Estrategias de Dijkstra, Habermann)

Con la evitación no se tienen reglas estáticas a los procesos, sino que el sistema operativo analiza cada petición de recursos y determina si el sistema quedará en un estado estable o inestable, en este último caso, se deniega la petición, posponiéndola temporalmente.

Conceptos

La evitación se basa en los siguientes conceptos:

• Estado de asignación de recursos:Número de recursos asignados, disponibles y máximo de recursos posibles por proceso.
• Secuencia segura:Secuencia de finalización de procesos, tal que todos los procesos puedan finalizar exitosamente, iniciando en un determinado estado de asignación de recursos
• Estado seguro de asignación de recursos:Estado de asignación de recursos, donde existe al menos una secuencia segura.
• Estado inseguro de asignación de recursos: No existe ninguna secuencia segura. Obsérvese, que aunque un estado inseguro no implica que exista interbloqueo, talvez una secuencia determinada de eventos lleve a uno.

Algoritmo del banquero (Dijkstra, Habermann)

En este algoritmo, de evitación en general procede así:

• Necesita que cada proceso declare el máximo número de recursos a utilizar
• En cada requerimiento, determina si el asignar los recursos pedidos deja un estado inseguro de asignación de recursos, entonces se pospone el requerimiento. De lo contrario se asignan los recursos solicitados.

Procedimiento de asignación

Cuando un proceso solicita recursos, el sistema operativo procede así:

1.    Determinar si hay disponibles

2.   Determinar que no exceda su máximo declarado

3.   Determinar que, si se concede la petición, el sistema quede en estado seguro

Si no se cumple cualquiera de estas condiciones, el proceso queda suspendido hasta que exista una liberación de recursos.

Estructuras de datos:

sea m el número de tipos de recursos y n el número de procesos

int disponible [m] ; unidades de R j disponibles

int max[n][m]; máximo número de requerimientos del proceso Pi del recurso Rj

int asignado [n][m]; asignación actual del proceso P i del recurso Rj

int necesario [n][m]; necesario [i][j] = max [i][j] - asignados[i][j]

int requerimiento[m]; vector de requerimiento de cada petición de recursos//

Relación <= entre vectores

si x in N m , y in N m : x <= y ssi para todo i = 0,...,m-1 : x[i] <= y[i]

Por ejemplo:

<1,1,1> <= <2,5,7>

<1,1,1> NO <= <2,0,7>

Algoritmo

void requerimiento_de_recursos (int requerimiento[], idProceso i) {

if (requerimiento >= necesario[i] )

error () ; máximo de recursos estimados agotados

i f (requerimiento >= disponible)

suspender () ; recursos no disponibles

disponible -= requerimiento;

asignado [i] += requerimiento;

necesario[i] -= requerimiento;

if (! estado_seguro ()) {

regresamos al estado anterior

disponible += requerimiento;

asignado[i] -= requerimiento;

necesario[i] += requerimiento;

suspender () ;

}

}

int estado_seguro() {

int disp_temp = disponible;

bool terminado[n] = (FALSE,...,FALSE);

int i;

encontrar un p[i] tal que terminado[i] = FALSE y necesario[i] <= disponible

while (terminado!=(TRUE,...TRUE)){

for (i=0; (i < n && terminado[i]) || necesario[i] > disp_temp); i++) {

if (i == n-1) {

return FALSE;

}else

if (!terminado[i]){

disp_temp += asignados[i] ;

terminado[i] = TRUE;

} if

} for

} while

return TRUE ;

}estado_seguro

Ejemplo

Sobre este estado de asignación de recursos (qué es estable ¿?) supongamos las siguientes peticiones de recursos:

• P2[1,0,1]:El sistema queda en un estado seguro
• P3[2,0,0]:El sistema queda en un estado inseguro

Desventajas

• necesita el conocimiento del máximo por recurso que usará cada proceso
• implica un retardo en cada asignación de recursos, lo que puede degradar el sistema si se manejan muchos recursos y/o procesos
• Se requiere una garantía de devolución: c/proceso liberará los recursos asignados. (suponga que después de hacer la primera asignación de recursos, el proceso P2 no termina, entonces ninguno de los procesos podría terminar, sin necesidad de que haya interbloqueo.