domingo, 26 de octubre de 2008

2.4.3.- INTERBLOQUEO (DEADLOCK)

Definición

Un conjunto de procesos se encuentra en estado de interbloqueo cuando cada uno de ellos espera un suceso que solo puede originar otro proceso del mismo conjunto.


En la mayoría de los casos, el evento que espera cada proceso es la liberación de cierto recurso que posee por el momento otro miembro del conjunto. En otras palabras, cada miembro del conjunto de procesos bloqueados espera un recurso poseído por un proceso bloqueado. Ninguno de los procesos puede continuar su ejecución, ni liberar recursos, y puede ser despertado.

Ejemplo de interbloqueos

Cuatro coches llegan aproximadamente en el mismo instante a un cruce de cuatro caminos. Los cuatro cuadrantes de la intersección son los recursos compartidos sobre los que se demanda control; por tanto, si los coches desean atravesar el cruce, las necesidades de recursos son las siguientes:

- El coche que va hacia el norte necesita los cuadrantes 1 y 2.
- El coche que va hacia el oeste necesita los cuadrantes 2 y 3.
- El coche que va hacia el sur necesita los cuadrantes 3 y 4.
- El coche que va hacia el este necesita los cuadrantes 4 y 1.



La norma más habitual en la carretera es que un coche en un cruce de cuatro caminos debe ceder el paso al coche que está a su derecha. Esta norma funciona si solo hay dos o tres coches en el cruce. Por ejemplo, si solo llegan al cruce los coches del norte y del oeste, el coche del norte esperará hasta que el del oeste pase. Sin embargo, si los cuatro coches llegan al mismo tiempo cada uno se abstendrá de entrar en el cruce, provocando interbloqueo. Si todos los coches ignoran las normas y entran (con cuidado) en el cruce, cada coche obtendrá un recurso (un cuadrante) pero no podrá continuar porque el segundo recurso que necesita ya ha sido invadido por otro coche. De nuevo, se tiene interbloqueo.
.
RECURSOS

Un sistema se compone de un numero finito de recursos que se distribuyen entre varios tipos:
  • Físicos: Ciclo de cpu, espacio en memoria, dispositivos de e/s (impresoras, unidades de cinta, etc.)
  • Lógicos: Ficheros, tablas del sistemas, etc.

Por lo general, una computadora tiene distintos recursos que pueden ser otorgados. Algunos recursos podrán tener varias instancias idénticas, como es el caso de tres unidades de cinta. Si se tienen disponibles varias copias de un recurso, cualquiera de ellas se pude utilizar para satisfacer cualquier solicitud del recurso. Un recurso es cualquier cosa que solo puede ser utilizada por un único proceso en un instante dado.
Los recursos son de dos tipos:
  • Apropiable
  • No apropiables

Un recurso apropiable es aquel que se puede tomar del proceso que lo posee sin efectos dañinos. La memoria es un ejemplo de recurso apropiable.
Por el contrario, un recurso no apropiable, es aquel que no se puede tomar de su poseedor activo sin provocar un fallo de cálculo. Si un proceso comienza a imprimir una salida, se toma la impresora y se le da a otro proceso, el resultado será una salida incomprensible. Las impresoras no son apropiables.

Los interbloqueos se relacionan con los recursos no apropiables. Lo usual es que los bloqueos asociados a recursos apropiables se pueden resolver, mediante la reasignación de recursos de un proceso a otro.

La secuencia de eventos necesaria para utilizar un recurso es:
  • Solicitar el recurso
  • Utilizar el recurso
  • Liberar el recurso

Si el recurso no está disponible cuando se le solicita, el proceso solicitante debe esperar. En algunos sistemas operativos, el proceso se bloquea de manera automática al fallar una solicitud de un recurso y se despierta cuando dicho recurso está disponible. En otros sistemas la solicitud falla con un código de error y el proceso solicitante debe esperar un poco e intentar de nuevo.

Un proceso cuya solicitud de un recurso ha sido denegada entra por lo general en un ciclo, en el cual solicita el recurso, duerme e intenta de nuevo.

Aunque este proceso no está bloqueado, para todos los efectos esta como bloqueado, puesto que no puede hacer ninguna labor útil.
.
CONDICIONES PARA PRODUCIR INTERBLOQUEO
.
En la política del sistema operativo, deben darse tres condiciones para que pueda producirse un interbloqueo:

1- Condición de exclusión mutua: Cada recurso está asignado a un único proceso o está disponible.

2- Condición de posesión y espera: Los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos.

3- Condición de 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.

En la mayoría de los casos, estas condiciones son bastantes necesarias. La exclusión mutua hace falta para asegurar la consistencia de resultados y la integridad de la base de datos. De forma similar, la apropiación no se puede aplicar arbitrariamente y, cuando se encuentran involucrados recursos de datos, debe estar acompañada de un mecanismo de recuperación y reanudación, que devuelva un proceso y sus recursos a un estado previo adecuado, desde el que el proceso puede finalmente repetir sus acciones.

Puede no existir interbloqueo con solo estas tres condiciones. Para que se produzca interbloqueo, se necesita una cuarta condición:

4- Condición de espera circular (o círculo vicioso de espera): 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.

Las tres primeras condiciones son necesarias, pero no suficientes, para que exista interbloqueo. La cuarta condición es, en realidad, 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. El círculo de espera de la condición 4 es irresoluble porque se mantienen las tres primeras condiciones. Las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.[13]

______________________________
[13] Universidad nacional del nordeste facultad de ciencias exactas y naturales y agrimensura. Magíster David Ruiz de la Red Martínez. Sistemas operativos, Principios del interbloqueo. (Noviembre de 2001). Extraído el 24 de octubre de 2008 desde http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/MonogSO/CINTIN02.htm

No hay comentarios: