2.14 PREVENCION, DETECCION Y PREDICCION EN UN INTERBLOQUEO PREVENCION

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 condicion de exclusión mutua. No obstante, es posible eliminar esta condicion 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 recuersos, 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, ademas, la implementacion de esta técnica puede introducir nuevos motivos de interbloqueo, ya que el spooling emplea una zona de disco finita). Retencion y espera La condicion de retencion 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 solucion resulta ineficiente por dos factores: - En primer lugar, un proceso puede estar suspendido durante mucho tiempo, esperando que concedan todas sus solicitudes de recursos, cuando de hecho podria haber avanzado con solo 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. 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 esta retenido por otro proceso, el sistema operativo debe expulsar al segundo proceso y exigirle que libere sus recursos. Este ultimo esquema evitará el interbloqueo sólo si nho 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 facil, como es el caso de un procesador. Circulo vicioso de espera La condición del circulo vicioso de espera puede prevenirse definiendo una ordenación lineal de los tipos de recursos. Si a un proceso se le han asignado recursos de tipo R, entonces sólo podrá realizar peticiones posteriores sobre los recursos de los tipos siguientes a R en la ordenación. Para comprobar el funcionamiento de esta estrategia, se asocia un índice a cada tipo de recurso. Como en la retención y espera, la prevención del circulo vicioso de espera puede ser ineficiente, retardando procesos y denegando accesos a recursos innecesariamente.
DETECCION: 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.
PREDICCION: 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 iniciación de procesos Confedérese un sistemas de n procesos y m tipos diferentes de recursos. Se definen los vectores y matrices siguientes: Recursos = (R1, R2, ... Rm) cantidad total de cada recurso en el sistema Disponible = (D1, D2, ... Dm) cantidad total de cada recurso sin asignar a los procesos La matriz Demanda indica las exigencias máximas de recursos para cada proceso, con una fila para cada uno. Es decir, Cij = demanda del recurso j por parte del proceso i. Esta información debe declararse por adelantado para que funcione la predicción de interbloqueo. De forma similar, Aij = asignación del recurso j al proceso i. Se puede ver que se cumplen las siguientes relaciones: Para todo i, Ri = Di + Σ Aki : todos los recursos están asignados o disponibles. Para todo k e i, Cki <= Ri: ningún proceso puede demandar más recursos que la cantidad total de recursos del sistema Para todo k e i, Aki <= Cki: ningún proceso tiene asignados más recursos de cualquier tipo que los que ha declarado necesitar. Con estas tres cantidades, se puede definir una política de predicción del interbloqueo que rechace iniciar un nuevo proceso si sus exigencias de recursos pueden conducir a un intebloqueo. Un nuevo proceso Pn+1 comenzará sólo si: Es decir, un proceso comenzará sólo si puede servirse la demanda máxima de todos los procesos actuales más la del nuevo proceso. Esta estrategia es poco óptima, puesto que asume el caso peor: que todos los procesos expresen su demanda máxima a la vez. 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 Dijkstra, 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. Los algoritmos siguientes muestran una versión abstracta de la logica de predicción del interbloqueo. Con el estado del sistema definido por la estructura de datos estado, solicitud [*] es un vector que define los recursos pedidos por el proceso i. En primer lugar, se hace una comprobación para asegurar que la solicitud no excede la demanda inicial del proceso. Si la solicitud es válida, el paso siguiente es determinar si es posible satisfacer la solicitud, esto es, si hay suficientes recursos disponibles. Si no es posible, el proceso se suspende. Si es posible, el paso final es determinar si es seguro satisfacer la solicitud. Para hacer esto, se prueba a asignar los recursos al proceso i desde nuevo_estado. Después, se realiza un test d seguridad usando el algoritmo del banquero.