Nombre: Roberto Valladolid.

INTERBLOQUEOS

En un entorno multiprogramación, varios procesos pueden competir por un numero finito de recursos. Un proceso solicita recursos y, si los recursos no están disponibles en ese momento, el proceso pasa a estado de espera.

Es posible que algunas veces, un proceso en espera no pueda nunca cambiar de estado, por que los recursos que ha utilizado estén ocupados por otros procesos que a su vez estén esperando otros recursos. Cuando se produce una situación como esta, se dice que ha ocurrido un interbloqueo.

El interbloqueo se puede definir como el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros. A diferencia de otros problemas de la gestión concurrente de procesos, no existe una solución eficiente para el caso general.

Caracterización de los interbloqueos.

En un interbloqueo, los procesos nunca terminan de ejecutarse y los recursos del sistema están ocupados, lo que impide otros trabajos, a continuación algunos detalles de características.

Condiciones Necesarias:

Una situación de interbloqueo puede surgir si se dan simultáneamente las cuatro condiciones siguientes en un sistema.

1.     Exclusión mutua: Al menos un recurso debe estar en modo no compartido; es decir, solo un proceso puede usarlo cada vez. Si otro proceso solicita otro recurso, el proceso solicitante tendrá que esperar hasta que el recurso sea liberado.

2.     Retención y espera: Un proceso debe estar reteniendo al menos un recurso y esperando para adquirir otros recursos adicionales que actualmente estén retenidos por otros procesos.

3.     Sin desalojo: Los recursos no pueden ser desalojados; es decir u  recurso solo puede ser liberado voluntariamente por el proceso que le retiene, después de que dicho proceso haya completado su tarea.

4.     Espera Circular: Debe existir un conjunto {P0,P1,…,Pn} de procesos en espera, tal que P0 este esperando a un recurso retenido por P1, P1 esté esperando a un recurso retenido por P2, …, Pn-1 este esperando a un recurso retenido por Pn’ y Pn esté esperando a un recurso retenido por P0. Los procesos interbloqueados forman una cadena circular de modo que cada proceso retiene uno o más de los recursos que son solicitados por el siguiente proceso de la cadena.

Grafo de asignación de recursos

Los interbloqueos pueden definirse de forma mas precisa mediante un grafo dirigido, que se llama grafo de asignación de recursos del sistema. Este grafo consta de un conjunto de vértices V y de un conjunto de aristas E.

Métodos para tratar los interbloqueos

En general, podemos abordar el problema de los interbloqueos de una de tres formas:

·         Podemos emplear un protocolo para impedir o evitar los interbloqueos, asegurando que el sistema nunca entre en estado de interbloqueo.

·         Podemos permitir que el sistema entre en estado de interbloqueo, detectarlo y realizar una recuperación.

·         Podemos ignorar el problema y actuar como si nunca se produjeran interbloqueos en el sistema.

Estos métodos básicos se pueden combinar, permitiéndonos seleccionar un método óptimo para cada clase de recurso existente en el sistema.

La prevención de interbloqueos proporciona un conjunto de métodos para asegurar que al menos una de las condiciones necesarias no pueda cumplirse. Estos métodos evitan los interbloqueos restringiendo el modo en que se pueden realizar las solicitudes.

Si un sistema no emplea un algoritmo de prevención de interbloqueo ni un algoritmo de evasión, entonces puede producirse una situación de interbloqueo.

El sistema debe disponer de métodos de recuperación manual para tales condiciones y puede, simplemente, usar esas mismas técnicas para recuperarse de los interbloqueos.

Prevención de interbloqueos

Estas cuatro condiciones no se cumpla, podemos prevenir la aparición de interbloqueos.

Exclusión mutua

La condición de exclusión mutua se aplica a los recursos que no pueden ser compartidos. Un proceso no necesita esperar nunca para acceder a un recurso compartible. Sin embargo, en general, no podemos evitar los interbloqueos negando la condición de exclusión mutua, ya que algunos recursos son intrínsecamente no compartibles.

Retención y espera

