Bloqueos Mutuos

Bloqueos Mutuos
Tambin llamado deadlock o abrazo mortal. Varios procesos bloqueados en espera de un evento (por ejemplo, la obtencin de un recurso) que es imposible que ocurra. Procesos bloqueados: no estn en ejecucin, nunca terminan, tienen asignados recursos que no pueden usar (puesto que no estn en ejecucin) y nunca devuelven los recursos porque nunca acaban. Baja la eficiencia del sistema.
1 Modelo del Sistema

Los procesos compiten en el Sistema informtico para la adquisicin de recursos con los que completar sus tareas. Los recursos son de varios tipos, cada tipo puede contener uno o varios ejemplares idnticos. Un proceso solicita un recurso al SO antes de usarlo, y lo libera cuando no lo necesita ms: solicitud uso liberacin n conjunto de procesos est en un estado de BM (Bloqueo Mutuo), si cada uno de los procesos del conjunto est esperando (bloqueado) un suceso que slo puede causar otro de los procesos de ese conjunto (tambin bloqueado).
2 Caractersticas del BM
2.1 Condiciones necesarias
Las Cuatro Condiciones Necesarias:. o Un sistema que est en BM cumple en un determinado momento todas y cada una de las condiciones. o Que se cumplan todas y cada una de las condiciones, no quiere decir que necesariamente est en una situacin de BM. 1.- Exige el uso de un recurso en Exclusin Mutua. 2.- Espera y Retencin: mientras espera (bloqueado) la obtencin de un recurso adicional, no libera los que ya posee. 3.- No apropiacin: un recurso slo puede ser liberado voluntariamente por el proceso que lo tiene asignado. 4.- Espera Circular. Las Cuatro Condiciones no son independientes o La cuarta, espera circular, implica las otras tres. o Se mantienen las 4 porque permite establecer claramente mecanismos de prevencin.
2.2 Grafo de asignacin de recursos

o o o o Permiten describir con precisin los BM. Constan de: Dos tipos de vrtices: Procesos. Recursos Dos tipos de arcos:
De peticin: Proceso Recursos De asignacin: Recurso proceso. o Grficamente: o Procesos son globos con su nombre dentro. o Recursos: cajas cuadradas con tantos puntos o marcas como ejemplares del recurso. o Los arcos de peticin van al cuadrado del recurso que se pide. o Los arcos de asignacin van de la instancia al proceso.
Dada la definicin del grafo, se puede demostrar que: o Si el grafo no contiene ciclos, no hay procesos en BM. o Si hay un nico ejemplar de cada recurso, y hay uno o ms ciclos en el grafo, entonces hay BM. En este caso, la existencia de un ciclo es necesaria y suficiente para un BM. o Si cada tipo de recurso tiene ms de un ejemplar, la existencia de ciclos no garantiza la existencia de BM.
3 Mtodos para manejar el BM

Obviamente, hay que tratar el problema o Hay procesos bloqueados no avanzan en su ejecucin tienen asignados recursos que no usan recursos que podran utilizar otros procesos. o Peligroso, por ejemplo en las tareas de control. o Baja eficiencia. Opciones: o No hacer nada sencillo pero ineficiente. o Usar un protocolo en la asignacin / liberacin de recursos que asegure que nunca se va a llegar a una situacin de BM. Prevencin. poca informacin sobre los procesos Evitacin. recurso se le asigna a un proceso que lo pide, o si debe esperar hasta que se le pueda dar.
o Permitir que se pueda llegar a una situacin de BM. Esto sucede cuando no se hace nada para prevenir ni evitar. Detectarlo Recuperar el sistema (eliminarlo).
4 Prevencin
Basada en que si existe BM se deben cumplir simultneamente las cuatro condiciones. Negando al menos alguna de ellas mediante la adopcin de un protocolo de asignacin y liberacin, se estar impidiendo que exista BM. Negar Exclusin Mutua. o No es admisible, pues muchos de los recursos del Sistema Informtico requieren para su uso la exclusin mutua. Negar Retencin y Espera. Siempre que un proceso solicite un recurso, debe ocurrir que no tiene concedidos ninguno otro. Pidiendo todos los recursos que va a usar al inicio de su ejecucin. De forma equivalente, un proceso puede tener recursos asignados, y cuando pida uno adicional, previamente libera todos los que tena asignados, y si es necesario, vuelve a pedir todos los que tena asignados hasta el momento, incluyendo el nuevo. Desventajas: Baja eficiencia en la utilizacin de recursos: tener asignado un recurso desde el inicio de la ejecucin del proceso, si slo lo va a usar al final, impide su uso por otros procesos. Puede haber inanicin: un proceso que pide varios recu rsos populares, quizs se deber quedar esperando un tiempo largo indefinido hasta que estn todos libres. Negar No Expropiacin. o Si un proceso tiene unos recursos asignados, y solicita uno nuevo que no est disponible (y por lo tanto se queda bloqueado a la espera), implcitamente libera todos los recursos que posea (antes de bloquearse), es decir, los pone a disposicin por si acaso alguien los necesita. Este proceso que se ha bloqueado, slo se despertar cuando todos los recursos que ha liberado y el nuevo que peda estn disponibles. o Otra alternativa: cuando un proceso P solicita un recurso y no est libre, el SO examina si dicho recurso lo posee un proceso que tambin se halla esperando la asignacin de un recurso. Si es as, el sistema se apropia de dichos recursos y se los ofrece P. o Es un procedimiento que se aplica a recursos expropiables, es decir, que su estado se puede guardar y recuperar ms tarde (p.ej. memoria, registros de CPU...) Negacin de la Espera Circular. o Imponer un orden total en todos los tipos de recurso, y exigir que cada proceso solicite los recursos en orden creciente. Ej.: R1 (cinta), R2 (disco), R3 (Impresora). Un proceso puede pedir R1 y luego R3, pero no R2 y luego R1. (Si hay varias cintas, y un proceso quiere utilizar ms de una, las debe de pedir todas a la vez). Cuando un proceso necesite un Ri cuando ya ha adquirido un Rk (i<k), debe liberar todos los Rj (i<j<k), para luego volver a pedirlos en el orden correcto. o Desventajas: La Funcin de Orden se debe definir cada vez que se aade un nuevo recurso al sistema.
La Funcin de Orden debe ser conocida explcitamente por el usuario/programador. Los programas desarrollados no son transportables a sistemas con distinta Funcin de Orden.
5 Evitacin del BM
La prevencin hace que el sistema no aproveche los recursos de forma eficiente, pero no requiere informacin adicional sobre los procesos que ejecuta el sistema. La evitacin necesita informacin adicional sobre los procesos. Cada vez que un proceso hace una peticin, dicha peticin se evala, y de acuerdo al conocimiento que tengamos del sistema y de los procesos, se decide concederla o no. Dependiendo del algoritmo de evitacin, as tendremos necesidad de distintas informaciones. Generalmente son: o Nmero de recursos que posee cada proceso. o Nmero de recursos que puede llegar a pedir cada proceso, y o Nmero de recursos disponibles (libres) en el Sistema Informtico, El algoritmo examina dinmicamente el estado de asignacin de recursos en el sistema, y decide si conceder inmediatamente el recurso o bloquear al proceso que lo pidi (antes de asignrselo), en espera de un cambio en el estado del sistema y volver a preguntar si se le concede o no.
5.1 Estado (de asignacin de recursos) Seguro

Un estado es seguro si el sistema puede asignar recursos a cada proceso (hasta llegar a su mximo necesitado) en algn orden y an as evitar los bloqueos mutuos. o o Un estado es seguro si existe al menos una secuencia segura. <P1, P2, P3, ... Pi, o o solicitar (hasta alcanzar su nmero mximo necesario) se pueden satisfacer con los recursos actualmente libres ms los que tienen asignados los Pj (j<i). Un proceso que ha conseguido todos los recursos que necesita, tarde o temprano acabar y liberar los recursos que tena asignados.
Un sistema donde no hay BM est en un estado seguro. o o Todos los procesos acaban. Un sistema con BM est en un estado inseguro o o No todos los procesos acaban (no acaban los que estn bloqueados). No todos los estados inseguros implican que haya BM en el sistema. Ejemplo:
Hay una secuencia segura, luego el estado es seguro. Es posible pasar de un estado seguro a uno inseguro.
5.2 Algoritmo de grafo de asignacin de recursos

Se usa en un sistema informtico con un solo ejemplar por recurso.
5.3 Algoritmo del Banquero

Debido a Dijkstra. Imita el comportamiento de una entidad bancaria a la hora de conceder o no los crditos a sus clientes. Se puede usar para un nmero arbitrario de instancias de los recursos. Condiciones: o Se parte de que el Sistema Informtico se encuentra en un Estado Seguro, y que por lo tanto todos los procesos acaban. o El proceso antes de comenzar su ejecucin debe especificar su necesidad mximas en cuanto a ejemplares de todos los recursos que use. o Obviamente, si las necesidades mximas de un recurso exceden el nmero de ejemplares que tiene el sistema (libres o en uso), el proceso no es admitido. o Debemos garantizar que un proceso que haga una peticin tenga siempre una espera finita hasta que le sea asignado el recurso que pidi. o Los recursos siempre se liberan por parte del proceso que los tiene asignados. o Tambin se exige que: El nmero de recursos es constante a lo largo de la vida del sistema informtico. El nmero de procesos tambin es constante. Debemos conocer: o El nmero de recursos de cada tipo que hay en el sistema. o Para cada proceso El nmero de recursos que tiene asignados. Las necesidades mximas de cada tipo de recurso. Algoritmo de Seguridad o Determina si el Sistema est o no en un estado seguro. Algoritmo del Banquero: o Se supone que parte de un estado seguro. o Simula que se concede la peticin. o Determina si el estado de llegada es seguro o no: Si es seguro, queda garantizado que tal y como estn repartidos los recursos, todava hay una va de escape al BM, y en consecuencia, se puede conceder el recurso. Si no es seguro, cabra la posibilidad de llegar a un BM, con lo que el proceso que ha hecho la peticin se bloquea SIN conceder el recurso hasta que se pueda obtener el recurso de manera segura. Cuando cambie el estado de asignacin de recursos del sistema (por la liberacin de algn recurso previamente asignado), se reevalan las peticiones de los procesos que esperan mediante el algoritmo, y si se determina que la peticin no conduce a un estado no seguro, se asigna.
6 Deteccin del BM
Si no se previene ni evita, el BM puede aparecer. Algoritmo de deteccin, como el seguridad, pero ahora en vez de Necesidades Mximas, lo que se pone es la Solicitud actual. Se es optimista: si se puede conceder la peticin de un recurso, suponemos que nos lo devolver. Tambin se puede hacer con grafo de asignacin de recursos. Operacin de reduccin de un grafo. Transformar si es posible- los arcos de peticin en arcos de asignacin. Eliminar todos los procesos que slo tienen arcos de asignacin, pues esos procesos no estn bloqueados, y suponemos que acabarn en un tiempo finito, devolviendo los
recursos que tenan asignados.

Repetir los dos puntos anteriores tantas veces como se pueda. Si al final han podido acabar todos los procesos, es que ahora no hay bloqueo mutuo. En caso contrario, es que hay bloqueo mutuo, y los procesos que no se han podido eliminar son los culpables. Cundo se debe usar del algoritmo de deteccin? Cada vez que se pida un recurso y no se conceda (el proceso se bloquea y queda esperando). Si el algoritmo nos dice que hay BM, queda claro cul ha sido el proceso causante del BM. Puede ser una tarea muy costosa en tiempo. A intervalos regulares de tiempo.
7 Recuperacin despus de un BM
Opciones: o Abortar procesos hasta que se rompa el BM. o Expropiar recursos (que sean expropiables).
7.1 Terminacin de procesos

Eleccin de la vctima: o Abortar todos los que estn en BM. o Abortar uno a uno. Por menor prioridad. El que lleva menor tiempo de ejecucin. El que le falta mayor tiempo de ejecucin. El que libera ms recursos. ... Puede haber inanicin.
7.2 Expropiacin de recursos

Parece lgico expropiar los recursos que puedan ser recuperados ms tarde (recursos a los que se pueda guardar el estado). El recurso expropiado es asignado al proceso que lo pidi. Puntos a considerar o Seleccin de la vctima. o Si es posible, tener puntos de retroceso. o Cuidado con la inanicin.
7.8 Estrategias combinadas

Se hace una clasificacin de los recursos en categoras, por ejemplo: o o Espacio de intercambio. o o Recursos de proceso (recursos asignables como cintas, archivos). o o Memoria principal. o o Recursos internos (canales de E/S, ) Dependiendo del tipo de recurso se utiliza una estrategia, para cada caso la ms adecuada. o o Si es un recurso que se puede guardar el estado, estrategia de expropiacin. o o Si es un recurso (o conjunto de recursos) que conocemos sus necesidades mximas desde el principio de la ejecucin del proceso (p.ej. el tamao del rea de intercambio), se puede hacer una reserva, y se estara aplicando negacin de Espera y Retencin, o evitar con el Algoritmo del Banquero.
DOCENTE: ING. LILIANA SARMIENTO LPEZ

Bloqueos Mutuos

Cargado por

Copyright:

Formatos disponibles

Bloqueos Mutuos

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Bloqueos Mutuos

Cargado por

Copyright:

Formatos disponibles

Bloqueos Mutuos

1 Modelo del Sistema

2.2 Grafo de asignacin de recursos

3 Mtodos para manejar el BM

5.1 Estado (de asignacin de recursos) Seguro

5.2 Algoritmo de grafo de asignacin de recursos

5.3 Algoritmo del Banquero

recursos que tenan asignados.

7.1 Terminacin de procesos

7.2 Expropiacin de recursos

7.8 Estrategias combinadas

DOCENTE: ING. LILIANA SARMIENTO LPEZ

También podría gustarte