PDF de programación - Tema 11: Interbloqueo sobre sistemas operativos

Sistemas Operativos
Tema 11. Interbloqueo

© 1998-2008 José Miguel Santos – C. Rubén García - Alexis Quesada

Modelo del sistema

n  El interbloqueo es un problema que afecta a

procesos concurrentes que utilizan recursos en
un sistema.

n  Los procesos solicitan recursos al sistema y los
liberan cuando ya no los necesitan. Un recurso
puede estar disponible o bien asignado a algún
proceso.

1

3

Contenidos

n  Caracterización del interbloqueo
n  Estrategias de tratamiento del interbloqueo
n  Métodos de prevención
n  Métodos de evitación
n  Detección del interbloqueo
n  Recuperación tras un interbloqueo

2

Modelo del sistema

n  Ejemplares. Puede haber varios ejemplares de
un mismo tipo de recurso (ej. varias impresoras).
En este caso, cuando un proceso solicita un
recurso, se le concede cualquiera de los
ejemplares que esté disponible.

n  Si un proceso solicita un recurso que no tiene

ejemplares disponibles, el proceso queda
bloqueado, esperando hasta que se le asigna un
ejemplar.

Modelo del Sistema

El problema

n  Un conjunto de procesos bloqueados, cada uno de

ellos esperando por un recurso que retiene otro
proceso de ese conjunto.
q  ningún proceso del conjunto puede avanzar
q 

interbloqueo, bloqueo mutuo, abrazo mortal (deadlock).

n  Esquema de funcionamiento normal

q  1.- Solicitud
q  2.- Uso
q  3.- Liberación

Llamadas al

Sistema

n  ¿ Como saber en qué estados están los

recursos ?
q  Tabla de sistema podría registrar si cada recurso está
libre o asignado, y si un recurso está asignado, a qué
proceso se le asignó

5

4

6

1

¿De quién es la culpa del
interbloqueo?

n  Muchas veces, el interbloqueo no es responsabilidad

de las aplicaciones, sino del sistema de gestión de
recursos

n  Ejemplo: Los procesos A y B se pueden

interbloquear, aunque están escritos correctamente
Proceso A
Pide(escáner)
Pide(impresora)
usa impr. y escáner
Libera(impresora)
Libera(escáner)

Proceso B
Pide(impresora)
Pide(escáner)
usa impr. y escáner
Libera(escáner)
Libera(impresora)

Ejemplo de grafo de
asignación

P1, P2 y P3 están en interbloqueo

·

·

p1

p2

· ·

p3

p4

·

7

9

Grafo de asignación de recursos

n  Sirve para representar el estado de un sistema de
asignación de recursos. Muestra esta información:
q  cuántos ejemplares hay de cada tipo de recurso
q 
q  qué recursos están asignados y a qué proceso
q  qué procesos están bloqueados y por cuáles recursos

los procesos activos en el sistema

espera

··

asignación

···

proceso
bloqueado

recurso

con dos ejemplares

proceso con un
recurso asignado

recurso

con tres ejemplares

8

Condiciones para el
interbloqueo
n  Si en un sistema se produce una situación de

interbloqueo, entonces se cumplen simultáneamente
estas cuatro condiciones:
q  Exclusión mutua. Los recursos no se pueden compartir.
q  Retención y espera. Un proceso que retiene uno o varios

recursos se encuentra esperando por recursos asignados a otros
procesos.

q  No expropiación. Un recurso sólo puede ser liberado por el

proceso que lo retiene, voluntariamente.

q  Espera circular. Existe una serie de procesos en espera

{Po,P1,...Pn} en la que todo Pi espera por un recurso retenido
por Pi+1; y Pn espera por un recurso retenido por Po.

10

Tratamiento del interbloqueo

Prevención del interbloqueo

n  Garantizar que en el sistema nunca ocurren

interbloqueos
q  prevención: diseñar el sistema de manera que nunca se cumpla

alguna de las cuatro condiciones del interbloqueo.

q  evitación: tratar de no caer nunca en un estado de interbloqueo.

n  Permitir la aparición de interbloqueos y recuperarse

cuando ocurran
q  necesitamos un sistema de detección y un mecanismo de

recuperación

n  Se trata de eliminar la aparición de alguna de

las cuatro condiciones necesarias para el
interbloqueo.
q  Exclusión mutua. Depende de la naturaleza del

recurso, así que esta condición no se puede
eliminar.

n  No tratar el problema

q  si hay interbloqueos, el usuario tiene que intervenir

11

12

2

Prevención del interbloqueo (2)

Prevención del interbloqueo (3)

n  Retención y espera. Hay que garantizar que un

proceso no pueda quedar bloqueado si retiene algún
recurso. ¿Cómo conseguirlo?
q  el proceso tiene que pedir todos sus recursos de una vez, p.ej.

antes de empezar a ejecutarse
n  efecto negativo: muchos recursos retenidos pero no usados,
q  un proceso sólo puede solicitar recursos cuando no tiene

ninguno asignado
n  Efecto negativo: puede ocurrir que tengamos que liberar un recurso y

volver a pedirlo para poder solicitar otros recursos

q  En ambos caso puede que un proceso nunca se ejecute (inanición)

Prevención del interbloqueo (4)

n  Espera circular. Se puede evitar forzando un

orden en la petición de los recursos.
q  Cada recurso tiene asignado un número de orden
q  Los recursos se deben pedir en orden ascendente
q  Aconsejable: el orden de petición de los recursos se

establezca según el orden de uso normal de los
recursos de un sistema

q  Efectos negativo

n  se limita la libertad de escritura de código
n  se puede inducir a una mala utilización de los recursos

n  No expropiación. Permitir que el S.O. desasigne

recursos a un proceso bloqueado.
q  Si un proceso se bloquea por un recurso, los recursos retenidos

quedan a disposición de los procesos activos

q  El proceso bloqueado tiene ahora que esperar por todos los

recursos

q  penaliza a los procesos que necesitan muchos recursos
q  Es posible seguir este protocolo en recursos cuyo estado se
puede guardar fácilmente y después restaurarse (registros de
CPU, espacio de memoria, ...). Generalmente no puede
aplicarse a recursos tales como impresoras y unidades de cinta

13

14

Evitación del interbloqueo:
algoritmo del banquero
n  Se trata de conceder los recursos sólo cuando no representen

un riesgo futuro de interbloqueo.

n  Lo procesos han de declarar por anticipado la cantidad

máxima de recursos que van a utilizar a lo largo de su vida

n  Estado seguro: un estado en el cual no hay riesgo inminente

de interbloqueo. Un estado es seguro si en él podemos
encontrar una secuencia segura con todos los procesos del
sistema
{P1, P2, ...,PN} es una secuencia segura si los recursos que Pi
puede pedir en el peor caso se pueden atender con lo que hay
disponible más los recursos poseídos por todos los procesos
Pj,j<i

n  Sólo concedemos recursos si el estado resultante tras la

n 

petición es seguro

15

16

Algoritmo del banquero (2)

Algoritmo del banquero (3)

n  ¿ Qué significa una secuencia segura ?

q  Nos ponemos en el peor caso del sistema: que todos los

procesos soliciten al mismo tiempo el máximo de recursos a los
que tiene derecho

q  El primer proceso de la secuencia es uno que podría finalizar en

ese peor caso, con los recursos disponibles en el sistema

q  El segundo proceso es uno que puede finalizar con lo que hay

disponible más los recursos que liberaría el primer proceso

q  De la misma forma, los siguientes procesos pueden finalizar con

los recursos que han liberado los anteriores en la secuencia

q  Y si todos los procesos pueden terminar, es que no hay

interbloqueo

n  Cuando un proceso realiza una petición, el SO
calcula si tras conceder los recursos el sistema
pasa a un estado seguro
q  si el nuevo estado es seguro, se concede la petición
q  si el nuevo estado no es seguro, el proceso queda

bloqueado (aunque existan recursos suficientes para
atender la petición). La petición se concede cuando se
observa que no hay riesgo de interbloqueo

17

18

3

Algoritmo del banquero: ejemplo

Detección del interbloqueo

n  Dos recursos R1 y R2, con 5 y 6 ejemplares
n  En el instante actual quedan libres 1 y 1 ejemplares

Asignado

Máximo

Necesidades

Pa
Pb
Pc

1 0
1 3
2 2

2 2
3 4
3 2

1 2
2 1
1 0

n  El estado es seguro porque existe la secuencia segura {Pc, Pa, Pb}
n  ¿ Qué pasa si Pa pide un ejemplar de R1 y se lo damos ?

q  El sistema quedará en un estado inseguro

n  El interbloqueo se puede detectar comprobando si
existe una secuencia de terminación de procesos
(similar a la sec. segura):
q  Sea L la lista de procesos del sistema y R el conjunto de

recursos disponibles

recursos disponibles en R

1.  Buscar en L un proceso que puede continuar con los
2.  si no se encuentra ningún proceos, ir al paso 5
3.  suponer que P termina (lo retiramos de L) y que libera los
4.  volver al paso 1
5.  Si L no está vacía, hay interbloqueo

recursos que retiene (los añadimos a R)

19

20

Recuperación del interbloqueo

Recuperación del interbloqueo (2)

n  Un sistema que pretenda recuperarse del

interbloqueo, debe invocar a un algoritmo de
detección cuando lo considere oportuno (ej.
periódicamente)

n  Formas de intentar la recuperación:

q  Terminación de procesos
q  Expropiación de recursos

n  Terminación de procesos

q  matando a todos los procesos implicados (drástico)
q  matando a uno de los procesos ¿cuál?

n  el que más recursos libere
n  el que menos tiempo lleve en ejecución...

q  retrocediendo la ejecución de algún proceso (rollback)
n  muy complicado de implementar y necesita que el programa

esté diseñado para que pueda retroceder

21

22

Recuperación del interbloqueo (3)

n  Expropiación de recursos

q  Selección de la víctima

n  ¿ Qué recursos y de que procesos se expropian ?

q  Retroceso

n  Si expropiamos un recurso de un proceso, ¿ qué hacemos

con ese proceso ?

n  En ambos casos (terminación de procesos o

expropiación de recursos) hay que tener
cuidado de no provocar la inanición de procesos

23

4