Para asegurar que la condición de retención y espera nunca se produzca en el sistema, debemos garantizar que, cuando un proceso solicite un recurso, el proceso no esté retenido ningún otro recurso. Podemos implementar este mecanismo requerimiento que las llamadas al sistema que solicitan los recursos para un proceso precedan a todas las demás llamadas al sistema.

Una posible alternativa sería un protocolo que permitiera a un proceso solicitar recursos solo cuando no tenga ninguno retenido.

Ambos protocolos tienen dos desventajas importantes. Primero, la tasa de utilización de los recursos puede ser baja, dado que los recursos pueden asignarse pero no utilizarse durante un periodo largo de tiempo. La segunda desventaja es que puede producirse el fenómeno de inanición, un proceso que necesite varios recursos muy solicitados puede tener que esperar de forma indefinida, debido a que al menos uno de los recursos que necesita está siempre asignado a algún otro proceso.

Sin desalojo

La tercera condición necesaria para la aparición de interbloqueos es que los recursos que ya  están asignados no sean desalojados. Para impedir que se cumpla esta condición, podemos usar el protocolo siguiente: si un proceso esta retenido varios recursos y solicita otro recurso que no se le puede asignar de forma inmediata, entonces todos los recursos actualmente retenidos se desalojan.

Espera circular

Una forma de garantizar que esta condición nunca se produzca es imponer una ordenación total de todos los tipos de recursos y requerir que cada proceso solicite sus recursos en un orden creciente de enumeración.

Los recursos se clasifican por categorías y los procesos solo pueden solicitar los recursos en orden creciente, además todos los recursos de una categoría deben ser solicitados a la vez. Una vez que un proceso ha solicitado un recurso de una categoría, no puede solicitar otro de una categoría inferior.

Evasión de interbloqueos

Esas restricciones aseguran que al menos una de las condiciones necesarias para que haya interbloqueo no se produzca y, por tanto, que no puedan aparecer interbloqueos. Sin embargo, esta técnica de prevención de interbloqueos tiene algunos posibles efectos colaterales, como son una baja tasa de utilización de los dispositivos y un menor rendimiento del sistema.

Un método alternativo para evitar los interbloqueos consiste en requerir información adicional sobre como van a ser solicitados los recursos. Cada solicitud requiere que, para tomar la correspondiente decisión, el sistema considere los recursos actualmente disponibles, los recursos actualmente asignados a cada proceso y las solicitudes y liberaciones futuras de cada proceso.

El modelo más simple y útil requiere que cada proceso declare el número máximo de recursos de cada tipo que puede necesitar. El algoritmo de evasión de interbloqueos examina dinámicamente el estado de asignación de cada recurso con el fin de asegurar que nunca se produzca una condición de espera circular. El estado de asignación del recurso esta definido por el número de recursos disponibles y asignados y la demanda máxima de los procesos.

Estado seguro

Un estado es seguro si el sistema puede asignar recursos a cada proceso en determinado orden sin que eso produzca un interbloqueo. Un sistema está en estado seguro solo si existe lo que se denomina una secuencia segura. Un estado seguro implica que no puede producirse interbloqueo, a la inversa, todo estado de interbloqueo es inseguro, sin embargo, no todos los estados inseguros representan un interbloqueo.

Un estado inseguro puede llevar a que aparezca un interbloqueo, siempre y cuando el estado sea seguro, el sistema operativo podrá evitar los estados inseguros, el sistema operativo no puede impedir que los procesos soliciten recursos de tal modo que se produzca un interbloqueo, el comportamiento de los procesos es el que controla los estados inseguros.

Detección de interbloqueos

Las estrategias de prevención de interbloqueo; resuelven el problema limitando el acceso a recursos e imponiendo restricciones sobre los procesos. En cambio, las estrategias de detección de interbloqueo, no limitan el acceso a recursos ni restringen las acciones del proceso. Con la detección del interbloqueo, se concederán los recursos  que los procesos necesiten siempre que sea posible.  Periódicamente, el Sistema Operativo  ejecuta un algoritmo que permite detectar la condición de círculo vicioso de espera.

