Condición de exclusión mutua : los procesos exigen un control exclusivo de los recursos que necesitan.

 Condición de espera : los procesos mantienen la posesión de los recursos ya asignados a ellos mientras esperan recursos adicionales.

 Condición de no apropiación : los recursos no pueden arrebatarse a los procesos a los cuales están asignados hasta que termine su utilización.

 Condición de espera circular : existe una cadena circular de procesos en la que cada proceso tiene uno o más recursos que son requeridos por el siguiente proceso en la cadena.

Los resultados de la investigación sobre el bloqueo mutuo han sido satisfactorios en cuanto a que se han encontrado métodos limpios y rápidos para manejar la mayoría de los problemas más comunes. Existen cuatro áreas de interés relacionadas con los interbloqueos que pueden resumirse como prevención, técnicas para evitarlos, detección y recuperación de los mismos.

En la prevención del interbloqueo interesa ajustar el sistema para eliminar toda posibilidad de que ocurra un bloqueo mutuo. La prevención suele funcionar pero sus métodos ocasionan, en general, un aprovechamiento pobre de los recursos. No obstante, estos métodos se utilizan con frecuencia.

Las técnicas que tienen como objetivo evitar el interbloqueo imponen condiciones menos atractivas que en la prevención, para tratar de obtener un aprovechamiento de los recursos. No elimina como las técnicas de prevención todas las posibilidades de que se produzca un bloqueo mutuo, pero se esquiva cuanto está a punto de suceder (algoritmo del banquero de Dijkstra).

Los métodos de detección del interbloqueo es utilizan en sistemas que permiten la ocurrencia de los mismos, ya sea de manera voluntaria o involuntaria. Su objetivo es determinar si ha ocurrido un bloqueo mutuo y saber exactamente cuáles son los procesos y recursos implicados en él.

Los métodos de recuperación están íntimamente ligados a los de detección. Sirven para eliminar los interbloqueos detectados en un sistema para poder seguir trabajando y para que los procesos implicados puedan terminar su ejecución y liberen sus recursos. La recuperación es un problema complejo, en el mejor de los casos, los sistemas se recuperan de un bloqueo mutuo eliminando completamente uno o varios de los procesos implicados. Después, se inician de nuevo los procesos eliminados, perdiéndose la mayor parte o todo el trabajo previo realizado por el proceso.

La estrategia más sencilla es el algoritmo del avestruz : esconder la cabeza bajo tierra y pretender que el problema no existe. La gente reacciona a esta estrategia de distintos modos según su formación. Los matemáticos consideran que es inaceptable y argumentan que los interbloqueos se deben evitar a toda costa. Los ingenieros se interrogan sobre la frecuencia del problema, la frecuencia con el que el sistema se para por otras causas y la importancia de los interbloqueos. Si éstos se presentan de una vez cada cinco años, y los sistemas se paran una vez al mes por errores en el hardware, en el compilador o en el sistema operativo, a casi ningún ingeniero le gustaría tener que sufrir una degradación seria de las prestaciones del sistema para garantizar la eliminación de los interbloqueos.

Por ejemplo, Unix pude sufrir interbloqueos que ni siquiera se detectan, y que, por supuesto, no se eliminan automáticamente. El número total de procesos en el sistema viene determinado por el número de posiciones de la tabla de procesos, que, en definitiva, constituye un recurso limitado. Supongamos ahora que un sistema Unix con 100 posiciones en la tabla de procesos tiene ejecutándose diez programas, cada uno de los cuales ha de crear 12 subprocesos. Después de que cada proceso haya creado otros 9, los 10 procesos originales y los 90 nuevos llenarán por completo la tabla. Los 10 procesos originales se encontrarán ahora en un bucle infinito intentando crear un nuevo proceso sin poder : se ha producido un interbloqueo. Otros ejemplos de recursos que suelen ser limitados son : el número máximo de ficheros que pueden estar abiertos está limitado, el área en el disco para intercambio con memoria principal. En realidad, casi todas las tablas del sistema operativo representan recursos limitados, ¿deberíamos, por tanto, limitar estos recursos para no producir un interbloqueo?

