1. Educación

Contenido
Interbloqueo
• ¿Qué es el interbloqueo?
• ¿Cómo prevenirlo?
• ¿Cómo evitarlo?
• ¿Cómo detectarlo?
M. B. Ibáñez
M. B. Ibáñez
¿Qué es?
Cruce en un Puente
• 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
Tráfico en una sola dirección
Cada sección del puente puede verse como un recurso
Si un bloqueo existe, ésta puede resolverse si algún carro
retrocede (intervención de recursos y vuelta atrás)
La inanición es posible
From Operating Systems. Internals and Principles. W. Stalling. Prentice Hall
From Operating System Concepts. Silbershatz & Galvin
M. B. Ibáñez
M. B. Ibáñez
Recursos Reutilizables
Ejemplo de interbloqueo posible
• 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 semáforos
• El interbloqueo se produce si cada proceso
mantiene un recurso y requiere el otro
From Operating Systems. Internals and Principles. W. Stalling. Prentice Hall
M. B. Ibáñez
process P1{
...
<request 80K bytes>
…
<request 60K bytes>
}
process P2{
...
<request 70K bytes>
…
<request 60K bytes>
}
Hay espacio disponible para
asignar 200K
El interbloqueo se produce si
ambos procesos progresan
en su segunda petición
M. B. Ibáñez
1
Recursos Consumibles
• Creado (producido) y destruido (consumido) por
un proceso
• Interrupciones, señales, mensajes, e información
en buffers de E/S
• Un interbloqueo puede ocurrir si se tiene un
blocking receive
• Una rara combinación de eventos puede causar
interbloqueo
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
From Operating Systems. Internals and Principles. W. Stalling. Prentice Hall
M. B. Ibáñez
M. B. Ibáñez
Condiciones
necesarias y suficientes
para el interbloqueo
Prevención
E xclusión 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 , …, Pn–1 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
Diseñar un sistema de manera que la
posibilidad de interbloqueo esté excluida a
priori
Prevención indirecta
Prevenir la ocurrencia de al menos una de las
condiciones necesarias
Prevención indirecta
Prevenir la aparición de la espera circular
M. B. Ibáñez
M. B. Ibáñez
Prevención
Exclusión Mutua
Prevención de interbloqueo
Mantener y Esperar
No puede evitarse
• 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. Ibáñez
M. B. Ibáñez
2
Prevención de interbloqueo
Mantener y Esperar
• Desventajas
– Puede ser que los procesos estén esperando por
sus recursos por mucho más 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
Prevención 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
operación puede quitarle el recurso al
segundo proceso
M. B. Ibáñez
M. B. Ibáñez
Prevención de Interbloqueo
Espera Circular
Prevención 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
• Desventajas: Puede ser ineficiente:
– Los procesos se ejecutarán más lentamente
– Pueden descartarse recursos innecesarios
M. B. Ibáñez
M. B. Ibáñez
Evitando el interbloqueo
No comience un proceso si sus demandas
pueden ocasionar interbloqueo. Conceptos.
• Se permitirá la existencia de las tres
condiciones necesarias pero se escogerá
juiciosamente a quién se le darán los
recursos de manera de evitar la condición de
interbloqueo
• Dos estrategias
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 aún
Disponibilidad = (V1,V2,…,Vm)
– Evitar comenzar un nuevo proceso
– No asignar nuevos recursos
M. B. Ibáñez
M. B. Ibáñez
3
No comience un proceso si sus demandas
pueden ocasionar interbloqueo. Conceptos.
Requerimientos de cada proceso para cada
recurso
| C11 C12 … C1m |
Petición = | C21 C22 … C2m |
|
…
|
| Cn1 Cn2 … Cnm |
No comience un proceso si sus demandas
pueden ocasionar interbloqueo. Conceptos.
Asignación actual
| A11 A12 … A1m |
Asignación = | A21 A22 … A2m |
|
…
|
| An1 An2 … Anm |
M. B. Ibáñez
M. B. Ibáñez
Relaciones que deben mantenerse
Relaciones que deben mantenerse
Todos los recursos deben estar
Ningún proceso puede pedir más recursos que
el total de recursos del sistema
Disponibles, o
Asignados
Ri = Vi + ∑ Aki (k = 1…n)
Cki ≤ Ri (para todo k, i)
M. B. Ibáñez
M. B. Ibáñez
Relaciones que deben mantenerse
¿Cuándo permitir la admisión de
un nuevo proceso?
A ningún proceso se le asignan más recursos
de ningún tipo que los que originalmente el
proceso dice necesitar
Aki ≤ Cki (para todo k, i)
M. B. Ibáñez
No se comienza un nuevo proceso a menos
que haya suficiente recursos para
satisfacer las demandas máximas de los procesos actuales
más las del nuevo proceso
Ri ≥ C(n+1)i + ∑ Cki (para todo i, k = 1..n)
M. B. Ibáñez
4
Evitando interbloqueo
Estado del Sistema
Asignación actual de recursos a
procesos
El estado consiste de:
los vectores: Recursos y
Disponibilidad
Las matrices: Petición y Asignación
•
•
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. Ibáñez
M. B. Ibáñez
Evitando interbloqueo
Estado Seguro
Ejemplo de Estado Seguro
Cuando un proceso requiere un recurso disponible, el sistema debe
decidir si su asignación 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 aún pedir pueden ser asignados por los recursos actuales
más los recursos liberados por los P j, con j<i.
– Si P i necesita recursos que no están 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.
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. Ibáñez
M. B. Ibáñez
Estado Seguro
Estado Seguro
(cont)
• Un estado seguro no es un estado de
interbloqueo
• Un estado de interbloqueo no es un estado
inseguro
M. B. Ibáñez
• 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 Banker’s Algorithm at
pp. 220-223)
M. B. Ibáñez
5
Desventajas de la estrategia:
Evitando interbloqueo
• Deben conocerse de antemano los requerimientos
máximos de recursos de cada proceso
• Los procesos bajo consideración deben ser
independientes. Esto es, el orden en el que se
ejecutan no debe depender de ningún tipo de
sincronización entre los procesos
• Debe haber un número máximo de recursos a
asignar
• Ningún proceso debe terminar mientras tenga
recursos asignados
Detección del Interbloqueo
• El Sistema de Operación verifica si hay o
no interbloqueo periódicamente
• El S.O. verifica cada vez que se solicita un
recurso
– Temprana detección del interbloqueo
– Verificaciones frecuentes consumen tiempo del
procesador
M. B. Ibáñez
M. B. Ibáñez
Algoritmo de Detección de
Interbloqueo
Estrategias a seguir una vez que
se detecta un interbloqueo
qij: El proceso Pi solicita qij recursos de tipo j
1. Marque cada proceso que tenga en la matriz Asignación
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. Ibáñez
• Abortar todos los procesos que intervienen en el
interbloqueo
• Llevar cada proceso en interbloqueo a un punto
previo predefinido (checkpoint), y recomenzar
ejecución 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. Ibáñez
6