Operaciones atómicas y objetos inmutables en Java

Problema

Un cerrojo para un solo +1

Una venta relámpago: 100 auriculares a mitad de precio, a las 10:00. La página del producto se abre miles de veces por segundo, y cada apertura incrementa el contador de visitas. De la lección sobre bloqueo sabes cómo no perder incrementos: un cerrojo alrededor de views++.

Eso es correcto. Pero cada hilo hace cola delante del cerrojo para un único +1. Un hilo que no consigue el cerrojo suele ser puesto a dormir y despertado más tarde por el sistema operativo. Eso cuesta mucho más que la suma misma.

El segundo problema es peor. El último artículo se compra con «si hay uno, disminuir en 1». Son dos pasos, y entre ellos otro hilo puede llevarse el mismo artículo.

La idea

Un paso indivisible

El procesador tiene instrucciones que leen, cambian y escriben una celda de memoria en un paso indivisible. Ningún otro hilo puede meterse en medio. Esto es una operación atómica. No hay cerrojo, nadie hace cola y nadie duerme.

En Java están en java.util.concurrent.atomic. AtomicInteger guarda un int, e incrementAndGet() es el +1 atómico y devuelve el valor nuevo. También hay addAndGet, getAndIncrement, y AtomicLong para long.

Míralo

El contador de visitas

Cuatro hilos, cada uno con 100 000 visitas:

AtomicInteger views = new AtomicInteger();
Runnable visitor = () -> {
    for (int i = 0; i < 100_000; i++) {
        views.incrementAndGet();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(visitor);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Vistas: " + views.get());

Vistas: 400000

400 000 en cada ejecución. Sin el +1 atómico sería menos y distinto cada vez, como en la lección sobre condiciones de carrera.

Más precisamente, para curiosos

LongAdder. Cuando muchos hilos incrementan el mismo AtomicInteger, todos golpean una celda de memoria y los procesadores se la pasan de uno a otro. LongAdder cuenta en varias celdas (una por grupo de hilos) y las suma solo en sum(). Es más rápido con mucha carga, pero no da el valor después de cada incremento. Sirve para contadores que solo se leen al final:

LongAdder views = new LongAdder();
Runnable visitor = () -> {
    for (int i = 0; i < 100_000; i++) {
        views.increment();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(visitor);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Vistas: " + views.sum());

Vistas: 400000

¿Cuánto más rápido que un cerrojo es? Depende de la máquina y de cuántos hilos peleen por una celda. Sin pelea, un +1 atómico son unos pocos nanosegundos. Un cerrojo sin pelea se acerca. La diferencia llega con muchos hilos: entonces el cerrojo pone hilos a dormir, mientras que la operación atómica solo repite.

La idea

Comprobar y cambiar: compare-and-set

Comprar no es solo −1. Es «si hay al menos uno, disminuir en 1». La comprobación y el cambio deben ser un solo paso.

Para esto hay una operación atómica más general: compare-and-set (CAS). Le das dos números: lo que crees que hay y lo que quieres que haya. Cambia el valor solo si sigue siendo lo que crees, y te dice si lo consiguió. Si otro hilo lo ha cambiado entretanto, CAS no toca nada y responde «no».

Entonces comprar es un bucle:

leer las existencias;
si es 0, rechazar;
CAS: «si sigue siendo tanto, déjalo en uno menos»;
si CAS falla, alguien ha comprado entretanto: volver a 1.

En Java esto es compareAndSet(expected, new), que devuelve true o false.

Míralo

Los últimos tres auriculares

class FlashSale {
    private final AtomicInteger stock;

    FlashSale(int items) {
        stock = new AtomicInteger(items);
    }

    boolean tryBuy() {
        while (true) {
            int left = stock.get();
            if (left == 0) return false; // agotado
            if (stock.compareAndSet(left, left - 1)) {
                return true;
            }
            // alguien cambió stock: leer otra vez
        }
    }

    int stock() {
        return stock.get();
    }
}

Paso a paso, en palabras

Los últimos 3 auriculares: las existencias son 3. Los hilos A y B llaman a tryBuy() al mismo tiempo.
A lee las existencias: left = 3.
B las lee antes de que A haya cambiado nada: también 3.
B: compareAndSet(3, 2). «Si todavía es 3, ponlo en 2.» Todavía es 3, así que se escribe 2. B compró.
A prueba lo mismo: «si todavía es 3…». Ahora es 2, así que no se escribe nada y la respuesta es false. No se pierde nada.
A no espera ni se rinde: el bucle da otra vuelta y A lee de nuevo: 2. Ningún hilo ha dormido.
A: «si todavía es 2, ponlo en 1». Todavía es 2: se escribe 1. A también compró.
Dos compradores, dos vendidos, existencias 1. No hay cerrojo: el procesador comprueba y escribe en un solo paso, y el que pierde solo repite el bucle.

Nadie espera: el hilo que perdió solo repite dos líneas. Esto se llama lock-free. Cien artículos para 160 intentos:

FlashSale sale = new FlashSale(100);
AtomicInteger sold = new AtomicInteger();
AtomicInteger refused = new AtomicInteger();
Runnable buyers = () -> {
    for (int i = 0; i < 40; i++) {
        if (sale.tryBuy()) sold.incrementAndGet();
        else refused.incrementAndGet();
    }
};
List<Thread> threads = new ArrayList<>();
for (int t = 0; t < 4; t++) {
    Thread thread = new Thread(buyers);
    threads.add(thread);
    thread.start();
}
for (Thread thread : threads) thread.join();
System.out.println("Vendidos: " + sold.get());
System.out.println("Rechazados: " + refused.get());
System.out.println("Existencias: " + sale.stock());

Vendidos: 100
Rechazados: 60
Existencias: 0

Cuántas veces dio vueltas el bucle es distinto en cada ejecución, por eso el programa no lo imprime. Los totales son siempre los mismos: 100 vendidos, 60 rechazados, 0 en existencias.

Pruébalo

Predice la salida

Aquí los dos «hilos» están escritos uno tras otro en un solo hilo, para que el orden sea el mismo que en la escena en cada ejecución. ¿Qué imprime?

AtomicInteger stock = new AtomicInteger(3);
int seenByA = stock.get();
int seenByB = stock.get();
System.out.println("B: " + stock.compareAndSet(seenByB, seenByB - 1));
System.out.println("A: " + stock.compareAndSet(seenByA, seenByA - 1));
seenByA = stock.get();
System.out.println("A otra vez: " + stock.compareAndSet(seenByA, seenByA - 1));
System.out.println("Existencias: " + stock.get());

Respuesta

B: true
A: false
A otra vez: true
Existencias: 1

B: true
A: true
A otra vez: false
Existencias: 1

B: true
A: true
A otra vez: true
Existencias: 0

Pruébalo

Completa

¿Con qué compara el CAS al comprar?

if (stock.compareAndSet(, left - 1)) {

Pruébalo

Encuentra el error

Un colega ha simplificado la compra. Cada línea por sí sola es segura, y aun así en la venta se venden 103 auriculares de 100. ¿En qué línea está el error?

Elige la línea con el error.

Problema

La lista de precios que cambia a la mitad

A las 10:00 el administrador empieza la promoción: auriculares de 60 a 48 €, funda de 15 a 12 €, cable de 5 a 4 €. Al mismo tiempo las cajas calculan carritos. Si los precios están en un diccionario compartido y cambian uno por uno, una caja puede leer el precio nuevo de los auriculares y el viejo de la funda:

// el administrador
prices.put("headphones", 48);
prices.put("case", 12);
prices.put("cable", 4);

// el cobro, al mismo tiempo
int total = 0;
for (String item : cart) total += prices.get(item);

El carrito sale en 68 €: un total que no fue correcto en ningún momento. Ni con los precios viejos (80 €), ni con los nuevos (64 €). Y un HashMap o Dictionary que un hilo cambia mientras otro lee puede incluso lanzar una excepción o devolver un valor incorrecto.

La idea

No lo cambies, reemplázalo entero

La lista de precios se lee muchas veces y se cambia pocas. Entonces no la cambies nunca. Hazla un objeto inmutable: una vez creada, se queda igual. Para la promoción el administrador hace una lista de precios nueva y cambia una referencia: «la lista de precios actual es esta».

Un objeto que nadie cambia puede ser leído por tantos hilos como quieras, sin ninguna protección.
Lo único compartido es la referencia, y cambiarla es un paso atómico.
La caja toma la referencia una vez, al empezar el carrito, y calcula todo el carrito con ella. Ve la lista de precios vieja entera o la nueva entera, nunca una mezcla.

Un record con Map.copyOf es inmutable: los campos son final, y Map.copyOf hace una copia que no se puede cambiar. AtomicReference guarda la lista de precios actual: set la cambia y get la lee, así que cada hilo ve la última escrita.

record PriceList(int version, Map<String, Integer> prices) {
    PriceList {
        prices = Map.copyOf(prices); // una copia no modificable
    }

    int total(List<String> cart) {
        int sum = 0;
        for (String item : cart) sum += prices.get(item);
        return sum;
    }
}

Map<String, Integer> regular = Map.of("headphones", 60, "case", 15, "cable", 5);
Map<String, Integer> promo = Map.of("headphones", 48, "case", 12, "cable", 4);
List<String> cart = List.of("headphones", "case", "cable");
AtomicReference<PriceList> current =
        new AtomicReference<>(new PriceList(1, regular));
AtomicInteger mixed = new AtomicInteger();

Thread admin = new Thread(() -> {
    for (int v = 2; v <= 1001; v++) {
        Map<String, Integer> prices = v % 2 == 0 ? promo : regular;
        current.set(new PriceList(v, prices)); // una instantánea nueva, una referencia
    }
});
Thread checkout = new Thread(() -> {
    for (int i = 0; i < 100_000; i++) {
        PriceList list = current.get(); // una instantánea para todo el carrito
        int total = list.total(cart);
        if (total != 80 && total != 64) mixed.incrementAndGet();
    }
});
admin.start();
checkout.start();
admin.join();
checkout.join();
PriceList last = current.get();
System.out.println("Totales comprobados: 100000");
System.out.println("Totales mezclados: " + mixed.get());
System.out.println("Última versión: " + last.version() + ", total " + last.total(cart) + " €");

Totales comprobados: 100000
Totales mezclados: 0
Última versión: 1001, total 80 €

La caja ha comprobado decenas de miles de carritos mientras la lista de precios cambiaba mil veces, y ni un solo total es mezclado. Cuántos carritos fueron por la lista vieja y cuántos por la nueva es distinto en cada ejecución, por eso el programa no lo imprime.

Más precisamente, para curiosos

Así funcionan también las colecciones «copy on write»: CopyOnWriteArrayList en Java, ImmutableList en C#. Cada cambio hace una copia nueva, y leer no necesita cerrojo. Compensa cuando hay muchas lecturas y pocas escrituras. Si las escrituras son frecuentes, copiar sale caro.

La inmutabilidad es honesta solo si llega hasta el fondo. Un objeto con un campo final que apunta a una lista modificable no es inmutable: la lista se puede cambiar desde fuera. Por eso es Map.copyOf, no el Map que se pasó.

Cómo es en los otros lenguajes: record y Map.copyOf con AtomicReference en Java; record con ImmutableDictionary y Volatile o Interlocked.Exchange en C#; una dataclass frozen, una tuple o MappingProxyType y asignación en Python; Object.freeze y mensajes entre Workers en JavaScript.

La idea

Cuando lo atómico no basta

Una reserva mueve un artículo de las existencias a la cuenta de reservados. La regla es que los dos juntos suman siempre 10 000. Dos variables atómicas no la mantienen:

AtomicInteger stock = new AtomicInteger(10);
AtomicInteger reserved = new AtomicInteger(0);

void reserve() {
    stock.decrementAndGet();    // cada línea es atómica,
    reserved.incrementAndGet(); // las dos juntas no
}

Entre las dos líneas el auditor ve 9999 en total. Lo atómico protege un valor. Cuando la regla trata de varios valores juntos, necesitas un cerrojo alrededor de todos los cambios y de la comprobación:

class Warehouse {
    private final Object lock = new Object();
    private int stock;
    private int reserved;

    Warehouse(int stock) {
        this.stock = stock;
    }

    boolean reserve() {
        synchronized (lock) { // las dos o ninguna
            if (stock == 0) return false;
            stock--;
            reserved++;
            return true;
        }
    }

    int audit() {
        synchronized (lock) {
            return stock + reserved;
        }
    }

    String report() {
        synchronized (lock) {
            return "Existencias: " + stock + ", reservados: " + reserved;
        }
    }
}

Warehouse warehouse = new Warehouse(10_000);
AtomicInteger broken = new AtomicInteger();
Runnable reserver = () -> {
    while (warehouse.reserve()) { }
};
Runnable auditor = () -> {
    for (int i = 0; i < 50_000; i++) {
        if (warehouse.audit() != 10_000) broken.incrementAndGet();
    }
};
List<Thread> threads = List.of(new Thread(reserver), new Thread(reserver), new Thread(auditor));
for (Thread thread : threads) thread.start();
for (Thread thread : threads) thread.join();
System.out.println(warehouse.report());
System.out.println("Comprobaciones rotas: " + broken.get());

Existencias: 0, reservados: 10000
Comprobaciones rotas: 0

Más precisamente, para curiosos

Otra manera sin cerrojo: los dos valores en un objeto inmutable (existencias, reservados), y el cambio con un CAS sobre la referencia (AtomicReference.compareAndSet). Un objeto nuevo con los dos valores nuevos reemplaza al viejo de golpe. Eso combina las dos ideas de esta lección, pero el cerrojo suele ser más claro.

Qué usar cuándo:

un valor, un contador o una bandera: una operación atómica;
comprobar y cambiar un valor: un bucle CAS;
datos que se leen mucho y se cambian poco: un objeto inmutable y un cambio de referencia;
varios valores relacionados: un cerrojo.

Ejercicio

Un vale con usos limitados

Resuelve la tarea en tu editor.

El vale «SPRING20» se puede usar 50 veces. Ocho hilos, cada uno con 10 clientes, intentan usarlo al mismo tiempo. Escribe Coupon con tryUse() de modo que el vale nunca se use más de 50 veces. Sin cerrojo: con un bucle de compare-and-set. Imprime cuántas veces se usó, cuántos rechazos hubo y cuántos usos quedan:

Usados: 50
Rechazados: 30
Quedan: 0

Más tareas

El máximo. Guarda el pedido más grande del día mientras muchos hilos añaden pedidos. Pista: un bucle CAS que escribe solo si el nuevo es mayor.
Dos promociones. Dale una versión a la lista de precios y haz que dos administradores publiquen al mismo tiempo. ¿Cómo evitas que se pierda la promoción de uno? (Pista: cambia la referencia con CAS solo si la versión sigue siendo la que leíste.)
El auditor sin cerrojo. Pon las existencias y la cuenta de reservados en un objeto inmutable y cámbialo con CAS. Comprueba que el auditor sigue viendo siempre 10 000.

Test

Ponte a prueba

1. Las existencias son 6. Un hilo llama a CAS «si es 5, ponlo en 4». ¿Qué pasa?El hilo duerme hasta que el valor sea 5Se escribe 4No se escribe nada y la respuesta es «falló»: el hilo tiene que leer otra vez

2. tryBuy tiene «si las existencias son > 0» y luego «disminuir en 1». Las dos líneas son atómicas. ¿Por qué aun así vende más de lo que hay?No puede: si cada línea es atómica, todo el método es seguroPorque las operaciones atómicas a veces pierden incrementosEntre la comprobación y la disminución otro hilo puede llevarse el último artículo: cada paso es indivisible, pero los dos juntos no

3. Las cajas leen la lista de precios miles de veces por segundo, y cambia una vez al día. ¿Cuál es la mejor manera de compartirla?Un objeto inmutable: el administrador hace una lista de precios nueva y cambia una referencia; cada caja lee la lista vieja entera o la nueva enteraUn cerrojo alrededor de cada lectura de un precioUn diccionario compartido en el que el administrador cambia los precios uno por uno

4. Reservas un artículo: las existencias bajan 1 y la cuenta de reservados sube 1. El auditor comprueba que la suma sea siempre 10 000. ¿Qué necesitas?Nada: la suma se calcula al finalUn cerrojo alrededor de los dos cambios y de la comprobaciónDos variables atómicas

Operaciones atómicas y objetos inmutables

Cookies