Métodos de detección y recuperación de Deadlocks con ejemplo de variación del algoritmo del banquero

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

Detección de interbloqueos

¿Qué es un deadlock?

Analogía de deadlock.

Un deadlock, es una situación difícil de reproducir, y se dará sólo en algunas circunstancias muy concretas, por eso son situaciones difíciles de prever y de depurar. En sistemas operativos, un deadlock (o interbloqueo) es el bloqueo permanente de un conjunto de procesos o hilos de ejecución en un sistema concurrente que compiten 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. Cabe recalcar que la mayoría de los sistemas operativos actuales no pueden evitar que se produzcan. Por eso, cuando ocurren los diferentes sistemas operativos los manejan de diferentes maneras, ninguna de ellas convencional. La mayoría de los sistemas operativos están enfocados en prevenir una de las cuatro condiciones de Coffman. Toman especial cuidado en la cuarta:

  • Exclusión mutua: El recurso está asignado a un proceso pero debe ser usado una vez.
  • Retención y espera:
  • No apropiación: Los procesos no pueden ser forzados por otros procesos de igual categoría.
  • Espera circular: Cadena circular de solicitudes. Si existen n procesos el proceso p1 espera al p{n+1} y el p{n+1} espera a p1


Uno de los métodos para el manejo de deadlocks es la “Detección de deadlocks” y consiste en:

  • Permitir que el sistema entre en un estado de deadlock
  • Aplicar un algoritmo de detección de deadlock
  • Aplicar un mecanismo de recuperación

¿Por qué utilizar esta estrategia? La prevención de deadlock tiene un costo ya que todos los estados inseguros no son estados de deadlock. Esto implica que algunas veces para algunos procesos tienen que esperar y los recursos están desocupados sin ser necesario.

El sistema operativo puede chequear de vez en cuando si hay un deadlock. ¿Cuán frecuentemente debiéramos chequear si hay deadlock?

  • El costo de algoritmo vs. el número de procesos en deadlock.
  • Cuando la utilización de la CPU es baja.

Una vez decidida implementar esta estrategia, se deben eliminar los deadlocks que encontramos. Para ello podemos:

  • Abortar todos los procesos en deadlock.
  • Abortar procesos uno a la vez hasta que no haya deadlock.
  • Retroceder los procesos a algún punto y reiniciar. El deadlock puede reocurrir.
  • Expropiar recursos de procesos hasta que no haya deadlock. Retrocedemos los procesos expropiados.

Tenemos que seleccionar un proceso para abortar o retroceder. Se debe tener en consideración:

  • La prioridad.
  • El tiempo que el proceso ha corrido.
  • El número y tipo de los recursos adquiridos.
  • La clase de proceso (batch o interactiva).
  • La starvation es un problema.

Algoritmo utilizados para detección

El algoritmo normalmente utilizado es el algoritmo de Chandy-Misra-Haas. Un proceso espera un recurso, este envía un mensaje: el proceso está bloqueado, el proceso esta enviando la solicitud y el destino. Cuando se recibe el mensaje, el proceso si está esperando por un recurso envía nuevamente el mensaje al proceso para pedir recurso. Si el mensaje regresa al mensaje al proceso original se detecta el deadlock.

Algoritmo Numero de mensajes Delay Tamaño del mensaje
Goldman <m,n t + nT Variable (mediano)
Isleor-Marsland r(N-1) 0 Constante (mediano)
Menasce-Muniz m(n-1) nT Constante (pequeño)
Obermack m(n-1)/2 nT Constante (mediano)

Instancias de recursos

Instancias simples

El primer grafo corresponde a uno de asignación de recursos mientras que el segundo a uno Wait-for.

En el método de detección de deadlocks, podemos encontrar instancias simples o múltiples. Cuando nos encontramos con instancias simples podemos trabajar con un grafo de asignación de recursos y el grafo wait-for.

  • Grafo de asignación de recursos: Es un grafo que contiene información acerca de los procesos y los recursos utilizados, en particular, representaremos los procesos por círculos y los recursos por rectángulos. Las flechas asignadas de proceso a recurso representan la solicitud de un proceso a dicho recurso, por otra parte la asignación de una flecha de la instancia de un recurso a un proceso significa que el recurso está siendo utilizado por el ya mencionado proceso.
  • Grafo “Wait-for”: Este grafo representado por los procesos (de figuras circulares) muestra aquellos que esperan a otro proceso para la asignación de recursos a los cuales este segundo tiene.

