Contenido Interbloqueo Qu es el interbloqueo? Cmo prevenirlo? Cmo evitarlo? Cmo detectarlo?
M. B. Ibez
M. B. Ibez
Qu es?
Bloqueo permanente de un conjunto de procesos que para terminar necesitan o bien los recursos del sistema, o bien comunicar los unos con los otros Involucra conflicto de necesidades por recursos de uno o varios procesos
From Operating Systems. Internals and Principles. W. Stalling. Prentice Hall
Cruce en un Puente
.
Trfico en una sola direccin Cada seccin del puente puede verse como un recurso Si un bloqueo existe, sta puede resolverse si algn carro retrocede (intervencin de recursos y vuelta atrs) La inanicin es posible
From Operating System Concepts. Silbershatz & Galvin
M. B. Ibez
M. B. Ibez
Recursos Reutilizables
Los procesos obtienen recursos que luego liberan para que sean reutilizados por otros procesos
Tiempo del procesador, I/O channels, memoria secundaria, files, databases, y semforos
Ejemplo de interbloqueo posible
process P1{ ... <request 80K bytes> <request 60K bytes> } process P2{ ... <request 70K bytes> <request 60K bytes> }
El interbloqueo se produce si cada proceso mantiene un recurso y requiere el otro
From Operating Systems. Internals and Principles. W. Stalling. Prentice Hall
Hay espacio disponible para asignar 200K
El interbloqueo se produce si ambos procesos progresan en su segunda peticin
M. B. Ibez
M. B. Ibez
Recursos Consumibles
Creado (producido) y destruido (consumido) por un proceso Interrupciones, seales, mensajes, e informacin en buffers de E/S Un interbloqueo puede ocurrir si se tiene un blocking receive Una rara combinacin de eventos puede causar interbloqueo
From Operating Systems. Internals and Principles. W. Stalling. Prentice Hall
Ejemplo de interbloqueo
El interbloqueo se produce si el receive es bloqueante
P1 P2
...
R ec eive(P2);
...
R ec eive(P1);
...
...
Send(P2);
Send(P1);
From Operating Systems. Internals and Principles. W. Stalling. Prentice Hall
M. B. Ibez
M. B. Ibez
Condiciones necesarias y suficientes para el interbloqueo
E xclusin mutua: solo un proceso a la vez puede usar un recurso. Manten er y esperar: un proceso que tiene al menos un recurso est esperando para adquirir recursos adicionales pero no libera los que ya tiene No interferencia: un recurso puede ser liberado solo voluntariamente por el proceso que lo posee, incluso si el proceso ya termin de usar el recurso E sp era circular: exsiste un conjunto {P 0, P1 , , P0} de procesos en espera tales que P0 espera por un recurso que posee P 1 , P1 espera por un recurso que posee P 2 , , Pn1 espera por un recurso que posee by Pn , y P 0 espera por un recurso que posee P 0 .
From Operating System Concepts. Silbershatz & Galvin
M. B. Ibez
Prevencin
Disear un sistema de manera que la posibilidad de interbloqueo est excluida a priori Prevencin indirecta
Prevenir la ocurrencia de al menos una de las condiciones necesarias
Prevencin indirecta
Prevenir la aparicin de la espera circular
M. B. Ibez
Prevencin Exclusin Mutua No puede evitarse
Prevencin de interbloqueo Mantener y Esperar
Solicitar que los procesos pidan todos sus recursos a la vez Bloquear los procesos hasta que puedan satisfacerse todos sus requerimientos
From Operating Systems. Internals and Principles. W. Stalling. Prentice Hall From Operating Systems. Internals and Principles. W. Stalling. Prentice Hall
M. B. Ibez
M. B. Ibez
Prevencin de interbloqueo Mantener y Esperar
Desventajas
Puede ser que los procesos estn esperando por sus recursos por mucho ms tiempo del requerido normalemente Los recursos asignados a los procesos pueden permanecer sin uso por largo tiempo. Estos recursos pueden ser usados por otros procesos
Prevencin del Interbloqueo No Preemption
Si a un proceso se le niegan futuros recursos, el proceso debe regresar los que ya tiene asignados Si un proceso necesita un recurso que es usado por otro proceso, el sistema de operacin puede quitarle el recurso al segundo proceso
M. B. Ibez
M. B. Ibez
Prevencin de Interbloqueo Espera Circular
Definir un orden linear de los recursos Una vez que se obtiene un recurso, solo aquellos recursos mayores en la lista, pueden ser obtenidos
M. B. Ibez
Prevencin de Interbloqueo Espera Circular
Desventajas: Puede ser ineficiente:
Los procesos se ejecutarn ms lentamente
Pueden descartarse recursos innecesarios
M. B. Ibez
Evitando el interbloqueo
Se permitir la existencia de las tres condiciones necesarias pero se escoger juiciosamente a quin se le darn los recursos de manera de evitar la condicin de interbloqueo Dos estrategias
Evitar comenzar un nuevo proceso No asignar nuevos recursos
M. B. Ibez
No comience un proceso si sus demandas pueden ocasionar interbloqueo. Conceptos. n procesos m recursos Cantidad Total de Recursos en el Sistema Recursos = (R1,R2,,Rm) Cantidad Total de cada Recurso que no ha sido asignado an Disponibilidad = (V1,V2,,Vm)
M. B. Ibez
No comience un proceso si sus demandas pueden ocasionar interbloqueo. Conceptos. Requerimientos de cada proceso para cada recurso | C11 C12 C1m | Peticin = | C21 C22 C2m | | | | Cn1 Cn2 Cnm |
No comience un proceso si sus demandas pueden ocasionar interbloqueo. Conceptos. Asignacin actual | A11 A12 A1m | Asignacin = | A21 A22 A2m | | | | An1 An2 Anm |
M. B. Ibez
M. B. Ibez
Relaciones que deben mantenerse
Todos los recursos deben estar
Disponibles, o Asignados Ri = Vi + Aki (k = 1n)
Relaciones que deben mantenerse
Ningn proceso puede pedir ms recursos que el total de recursos del sistema Cki Ri (para todo k, i)
M. B. Ibez
M. B. Ibez
Relaciones que deben mantenerse
A ningn proceso se le asignan ms recursos de ningn tipo que los que originalmente el proceso dice necesitar Aki Cki (para todo k, i)
Cundo permitir la admisin de un nuevo proceso?
No se comienza un nuevo proceso a menos que haya suficiente recursos para
satisfacer las demandas mximas de los procesos actuales ms las del nuevo proceso
Ri C(n+1)i + Cki (para todo i, k = 1..n)
M. B. Ibez
M. B. Ibez
Evitando interbloqueo Estado del Sistema
Asignacin actual de recursos a procesos El estado consiste de:
los vectores: Recursos y Disponibilidad Las matrices: Peticin y Asignacin
M. B. Ibez
Evitando interbloqueo Estado Seguro
Estado en el que hay al menos una secuencia de eventos que hace que todos los procesos corran hasta terminar, i.e. no se produce interbloqueo
M. B. Ibez
Evitando interbloqueo Estado Seguro
Cuando un proceso requiere un recurso disponible, el sistema debe decidir si su asignacin hace que el sistema est en estado seguro La secuencia <P 1 , P2 , , Pn> es segura si para cada P i, los recursos que Pi puede an pedir pueden ser asignados por los recursos actuales ms los recursos liberados por los P j, con j<i . Si P i necesita recursos que no estn disponibles inmediatamente, entonces P i debe esperar hasta que Pj haya terminado. Cuando Pj termine, Pi puede obtener los recursos que requiere, ejecutar, regresar los recursos asignados, y terminar. Cuando P i termina, Pi+1 puede obtener los recursos que necesita, y as sucesivamente.
Ejemplo de Estado Seguro
Maximum Needs P0 P1 P2 10 04 09
Current Needs t0 5 2 2
Current Needs t1 5 2 4
Resources: 12 tapes t0: safe state <P1,P0,P2> t1: unsafe
M. B. Ibez
M. B. Ibez
Estado Seguro
Un estado seguro no es un estado de interbloqueo Un estado de interbloqueo no es un estado inseguro
Estado Seguro (cont)
No todos los estados inseguros son estados de interbloqueo, sin embargo a partir de un estado inseguro puede llevarse a un interbloqueo Los algoritmos que evitan interbloqueo solo permiten ir de un estado seguro a otro estado seguro (ver Bankers Algorithm at pp. 220-223)
M. B. Ibez
M. B. Ibez
Desventajas de la estrategia: Evitando interbloqueo
Deben conocerse de antemano los requerimientos mximos de recursos de cada proceso Los procesos bajo consideracin deben ser independientes. Esto es, el orden en el que se ejecutan no debe depender de ningn tipo de sincronizacin entre los procesos Debe haber un nmero mximo de recursos a asignar Ningn proceso debe terminar mientras tenga recursos asignados
M. B. Ibez
Deteccin del Interbloqueo
El Sistema de Operacin verifica si hay o no interbloqueo peridicamente El S.O. verifica cada vez que se solicita un recurso
Temprana deteccin del interbloqueo Verificaciones frecuentes consumen tiempo del procesador
M. B. Ibez
Algoritmo de Deteccin de Interbloqueo
qij: El proceso Pi solicita qij recursos de tipo j 1. Marque cada proceso que tenga en la matriz Asignacin una fila llena de ceros 2. Inicialice el vector W con el vector Disponibilidad 3. Encuentre un proceso Pi que est sin marcar y para el cual la I-sima fila de Q sea menor o igual a W. Si no lo halla: fin 4. Marque el proceso Pi y actualice W as: Wk = Wk + Aik Regrese al paso (3) Existe interbloqueo si y solo si existen procesos sin marcar al final del algoritmo
M. B. Ibez
Estrategias a seguir una vez que se detecta un interbloqueo
Abortar todos los procesos que intervienen en el interbloqueo Llevar cada proceso en interbloqueo a un punto previo predefinido (checkpoint), y recomenzar ejecucin a partir de ese punto de nuevo Ir abortando los procesos uno a uno hasta que el interbloqueo desaparezca Desasignar recursos uno a uno hasta que el interbloqueo desaparezca
M. B. Ibez
