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.
Todos los interbloqueos suponen necesidades contradictorias de recursos por parte de dos o más procesos.
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.
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. El interbloque se puede definir entonces de la siguiente forma: 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
PREVENCIÓN DEL 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.
Los métodos para prevenir el interbloqueo son de dos tipos:
- Los métodos indirectos que consisten en impedir la aparición de alguna de las tres condiciones necesarias para que se de el interbloqueo.
- Los métodos directos que consisten en evitar la aparición del circulo vicioso de espera.
Exclusión mutua
Si ningún recurso se puede asignar de forma exclusiva, no se producirá interbloqueo. Sin embargo, existen recursos para los que no es posible negar la condición de exclusión mutua. No obstante, es posible eliminar esta condición en algunos procesos. 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 resulta 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)
No apropiación
La condición de no apropiación puede prevenirse de varias formas. Primero, si a un proceso que retiene ciertos recursos se le deniega una nueva solicitud, dicho proceso deberá liberar sus recursos anteriores y solicitarlos d eneuvo, cuando sea necesario, junto con el recurso adicional. Por otra parte, si un proceso solicita un recurso que actualmente está retenido por otro proceso, el sistema operativo debe expulsar al segundo proceso y exigirle que libere sus recursos. Este último esquema evitará el interbloqueo sólo si No hay dos procesos que posean la misma prioridad.
Esta técnica es práctica sólo cuando se aplica a recursos cuyo estado puede salvarse y restaurarse más tarde de una forma fácil, como es el caso de un procesador.
PREDICCIÓN DEL INTERBLOQUEO
Una forma de resolver el problema del interbloqueo, que se diferencia sutilmente de la prevención, es la predicción del interbloqueo. En la prevención de interbloqueo, se obligaba a las solicitudes de recursos a impedir que sucediera , por lo menos, alguna de las cuatro condiciones de interbloqueo. Esto se hace indirectamente, impidiendo la aparición de una de las tres condiciones necesarias (exclusión mutua, retención y espera, no apropiación) o directamente, impidiendo la aparición de un circulo viciosos de espera. Se llega así a un uso ineficiente de los recursos y una ejecución ineficiente de los procesos. Con predicción del interbloqueo, por otro lado, se pueden alcanzar las tres condiciones necesarias, pero se realizan elecciones acertadas para asegurar que nunca se llega al punto de interbloqueo. La predicción, por lo tanto, permite más concurrencia que la prevención.
Con predicción del interbloqueo, se decide dinámicamente si la petición actual de asignación de un recurso podría, de concederse, llevar potencialmente a un interbloqueo. La predicción del interbloqueo necesita, por lo tanto, conocer las peticiones futuras de recursos.
Enfoques para la predicción del interbloqueo:
- No iniciar un proceso si sus demandas pueden llevar a interbloqueo.
- No conceder una solicitud de incrementar los recursos de un proceso si esta asignación puede llevar a interbloqueo.
Negativa de asignación de recursos
La estrategia de negar la asignación de recursos, denominada algoritmo del banquero, fue propuesta por primera vez por Hijastra, que usó este nombre por la analogía de este problema con el de un banco cuando los clientes quieren obtener dinero prestado. Los clientes sería los procesos y el dinero a prestar, los recursos. Si se enuncia de esta manera, el banco tiene una reserva limitada de dinero para prestar y un conjunto de clientes con líneas de crédito. Un cliente puede elegir pedir dinero a cargo de la línea de crédito en un instante dado y no hay garantía de que el cliente realice ninguna reposición hasta después de sacar la cantidad máxima. El banquero puede rechazar un préstamo a un cliente si hay riesgo de que el banco no tenga fondos suficientes para hacer préstamos futuros que los clientes finalmente repondrán.
Para empezar se definen los conceptos de estado y de estado seguro. Considérese un sistema con un número fijo de procesos. Así pues, el estado estará formado por los dos vectores, Recursos y Disponible, y las dos matrices, Demanda y Asignación, definidas anteriormente. Un estado seguro es un estado en el cual existe al menos una secuencia que no lleva al interbloqueo ( es decir, todos los procesos pueden ejecutarse hasta el final). Un estado inseguro es, naturalmente, un estado que no es seguro.
El algoritmo del banquero usa una tabla de recursos para saber cuántos recursos tiene de todo tipo. También requiere que los procesos informen del máximo de recursos que va a usar de cada tipo. Cuando un proceso pide un recurso, el algoritmo verifica si asignándole ese recurso todavía le quedan otros del mismo tipo para que alguno de los procesos en el sistema todavía se le pueda dar hasta su máximo. Si la respuesta es afirmativa, el sistema se dice que está en 'estado seguro' y se otorga el recurso. Si la respuesta es negativa, se dice que el sistema está en estado inseguro y se hace esperar a ese proceso.
DETECCIÓN DEL INTERBLOQUEO
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. Con la detección del interbloqueo, se concederán los recursos que los procesos necesiten siempre que sea posible. Periódicamente, el S. O. ejecuta un algoritmo que permite detectar la condición de circulo 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.
Algoritmo de detección del interbloqueo
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.
Recuperación de 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.
Recuperación Manual
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.
Abortar los Procesos
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 interbloqueos. 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 en mucho 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:
- La prioridad del proceso. Se elimina el proceso de menor prioridad.
- 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.
- Tipos de recursos utilizados. Si los recursos son muy necesarios y escasos será preferible liberarlos cuanto antes.
- Cuántos recursos más necesita el proceso. Es conveniente eliminar a aquellos procesos que necesitan un gran número de recursos.
- Facilidad de suspensión / reanudación. Se eliminarán aquellos procesos cuyo trabajo perdido sea más fácil de recuperar.
Apropiación de Recursos
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:
- Selección de la víctima
- Retroceso
- Bloqueo indefinido
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.