Instancias múltiples

Al trabajar con instancias múltiples, podemos utilizar una variación del algoritmo del banquero, el cual presentaremos a continuación:

Se deben considerar las siguientes matrices/vectores:

Available: Un vector de largo m que indica el número de recursos disponibles de cada tipo.

Allocation: Una matriz de n x m que define el número de recursos de cada tipo que actualmente están asignados a cada proceso.

Request: Una matriz de n x m que indica el requerimiento actual de cada proceso. Si Request [ij] = k, entonces el proceso Pi requiere k instancias adicionales del recurso tipo Rj.

El algoritmo es el siguiente:

1. Sea Work y Finish vectores de largo m y n, respectivamente Inicializar:

(a) Work = Available

  • Se igualan los vectores Work y Available, quien contiene los datos del número de recursos disponibles.

(b) for i = 1,2, …, n

      if Allocation[ij] ≠ 0 then
        Finish[i] = false;
      otherwise
        Finish[i] = true
  • El vector finish es de largo del número de procesos con los que se está trabajando, si un proceso tiene asignado recursos, finish[i] es false, si no posee recursos asignados finish[i] es true.

2. Encontrar un índice i tales que ambos: (a) Finish[i] == false (b) Requesti ≤ Work

  • Si Finish[i] es true, significa que no tiene ningún recurso asignado, de lo contrario se verifica que la solicitud del vector Request no sobre pase los recursos disponibles, representado por el vector Work.

Si no existe un i, ir al paso 4.

3. Work = Work + Allocationi

   Finish[i] = true
   go to paso 2
  • De manera recursiva se van asignando los recursos solicitados y actualizando el vector Finish[i] quien nos informa del “estado” del proceso i

4. if Finish[i] == false, para algún i, 1 ≤ i ≤ n,

  • Entonces el sistema está en un estado de deadlock, es decir, algún proceso esta en espera a la asignación de recursos por parte de otro proceso quien los está utilizando.
  • En particular:

if Finish[i] == false, entonces Pi está en deadlock.

Un algoritmo que se utiliza normal para detección de deadlock es el algoritmo de Chaudy, Misra y Haas. Este algoritmo permite pedir más de un recurso a la vez en vez de uno ya sea remoto o no.

Un proceso espera un recurso, este envía un mensaje: el proceso está bloqueado, el proceso esta enviando la solicitud y el destino. Cuando se recibe el mensaje, el proceso si está esperando por un recurso envía nuevamente el mensaje al proceso para pedir recurso. Si el mensaje regresa al mensaje al proceso original se detecta el deadlock.

Recuperación de un interbloqueo

Una vez determinada la existencia de un interbloqueo por medio del algoritmo de detección, existen distintas alternativas de recuperación. La primera y la más simple son de manera manual, se informa al operador del sistema para que este se ocupe manualmente. Otra alternativa es hacer que el sistema rompa el interbloqueo y se recupere automáticamente. Para esto existen dos opciones: Terminación de procesos y expropiación de recursos

Terminación de procesos

El sistema recupera todos los recursos de los procesos terminados mediante dos métodos:

  • Abortar todos los procesos interbloqueados.

Es una de las soluciones mas comunes. En este método se rompe definitivamente el ciclo, pero con un costo mas elevado, ya que estos procesos efectuaron cálculos durante mucho tiempo y habrá que descartar los resultados de estos cálculos parciales, para quizás tener que volver a calcularlos mas tarde

  • Abortar procesos de uno en uno , hasta eliminar el ciclo.

El orden en que se seleccionan los procesos para abortarlos debe basarse en algún criterio de costo mínimo. Después de cada aborto, debe solicitarse de nuevo el algoritmo de detección, para ver si todavía existe el interbloqueo. Este método cae en mucho tiempo de procesamiento adicional.

En ambos casos puede ser difícil abortar un proceso , ya que si se encuentra actualizando un fichero, cortarlo a la mitad de la operación , puede causarle daño y quedar en mal estado. Si se utiliza el método de terminación parcial, entonces, dado un conjunto de procesos bloqueados, debemos determinar cuál proceso o procesos debe terminarse para intentar romper el interbloqueo. Desde un punto de vista económico se debe seleccionar aquel proceso cuya terminación represente el costo mínimo.


