Maekawa, Oldehoeft y Oldehoeft definen el interbloqueo como el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o se comunican uno con otro. A diferencia de otros problemas en la administración de procesos concurrentes, no existe solución eficiente a nivel general.

Todos los interbloqueos involucran necesidades de recursos conflictivas entre dos o mas procesos. La siguiente figura ilustra esta situación, involucrando a dos procesos y a dos recursos.

Los sistemas de cómputo tienen muchos recursos que sólo pueden ser utilizados por un proceso a la vez. Si dos procesos utilizaran en forma simultánea la impresora, el resultado sería un desastre.

En muchas aplicaciones, un proceso necesita el acceso exclusivo no sólo a un recurso, sino a varios. Un proceso que copie un archivo mayor que un disco desde una cinta magnética hacia la impresora necesita el acceso exclusivo a la unidad de cinta y a la impresora al mismo tiempo. En un sistema con un único proceso, éste puede tener el acceso a todos los recursos que necesite y realizar su trabajo.

Sin embargo, en un sistema con multiprogramación, pueden surgir serios problemas. Supongamos, por ejemplo, que dos procesos desean imprimir cada uno un enorme archivo en cinta. El proceso A solicita el permiso para utilizar la impresora, el cual se le concede. Es entonces cuando el proceso B solicita permiso para utilizar la unidad cinta y se le otorga. El proceso A solicita entonces la unidad de cinta, pero la solicitud es denegada hasta que B la libere. Por desgracia, en este momento, en vez de liberar unidad de cinta, B solicita la impresora. Los procesos se bloquean en ese momento y permanecen así por siempre. Esta situación se llama bloqueo (deadlock).

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

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

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.

Condición de espera circular. Debe existir una cadena circular de dos ó más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena.

Estas cuatro condiciones deben estar presentes para que ocurra un bloqueo. Si una de ellas está ausente, no es posible el bloqueo.

En los sistemas operativos, se puede definir el problema del interbloqueo como la situación de un conjunto de procesos que están en espera y que ninguno de ellos tiene las condiciones necesarias para continuar su ejecución. Veamos el siguiente ejemplo.

En una carretera de dos direcciones, donde en un determinado cruce con la vía del ferrocarril, se ha construido un puente que sólo deja pasar vehículos en un sentido. El bloqueo ocurre cuando dos carros intentan pasar por el puente al mismo tiempo.

Una manera de resolver el bloqueo es: el conductor situado, en uno de los extremos es lo suficientemente educado que deja pasar en primer lugar al del otro extremo y luego pasa él.

El ejemplo anterior nos muestra como sucede el interbloqueo en nuestra vida diaria.

Las estrategias de prevención de interbloqueo son muy conservadoras; 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. 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 ser presente y que los recursos del sistema que han sido asignados, se liberarán en el momento que otro proceso lo requiera.

Una comprobación para interbloqueo puede hacerse con igual o menor frecuencia que cada solicitud de recursos, dependiendo de que tan probable es que ocurra un interbloqueo. Comprobar cada solicitud de recursos tiene dos ventajas: Conduce a la detección temprana y el algoritmo es simple, de manera relativa porque se basa en cambios crecientes al estado del sistema. Además, las comprobaciones frecuentes consumen un tiempo considerable de procesador.

El empleo de algoritmos de detección de interbloqueo implica cierto gasto extra durante la ejecución. Así pues, se presenta de nuevo la cuestión de costeabilidad, tan habitual en los sistemas operativos. Los algoritmos de detección de interbloqueo determinan por lo general si existe una espera circular.

Usaremos una variante del grafo de asignación de recursos, llamado grafo de espera. Podemos obtener este grafo a partir del grafo de asignación de recursos, eliminando los nodos correspondientes al recurso y uniendo los arcos de forma que habrá un arco del proceso Pi al proceso Pj, si Pj tiene un recurso que Pi ha solicitado. Existirá un interbloqueo si y solo si hay un ciclo en el grafo resultante.

