Qué hay detrás de counter++

1. La ilusión de la atomicidad

A nivel de código fuente, counter++ parece una sola operación. El programador la escribe como una línea, la lee como una instrucción y espera que se ejecute de forma indivisible. Pero esta es una ilusión: el compilador traduce esa línea en varias instrucciones de máquina, y el procesador las ejecuta una por una.

La atomicidad no es una propiedad del código fuente: es una propiedad de la ejecución. Una operación es atómica si se ejecuta de forma indivisible, sin que otro hilo pueda observar un estado intermedio. counter++ no cumple esta propiedad en la mayoría de los procesadores.

Esta ilusión es la causa de la mayoría de las condiciones de carrera: el programador asume que counter++ es atómico, pero no lo es. Cuando dos hilos ejecutan counter++ simultáneamente, sus instrucciones se intercalan y el resultado es incorrecto.

2. Las tres instrucciones de máquina

A nivel de máquina, counter++ se descompone en tres instrucciones:

1. LOAD (leer): leer el valor de counter de la memoria a un registro de la CPU. leer
2. ADD (modificar): incrementar el valor en el registro. modificar
3. STORE (escribir): escribir el valor del registro de vuelta a la memoria. escribir

Estas tres instrucciones son independientes: el procesador las ejecuta una por una, y el planificador puede interrumpir entre ellas. Si dos hilos ejecutan counter++ simultáneamente, sus tres instrucciones se pueden intercalar de formas que producen resultados incorrectos.

El problema no es que las instrucciones sean lentas: es que no son indivisibles. Entre el LOAD y el STORE, otro hilo puede leer el mismo valor y escribir el mismo resultado, perdiendo un incremento.

3. Lo que genera el compilador

El compilador traduce counter++ en instrucciones de máquina específicas del procesador. En x86-64, con GCC, el código generado es:

movl    counter(%rip), %eax    ; LOAD: leer counter a eax
addl    $1, %eax              ; ADD: incrementar eax
movl    %eax, counter(%rip)    ; STORE: escribir eax a counter

Con optimización (-O2), el compilador puede optimizar el código, pero las tres instrucciones siguen estando presentes (a menos que el compilador pueda probar que no hay concurrencia, lo que no puede hacer en general):

movl    counter(%rip), %eax
incl    %eax
movl    %eax, counter(%rip)

El compilador puede usar incl (increment) en lugar de addl $1, pero sigue siendo una instrucción separada de LOAD y STORE. La operación sigue sin ser atómica.

Si el compilador puede probar que counter es local (no compartido), puede optimizar más agresivamente. Pero si counter es global o compartido, el compilador debe generar las tres instrucciones.

4. Cómo se intercalan las instrucciones

Cuando dos hilos ejecutan counter++ simultáneamente, el planificador puede intercalar sus instrucciones de cualquier forma. El espacio de intercalados es enorme: con 2 hilos y 3 instrucciones cada uno, hay C(6,3) = 20 formas de intercalar, aunque muchas son equivalentes.

Los intercalados que producen un resultado incorrecto son aquellos en que ambos hilos leen el mismo valor antes de que alguno escriba. En ese caso, ambos suman 1 al mismo valor y ambos escriben el mismo resultado, perdiendo un incremento.

El número de intercalados incorrectos crece exponencialmente con el número de hilos y de incrementos. Con 4 hilos y 100.000 incrementos, el número de intercalados posibles es astronómico, y solo unos pocos producen el resultado correcto.

5. Los casos posibles para dos hilos

Para dos hilos que ejecutan counter++ una vez cada uno (counter empieza en 0), hay tres casos posibles:

El caso 3 es el que produce el error: ambos hilos leen 0, ambos suman 1, y ambos escriben 1. El resultado es 1 en lugar de 2.

Hay más casos intermedios (por ejemplo, A: LOAD → A: ADD → B: LOAD → A: STORE → B: ADD → B: STORE, que también da 1), pero todos los incorrectos tienen en común que ambos hilos leen el mismo valor antes de que alguno escriba.

De los 20 intercalados posibles, solo 2 producen el resultado correcto (2). Los otros 18 producen 1. La probabilidad de obtener el resultado correcto es del 10 %.

6. Generalización a N hilos

Con N hilos y M incrementos por hilo, el número de intercalados posibles es (3NM)! / (3!)^(NM), que es astronómico. Solo unos pocos producen el resultado correcto (N×M).

La probabilidad de obtener el resultado correcto disminuye exponencialmente con el número de hilos y de incrementos. Con 4 hilos y 100.000 incrementos, la probabilidad de obtener el resultado correcto es prácticamente cero.

Esto explica por qué el resultado del experimento del tema 3 es siempre incorrecto: con 4 hilos y 100.000 incrementos, la probabilidad de obtener 400.000 es prácticamente nula.

7. Por qué el resultado siempre es menor o igual

En una condición de carrera de incremento, el resultado siempre es menor o igual al esperado, nunca mayor. Esto es porque:

• Los incrementos se pierden, no se crean: cuando dos hilos leen el mismo valor, ambos escriben el mismo resultado. El segundo incremento se pierde.
• No hay valores intermedios inválidos: el valor siempre es un entero entre 0 y N×M. No se pueden crear valores que no correspondan a un número de incrementos.
• La pérdida es monótona: cada carrera pierde al menos un incremento. Nunca se gana un incremento extra.

Esta propiedad es útil para detectar el problema: si un contador compartido da resultados menores que los esperados, probablemente hay una condición de carrera. Si diera resultados mayores, el problema sería diferente (por ejemplo, una doble escritura).

8. Cómo el hardware puede hacerlo atómico

Los procesadores modernos tienen instrucciones que ejecutan counter++ de forma atómica, en una sola operación indivisible. En x86, la instrucción LOCK INC (o LOCK ADD) hace esto:

lock incl counter(%rip)    ; LOCK INC: incrementar counter de forma atómica

El prefijo LOCK le dice al procesador que la instrucción debe ser atómica: ningún otro procesador puede acceder a la memoria mientras se ejecuta. Esto se logra bloqueando el bus de memoria (en procesadores antiguos) o usando protocolos de coherencia de caché (en procesadores modernos).

Con lock incl, la operación de incremento es atómica: no hay punto intermedio en el que otro hilo pueda leer el valor parcial. El resultado siempre es correcto, sin importar el intercalado.

9. El prefijo LOCK en x86

El prefijo LOCK se puede aplicar a varias instrucciones de x86:

No todas las instrucciones soportan LOCK. Las instrucciones de lectura/escritura simples (MOV) no lo soportan porque no son operaciones de read-modify-write.

En procesadores modernos (desde Pentium), el prefijo LOCK no bloquea el bus de memoria completo: usa el protocolo de coherencia de caché (MESI) para invalidar la línea de caché en otros procesadores. Esto es más eficiente que bloquear el bus.

10. Los límites de la atomicidad por hardware

Aunque el hardware puede hacer counter++ atómico, hay limitaciones:

• Solo para operaciones simples: el hardware solo puede hacer atómicas operaciones simples (incremento, suma, compare-and-swap). Operaciones complejas (como insertar en una lista enlazada) no son atómicas a nivel de hardware.
• Costo: las instrucciones atómicas son más lentas que las normales (por el overhead de coherencia de caché).
• Escalabilidad: con muchos procesadores compitiendo por el mismo dato, las instrucciones atómicas se serializan (por el protocolo de coherencia de caché), lo que reduce el rendimiento.
• No resuelve todos los problemas: la atomicidad de counter++ no resuelve el problema de la sección crítica (que puede incluir múltiples operaciones).

Por eso, las operaciones atómicas del hardware son la base para construir mecanismos de sincronización de más alto nivel (mutex, semáforos), pero no son la solución completa.

11. Simulador de intercalados

Este simulador permite explorar los intercalados de dos hilos que ejecutan counter++. Cada hilo tiene 3 instrucciones (LOAD, ADD, STORE). El simulador genera intercalados aleatorios y muestra el resultado:

12. Experimento: ver el assembly

Este experimento muestra el código assembly generado por el compilador:

$ cat > asm_test.c << 'EOF'
volatile int counter = 0;
void inc(void) { counter++; }
EOF
$ gcc -std=c17 -O0 -S -o asm_test.s asm_test.c
$ cat asm_test.s

inc:
    pushq   %rbp
    movq    %rsp, %rbp
    movl    counter(%rip), %eax    # LOAD
    addl    $1, %eax              # ADD
    movl    %eax, counter(%rip)    # STORE
    popq    %rbp
    ret
$ gcc -std=c17 -O2 -S -o asm_test2.s asm_test.c
$ cat asm_test2.s

inc:
    movl    counter(%rip), %eax
    addl    $1, %eax
    movl    %eax, counter(%rip)
    ret

El compilador genera las tres instrucciones (LOAD, ADD, STORE) tanto con como sin optimización. Con -O2 se eliminan las instrucciones de prólogo y epílogo (push/pop), pero las tres instrucciones de la operación siguen presentes.

Para generar la instrucción atómica, se usa __atomic_fetch_add o _Atomic en C11:

$ cat > atomic_test.c << 'EOF'
#include <stdatomic.h>
_Atomic int counter = 0;
void inc(void) { counter++; }
EOF
$ gcc -std=c17 -O2 -S -o atomic_test.s atomic_test.c
$ cat atomic_test.s

inc:
    lock addl   $1, counter(%rip)    # LOCK ADD: atómico
    ret

Con _Atomic, el compilador genera lock addl, que es atómico. Una sola instrucción en lugar de tres.

13. Resumen

• counter++ son tres instrucciones de máquina: LOAD, ADD, STORE.
• El planificador puede interrumpir entre ellas, causando condiciones de carrera.
• Los intercalados incorrectos producen resultados menores que el esperado.
• El hardware puede hacer la operación atómica con LOCK INC o LOCK ADD.
• La atomicidad por hardware tiene costo: coherencia de caché.
• Las operaciones atómicas son la base para construir mutex y semáforos.
• volatile no hace la operación atómica.
• En C11, _Atomic genera instrucciones atómicas automáticamente.

14. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Compila asm_test.c con -O0 y -O2 y compara el assembly.
2. Compila atomic_test.c y verifica que se genera lock addl.
3. Usa objdump -d para ver las instrucciones de counter++ en un programa compilado.
4. Modifica el simulador para 3 hilos y observa los resultados.
5. Investiga qué instrucciones de x86 soportan el prefijo LOCK.
6. Explica por qué las operaciones atómicas por hardware no resuelven todos los problemas de concurrencia.