En sistemas operativos, el bloqueo mutuo (también conocido como interbloqueo, traba mortal, deadlock, abrazo mortal) es el bloqueo permanente de un conjunto de procesos o hilos de ejecución en un sistema concurrente que compiten por recursos del sistema o bien se comunican entre ellos. A diferencia de otros problemas de concurrencia de procesos, no existe una solución general para los interbloqueos.
Todos los interbloqueos surgen de necesidades que no pueden ser satisfechas, por parte de dos o más procesos. En la vida real, un ejemplo puede ser el de dos niños que intentan jugar al arco y flecha, uno toma el arco, el otro la flecha. Ninguno puede jugar hasta que alguno libere lo que tomó.
Algoritmo del Banquero
Para evitar el deadlock se puede optar por dos soluciones:
- Analizar como se requieren los recursos, velando porque no se cumpla ninguna de las condiciones necesarias para el deadlock (exclusión mutua, espera y retention, no apropiacion y espera circular). Esta solucion puede provocar baja utilización de los recursos, y por lo tanto, una baja general del rendimiento del sistema.
- Pedir mas info sobre los recursos: como se requieren, en que momento del sistema son requeridos, la demanda máxima, etc.
En este ultimo caso se debe conocer la secuencia de solicitud, uso y liberation de cada recurso requerido por el proceso.
El sistema evaluara con cada requerimiento, los requerimientos del resto de los procesos, los disponibles, y los futuros de ese proceso y de los demás.
El mas simple de este tipo de algoritmos es aquel que pide al proceso que declare la cantidad máxima de recursos de cada tipo que necesitara. Con esta info el sistema hará un análisis para ver como asignarlo para que no haya deadlock.
Estado sano o seguro
Definimos que un sistema esta en un estado seguro (con respecto a la ausencia de deadlock) si se pueden asignar recursos a cada proceso de un conjunto de alguna manera, evitando el deadlock.
Para ello debe haber una secuencia de procesos <Po, Pi , , Pn >, que asegure que, con los recursos disponibles puede garantizar los recursos que requiere Pi considerando los recursos que ya tienen asignados todos los Pj, con jdeadlock.
Si Pi no puede disponer de esos recursos inmediatamente entonces Pi se debe dormir hasta que todos los Pj terminen. En ese momento Pi recupera los recursos que necesitaba y puede terminar y asi Pi+1 puede obtener los recursos que necesitaba y puede terminar … y así sucesivamente.
SI no se puede construir esta secuencia, el estado del sistema es inseguro.
Considerar que:
- Un estado seguro garantiza que no hay deadlock.
- Un estado de deadlock, es un estado inseguro.
- .. no todos los estados inseguros son deadlock.
En los estados seguros, el SO tiene control sobre los procesos. En un estado inseguro el control depende del comportamiento de los procesos.
Ejemplo
Sea un sistema donde 3 procesos Po, Pi ,P2 comparten 12 unidades de cinta. Veamos la utilización en un momento del sistema.
| Procesos | Máximo a usar | EN uso |
| Po | 10 | 5 |
| Pi | 4 | 2 |
| P2 | 9 | 2 |
Por lo tanto, en este momento hay 3 cintas libres. Si le damos 2 a Pi (quedara una disponible), P1 tendrá todas las que necesite como para terminar de ejecutarse y liberar las 4 unidades de cinta que utilizo. Estas 4 mas la que había quedado disponible se le pueden dar a P0 . Cuando este termine liberara 10 unidades y se podrá ejecutar P2 .
No obstante, debemos considerar que desde un estado seguro, basta la asignación incorrecta de un recurso para entrar en un estado inseguro.
Los algoritmos deben asegurar que nunca habrá deadlock, manteniendo al sistema en un estado seguro. Y ese análisis se debe hacer con cada requerimiento analizando si se asigna o el proceso espera.
Debemos tener en cuenta que puede bajar la performance en un sistema que use este algoritmo, pero la ventaja es que no habrá deadlock.
El algoritmo del banquero sirve para sistemas con múltiples instancias de cada recurso. Los procesos deben declarar el numero máximo de instancias de cada recurso que necesitará y ese numero no puede exceder total de instancias de recursos de ese tipo en el sistema. Este decidirá en que momento asignarlos, garantizando un estado seguro.
Estructuras asociadas
Consideremos n: cantidad de proceso, m: cantidad de tipos de recursos, disponible: vector de m componentes, con la cantidad de recursos disponibles para cada tipo, tal que si disponible(j)=k, indica que hay k instancias del recurso Rj . asignación: matriz de n x m que define la cantidad de instancias de cada tipo de recurso que tienen asignadas cada proceso, tal que asignación(i,j)=k, indica que hay k instancias del recurso Rj asignadas a Pi; max: matriz de n x m que define la cantidad máxima de instancias de cada tipo de recurso que necesita cada proceso, tal que max(i,j)=k, indica que Pi necesitara en total k instancias del recurso Rj, need: matriz de n x m que define la cantidad de instancias de cada tipo de recurso que necesita cada proceso ademas de las que tiene ya asignadas, tal que need(i,j)=k, indica que Pi necesitara k instancias mas de las que ya tiene, del recurso Rj . need surge de restar max- asignacion.
Consideremos también la siguiente notación:
Si X e Y son vectores de n componentes, decimos que X ≤ Y si y solo si X (i) ≤ Y(i), para todo i=1,..,n.
Para este algoritmo, tomaremos filas de las matrices como si fueran vectores. Asi, los recursos asignados a Pi , sera el vector Asignación-i que es la fila i de la matriz Asignación.
Algoritmo del estado seguro (Safety Algorithm)
Sean work un vector de m componentes, inicializado de tal manera que work=disponible; y otro vector final de n componentes, inicializado en falso.
Encontrar un i, tal que se cumpla que:
- final(i)= falso.
- needi ≤ work
Si no existe tal i, va al paso 5.
Realizar las siguientes operaciones
- work=work + asignacióni
- final(i)= verdadero.
- Si final(i)=verdadero para todo i, el sistema esta en estado seguro.
Para realizar este algoritmo debo hacer m x n .
Analicemos el algoritmo: lo que estamos haciendo es un análisis sobre que pasa en el sistema al darle lo que necesita a aquel proceso que con lo que tiene (need) mas lo disponible (work) puede terminar de ejecutarse (final=verdadero). Luego liberana todos sus recursos, para que puedan estar disponibles de nuevo (work=work + asignacióni). Cuando todos los procesos terminaran (todos los final(i)=verdadero), seria un estado seguro: todos los procesos pueden ejecutarse sin producir deadlock.
Cabe aclarar que no estoy ejecutando en realidad los procesos: estoy encontrando cual es la secuencia segura de ejecución.
Algoritmo de requerimiento de recursos
Sea solicitudi un vector de m componentes que representa los recursos que solicita Pi . solicitudi [j]=k, indica que Pi necesita k instancias del recurso Rj .
Cuando el proceso requiere recursos se realizan los siguientes pasos:
Si solicitudi ≤ needi va la paso 2. Si no es asi, se reporta un error pues no puede pedir mas de lo que necesita.
Si solicitudi ≤ work va al paso 3. Si no es asi Pj debera dormir hasta que el recurso este disponible.
Cuando el sistema va a asignar el recurso se hacen los siguientes calculos work = work – solicitudi asignacióni = asignacióni + solicitudi needi = needi – solicitudi
Luego aplicamos el algoritmo de estado seguro para ver si asignarle la solicitud deja el sistema en estado seguro o no.
Ejemplo
Sean 5 procesos Po, Pi ,P2 ,P3 ,P4 . A continuación se detallan los recursos asignados (hay 3 tipos) y el máximo de recursos que necesitara cada proceso.
| Procesos | asignación | máximo | need | ||||||
| P0 | 0 | i | 0 | 7 | 5 | 3 | 7 | 4 | 3 |
| Pi | 2 | 0 | 0 | 3 | 2 | 2 | i | 2 | 2 |
| P2 | 3 | 0 | 2 | 9 | 0 | 2 | 6 | 0 | 0 |
| P3 | 2 | i | i | 2 | 2 | 2 | 0 | i | i |
| P4 | 0 | 0 | 2 | 4 | 3 | 3 | 4 | 3 | i |
Hay disponibles lo que se describe en el vector work=(3,3,2). Voy a buscar una secuencia segura de ejecución, o sea que me garantice que no habrá deadlock.
Busco un proceso i que cubra sus necesidades con lo que hay disponible, o sea needi ≤ work.
Por ejemplo las necesidades de P0 superan lo que hay pues (7,4,3) > (3,3,2). Elijo Pi.
Pi necesita (1,2,2). SI se las diera, el ya tiene (2,0,0) Cuando termine, tendré lo que tenia disponible mas lo que tenia asignado Pi, es decir (3+2,3+0,2+0)=(5,3,2) que sera mi nuevo vector work. Pi termina.
Busco de entre el resto de los procesos cual de ellos cubrirían sus necesidades con lo que hay disponible, o sea needi ≤ work. P3 necesita (0,i,i), asi que proceden a considerarlo.
Así, el ya tiene (2,i,i). Cuando termine, tendré lo que tenia disponible mas lo que tenia asignado , es decir (5+2,3+i,2+i)=(7,4,3) que sera mi nuevo vector work. P3 terminará. Busco de entre el resto de los procesos cual de ellos cubriría sus necesidades con lo que hay disponible, o sea needi ≤ work . P0 necesita (7,4,3).
Al terminar liberan a (0,i,0), así que work=(7,5,3) que me sirve para ejecutar P2 y luego P4. Una secuencia de ejecución segura seria <Pi, P3 ,P0 ,P2 ,P4 >.
Desventajas de la avoidance
Avoidance se basa en el conocimiento constante de requerimientos por parte de procesos, lo cual no es habitual en la practica. El usuario de hoy, apoyado por interfaces cada vez mas amigables, niveles de abstracción cada vez mayores e invocación dinámica, sabe cada vez menos sobre cuales recursos (y cuanto de cada uno de ellos) consumen las aplicaciones.
Ademas en este esquema estamos asumiendo un numero fijo de instancias por tipo de recursos, lo cual en la practica puede variar ante la caída y recuperación de algunas instancias.
Otro punto en contra es que la manera de restringir la asignación de recursos es muy elegida y degrada la performance. El algoritmo supone el peor caso y construye la solución en base a el.