Para detectar un interbloqueo, el sistema necesita mantener el grafo de espera y periódicamente invocar un algoritmo que busque un ciclo en el grafo.

Este algoritmo de detección emplea estructuras de datos que varían con el tiempo, muy similares a las que se unas en el algoritmo del banquero:

Variable	Contenido
Disponible [m]	Número de recursos disponible de cada tipo
Asignado [n,m]	Cantidad de recursos asignados a los procesos
Petición [n,m]	Petición o solicitud actual de cada proceso

Mientras haya un i tal que Acabado [i]:=False y Petición [i]<=Trabajo Trabajo:= Trabajo + Asignado[i]

El algoritmo de detección escrito se limita a investigar cada una de las posibles secuencias de asignación para los procesos que quedan por terminar. Aquellos procesos para los que Acabado[i] tengan un valor de falso, formarán parte de un interbloqueo.

Este algoritmo se puede invocar cada vez que ocurre una petición de recursos y no puede ser atendida de inmediato. Otra alternativa es invocarlo cada cierto intervalo de tiempo previamente establecido por el sistema.

Otro enfoque para resolver el problema del interbloqueo, el cual difiere en formas sutil de la prevención, es la anulación. En la prevención, se restringen solicitudes de recursos para impedir la aparición de, por lo menos, una de las cuatro condiciones de interbloqueo. Esto se logra, de manera indirecta, impidiendo una de las tres condiciones de políticas necesarias (exclusión mutua, conservar y esperar, no otorgar preferencias) o en forma directa, al impedir la espera circular. Esto conduce a un uso ineficiente de recursos y a la ejecución ineficiente de procesos. La anulación del interbloqueo, por otra parte, permite las tres condiciones necesarias pero elige con sensatez, a fin de asegurar que el punto de interbloqueo no se alcance nunca. Por lo tanto, la anulación permite más concurrencia que la prevención. Con la anulación del interbloqueo se decide en forma dinámica si la solicitud de asignación de recursos actual, si se concede, tiene el potencial para conducir a un interbloqueo. Por lo tanto, la anulación del interbloqueo requiere el conocimiento de solicitudes futuras de recursos del proceso.

Por lo tanto, los dos enfoques que se encuentran para la anulación del interbloqueo son:

§ No conceder una solicitud de recursos creciente a un proceso si su asignación podría conducir a un interbloqueo.

La estrategia básica de la prevención del interbloqueo consiste, a grandes rasgos, en diseñar su sistema de manera que esté excluida, a priori, la posibilidad de interbloqueo.

Si ningún recurso se puede asignar de forma exclusiva, no se produciría interbloqueo. Sin embargo, existen recursos para los que no es posible negar la condición de exclusión mutua, pues la propia naturaleza de los mismos obliga a que sean utilizados en exclusión mutua.

No obstante, es posible eliminar esta condición en algunos recursos. Por ejemplo, una impresora es un recurso no compatible pues si se permite que dos procesos escriban en la impresora al mismo tiempo, la salida resultara caótica. Pero con el spooling de salida varios procesos pueden generar salida al mismo tiempo. Puesto que el spooler nunca solicita otros recursos, se elimina el bloqueo originado por la impresora.

