Deadlocks y sus métodos para prevenir/evitar (con ejemplo de algoritmo del banquero)

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

Contenido

¿Qué es un Deadlock?

Un deadlock, bloqueo mutuo o abrazo mortal, se refiere al bloqueo que se produce entre dos o más procesos cuando éstos están compitiendo por recursos en un sistema concurrente. A diferencia de otros problemas, los deadlocks no poseen una solución general y esta dependerá de las características del problema que se esté abordando.

Ejemplo de representación de Bloqueo Mutuo en una carretera.

Condiciones de Coffman

Las condiciones de Coffman son las condiciones necesarias para que se produzca un deadlock. Reciben este nombre por E. G. Coffman quien las describió por primera vez en un artículo en 1971.

  • Condición de exclusión mutua: Esta condición se refiere a que por vez, solo un proceso puede usar el recurso.
  • Condición de posesión y espera: En esta condición, debe haber un proceso reteniendo a lo menos un recurso y que esté esperando por recursos adicionales que estén siendo usados por otro proceso.
  • Condición de no expropiación: En la condición de no expropiación, un recurso solo puede ser liberado de forma voluntaria por el proceso que lo retiene, una vez que éste terminó la tarea que estaba realizando.
  • Condición de espera circular: Para esta condición tiene que existir un conjunto de procesos en espera, tal que un proceso P0 esté a la espera de un recurso retenido por otro proceso P1, P1 a la espera de un recurso retenido por P2 y así sucesivamente hasta Pn, y Pn esté esperando un recuso retenido por P0.

Evitando deadlocks

Existen diferentes formas de evitar los deadlocks si se cuenta, antes de asignar recursos, con información sobre los procesos. Para evitar los deadlocks podemos usar alguno de los algoritmos que se ven a continuación, dependiendo de la situación en la cual nos encontremos.

Algoritmo del banquero

El algoritmo del banquero fue propuesto por Dijkstra y permite destrabar los deadlocks. Para poder utilizar el algoritmo del banquero deben primero darse una serie de restricciones:

  • Se debe conocer a priori, cuál será la demanda máxima de recursos.
  • Los procesos deberán ser ejecutables en cualquier orden.
  • Debe existir un número determinado de recursos a utilizar y de procesos que los utilicen.
  • Mientras estén reteniendo recursos, los procesos no pueden finalizar.

Para lograr comprender a cabalidad el algoritmo necesitamos tener claros algunos conceptos de forma previa, estos son:

  • Asignado: Es el estado actual en que se encuentra la asignación de recursos a los procesos.
  • Matriz demanda: Es el máximo que de recursos que exige cada proceso para ejecutarse.
  • Matriz asignación: Son las asignaciones que tiene actualmente cada proceso.
  • Vector disponible: Es el total de los recursos sin asignar a ningún proceso.

A pesar de todo, el algoritmo del banquero tiene ciertas desventajas, tales como:

  • Debe existir un número fijo de recursos para asignar.
  • La población de usuarios debe mantenerse constante.
  • Requiere que el sistema operativo pueda dar garantía de que las peticiones se concederán en un tiempo finito.
  • Los procesos deben indicar las máximas necesidades de recursos por adelantado.
  • Generalmente no se usa en sistemas operativos reales.

Para lograr comprender mejor este algoritmo, en las siguientes secciones se demostrará su uso con un ejemplo practico.

Algoritmo de grafo de asignación de recursos

Ejemplo de Grafo de Asignación de Recursos.

Este algoritmo implica que cada proceso va siendo liberado una vez que se le han asignado los recursos necesarios para su ejecución. En este caso, cada requerimiento puede ser atendido solo si al cambiar un arco de requerimiento a uno de solicitud no se forma un ciclo en el grafo de asignación.

Algoritmo de Seguridad

Un sistema está en un estado seguro si hay un orden en el cuál todas las peticiones de recursos pueden ser concedidas a todos los procesos, previniendo un deadlock.

  • Un "deadlock" es un estado "inseguro".
  • Un estado "inseguro" puede terminar siendo un "deadlock", pero no necesariamente es uno.

Este algoritmo determina si el sistema se encuentra o no en un estado seguro y sin necesidad de "molestar" a un recurso.

Algoritmo de solicitud de recursos

El algoritmo de solicitud de recursos determinará, cuando se realiza un pedido de recursos, si este puede ser satisfecho o no de forma segura.

Este algoritmo se ejecuta cada vez que llega una solicitud de recursos por parte de un proceso.

Previniendo deadlocks

Para prevenir los deadlocks hay diversos mecanismos, estos consisten básicamente en eliminar alguna de las condiciones de Coffman, para destrabar así los bloqueos mutuos.

Eliminando la exclusión mutua

No existen recursos exclusivos, es decir, ningún proceso puede acceder de forma exclusiva a algún recurso.

La condición de posesión y espera

Esta condición se puede eliminar haciendo una asignación total de recursos al inicio de la ejecución del proceso, y si tiene se debe pedir un nuevo recurso, que se libere primeramente el que está en uso.

La condición de no expropiación

Esta condición puede ser imposible de eliminar debido a que todo proceso debe tener un recurso durante un tiempo determinado o el procesamiento se torna inconsistente.

La condición de espera circular

Para eliminar esta condición se debe permitir a un proceso poseer solamente un recurso en un momento determinado, es decir, imponer una jerarquía de tal forma de hacer imposible que existan círculos de espera.

Ejemplo de algoritmo del banquero

Sea {P0, P1, P2, P3, P4} el conjunto de procesos y {A,B,C} tres recursos, donde A tiene diez instancias, B cinco y C siete instancias.

Tabla de Asignación y Máximos.

Disponible {A,B,C} = {3,3,2}

Requerimiento de P1 = <1,0,2>

Para verificar que el requerimiento puede ser satisfecho debemos ver que:

a) Req(i) ≤ Disponible ((1,0,2) ≤ (3,2,2)) b) Req(i) ≤ Necesidad ((1 0 2 ) ≤ (1 2 2))

Una vez cumplido el requerimiento se actualiza la información y se pasa al siguiente estado:

Tabla de Asignación y Necesidad para el nuevo proceso.

Disponible nuevo {A,B,C} = {2,3,0}

Ahora aplicamos el algoritmo de seguridad y obtenemos:

Paso 1: WORK=<2,3,0> y Finish(i)=F para todo i.

Paso 2: Existe i? Tomemos P1 porque <0,2,0>≤<2,3,0> y Finish(1)=F

Paso 3: WORK=WORK+ASIG P(1)=<2,3,0>+<3,0,2>=<5,3,2>

Finish(1)=V

Paso 2: Existe i? Tomemos P3 porque <0,1,1>≤<5,3,2> y Finish(3)=F

Paso 3: WORK=WORK+ASIG P(3)=<5,3,2>+<2,1,1>=<7,4,3>

Finish(3)=V

Paso 2: Existe i? Tomemos P4 porque <4,3,1>≤<7,4,3> y Finish(4)=F

Paso 3: WORK=WORK+ASIG P(4)=<7,4,3>+<0,0,2>=<7,4,5>

Finish(4)=V

Y así continuando se puede obtener que una secuencia segura corresponde a {P1, P3, P4, P0, P2}

Referencias

http://cs.uns.edu.ar/~so/data/apuntes/SO-2012-mod%2007.pdf

http://proyecsisinfor.blogspot.com/2010/11/concepto-de-bloqueo-mutuo-bloqueo-mutuo.html

http://www.soygik.com/

http://exa.unne.edu.ar/

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

http://seneca.cucea.udg.mx/curso_linea/Sistemas_OperativosI/cursoSO/modulo2seccion5.pdf

http://proyecsisinfor.blogspot.com/2010/11/concepto-de-bloqueo-mutuo-bloqueo-mutuo.html

http://es.wikipedia.org/wiki/Algoritmo_del_banquero

http://www.slideshare.net/ozkar21/bloqueos-mutuos-7589167

http://www.slideshare.net/zan45kbh/algoritmo-del-baquero

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas