Programación concurrente: datos compartidos y exclusión mutua

dit UPM

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

Programación concurrente — Datos compar9dos y exclusión mutuaJuan Antonio de la Puente <[email protected]> !!

20141008

http://creativecommons.org/licenses/by-nc-sa/3.0/deed.es_ES

mailto:[email protected]

Programación concurrente — Exclusión mutua © 2014 Juan A. de la Puente

Referencias

•ScoB Oaks & Henry WongJava Threads O'Reilly Media; 3rd ed (2004) !

•Kathy Sierra & Bert Bates Head First Java, ch. 15O'Reilly Media; 2nd ed (2005)

2

http://proquest.safaribooksonline.com/book/programming/java/0596007825

http://proquest.safaribooksonline.com/book/programming/java/0596009208

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)

4


Ejemplo

• Dos hebras que incrementan concurrentemente el valor de un 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

5

hebra 1 hebra 2

contador

contador++ contador++


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

6

© 2014 Juan A. de la PuenteProgramación concurrente — Exclusión mutua

Secuencias de ejecución (1)

7

registro = contador

hebra 1

registro = registro+1

hebra 2

registro = contador


contador = registro

contador = registro

registro ⟵ 0

registro ⟵ 1

registro ⟵ 0

registro ⟵ 1

contador ⟵ 1

contador ⟵ 1

contador == 0

contador == 1


Secuencias de ejecución (2)

8

registro = contador

hebra 1


hebra 2

registro = contador


contador = registro

contador = registro

registro ⟵ 0

registro ⟵ 1

registro ⟵ 1

registro ⟵ 2

contador ⟵ 2

contador ⟵ 1

contador == 0

contador == 2


Condición de carrera

9

• ¡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


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); } }

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

11

hebra1 hebra2

Contador

- cuenta

+ incrementar() + valor()


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; } }

12



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

13



// 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(); ... }

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 ningunaotra 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

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

17


Ejemplo

18

registro = contador

hebra 1


hebra 2

registro = contador


contador = registro

contador = registro

registro ⟵ 0

registro ⟵ 1

registro ⟵ 1

registro ⟵ 2

contador ⟵ 2

contador ⟵ 1

contador == 0

contador == 2

bloquear cerrojocerrojo bloqueado

bloquear cerrojo

desbloquear cerrojo

desbloquear cerrojo

cerrojo desbloqueado

(cerrojo desbloqueado)

(cerrojo bloqueado)


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

19

Monitores


Exclusión mutua en Java

21

• 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


Métodos sincronizados

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

22

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;

}

}


Métodos sincronizados (con9nuación)

• Las llamadas concurrentes a métodos sincronizados se ejecutan en exclusión mutua

23

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

• 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


Implementación

24

!lock

entry set

hebra en método

sincronizado

hebras en espera


Algunos detalles

• Sólo se ejecutan en exclusión mutua los métodos sincronizados ‣ si se olvida sincronizar algún método se pueden producir condiciones de carrera

• Los métodos de clase también se pueden sincronizar ‣ se usa un cerrojo para la clase y uno por cada objeto

• Los constructores no se pueden sincronizar ‣ pero sólo se invocan al crear un objeto

25


Monitores

• Un monitor es una clase que encapsula datos compar9dos y operaciones con los mismos ‣ todos los campos de datos se hacen privados -‐ sólo se puede acceder a ellos a través de métodos

‣ todos los métodos están sincronizados

• Es un esquema clásico para construir programas concurrentes ‣ inventado por Per Brinch Hansen y C. Anthony Hoare (1984)

• Ventajas ‣ la sincronización se especifica al mismo 9empo que los datos ‣ las hebras que acceden a los datos no 9enen que incluir ningún mecanismo especial ‣ consistente con los principios de la programación con objetos

26


Bloques sincronizados

• Permiten definir regiones crí9cas mutuamente exclusivas con una granularidad menor !

!

!

• Las instrucciones del cuerpo se ejecutan en exclusión mutua

• Se usa el cerrojo asociado al objeto • Puede ser ú9l para mejorar las prestaciones • Pero es más diwcil de usar que los métodos sincronizados

27

synchronized(objeto) { instrucciones }


Precauciones

• Hay que iden9ficar bien las regiones crí9cas ‣ secuencia de instrucciones donde se lee y se modifica el estado interno de los objetos compar9dos ‣ no siempre es evidente dónde están ‣ puede haber regiones crí9cas fuera de los datos encapsulados si no se han diseñado bien los métodos

!