El inconveniente es que no todos los recursos pueden usarse de esta forma (por ejemplo, la tabla de procesos no se presenta al spooling y, además, la implementación de esta técnica puede introducir nuevos motivos de interbloqueo, ya que el spooling emplea una zona de disco finita.

La condición de retención y espera puede prevenirse exigiendo que todos los procesos soliciten todos los recursos que necesiten a un mismo tiempo y bloqueando el proceso hasta que todos los recursos puedan concederse simultáneamente. Esta solución resulta ineficiente por dos factores:

En primer lugar, un proceso puede esta suspendido durante mucho tiempo, esperando que concedan todas sus solicitudes de recursos, cuando de hecho podría haber avanzado con sólo algunos de los recursos.

Y en segundo lugar, los recursos asignados a un proceso pueden permanecer sin usarse durante periodos considerables, tiempo durante el cual se priva del acceso a otros procesos.

Esta puede ser obviamente denegada permitiendo la interrupción con prioridad, esto es, autorizando al sistema para revocar la prioridad de ciertos recursos de los procesos bloqueados. Dado que la interrupción con prioridad es involuntaria desde el punto de vista del proceso afectado, el sistema operativo debe encargarse de guardar el estado y restaurarlo cuando el proceso en cuestión es reanudado después.

La interrupción con prioridad es posible para ciertos tipos de recursos, tal como la CPU y la memoria principal, ya que la porción de CPU del estado de proceso es guardada rutinariamente durante la operación de conmutación del proceso y los contenidos de las páginas de memoria interrumpidos se pueden pasar al almacenamiento secundario. Sin embargo, algunos tipos de recursos, como archivos principalmente actualizados, no pueden ser interrumpidos con prioridad sin corromper el sistema. Por lo tanto la interrupción con prioridad es posible sólo para ciertos tipos de recursos, y se puede aplicar cuando los beneficios de la prevención del interbloqueo superan el costo de las operaciones de guardado y recuperación del estado. Sin embargo, ya que algunos recursos, no pueden ser interrumpidos con prioridad seguramente, este método solo no puede, en general, porporcionar la prevención completa del interbloqueo.

Cuando se ha detectado que existe un interbloqueo, podemos actuar de varias formas. Una posibilidad es informar al operador que ha ocurrido un interbloqueo y dejar que el operador se ocupe de él manualmente. La otra posibilidad es dejar que el sistema se recupere automáticamente del interbloqueo. Dentro de esta recuperación automática tenemos dos opciones para romper el interbloqueo: Una consiste en abortar uno o más procesos hasta romper la espera circular, y la segunda es apropiar algunos recursos de uno o más de los procesos bloqueados.

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.

Los procesos pueden eliminarse de acuerdo con algún orden de prioridad, aunque es posible que no existan prioridades entre los procesos bloqueados, de modo que el operador necesita tomar una decisión arbitraria para decidir que procesos se eliminarán.

Está forma de recuperación consiste en avisarle al administrador o al operador del sistema que se ha presentado un interbloqueo, y será el administrador el que solucione dicho problema de la manera más conveniente posible, de modo que su decisión no afecte demasiado a al usuario del proceso en conflicto, y sobre todo que no afecte a los demás usuarios del sistema.

Para eliminar interbloqueos abortando un proceso, tenemos dos métodos; en ambos, el sistema recupera todos los recursos asignados a los procesos terminados.

1 ) Abortar todos los procesos interbloqueados. Esta es una de las soluciones más comunes, adoptada por Sistemas Operativos. Este método romperá definitivamente el ciclo de interbloqueo pero con un costo muy elevado, ya que estos procesos efectuaron cálculos durante mucho tiempo y habrá que descartar los resultados de estos cálculos parciales, para quizá tener que volver a calcularlos más tarde.

2 ) Abortar un proceso en cada ocasión hasta eliminar el ciclo de interbloqueo. 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 enmucho tiempo de procesamiento adicional.

Quizá no sea fácil abortar un proceso. Si éste se encuentra actualizando un archivo, cortarlo a la mitad de la operación puede ocasionar que el archivo quede en un 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. Se trata sobre todo de una cuestión económica, debemos abortar los procesos que nos representen el menor costo posible. Existen muchos factores que determinan el proceso que se seleccionará, siendo los principales los siguientes:

2 ) Tiempo de procesador usado. Se abortará aquel proceso que haya utilizado menos tiempo el procesador, ya que se pierde menos trabajo y será más fácil recuperarlo más tarde.

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. Es conveniente eliminar a aquellos procesos que necesitan un gran número de recursos.

5 ) Facilidad de suspención/reanudación.Se eliminarán aquellos procesos cuyo trabajo perdido sea más fácil de recuperar.

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

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

La detección y recuperación es la estrategia que a menudo se utiliza en grandes computadoras, especialmente sistemas por lote en los que la eliminación de un proceso y después su reiniciación suele aceptarse.