Operaciones atómicas y objetos inmutables

Código en:JavaC#PythonJavaScript

En resumen: Una operación atómica (como +1 o compare-and-set) se ejecuta de una sola vez, sin que otro hilo la interrumpa, y protege datos compartidos sin cerrojo; un objeto inmutable no cambia nunca.

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 C# están en la clase Interlocked. Interlocked.Increment(ref views) es el +1 atómico sobre un campo o variable int normal y devuelve el valor nuevo. También hay Interlocked.Add, Interlocked.Decrement y versiones para long.

Míralo

El contador de visitas

Cuatro hilos, cada uno con 100 000 visitas:

int views = 0;
var threads = new List<Thread>();
for (int t = 0; t < 4; t++)
{
    var thread = new Thread(() =>
    {
        for (int i = 0; i < 100_000; i++)
        {
            Interlocked.Increment(ref views);
        }
    });
    threads.Add(thread);
    thread.Start();
}
foreach (var thread in threads) thread.Join();
Console.WriteLine($"Vistas: {views}");

Salida

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

Contar en tu propio lugar. Cuando muchos hilos incrementan el mismo campo, todos golpean una celda de memoria y los procesadores se la pasan de uno a otro. Si el valor se necesita solo al final, es más rápido que cada hilo cuente en una variable local y haga un solo Interlocked.Add al final. Java tiene una clase hecha para esto: LongAdder.

¿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:

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

En C# esto es Interlocked.CompareExchange(ref field, new, expected). Ojo con el orden: el valor nuevo va antes que el esperado. El método devuelve el valor que encontró. Si es el esperado, el cambio se ha hecho. Volatile.Read lee el campo para que veas el último valor escrito por otro hilo.

Míralo

Los últimos tres auriculares

class FlashSale
{
    private int stock;

    public FlashSale(int items)
    {
        stock = items;
    }

    public bool TryBuy()
    {
        while (true)
        {
            int left = Volatile.Read(ref stock);
            if (left == 0) return false; // agotado
            int was = Interlocked.CompareExchange(
                ref stock, left - 1, left);
            if (was == left) return true;
            // alguien cambió stock: leer otra vez
        }
    }

    public int Stock => Volatile.Read(ref stock);
}

Paso a paso, en palabras

1. Los últimos 3 auriculares: las existencias son 3. Los hilos A y B llaman a TryBuy() al mismo tiempo.
2. A lee las existencias: left = 3.
3. B las lee antes de que A haya cambiado nada: también 3.
4. B: CompareExchange(…, 2, 3). «Si todavía es 3, ponlo en 2.» Todavía es 3, así que se escribe 2. B compró.
5. 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.
6. A no espera ni se rinde: el bucle da otra vuelta y A lee de nuevo: 2. Ningún hilo ha dormido.
7. A: «si todavía es 2, ponlo en 1». Todavía es 2: se escribe 1. A también compró.
8. 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:

var sale = new FlashSale(100);
int sold = 0, refused = 0;
var threads = new List<Thread>();
for (int t = 0; t < 4; t++)
{
    var thread = new Thread(() =>
    {
        for (int i = 0; i < 40; i++)
        {
            if (sale.TryBuy()) Interlocked.Increment(ref sold);
            else Interlocked.Increment(ref refused);
        }
    });
    threads.Add(thread);
    thread.Start();
}
foreach (var thread in threads) thread.Join();
Console.WriteLine($"Vendidos: {sold}");
Console.WriteLine($"Rechazados: {refused}");
Console.WriteLine($"Existencias: {sale.Stock}");

Salida

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?

int stock = 3;
int seenByA = Volatile.Read(ref stock);
int seenByB = Volatile.Read(ref stock);
bool b = Interlocked.CompareExchange(ref stock, seenByB - 1, seenByB) == seenByB;
Console.WriteLine($"B: {b}");
bool a = Interlocked.CompareExchange(ref stock, seenByA - 1, seenByA) == seenByA;
Console.WriteLine($"A: {a}");
seenByA = Volatile.Read(ref stock);
a = Interlocked.CompareExchange(ref stock, seenByA - 1, seenByA) == seenByA;
Console.WriteLine($"A otra vez: {a}");
Console.WriteLine($"Existencias: {stock}");

Respuesta

B: True
A: True
A otra vez: False
Existencias: 1

B: True
A: True
A otra vez: True
Existencias: 0

B: True
A: False
A otra vez: True
Existencias: 1

Comprobar

Pruébalo

Completa

¿Con qué compara el CAS al comprar?

int was = Interlocked.CompareExchange(
    ref stock, left - 1, );

Comprobar

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.

1public bool TryBuy()2{3 if (Volatile.Read(ref stock) > 0)4 {5 Interlocked.Decrement(ref stock);6 return true;7 }8 return false;9}

Comprobar

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["headphones"] = 48;
prices["case"] = 12;
prices["cable"] = 4;

// el cobro, al mismo tiempo
int total = cart.Sum(item => prices[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 ImmutableDictionary (de System.Collections.Immutable) es inmutable: las propiedades son de solo lectura y el diccionario no se puede cambiar. La lista de precios actual es una variable normal. Volatile.Write la cambia y Volatile.Read la lee, así que cada hilo ve la última escrita. Interlocked.Exchange también cambia la referencia y devuelve la vieja.

record PriceList(int Version, ImmutableDictionary<string, int> Prices)
{
    public int Total(List<string> cart) => cart.Sum(item => Prices[item]);
}

var regular = new Dictionary<string, int> { ["headphones"] = 60, ["case"] = 15, ["cable"] = 5 }.ToImmutableDictionary();
var promo = new Dictionary<string, int> { ["headphones"] = 48, ["case"] = 12, ["cable"] = 4 }.ToImmutableDictionary();
var cart = new List<string> { "headphones", "case", "cable" };
var current = new PriceList(1, regular);
int mixed = 0;

var admin = new Thread(() =>
{
    for (int v = 2; v <= 1001; v++)
    {
        var prices = v % 2 == 0 ? promo : regular;
        Volatile.Write(ref current, new PriceList(v, prices)); // una instantánea nueva, una referencia
    }
});
var checkout = new Thread(() =>
{
    for (int i = 0; i < 100_000; i++)
    {
        var list = Volatile.Read(ref current); // una instantánea para todo el carrito
        int total = list.Total(cart);
        if (total != 80 && total != 64) Interlocked.Increment(ref mixed);
    }
});
admin.Start();
checkout.Start();
admin.Join();
checkout.Join();
Console.WriteLine("Totales comprobados: 100000");
Console.WriteLine($"Totales mezclados: {mixed}");
Console.WriteLine($"Última versión: {current.Version}, total {current.Total(cart)} €");

Salida

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.

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:

int stock = 10;
int reserved = 0;

void Reserve()
{
    Interlocked.Decrement(ref stock);    // cada línea es atómica,
    Interlocked.Increment(ref reserved); // 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 readonly object sync = new object();
    private int stock;
    private int reserved;

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

    public bool Reserve()
    {
        lock (sync) // las dos o ninguna
        {
            if (stock == 0) return false;
            stock--;
            reserved++;
            return true;
        }
    }

    public int Audit()
    {
        lock (sync)
        {
            return stock + reserved;
        }
    }

    public string Report()
    {
        lock (sync)
        {
            return $"Existencias: {stock}, reservados: {reserved}";
        }
    }
}

var warehouse = new Warehouse(10_000);
int broken = 0;
ThreadStart reserver = () =>
{
    while (warehouse.Reserve()) { }
};
ThreadStart auditor = () =>
{
    for (int i = 0; i < 50_000; i++)
    {
        if (warehouse.Audit() != 10_000) Interlocked.Increment(ref broken);
    }
};
var threads = new List<Thread> { new Thread(reserver), new Thread(reserver), new Thread(auditor) };
foreach (var thread in threads) thread.Start();
foreach (var thread in threads) thread.Join();
Console.WriteLine(warehouse.Report());
Console.WriteLine($"Comprobaciones rotas: {broken}");

Salida

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 (Interlocked.CompareExchange sobre la referencia). 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:

Salida

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

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Hilos · Por qué hilos · Condición de carrera · Bloqueo
• Continúa en: Deadlock · Productor y consumidor · Cómo probar código concurrente
• Ejercicios sobre el tema: Concurrencia y condiciones de carrera