Programación Concurrente

UPV / EHU
en Linux

El problema
del interbloqueo

Alberto Lafuente, Dep. KAT/ATC de la UPV/EHU, bajo Licencia Creative Commons 1

 Contenido

UPV / EHU

1.  Inanición e interbloqueo

2.  Modelo del interbloqueo
3.  Soluciones al interbloqueo

2
UPV / EHU

1. Inanición e interbloqueo

3
 Inanición e interbloqueo

•  El acceso a recursos compartidos no está libre de

problemas:
–  Inanición: un proceso/hilo espera indefinidamente para
UPV / EHU entrar a la sección crítica.
•  Posible escenario: Algunas primitivas de sincronización
pueden estar implementadas con criterios de prioridad
para seleccionar el siguiente proceso a entrar en la sección
crítica.
–  Interbloqueo: es una situación de reciprocidad en el
acceso a recursos múltiples.
•  Un conjunto de procesos está interbloqueado cuando cada
proceso está esperando por un recurso que está siendo
usado por otro proceso del conjunto.
•  ¡Aunque las primitivas cumplan rigurosamente las
propiedades del acceso exclusivo!

4
 Interbloqueo
Un escenario sencillo
•  El siguiente código puede conducir a un
interbloqueo entre P1 y P2

UPV / EHU
Proceso P1 Proceso P2
... ...
bajar(R1); bajar(R2);
... ...
bajar(R2); bajar(R1);
... ...
subir(R2); subir(R1);
subir(R1); subir(R2);
... ...

5
 Interbloqueo
Un escenario sencillo

•  El siguiente código puede conducir a un interbloqueo

entre P1 y P2:

UPV / EHU Proceso P1 Proceso P2

... ...
SC R1
bajar(R1); bajar(R2); SC R2
... ...
bajar(R2);
SC R2 SC R1bajar(R1);
... ...
subir(R2); subir(R1);
subir(R1); subir(R2);
... ...

6
 Interbloqueo
Otro escenario: recursos múltiples
•  Un proceso/hilo necesita n unidades (bloques) de
memoria:
proceso_que_usa_memoria(int n) {
UPV / EHU for (i=0; i<n; i++)
b[i]= dame_un_bloque(); // en exc. mutua
// Se usan los bloques...

for (i=0; i<n; i++)

liberar_bloque(b[i]); // en exc. mutua
}

•  Supongamos la siguiente situación:

–  Un proceso P va a usar M bloques
–  Un proceso Q va a usar N bloques
–  En el sistema quedan B bloques libres, tal que B<M+N
7
UPV / EHU

2. Modelo del interbloqueo

8
 Modelo del interbloqueo
Grafo de asignación de recursos a procesos
Notación:
UPV / EHU
P R

El proceso P ha solicitado usar el recurso R

P R

El proceso P está usando el recurso R

9
 Modelo del interbloqueo

•  El escenario sencillo anterior. Una posible secuencia:

UPV / EHU
R2

P1 P2

R1

10
 Modelo del interbloqueo

•  El escenario sencillo anterior. Una posible secuencia:

UPV / EHU
R2
P1: bajar(R1)
Como está libre,
lo usa
P1 P2

R1

11
 Modelo del interbloqueo

•  El escenario sencillo anterior. Una posible secuencia:

UPV / EHU
R2
P2: bajar(R2)
Como está libre,
lo usa
P1 P2

R1

12
 Modelo del interbloqueo

•  El escenario sencillo anterior. Una posible secuencia:

UPV / EHU
R2

P1 P2

R1

El interbloqueo ya es inevitable…
13
 Modelo del interbloqueo

•  El escenario sencillo anterior. Una posible secuencia:

UPV / EHU
R2

P1 P2

R1

14
 Modelo del interbloqueo

•  El escenario sencillo anterior. Una posible secuencia:

UPV / EHU
R2

P1 P2

R1

…se forma un ciclo en el grafo de asignación

15
 Modelo del interbloqueo

•  El escenario sencillo anterior. Una posible secuencia:

UPV / EHU
R2

P1 P2

R1

P1 y P2 están interbloqueados
16
 Modelo del interbloqueo

•  Otro ejemplo:

UPV / EHU
R2 R3

P1 P2 P3

R1 R4

17
 Modelo del interbloqueo

•  Otro ejemplo:

UPV / EHU
R2 R3

P1 P2 P3

R1 R4

Si P2 solicita R1 hay interbloqueo entre P1 y P2

18
 Modelo del interbloqueo

•  Otro ejemplo:

UPV / EHU
R2 R3

P1 P2 P3

R1 R4

…o si P3 solicita R1 hay interbloqueo entre P1, P2 y P3

19
 Modelo del interbloqueo

•  Otro ejemplo:

UPV / EHU
R2 R3

P1 P2 P3

R1 R4

…pero no lo habría si P3 solicita R4

20
 Modelo del interbloqueo

•  Otro ejemplo:

UPV / EHU
R2 R3

P1 P2 P3

R1 R4

…o si P3 solicita R1 una vez que P1 lo libere

21
UPV / EHU

3. Soluciones al interbloqueo

22
 Soluciones al interbloqueo

UPV / EHU •  Dos enfoques:

–  Políticas paliativas:
•  El Algoritmo del Avestruz
•  Detección y eliminación
–  Políticas preventivas:
•  Prevención de interbloqueos
•  Predicción de interbloqueos

23
 Soluciones al interbloqueo

•  El Algoritmo del Avestruz

–  No hacer nada
•  …se reinicia el ordenador cuando suceda.
UPV / EHU •  Esta solución resulta práctica si el ordenador no se
usa para tareas crítica ([Link]., un PC doméstico o un
móvil).
•  Detección y eliminación
–  Detectar cuando ocurra un interbloqueo
•  Manteniendo un grafo de asignación o mediante
otros indicios.
–  Una vez detectado, tratar de eliminarlo
•  Eliminando alguno de los procesos involucrados.

24
 Soluciones al interbloqueo

UPV / EHU
•  Mejor prevenir que curar…

–  Las políticas preventivas evitan los interbloqueos

impidiendo las condiciones para que ocurran o,
sin impedirlas, prediciendo la posibilidad de un
interbloqueo para actuar en consecuencia.

25
 Soluciones al interbloqueo
Condiciones para el interbloqueo

•  Un interbloqueo solo puede producirse si en el

sistema se cumplen todas y cada una de las
condiciones siguientes:
UPV / EHU

1.  Exclusión mutua. En todo momento, cada recurso, o

está asignado a un proceso, o está libre.
2.  Retención y espera. Un proceso que está utilizando un
recurso ri puede solicitar otro recurso rj antes de
liberar ri.
3.  No expulsión. Un proceso no puede ser forzado a
liberar un recurso.
4.  Espera circular. Existe un conjunto de procesos PD
entre los que se define un círculo de espera por
recursos que están siendo usados

26
 Soluciones al interbloqueo
Prevención de interbloqueos

•  Si el sistema impide una sola de las

condiciones para el interbloqueo, ¡estos no
se producirán!
UPV / EHU

–  Impedir las Condiciones 1 y 3 resulta muy

restrictivo o imposible.

–  Impedir la Condición 2:
•  Asignando recursos por conjuntos.
•  Restringe la concurrencia.

–  Impedir la Condición 4:
•  Asignar recursos en un orden determinado:
–  Si P está usando Ri, puede solicitar Rk solo si k>i

27
 Soluciones al interbloqueo
Prevención de interbloqueos
•  ¡No pueden producirse ciclos si los recursos se
asignan en orden creciente!

UPV / EHU
R2 R3

P1 P2 P3

R1 R4

28
 Soluciones al interbloqueo
Predicción de interbloqueos

UPV / EHU
•  Se definen estados seguros e inseguros.
–  Los estados inseguros son los que pueden
conducir a interbloqueos y se evitan denegando el
acceso a recursos libres.
–  Se usa el Algoritmo del banquero
•  Requiere un número fijo de procesos.
•  Muy restrictivo y computacionalmente complejo.

29
 Soluciones al interbloqueo
El Algoritmo del Banquero
•  Con dos procesos y dos recursos se puede representar en el plano.
•  Objetivo: conseguir una trayectoria en la ejecución que haga que
todos los procesos terminen.
P2
Fin P2

UPV / EHU

R1

X
R2

P1
R1 Fin P1
R2

Estados  imposibles:  uso  simultaneo  de  R1        

Estados  imposibles:  uso  simultaneo  de  R2        

Estados  inseguros:  conducen  a  interbloqueo  

X Estado  de  interbloqueo  

Ejemplo  de  trayectoria  que  conduce  a  interbloqueo  

30