Existen muchos factores que determinan el proceso que se seleccionará, siendo los principales los siguientes:

  1. La prioridad del proceso. Se elimina el proceso de menor prioridad.
  2. Tiempo de ejecución ya consumido y tiempo de ejecución previsto
  3. Tipos de recursos utilizados. Si los recursos son muy necesarios y escasos será preferible liberarlos cuanto antes.
  4. Cuántos recursos más necesita el proceso para concluir.
  5. Facilidad de suspensión/reanudación.Se eliminarán aquellos procesos cuyo trabajo perdido sea más fácil de recuperar.
  6. Tipo del proceso (por lotes o interactivo)

Expropiación de recursos

Para eliminar interbloqueos utilizando la expropiación de recursos, se van quitando sucesivamente recursos de los procesos y los asignamos a otros hasta romper el ciclo de interbloqueo.

Si se utiliza la expropiación de recursos para tratar los interbloqueos, hay que considerar tres aspectos:

  • Selección de la víctima
  • Retroceso
  • Bloqueo indefinido


En el primer caso esta , selección de la victima, este aspecto esta ligado a la pregunta ¿A qué procesos y qué recursos se expropiarán?, Igual que antes, se debe determinar el orden de expropiación para minimizar el costo. En el segundo aspecto Retroceso o rollback la pregunta frecuente es ¿Qué pasa con el proceso al que se expropia un recurso? Obviamente, no puede continuar con su ejecución normal, pues le falta un recurso necesario. Se debe hacer retroceder al proceso hasta llegar a un estado anterior seguro, para más adelante reiniciarlo a partir ese estado. Y finalmente el ultimo aspecto es Bloqueo indefinido o Postergación indefinidaque dice que en un sistema donde la selección de la víctima se basa en factores de costo, puede suceder que siempre se elija como víctima al mismo proceso, lo cual puede conducir a una situación de bloqueo efectivo del mismo. Se debe asegurar que un mismo proceso sólo es elegido un número finito y pequeño de veces. La solución habitual es incluir el número de retrocesos como factor de costo.

Algoritmo del banquero

Para solucionar el problema de deadlocks en sistemas de asignación con varios tipos de recursos y con múltiples instancias nace el algoritmo del banquero.

Es necesario que cuando un proceso nuevo ingresa al sistema, el proceso debe declarar el número máximo de instancias del recurso que necesita.

Por ej. El proceso con pid=1000 entra al sistema y declara que necesita 10 instancias del recurso A y 20 del recurso B. Esto se puede representa en un vector. Este vector generar el vector max.

En caso que un uusario solicite recursos el sistema debe analizar si la asignación de los recursos dejará al sistema en un estado seguro.


  • Un sistema tiene un grupo de instancias disponibles de recursos, se representará como el vector unidimensional available (disponible).
  • Un proceso como se dijo anteriormente tiene un máximo de instancias para pedir, por lo tanto puede representarse como un vector bidimensional los maximos de todos los procesos: Max
  • La asignación de recursos se representada con el vector bidimensional Allocation (asignación)
  • Se llama necesitada a la resta del maximo del proceso con los procesos asignados. Y se representa la necesidad con el vector bidimensional need (necesidad)

Algoritmo de seguridad

Determinar si el sistema está en un estado seguro.

  1. Sea Work y finish (vector de tamaño m). Inicialmente Work = Available y Finish[i] = false
  2. Encontrar i que cumpla
    1. finish[i] == false
    2. need[i] <= work
    3. Si no existe tal i, continuar con el paso 4.
  3. Hacer:
    1. work[i] = work[i] + available[i]
    2. finish[i] = true
  4. En caso que existe algun valor de i finish[i] == false continuar con el paso 2, en caso contrario el sistema esta seguro
Diagrama de flujo de algoritmo de seguridad

Algoritmo de solicitud de recursos

Un proceso hace una petición que puede ser de varias instancias de distintos tipos de recursos

  1. request[i] <= need[i]
    1. Si es verdadero: paso 2
    2. Si es falso: error, se ha excedido en la cantidad máxima de recursos que declaró.
  2. request[i] <= available
    1. Si es verdadero: paso 3
    2. Si es falso: No hay recursos. Espere.
  3. Asignar.
    1. available = available - request[i]
    2. allocation[i] = allocation[i] + request[i]
    3. need[i] = need[i] - request[i]
Diagrama de flujo de algoritmo de solicitud de recursos