La estrategia UNIX es simplemente desentenderse del problema, suponiendo que la mayoría de los usuarios preferirán un interbloqueo ocasional antes que la imposición de que cada usuario pueda crear un solo proceso, abrir un solo fichero y usar sólo una unidad de lo que sea. Veremos a continuación que se puede adoptar alguna estrategia adecuada que nos permitirá prevenir, evitar o detectar y recuperar situaciones de interbloqueo.

La estrategia empleada con más frecuencia por los diseñadores para tratar el bloqueo mutuo es la prevención. En esta sección se examinan los métodos de prevención, junto con los efectos que tienen sobre los usuarios y los sistemas, sobre todo desde la perspectiva del rendimiento.

Havender (68) llegó a la conclusión de que si falta alguna de las cuatro condiciones necesarias no puede haber un interbloqueo. Este autor sugiere las siguientes estrategias para negar varias de esas condiciones :

Como vemos Havender presenta tres estrategias y no cuatro. Cada una de ellas, está diseñada para negar una de las condiciones necesarias. La primera de estas condiciones, esto es, que los procesos exijan el uso exclusivo de los recursos que requieren, es una condición que no es deseable impedir, porque específicamente queremos permitir la existencia de recursos no compartibles o dedicados.

La primera de las estrategias requiere que los recursos que necesita un proceso sean pedidos de una sola vez. El sistema debe proporcionarlos según el principio de todo o nada. Si está disponible el conjunto de los recursos que necesita un proceso, entonces el sistema puede asignarle todos los recursos y éste seguir su ejecución. Si no está disponible alguno de ellos, el proceso debe esperar. Mientras espera no puede tener ningún recurso. Con esto se elimina la condición de espera y no puede ocurrir un interbloqueo.

Todo esto suena bien, pero puede llevar a un grave desperdicio de recursos. Supongamos que un proceso necesita diez unidades de un determinado recurso para su ejecución. Como debe solicitarlas todas antes de comenzar, los mantendrá en su poder durante toda su ejecución. Pudiera suceder, que el programa únicamente utilice estos recursos al principio de su ejecución, por tanto, los recursos están ociosos el resto del tiempo.

Dividir el programa en varios pasos que se ejecuten de manera relativamente independiente es una técnica empleada con frecuencia para conseguir una mejor utilización de los recursos en estas circunstancias. La asignación de recursos se controla por etapas. Esta solución reduce el desperdicio pero implica mucho trabajo extra tanto en el diseño de las aplicaciones como en al ejecución.

Por otro lado, esta estrategia puede provocar un aplazamiento indefinido, pues los recursos requeridos pueden no estar disponibles todos al tiempo. El sistema podría, entonces, permitir que se fueran acumulando recursos hasta conseguir todos los que necesita un proceso. Pero mientras se acumulan no se pueden asignar a otros procesos y volvemos a infrautilizarlos.

La segunda estrategia de Havender consiste en liberar los recursos que un proceso tiene asignados cuando se le niegan peticiones de recursos adicionales. De esta forma, se anula la condición de no apropiación. Los recursos se pueden quitar al proceso que los tiene antes de que termine su ejecución.

En este caso también existe un costo excesivo. Cuando un proceso libera recursos puede perder todo el trabajo realizado hasta ese momento. El costo puede parecer muy alto, pero la pregunta es : ¿con qué frecuencia ha de pagarse ese precio ? Si ocurre de tarde en tarde, entonces éste parece ser un buen método para prevenir el interbloqueo. Si, por el contrario, es muy frecuente, entonces el costo es sustancial y sus efectos demasiado perjudiciales (por ejemplo, para procesos de alta prioridad o plazo fijo).

Esta estrategia también adolece de aplazamiento indefinido. Un proceso puede aplazarse continuamente mientras pide y libera muchas veces los mismo recursos. Si esto ocurre, el sistema puede verse obligado a eliminar el proceso para que otros puedan ejecutarse.

La tercera estrategia de Havender anula la posibilidad de un espera circular. Como todos los recursos tienen una numeración única y como los procesos deben pedir los recursos en un orden lineal ascendente, es imposible que se presente una espera circular (figura 5.4). Esta estrategia presenta las siguientes dificultades :

Aún presentándose las condiciones para un interbloqueo, todavía es posible evitarlo mediante una asignación cuidadosa de los recursos. Tal vez el algoritmo más famoso para evitar el interbloqueo sea el algoritmo del banquero de Dijkstra (73), cuyo interesante nombre se debe a que atañe a un banquero que otorga préstamos y recibe pagos a partir de una determinada fuente de capital.

En principio, estudiaremos este algoritmo suponiendo que todos los recursos del mismo tipo. Considérese la asignación de una cantidad t, de unidades de cintas idénticas.

Un sistema operativo comparte un número fijo, t, de unidades de cinta entre un número fijo de, p, de procesos. Cada proceso especifica por adelantado el número máximo de unidades de cinta que necesitará durante su ejecución. El sistema operativo aceptará la petición de un usuario si la necesidad máxima de ese proceso no es mayor que t. Un proceso puede obtener o liberar unidades de cinta una a una. Algunas veces un usuario puede verse obligado a esperar para obtener una unidad adicional, pero el sistema operativo garantiza una espera finita. El número real de unidades asignadas a un proceso nunca será superior a la necesidad máxima declarada por ese usuario. Si el sistema operativo es capaz de satisfacer la necesidad máxima del proceso, entonces éste debe garantizar al sistema operativo que las unidades de cinta serán utilizadas y liberadas en un tiempo finito.

Se dice que el estado del sistema es seguro si el sistema operativo puede garantizar que todos los procesos terminan en un tiempo finito. En otro caso, el sistema está en un estado inseguro.

Sea préstamo (i) la representación del préstamo actual de unidades de cinta para el proceso i. Sea máx(i) la necesidad máxima de cintas de un proceso y, por último, sea petición (i) la petición actual del usuario, que es igual a su necesidad máxima menos el préstamo actual. Por ejemplo, el proceso 7 tiene una necesidad máxima de 6 unidades y un préstamo actual de 5, entonces tiene

El sistema operativo controla t unidades de cinta. Sea a el número de unidades de cinta todavía disponibles para asignar. Entonces a es igual a t menos la suma de los préstamos de los usuarios.

El algoritmo del banquero permite la asignación de unidades de cinta a los usuarios solamente cuando la asignación conduzca a estados seguros, y no a estados inseguros. Un estado seguro es una situación tal en la que todos los procesos son capaces de terminar en algún momento. Un estado inseguro es aquel en el cual puede presentarse un bloqueo mutuo.

Supóngase que un sistema tiene doce unidades de cinta y tres procesos que las comparten.

La tabla anterior representa un estado seguro porque el proceso 2 tiene un préstamo de 4 unidades y necesita como máximo 6, o sea, 2 más. El sistema tiene 12 de las cuales 10 están en uso y mantiene 2 disponibles. Si las que están disponible se asignan al proceso 2, cubriendo su demanda máxima, este proceso podrá terminar. Al acabar, devolverá todos los recursos, 6 unidades de cinta, y el sistema podrá asignarlas al proceso 1 y al 3. De esta forma, la clave de un estado seguro es que exista al menos una forma en la que terminen todos los procesos.

Ahora 11 de las 12 unidades de cinta están asignadas y solamente hay una disponible. En este momento, no se puede garantizar que terminen los tres procesos. Si el proceso 1 pide y obtiene la última unidad de cinta y los tres vuelven a solicitar una unidad de cinta más se produciría un bloqueo triple.

Es importante señalar, que un estado inseguro no implica la existencia, ni siquiera eventual, de un interbloqueo. Lo que sí implica un estado inseguro es la posibilidad de que ocurra por una desafortunada secuencia de eventos.

Saber que un estado es seguro no implica que serán seguros todos los estados futuros. La política de asignación de recursos debe considerar cuidadosamente todas las peticiones antes de satisfacerlas. Por ejemplo supongamos la situación que se muestra en la siguiente tabla.

Ahora supóngase que el proceso 3 pide un recurso más. Si el sistema satisface esta petición, el nuevo estado será el que se muestra en la tabla de abajo.

Según vemos, aunque, en principio el sistema no estaba bloqueado, ha pasado de un estado seguro a uno inseguro. La última de las tablas caracteriza un sistema en el cual no puede garantizarse la terminación de todos los procesos. Solamente hay un recurso disponible, pero deben estarlo al menos dos para asegurar que el proceso 2 o el 3 puedan terminar, devolver sus recursos al sistema y permitir que los otros procesos acaben.

La figura 5.5 representa dos matrices. La de la izquierda muestra el número de recursos asignados en ese instante (préstamo actual) a cada uno de los cinco procesos. En la derecha aparece el número de recursos que todavía necesita cada proceso para llevar a cabo su función (petición). Al igual que el caso de un único recurso, los procesos deben comunicar sus necesidades máximas antes de empezar a ejecutarse, de forma que en todo momento el sistema pueda calcular la matriz de la derecha.

Para describir los recursos existentes en el sistema, los que están en posesión y los que están disponibles, emplearemos tres vectores como los siguientes : E =(6342), P=(5322) y D=(1020). E indica que el sistema tiene 6 unidades de cinta, 3 trazadores, 4 impresoras y 2 cdrom. De ellos se están utilizando 5 unidades de cinta, tres trazadores gráficos, dos impresoras y dos cdrom. Esto se puede deducir sin más que sumar las cuatro columnas de recursos en préstamo de la matriz izquierda. El vector de recursos disponibles es simplemente la diferencia ente lo que el sistema tiene y lo que está usando en ese momento.

Ahora estamos en condiciones de describir en qué consiste el algoritmo de comprobación de estado seguro :

En el caso de que se pueda seleccionar más de un proceso en el paso 1, la elección sería indiferente: en cualquier caso, el conjunto de recursos disponibles aumenta o, en el peor de los casos, se queda igual.

Volviendo al ejemplo de la figura 5.5 . El estado actual es seguro. Supongamos que el proceso B solicita la impresora. Dado que el estado resultante es todavía seguro, esta petición puede concederse (el proceso D puede terminar, seguido por los procesos A o E y a continuación el resto).

Imaginemos ahora que, después de que B obtiene una de las dos impresoras restantes, E solicita la última impresora. Si se le concede esta petición, el vector de recursos disponibles se reduciría a (1 0 0 0), situación que produce interbloqueo. Por lo tanto, la petición de E debe posponerse de momento.

Ahora debe estar claro cómo opera el algoritmo del banquero de Dijkstra cuando asigna recursos. Están permitidas las condiciones de espera circular, espera y no apropiación, pero los procesos sí exigen el uso exclusivo de los recursos que requieren. Los procesos pueden conservar recursos mientras piden y esperan recursos adicionales y los recursos no pueden arrebatarse a los procesos que los tienen. Los procesos facilitan el trabajo al sistema pidiendo un solo recurso a la vez. El sistema puede satisfacer o rechazar cada petición. Si una petición es rechazada, el proceso conserva los recursos que ya tiene asignados y espera un tiempo finito a que se satisfaga la petición. El sistema sólo satisface peticiones que llevan a estados seguros. Una petición que condujese a un estado inseguro se rechazaría repetidamente hasta que pueda quedar satisfecha. Como el sistema se mantiene en un estado seguro, tarde o temprano (en un tiempo finito) todas las peticiones podrán ser atendidas y los procesos terminarán.

El algoritmo del banquero es interesante porque ofrece una forma de asignar los recursos que evita el interbloqueo. Permite ejecutar procesos que tendrían que esperar seguramente con alguna de las estrategias de prevención. Sin embargo, tiene varios defectos importantes :

En resumen, los métodos descritos anteriormente en el apartado de prevención son demasiado restrictivos, mientras que los de evitación que acabas de estudiar requieren información de la que, generalmente, no se dispone.

La detección del bloqueo mutuo es el proceso de determinar si realmente existe un interbloqueo e identificar los procesos y recursos implicados en él. Los algoritmos de detección determinan por lo general si existe una espera circular.

El empleo de algoritmos de detección del 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, ¿el gasto extra debido a los algoritmos de detección del bloqueo mutuo se justifica con los ahorros potenciales debidos a la localización y solución de los interbloqueos?

Para facilitar la detección de interbloqueos, se utilizará una notación en la que un grafo dirigido indica las asignaciones y peticiones de recursos. Los cuadrados representan procesos; los círculos grandes, clases de dispositivos idénticos; los círculos pequeños de color rojo en el interior de los grandes indican el número de dispositivos de cada clase. Por ejemplo, si un círculo grande etiquetado como R1 contiene tres círculos pequeños, significa que ya tres recursos del tipo R1 disponibles para asignación en este sistema.

La figura 5.6 muestra las relaciones que pueden indicarse en una gráfica de asignación y petición de recursos. Por ejemplo, en (a) el proceso P1 está pidiendo un recurso del tipo R1. La flecha que parte de P1 toca solamente el extremo del círculo grande, lo cual implica que se está estudiando la petición. En (b), el proceso P2 tiene asignado un recurso del tipo R2 (del cual existen dos unidades). La flecha va del círculo pequeño que se encuentra dentro del círculo grande R2 al cuadrado P2. En (c), el recurso R3 ha sido solicitado por el proceso P3, pero ya se ha asignado al proceso P4. Por último, en (d), se representa un interbloqueo. El proceso P5 tiene el recurso R5 que está siendo solicitado por el proceso P6, que tiene el recurso R4 que está siendo solicitado por el proceso P5 (una espera circular).

Una técnica útil para detectar los interbloqueos consiste en ir reduciendo una gráfica determinando los procesos que pueden completar su ejecución. Si pueden atenderse las peticiones de recursos de un proceso, se dice que la gráfica puede ser reducida por ese proceso. Esta reducción es equivalente a mostrar la gráfica como si el proceso hubiese acabado y hubiera devuelto los recursos al sistema. Si una gráfica puede ser reducida por todos sus procesos, entonces no hay interbloqueo. Si una gráfica no puede ser reducida por todos sus procesos, los procesos irreductibles constituyen el conjunto de procesos en bloqueo mutuo de la gráfica (figura 5.7).

Cuando se ha bloqueado un sistema, el interbloqueo debe romperse mediante la eliminación de una o más de las condiciones necesarias. Por lo general, varios procesos perderán una parte o la totalidad del trabajo efectuado, pero el precio pagado puede ser pequeño, en comparación con las consecuencias de permitir que el sistema siga bloqueado. La recuperación después de un bloqueo mutuo se complica por varias razones :

En los sistemas actuales la recuperación se suele realizar eliminado un proceso y arrebatándole sus recursos. Por lo general, el proceso eliminado se pierde pero ahora es posible concluir los procesos restantes. Algunas veces es necesario eliminar varios procesos hasta que se hayan liberado los recursos suficientes para que terminen los procesos restantes.

Los procesos pueden eliminarse de acuerdo con algún orden de prioridad. También existen dificultades para ello :

Parece ser que el enfoque más deseable para la recuperación después de un bloqueo mutuo sería un mecanismo efectivo de suspensión/reanudación. Ello implicaría suspender temporalmente los procesos y reanudarlos después sin pérdida de trabajo productivo. Para ello sería deseable la posibilidad de especificar puntos de verificación/reinicio. De este modo, se facilita la suspensión/reanudación, que se hará desde el último punto de verificación (es decir, la última grabación del estado del sistema). Pero muchos sistemas de aplicación se diseñan sin aprovechar las ventajas de las funciones de punto de verificación/reinicio. Por lo general, se requiere un esfuerzo consciente por parte de los diseñadores para incorporar la verificación/reinicio, y a menos que las tareas requieran muchas horas de ejecución, su uso es poco común.