La detección del interbloqueo es el proceso de determinar si realmente existe un interbloqueo e identificar los procesos  y recursos implicados en él. Una posibilidad detectar un interbloqueo es monitorear cada cierto tiempo el estado de los recursos. Cada vez que se solicita o se devuelve un recurso, se actualiza el estado de los recursos y se hace una verificación para observar si existe algún ciclo.

Este método está basado en suponer que un interbloqueo no se presente y que los recursos del sistema que han sido asignados, se liberarán en el momento que otro proceso lo requiera.

Si un sistema no emplea ni algoritmos de prevención ni de evasión de interbloqueos, entonces puede producirse una situación de interbloqueo. En este caso, el sistema debe proporcionar:

·        Un algoritmo que examine el estado del sistema para determinar si se ha producido un interbloqueo.

·        Un algoritmo para recuperarse del interbloqueo.

Una sola instancia de cada tipo de recurso

Si todos los recursos tienen una única instancia, entonces podemos definir un algoritmo de detección de interbloqueos que utilice una variante del grafo de asignación de recursos, denominada grafo de espera.

Varias instancias de cada tipo de recurso

El esquema del grafo de espera no es aplicable a los sistemas de asignación de recursos con múltiples instancias de cada tipo de recurso.

Available: Un vector de longitud m que indica el numero de recursos disponibles de cada tipo.

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

Request: Una matriz n * m que especifica la solicitud actual efectuada por cada proceso.

Utilización del algoritmo de detección

Los interbloqueos se producen solo cuando algún proceso realiza una solicitud que no se puede conceder de forma inmediata, esta solicitud puede ser la solicitud final que complete una cadena de procesos en espera. Si se invoca el algoritmo de detección de interbloqueo para cada solicitud de recursos, esto dará lugar a una considerable sobrecarga en el tiempo de uso del procesador.

Recuperación de un Interbloqueo

Cuando el algoritmo de detección determina que existe un interbloqueo, tenemos varias alternativas. Una posibilidad es informar al operador de que se ha producido un interbloqueo y dejar que lo trate de forma manual.

La recuperación después de un interbloqueo se complica porque puede no estar claro que el sistema se haya bloqueado. Las mayorías de los Sistemas Operativos no tienen los medios suficientes para suspender un proceso, eliminarlo del sistema y reanudarlo más tarde.

Actualmente, la recuperación se suele realizar eliminando un proceso y quitándole sus recursos. El proceso eliminado se pierde, pero gracias a esto ahora es posible terminar. Algunas veces es necesario, eliminar varios procesos hasta que se hayan liberado los recursos necesarios para que terminen los procesos restantes.

Terminación de procesos

En ambos métodos, el sistema reclama todos los recursos asignados a los procesos terminados.

Interrumpir todos los procesos interbloqueados: Claramente, este método interrumpirá el ciclo de interbloqueo, pero a un precio muy alto.

Interrumpir un proceso cada vez hasta que el ciclo de interbloqueo se elimine: Este método requiere una gran cantidad de trabajo adicional, ya que después de haber interrumpido cada proceso hay que invocar un algoritmo de detección de interbloqueos para determinar si todavía hay procesos en interbloqueo.

Hay muchos factores que influyen en que procesos seleccionar, entre los que se incluyen:

1.      La prioridad del proceso

2.     Durante cuanto tiempo ha estado el proceso ejecutándose y cuanto tiempo de adicional necesita el proceso para completar sus tareas.

3.      Cuantos y que tipo de recursos ha utilizado el proceso.

4.     Cuantos más recursos necesita el proceso para completarse.

5.     Cuantos procesos hará falta terminar.

6.     Si se trata de un proceso interactivo o de procesamiento por lotes.

Apropiación de recursos

Para eliminar los interbloqueos utilizando el método de apropiación de recursos, desalojamos de forma sucesiva los recursos de los procesos y asignamos dichos recursos a otros procesos hasta que el ciclo de interbloqueo se interrumpa.

Si se necesita el desalojo para tratar los interbloqueos, entonces debemos abordar tres cuestiones:

1.      Selección de una victima

2.      Anulación

3.      Inanición