PDF de programación - Programación concurrente - Datos compartidos y exclusión mutua

20151026

dit

UPM

Programación concurrente —
Datos compar9dos y 

exclusión mutua

Juan Antonio de la Puente

<[email protected]>

Algunos derechos reservados. Este documento se distribuye bajo licencia
Crea9ve Commons Reconocimiento-NoComercial-Compar9rIgual 3.0 Unported.
hBp://crea9vecommons.org/licenses/by-nc-sa/3.0/deed.es

Referencias

•ScoB Oaks & Henry Wong

Java Threads

O'Reilly Media; 3rd ed (2004)
•Kathy Sierra & Bert Bates

Head First Java, ch. 15

O'Reilly Media; 2nd ed (2005)

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

2

Datos compar9dos

Variables compar9das

• Las hebras de un programa pueden ser independientes
‣ la ejecución de una hebra no afecta a lo que hagan 

las demás hebras

• … pero a menudo es más interesante que varias hebras

cooperen para realizar una función común

• Un mecanismo de cooperación muy corriente consiste en
usar variables compar9das
‣ variables a las que 9enen acceso varias hebras
‣ las hebras pueden consultar (leer) el valor de la variable en un
momento determinado o modificarlo (escribir)

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

4

Ejemplo

• Dos hebras que incrementan concurrentemente el valor

de un contador

hebra 1

hebra 2

contador++

contador++

contador

• Problema: el resultado depende de en qué orden se
entrelace la ejecución de las operaciones de cada hebra
‣ esto se llama condición de carrera

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

5

Operaciones atómicas

• La operación contador++ no se ejecuta de una sola vez
‣ se descompone en

registro = contador // registro es una variable temporal local de cada thread
registro = registro + 1 // incrementar el valor del registro
contador = registro // actualizar el valor del contador

• Las operaciones que no se pueden descomponer se
llaman atómicas
‣ contador++ no es atómica
‣ pero las operaciones en que se descompone sí lo son

✓ en realidad depende de la implementación (JVM y lenguaje de máquina)

• Cuando varias hebras se ejecutan concurrentemente se

entrelaza la ejecución de sus instrucciones atómicas

• Veamos dos secuencias de ejecución posibles
‣ suponemos que inicialmente contador == 0

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

6

Secuencias de ejecución (1)

contador == 0

registro ⟵ 0
registro ⟵ 1

contador ⟵ 1

contador == 1

hebra 1

hebra 2

registro = contador

registro = registro+1

contador = registro

registro ⟵ 0
registro ⟵ 1
contador ⟵ 1

registro = contador

registro = registro+1

contador = registro

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

7

Secuencias de ejecución (2)

contador == 0

registro ⟵ 0
registro ⟵ 1
contador ⟵ 1

hebra 1

hebra 2

registro = contador

registro = registro+1

contador = registro

registro ⟵ 1
registro ⟵ 2
contador ⟵ 2

registro = contador

registro = registro+1

contador = registro

contador == 2

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

8

Condición de carrera

• ¡El resultado puede ser 1 o 2!
‣ depende de las velocidades de ejecución rela9vas de las hebras
- “quién corre más”

• El resultado de un programa no debe depender de estos
detalles
‣ imposible de prever de antemano
‣ cada ejecución es dis9nta
- comportamiento indeterminado
‣ imposible hacer ensayos
- cada vez un resultado diferente

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

9

Ejemplo: variable compar9da

public class PruebaCuenta {

static long cuenta = 0; /* variable compartida */

private static class Incrementa extends Thread {
public void run () {
for (int i = 0; i < 1000000; i++) {
cuenta++; /* región crítica */
}
}
}

public static void main(String[] args) {
new Incrementa().start(); /* hebra 1 */
new Incrementa().start(); /* hebra 2 */
System.out.println(“contador = “ + contador);
}
}

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

10

Datos compar9dos en objetos

• Los campos de datos de objetos a los que se accede
desde varias hebras también son datos compar9dos
‣ también pueden dan lugar a condiciones de carrera
‣ da igual que se acceda a los datos directamente (si son visibles) 

o mediante métodos

hebra1

hebra2

Contador

- cuenta

+ incrementar()
+ valor()

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

11

Ejemplo: objetos con estado (1)



public class Contador {

private long cuenta = 0; /* estado */

public Contador (long valorInicial) {
cuenta = valorInicial;
}


public void incrementar () {
cuenta++; /* modifica el estado */
}


public long valor () { /* devuelve el valor */
return cuenta;
}
}

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

12

Ejemplo: objetos con estado (2)

public class PruebaContador {

private static class Incrementa extends Thread {
Contador contador;

public Incrementa (Contador c) {
contador = c;
}

public void run () {
...
contador.incrementar(); /* región crítica */
...
}
}

// continúa

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

13

Ejemplo: objetos con estado (3)

// continuación

public static void main(String[] args) {
Contador contador = new Contador(0);
Thread hebra1 = new Incrementa(contador);
Thread hebra2 = new Incrementa(contador);
/* las dos hebras comparten el objeto contador */
hebra1.start();
hebra2.start();
...
}

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

14

Regiones crí9cas y exclusión mutua

• Los segmentos de código en que se accede a variables
compar9das se llaman regiones crí9cas
• Para evitar condiciones de carrera es preciso asegurar la 

exclusión mutua entre las hebras en las regiones crí9cas
• Cuando una hebra está en una región crí9ca ninguna

otra puede acceder a los mismos datos
‣ primero una hebra efectúa todas las operaciones de su región
crí9ca, luego la otra
‣ el orden no importa, siempre que no se entrelacen las operaciones
elementales

• De esta forma se consigue que las operaciones con

variables compar9das sean atómicas

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

15

Cerrojos

Cerrojos

• Un cerrojo (lock) es un mecanismo de sincronización para

asegurar la exclusión mutua

• Puede estar en uno de estos dos estados:
‣ bloqueado (cerrado)
‣ desbloqueado (abierto)
• Dos operaciones atómicas
‣ bloquear (lock)
- si ya está bloqueado, la hebra se queda esperando
‣ desbloquear (unlock)
- si hay hebras esperando, con9núa una de ellas
• Para asegurar la exclusión mutua
‣ bloquear cerrojo // espera si está ocupado
‣ región crí9ca
‣ desbloquear cerrojo // si alguien esperaba puede con9nuar

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

17

Ejemplo

contador == 0

registro ⟵ 0
registro ⟵ 1
contador ⟵ 1

hebra 1

bloquear cerrojo

registro = contador

registro = registro+1

contador = registro

desbloquear cerrojo

cerrojo bloqueado

(cerrojo desbloqueado)

(cerrojo bloqueado)

registro ⟵ 1
registro ⟵ 2
contador ⟵ 2

hebra 2

bloquear cerrojo

registro = contador

registro = registro+1

contador = registro

desbloquear cerrojo

contador == 2

cerrojo desbloqueado

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

18

Problemas de los cerrojos

• Es muy mecanismo de muy bajo nivel que no es
aconsejable u9lizar directamente
‣ hay que hacer siempre lock() y unlock(), en ese orden
‣ puede ser complicado con estructuras de programa complejas
‣ es fácil equivocarse, muchos problemas

• Es mejor dejar que el compilador lo haga por nosotros
‣ integrar exclusión mutua con objetos
‣ métodos y bloques sincronizados en Java

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

19

Monitores

Exclusión mutua en Java

• Java proporciona mecanismos de sincronización
abstractos
‣ métodos sincronizados
‣ bloques sincronizados
• Definen partes del programa que se ejecutan en exclusión

mutua (regiones crí9cas)

• El compilador y la JVM se encargan de ges9onar los

cerrojos de forma implícita

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

21

Métodos sincronizados



• Un método sincronizado se ejecuta en exclusión mutua
con los demás métodos sincronizados del mismo objeto
public class ContadorSincronizado {

private long cuenta = 0; /* estado */

public ContadorSincronizado (long valorInicial) {
cuenta = valorInicial;
}


public synchronized void incrementar () {
cuenta++;
}


public synchronized long valor () {
return cuenta;
}
}

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

22

Métodos sincronizados (con9nuación)

• Las llamadas concurrentes a métodos sincronizados se

ejecutan en exclusión mutua

...
public void run () {
...
contador.incrementar(); /* región crítica */
...
}
...

Programación concurrente — Exclusión mutua

© 2014 Juan A. de la Puente

23

Implementación

• Cada objeto 9ene asociado un cerrojo
‣ Al empezar a ejecutar un método sincronizado se bloquea el cerrojo
- si ya estaba bloqueado, la hebra que invoca el método se suspende
- las hebras que esperan están en una lista asociada al objeto (entry set)
‣ Al terminar se desbloquea
- si hay hebras esperando, se reanuda la ejecución de una de ellas
‣ El compilador genera el cerrojo y los bloqueos y desbloqueos

hebras en 

espera

entry set

lock

hebra en 

método

sincronizado

Programación concurrente — Exclusión mutua

© 2014 Juan A. d