Concurrencia: cuando dos hilos comparten datos

En el primer grado un hilo era una unidad que el planificador puede ejecutar, y un proceso la caja propietaria del espacio de direcciones. Ahora esa distincion empieza a doler. Dos hilos dentro de un proceso comparten los mismos datos: el mismo monton, las mismas variables globales, el mismo contador. Nada en el hardware les impide tocarlo en el mismo instante, y en cuanto lo hacen, la aritmetica que escribiste deja de ser la aritmetica que ejecuta la maquina.

Empieza por el ejemplo mas pequeno posible. Dos hilos, cada uno incrementa un contador compartido un millon de veces. Cualquier programador te dira que la respuesta es 2000000. Ejecutalo y lee el numero.

/* counter.c */
#include <pthread.h>
#include <stdio.h>

static long counter = 0;

static void *worker(void *arg) {
  (void)arg;
  for (long i = 0; i < 1000000; i++) {
    counter = counter + 1;
  }
  return NULL;
}

int main(void) {
  pthread_t a, b;
  pthread_create(&a, NULL, worker, NULL);
  pthread_create(&b, NULL, worker, NULL);
  pthread_join(a, NULL);
  pthread_join(b, NULL);
  printf("%ld\n", counter);
  return 0;
}

/* $ gcc -O2 -pthread counter.c -o counter && ./counter
 * 2000000   <- never guaranteed
 * 1431927   <- typical instead
 */Dos hilos, un contador compartido, ningun cerrojo. Se compila con gcc -O2 -pthread. El valor impreso cambia de una ejecucion a otra.

El cuerpo del bucle parece una accion pero son tres: leer el contador en un registro, sumar uno, escribirlo de vuelta. Un tic del planificador puede caer entre dos cualesquiera de ellas, y con dos nucleos los hilos ni siquiera se turnan. Aqui esta la secuencia mas corta en la que se pierde un incremento.

counter = 0

T1  r1 <- counter     r1 = 3417
T2  r2 <- counter     r2 = 3417
T1  r1 <- r1 + 1      r1 = 3418
T2  r2 <- r2 + 1      r2 = 3418
T1  counter <- r1     counter = 3418
T2  counter <- r2     counter = 3418

T1 done.  T2 done.  counter = 3418

Los dos hilos leen 3417, los dos suman uno, los dos escriben 3418. Hubo dos incrementos y el contador avanzo uno. Eso es una condicion de carrera: el resultado depende del orden que eligio el planificador por casualidad, no del programa. En una ejecucion real del programa de arriba salen unos 1,4 millones en lugar de 2 millones, y un numero distinto cada vez. El fallo no es raro ni es ruido aleatorio. Es la consecuencia inevitable de un entrelazado que no controlaste.

La misma perdida ocurre en todos los sitios donde aparece el patron leer - modificar - escribir: un saldo bancario, un contador de referencias, un elemento anadido a una lista, un contador de conexiones. Lo importante no es el operador. Lo importante es si el valor se lee y luego se reescribe en dos pasos separados por los que se puede colar otro hilo.

Para un solo contador hay una respuesta mas ligera. Los procesadores tienen instrucciones atomicas de leer-modificar-escribir (lock xadd en x86, ldrex y strex en ARM), y el compilador las expone como operaciones atomicas. Sin objeto de cerrojo, sin hilo esperando, sin seccion critica aparte.

atomic_long counter = 0;

void *worker(void *arg) {
  (void)arg;
  for (long i = 0; i < 1000000; i++) {
    atomic_fetch_add_explicit(&counter, 1, memory_order_relaxed);
  }
  return NULL;
}

/* lock xadd   -> uncontended, a few nanoseconds
 * contended   -> the cache line is ping-ponged between cores
 */

Lo que cuesta un cerrojo depende por completo de la contencion. Sin contencion, una suma atomica son unos nanosegundos y tomar y soltar un mutex unas decenas de nanosegundos: una sola instruccion y dos barreras. El problema empieza cuando un segundo hilo quiere el mismo cerrojo. Entonces el sistema operativo tiene que aparcar ese hilo, lo que significa entrar en el kernel, un cambio de contexto y mas tarde un despertar. Eso son microsegundos, no nanosegundos: dos o tres ordenes de magnitud mas que el trabajo protegido. Si la seccion critica son diez instrucciones y cuatro hilos se pelean por el cerrojo, el cerrojo pasa casi todo el tiempo moviendo hilos entre nucleos, y el programa va mas lento segun anades nucleos. Por eso un contador que crece es la clasica falsa optimizacion: la version atomica escala hasta que la linea de cache empieza a rebotar entre nucleos, y entonces tambien deja de escalar.

Ahora la parte incomoda: por que paso tu test el programa del contador? Una carrera necesita un entrelazado concreto, y los entrelazados no son igual de probables. En un nucleo libre los dos hilos corren tramos largos seguidos y la ventana mala se alcanza quizas una vez por millon de iteraciones. En una maquina cargada, o con un depurador enganchado, o en produccion bajo carga, esa ventana se alcanza continuamente. Asi que el test pasa en el portatil y el incidente ocurre en un servidor de 32 nucleos. Los fallos de concurrencia dependen del tiempo, y por eso la ausencia de un fallo no es prueba de correccion. Peor aun: un print anadido para investigar puede cambiar el tiempo lo suficiente como para esconder el fallo del todo.

El resumen honesto es que los humanos somos malos en esto, y la razon es concreta. Razonar sobre un programa secuencial es seguir un camino. Razonar sobre dos hilos es razonar sobre el conjunto de todos los entrelazados, y su numero crece de forma combinatoria con la longitud del codigo. Nadie tiene ese conjunto en la cabeza. Por eso la respuesta practica no es tener cuidado, sino reducir la superficie: manten el estado mutable compartido lo mas pequeno posible, prefiere datos inmutables entre hilos, sustituye la memoria compartida por una cola de mensajes cuando puedas y toma un cerrojo solo alrededor de las pocas instrucciones que de verdad lo necesitan. Donde la invariante no se pueda hacer obvia, hay que escribirla y comprobarla con herramientas hechas para eso - sanitizadores, verificadores de modelos y pruebas de estres que varian el tiempo a proposito -, no con tests unitarios normales.