• Hay que sincronizar todas las regiones crí9cas ‣ iden9ficar las operaciones con datos compar9dos y realizarlas como métodos sincronizados

28


Ejemplo (incorrecto)

29

public class Variable { private long valor = 0; ! public Variable (long valorInicial) { valor = valorInicial; } ! public synchronized void modificar(long v) { valor = v; } ! public synchronized long valor() { return valor; } }

… Variable v = new Variable(0); … long x = v.valor(); // ¡La región crítica es x +=1; // todo esto!! v.modificar(x); // ¡No está sincronizada! ...


Ejemplo (correcto)

30

public class Variable { private long valor = 0; ! … ! public synchronized void incrementar() { valor++; } ! … }

… v.incrementar (); // Ahora está sincronizado …

Datos volá9les


Datos volá9les

• Algunos campos de datos se pueden declarar volatile ‣ indica que el valor puede cambiar desde otras hebras ‣ en mul9procesadores no se hacen copias privadas ‣ se asegura que las lecturas y escrituras son atómicas -‐ ¡nada más!

!

• Puede ser eficiente si lo único que se hace es cambiar el valor en una hebra y leerlo en otra ‣ por ejemplo, para parar la ejecución de una hebra

32


Ejemplo

public class Tarea extends Thread { ! private volatile boolean vivo = true; ! public void run() { while (vivo) { // actividad concurrente } } ! public void para() { vivo = false; } }

33


Precauciones

• Sólo son atómicas la lectura y la escritura de datos primi9vos !!volatile int i; … i++; // ¡no es atómico, puede haber carreras !

!

• Si se declaran como volá9les arrays u objetos, los elementos individuales no están protegidos

34

Ejemplo


Ges9ón de un estacionamiento

• Varias entradas y salidas ‣ sensores que avisan cuando pasa un coche

• Supervisor ‣muestra la ocupación del estacionamiento (número de coches)

36

P

Entrada N

Entrada S Salida S

Sensor

Sensor Sensor

Supervisor


Diseño

37

«monitor»!Parking!

- n : natural!+ entra!+ sale!+ ocupado: natural

«thread»!Sensor!!

- acceso, id

«thread»!Supervisor


Parking

public class Parking {

! private int n = 0; // número de coches en el parking

// entra un coche por una de las puertas

public synchronized void entra (String puerta) {

n++;

}

// sale un coche por una de las puertas

public synchronized void sale (String puerta) {

n--;

}

// consulta

public synchronized int ocupado() {

return n;

}

}

38


Sensor

public class Sensor extends Thread { ! private String id; private Parking p; private Acceso acceso; // ENTRADA o SALIDA ! public Sensor(Parking p, String id, Acceso acceso) { this.p = p; this.id = id; this.acceso = acceso; } ! @Override public void run() { while (true) { … // detecta un coche switch (acceso) { case ENTRADA: p.entra(id); break; case SALIDA: p.sale(id); break; } } } }

39


Supervisor

public class Supervisor extends Thread {

! private Parking p;

public Supervisor(Parking p) {

this.p = p;

}

@Override

public void run() {

// comprueba el estado del parking cada 10 s

while (true) {

System.out.println("Número de plazas ocupadas: " + p.ocupado());

try {

sleep(10*1000);

} catch (InterruptedException e) {

System.err.println(e.toString());

}

}

}

}

40


Crí9ca

• El monitor protege el estado interno del estacionamiento ‣ no hay carreras al actualizar o leer !

• Pero no se asegura que el estado sea correcto ‣ no deberían entrar coches si el estacionamiento está lleno !

• Hace falta un mecanismo que permita imponer estas condiciones ‣ sincronización condicional

41

Resumen


Resumen

• El acceso concurrente a variables compar9das puede dar lugar a resultados erróneos ‣ carreras

• La forma de evitar este problema es asegurar la exclusión mutua entre las zonas donde se usan esas variables ‣ regiones crí9cas

• El mecanismo básico para conseguir la exclusión mutua es el cerrojo ‣ bloqueo y desbloqueo atómicos

• En Java se usan métodos y bloques sincronizados ‣ usan un cerrojo asociado implícitamente a cada objeto

43


Resumen (con9nuación)

• Los monitores son clases que aseguran un acceso correcto a objetos compar9dos ‣ todos los campos de datos son privados ‣ todos los métodos están sincronizados -‐ excepto los constructores

• Una clase que se puede usar sin problemas desde varias hebras se dice que es segura (thread safe)

44

Software

Programación concurrente: datos compartidos y exclusión mutua