El primer gran avance en la resolución de los problemas de los procesos concurrentes llego en 1965, con el tratado de Dijkstra sobre la cooperación entre procesos secuenciales (DIJK65) dijkstra estaba interesado en el diseño de un sistema operativo como un conjunto de procesos secuenciales cooperantes y en el desarrollo de mecanismos eficientes y fiables para dar soporte a la cooperación. Los procesos de usuario podrán utilizar estos mecanismos eficientes y fiables para dar soporte a la cooperación.
Los procesos de usuario podrán utilizar estos mecanismos en tanto que el procesador y el sistema operativo los hagan disponibles.
A fin de facilitar la escritura de programas correctos, hoare y brinch Hansen propusieron una primitiva de sincronización de nivel más alto llamada monitor. Sus propuestas tenían pequeñas diferencias, que describiremos mas adelante. Un monitor es una colección de procedimientos, variables y estructuras de datos que se agrupan en un tipo especial de modulo o paquete. Los procesos pueden invocar los procedimientos de un monitor en el momento en que deseen, pero no pueden acceder directamente a las estructuras de datos internas del monitor desde procedimientos declarados afuera del monitor.
Es 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, para el caso general no existe una solución eficiente. En esta sección, se examinara la naturaleza del problema del interbloqueo.
La estrategia de prevención del interbloqueo consiste, a grandes rasgos, en diseñar un 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 consisten en impedir la aparición de alguna de las tres condiciones necesarias. Los métodos directos consisten en evitar la aparición del círculo vicioso de espera.
Se examinaran a continuación las técnicas relacionadas con cada una de las cuatro condiciones.
En general, la primera de las cuatro condiciones no puede anularse. Si el acceso a un recurso necesita exclusión mutua, el sistema operativo debe soportar la exclusión mutua. Algunos recursos, como los archivos, pueden permitir varios accesos para lectura, pero solo accesos exclusivos para escritura. Incluso en este caso, se puede producir interbloqueo si más de un proceso necesita permiso de escritura.
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 estar suspendido durante mucho tiempo, esperando que se concedan todas sus solicitudes de recursos, cuando de hecho podría 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
La condición de no apropiación puede prevenirse de varias formas. Primero, si a unos procesos que retiene ciertos recursos se le deniega una nueva solicitud, dicho procesos deberá liberar sus recursos anteriores y solicitarlos de nuevo, cuando sea necesario, junto con el recurso adicional.
La condición del círculo 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 solo podrá realizar peticiones posteriores sobre los recursos de los tipos siguientes a R en la ordenación.
Las estrategias de prevención del interbloqueo son muy conservadoras; solucionan el problema del interbloqueo limitando el accesos a los recursos e imponiendo restricciones a los procesos. En el lado opuesto, las estrategias de detección del interbloqueo no limitan el acceso a los recursos ni restringen las acciones de los procesos. Con 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 descrita en el punto 4 anterior. Puede emplearse cualquier algoritmo de detección de ciclos en grafos dirigidos.
Un sistema que pretenda recuperarse del interbloqueo, debe invocar un algoritmo de detección cuando lo considere oportuno.