Ejercicio

Este ejercicio se presenta en el libro Fundamentos a Sistemas Operativos de [Abraham Silberschatz] pero no de manera paso a paso.

Imagine que un tiempo se ha tomado una imagen del sistema

Process Allocation Max Available
A B C A B C A B C
P_0 0 1 0 7 5 3 3 3 2
P_1 2 0 0 3 2 2
P_2 3 0 2 9 0 2
P_3 2 1 1 2 2 2
P_4 0 0 2 4 3 3

Podemos obtener la matriz need

Process Need
A B C
P_0 7 4 3
P_1 1 2 2
P_2 6 0 0
P_3 0 1 1
P_4 4 3 1

¿Se puede afirmar que sistema esta en un estado seguro? Usando el algoritmo de seguridad

work = <3,2,2>
finish[] = false
Paso 2.0

Revisamos si el proceso ha terminado y si puede ser atendido.

¿finish[0] == false?  TRUE
¿need[0] <= work? ¿<7,4,3> <= <3,2,2>? FALSE

El proceso no puede ser atendido.

Paso 2.1 : Revisamos para el proceso 1

¿finish[1] == false?  TRUE
¿need[1] <= work? ¿<0,2,0> <= <3,2,2>? TRUE

Paso 3.1 : Debido que puede: se hace la asignación y se marca el proceso como terminado

work = work + allocate[1]
work = <3,2,2> + <2,0,0>
work = <5,2,2>
finish[1] = true

Paso 2.2 : Revisamos para el proceso 2

¿finish[2] == false?  TRUE
¿need[2] <= work? ¿<6,0,0> <= <5,2,2>? FALSE

El proceso no puede ser atendido.

Paso 2.3 : Revisamos para el proceso 3

¿finish[3] == false?  TRUE
¿need[3] <= work? ¿<0,1,1> <= <5,2,2>? TRUE

Paso 3.3 : Debido que puede: se hace la asignación y se marca el proceso como terminado

work = work + allocate[3]
work = <5,2,2> + <2,1,1>
work = <7,3,3>
finish[3] = true

Paso 2.4 : Revisamos para el proceso 4

¿finish[4] == false?  TRUE
¿need[4] <= work? ¿<4,3,1> <= <7,3,3>? TRUE

Paso 3.4 : Debido que puede: se hace la asignación y se marca el proceso como terminado

work = work + allocate[4]
work = <7,3,3> + <0,0,2>
work = <7,3,5>
finish[4] = true

Existe algún proceso que no ha terminado, se obtiene que el proceso 0 no ha terminado

¿finish[*] == false?  TRUE 

Paso 2.0 : Revisamos para el proceso 0

¿finish[0] == false?  TRUE
¿need[0] <= work? ¿<7,4,3> <= <7,3,5>? FALSE

El proceso no puede ser atendido.

Paso 2.2 : Revisamos para el proceso 2

¿finish[2] == false?  TRUE
¿need[2] <= work? ¿<6,0,0> <= <7,3,5>? TRUE

Paso 3.2 : Debido que puede: se hace la asignación y se marca el proceso como terminado

work = work + allocate[2]
work = <7,3,5> + <3,0,2>
work = <10,3,7>
finish[2] = true

Paso 2.0 : Revisamos para el proceso 0

¿finish[0] == false?  TRUE
¿need[0] <= work? ¿<7,4,3> <=<10,3,7>? TRUE

Paso 3.0 : Debido que puede: se hace la asignación y se marca el proceso como terminado

work = work + allocate[0]
work = <10,3,7> + <0,1,0>
work = <10,4,7>
finish[0] = true

Todos los procesos han terminado por lo tanto es seguro ¿finish[] == true? TRUE Por lo tanto un orden posible para estar en estado seguro: P1, P3, P4, P0, P2

Referencias

http://es.wikipedia.org/wiki/Bloqueo_mutuo 13-11-2012

http://www.fceia.unr.edu.ar/~diegob/so/presenta/06-Deadlock.pdf 14-11-2012

http://www-2.dc.uba.ar/materias/so/datos2/08-deadlock.pdf 14-11-2012

http://www.personal.kent.edu/~rmuhamma/OpSystems/Myos/deadlockCondition.htm

Bibliografía

“Fundamentos de Sistemas Operativos”, Silberschatz, Galvin, Gagne, Séptima Edición, 2005.

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas