Hilos, condiciones de carrera y cerrojos

Un hilo es una secuencia de ejecución dentro de un proceso. Varios hilos pueden trabajar con los mismos datos del programa, pero cada uno necesita su propia posición en el código y sus propias llamadas a funciones aún sin terminar.

Qué se comparte y qué pertenece a un hilo

Los hilos de un proceso comparten código, variables globales y estáticas, objetos del montículo, descriptores de archivo abiertos y el identificador de proceso. Cada hilo tiene su propio contador de programa, registros, pila e identificador de hilo. Una variable global int total designa un único objeto compartido. Una variable local ordinaria int i en la función trabajadora designa un objeto distinto en cada llamada.

Un proceso con tres hilos tiene tres pilas en direcciones distintas del mismo espacio de direcciones. Una pila no es un compartimento protegido: otro hilo puede acceder a una variable local si recibe su dirección. Esa compartición solo es válida mientras la variable existe. Un puntero a un marco de pila de una función que ha terminado no puede mantener viva la variable. Los arreglos locales grandes y la recursión profunda también pueden agotar la pila de un hilo.

Cambios entre hilos

El sistema operativo guarda el estado de ejecución de cada hilo en un bloque de control de hilo, o TCB. Cuando cambia de T1 a T2, guarda los registros de T1 y restaura los de T2. El cálculo sin terminar de T1 permanece en sus registros guardados hasta que vuelva a ejecutarse.

Para los hilos del mismo proceso, el espacio de direcciones sigue siendo el mismo durante el cambio. No es necesario cambiar las tablas de páginas, lo que normalmente hace que este cambio cueste menos que cambiar entre procesos. La memoria compartida también implica fallos compartidos: una escritura mediante un puntero no válido puede dañar los datos de otro hilo, y un fallo que termine el proceso acaba con todos los hilos.

¿Por qué usar varios hilos?

El paralelismo significa ejecutar en el mismo instante en distintos núcleos de CPU. Cuatro partes independientes de un cálculo pueden acercarse a una aceleración de cuatro veces en cuatro núcleos, si el trabajo compartido y la coordinación no se convierten en cuellos de botella. Los hilos también permiten que un programa solape la espera con el trabajo: mientras uno espera una lectura de disco o una respuesta de red, otro puede usar la CPU.

La concurrencia significa que las ejecuciones avanzan durante periodos que se solapan. En un núcleo, el planificador cambia entre hilos, por lo que son concurrentes sin ejecutarse en paralelo. Un solo núcleo sigue permitiendo errores de concurrencia: un cambio puede interrumpir una actualización compartida entre sus instrucciones máquina.

¿Quién planifica los hilos?

Linux y Windows usan un modelo uno a uno: cada hilo ordinario de una aplicación corresponde a un hilo planificado por el núcleo. Distintos hilos pueden ejecutarse en distintos núcleos, y una llamada bloqueante bloquea al hilo que la realiza. Una biblioteca muchos a uno planifica varios hilos de usuario sobre un hilo del núcleo. Sus cambios pueden costar poco, pero no puede ejecutar esos hilos en varios núcleos, y una llamada al sistema bloqueante puede detener a todo el grupo.

Crear A antes que B no garantiza que A se ejecute primero. Si A imprime «A» y B imprime «B», puede aparecer «AB» o «BA». El orden de creación establece cuándo un hilo pasa a estar disponible para ejecutarse; el planificador elige su momento de ejecución.

La interfaz de hilos POSIX, o pthreads, inicia una función de C en otro hilo. Incluye <pthread.h> y compila con un comando como gcc -pthread -o sum sum.c. La opción -pthread proporciona la configuración del compilador y del enlazador para código con hilos.

Crea un hilo con argumentos estables

La llamada pthread_create(&t, NULL, worker, arg) guarda un identificador de hilo en t e inicia worker(arg). El puntero de atributos NULL solicita los valores predeterminados. Una función trabajadora tiene la firma void *worker(void *arg): el argumento y el valor de retorno son punteros. Una estructura permite que ese único puntero transporte varios campos.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

struct range { int lo, hi; long result; };

void *sum_range(void *arg) {
    struct range *r = arg;
    long sum = 0;
    for (int n = r->lo; n <= r->hi; n++)
        sum += n;
    r->result = sum;
    return NULL;
}

El hilo creador prepara dos estructuras, {1, 50, 0} y {51, 100, 0}, y pasa una dirección distinta a cada hilo trabajador. Mantén ambas estructuras en memoria hasta que los trabajadores terminen. Cada trabajador acumula en su propia variable local sum y escribe solo en su propio campo result.

pthread_create devuelve 0 si tiene éxito y un número de error si falla. Comprueba directamente ese número devuelto; no establece errno para comunicar el fallo. Solo una creación exitosa proporciona un hilo cuya terminación se pueda esperar.

Espera a la terminación antes de leer los resultados

Después de crear correctamente ambos trabajadores, el hilo principal llama a pthread_join(t[0], NULL) y pthread_join(t[1], NULL). La espera a la terminación bloquea hasta que termina el hilo indicado. Una espera exitosa también hace que las escrituras de ese trabajador sean visibles para el hilo que esperó. El hilo principal puede entonces leer 1275 y 3775 y sumarlos para obtener 5050 sin un mutex: los trabajadores escribieron en objetos separados y el hilo principal esperó antes de leerlos.

Iniciar ambos hilos antes de esperar a su terminación permite que su trabajo se solape. Crear un trabajador y esperar inmediatamente a que termine antes de crear el siguiente hace que los trabajadores se ejecuten uno después del otro.

Este es el programa principal. Termina si hay un error de pthread, por lo que nunca usa un identificador de una creación fallida:

static void require_success(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

int main(void) {
    struct range jobs[2] = {{1, 50, 0}, {51, 100, 0}};
    pthread_t threads[2];
    for (int i = 0; i < 2; i++)
        require_success(pthread_create(&threads[i], NULL,
                                      sum_range, &jobs[i]));
    for (int i = 0; i < 2; i++)
        require_success(pthread_join(threads[i], NULL));
    printf("%ld\n", jobs[0].result + jobs[1].result);
    return 0;
}

Para recoger un puntero devuelto, pasa la dirección donde se recibirá: void *answer; pthread_join(t, &answer);. El puntero debe referirse a memoria que siga existiendo después de que termine el trabajador, como memoria asignada en el montículo o una estructura que pertenezca al creador. Devolver &local_result desde el trabajador no es válido porque su variable local deja de existir cuando la función retorna.

Evita compartir una variable de bucle que cambia

Pasar &i a cada trabajador en un bucle de creación pasa repetidamente una misma dirección. Los trabajadores pueden leerla después de que el bucle la haya cambiado, por lo que varios pueden recibir el mismo identificador aparente. Usa un arreglo en su lugar: asigna ids[i] = i, pasa &ids[i] y mantén el arreglo en memoria y sin cambios hasta que terminen todas las esperas.

Termina hilos y procesos de forma deliberada

Retornar de main o llamar a exit() en cualquier hilo termina todo el proceso y puede interrumpir a los trabajadores. El hilo principal normalmente espera a que los trabajadores terminen antes de retornar. Llamar a pthread_exit() solo termina el hilo que llama; los demás pueden continuar.

Un hilo separado libera automáticamente sus recursos de hilo cuando termina y no se puede esperar a su terminación. Asegúrate de esperar una vez a la terminación de cada hilo que lo permita o de separarlo. Esperar a la terminación no protege a dos trabajadores que actualizan el mismo objeto mientras ambos se ejecutan.

La sentencia counter++ parece pequeña, pero el incremento ordinario de un entero compartido no es una operación indivisible. Suele cargar un valor, sumar en un registro y guardar el resultado. Otro hilo puede ejecutarse entre esos pasos.

Un seguimiento que pierde un incremento

Empieza con counter igual a 50. Trata la carga, la suma y el almacenamiento como pasos de máquina separados:

Dos incrementos deberían haber producido 52. En cambio, T1 sobrescribe el resultado de T2 con un valor calculado a partir del 50 anterior. Esto es una actualización perdida.

Un cambio de contexto conserva los registros de T1 en su TCB. Cuando T1 reanuda su ejecución, su registro sigue conteniendo 51; no vuelve a cargar el contador compartido solo porque T2 se haya ejecutado. El error está en la secuencia sin protección, no en que el planificador restaure un registro incorrecto.

Compara con una ejecución en serie

Si T1 completa los tres pasos antes de que T2 cargue el valor, T1 guarda 51 y después T2 guarda 52. Invertir el orden de los hilos completos también da 52. El resultado intercalado 51 no puede surgir de ninguno de los dos órdenes en serie. Para encontrar este tipo de fallo, marca una lectura, coloca después de ella la escritura de otro hilo y reanuda el cálculo del primer hilo basado en el valor antiguo.

Este seguimiento es un modelo del error a nivel de máquina. En C real, los accesos conflictivos sin sincronizar a un entero compartido ordinario forman una carrera de datos, que produce un comportamiento indefinido. C no limita ese programa a los resultados de un modelo sencillo de intercalado de instrucciones.

Por qué superar las pruebas es una prueba débil

Dos hilos que realizan 10 000 000 de incrementos cada uno deberían producir 20 000 000. Las ejecuciones experimentales sin protección pueden imprimir distintos totales menores, como 19 345 221 y 19 221 041 en ejemplos publicados. Una ejecución con buen resultado solo significa que el resultado observado fue aceptable por casualidad.

El intervalo vulnerable puede tener solo unas pocas instrucciones. Distintos números de núcleos, opciones del compilador o cargas del sistema pueden revelar un orden de ejecución que miles de ejecuciones anteriores no detectaron. Para dos hilos que realizan cada uno un incremento modelado desde cero, el modelo de seguimiento permite 1 o 2. Con al menos dos incrementos por hilo, órdenes de ejecución poco frecuentes pueden dejar un total tan bajo como 2 incluso cuando aumenta el número de incrementos previstos.

Corrige la operación, no su apariencia

Declarar el entero como volatile no hace indivisibles su carga, suma y almacenamiento ni sincroniza los hilos. Escribir todo el trabajo en una línea no cambia nada. Incluso una instrucción x86 que suma directamente en memoria necesita la forma atómica adecuada para coordinarse entre núcleos.

Protege toda la lectura-modificación-escritura con un mutex compartido o usa una operación atómica de lectura-modificación-escritura de C11 como atomic_fetch_add. La misma necesidad existe en un núcleo: un cambio provocado por el temporizador puede separar la carga del almacenamiento incluso sin ejecución en paralelo.

Un error de concurrencia puede afectar a un acceso a memoria o a toda una regla de negocio. Identifica tanto los objetos compartidos como la operación que debe parecer indivisible a los demás hilos.

¿Condición de carrera o carrera de datos?

Una condición de carrera se produce cuando la corrección depende de los tiempos relativos. Una carrera de datos se produce cuando distintos hilos acceden a la misma ubicación de memoria sin sincronización, al menos uno escribe en ella y al menos un acceso no es atómico. C11 y C++11 asignan comportamiento indefinido a una carrera de datos.

Los accesos atómicos pueden evitar una carrera de datos mientras una operación más amplia sigue teniendo una condición de carrera. Por ejemplo, las lecturas y escrituras protegidas individualmente no mantienen válida una decisión entre unas y otras. Dos hilos pueden leer cada uno un saldo suficiente, liberar el cerrojo y retirar después dinero basándose en esa decisión desactualizada.

Analiza una retirada

Un saldo empieza en 100. Dos hilos solicitan 80 cada uno. La regla es aceptar una retirada solo cuando el saldo la cubre.

1. T1 comprueba 100 y decide que su retirada puede tener éxito.
2. T2 también comprueba 100 y toma la misma decisión.
3. T1 resta 80 y deja 20.
4. T2 actúa según su decisión anterior y resta 80 de 20, dejando −60.

Proteger solo la resta no corrige esa secuencia. Protege la comprobación y la resta con el mismo cerrojo, mantenido de forma continua. Entonces un hilo deja 20 y el siguiente comprueba 20 y rechaza la retirada. Otro orden de ejecución sin protección puede perder una resta y dejar 20 después de haber pagado ambas retiradas, lo cual también es incorrecto.

Encuentra la sección crítica

Una sección crítica es la región que accede a datos compartidos y debe excluir los accesos de otros hilos. Una secuencia de lectura-modificación-escritura primero lee datos, calcula un valor nuevo y lo vuelve a escribir. Una secuencia de comprobar y actuar decide si se permite una acción y después la realiza. Las operaciones con listas, la inicialización diferida y la creación de archivos también pueden contener estos patrones.

Un cerrojo proporciona exclusión mutua: como máximo un hilo participante está dentro de la región protegida a la vez. Una operación atómica aparece ante los demás hilos participantes como una sola operación completa; no pueden observar un estado a medio terminar. Un mutex proporciona esa visión solo para el código que sigue el mismo acuerdo de uso del cerrojo.

No todos los objetos necesitan un cerrojo. Los datos a los que accede un hilo permanecen privados salvo que se comparta su dirección. Los datos inicializados por completo antes de que comiencen los trabajadores y que después solo se leen pueden compartirse sin cerrojo. Evalúa quién puede acceder a un objeto y si las escrituras se solapan con su uso, no solo dónde se declaró.

Qué garantiza una solución correcta

• Exclusión mutua: los hilos que compiten no pueden entrar juntos.
• Progreso: cuando la sección está libre y hay hilos que quieren entrar, los hilos que no intentan entrar no pueden posponer indefinidamente la elección de uno que entre.
• Espera acotada: después de una solicitud, hay un límite al número de entradas de otros hilos que pueden precederla.

atomic_fetch_add(&count, 1) de C11 realiza una actualización atómica sobre un atomic_int. La atomicidad está garantizada incluso en una plataforma que implementa la operación con un cerrojo interno de la biblioteca. Hacer atómicos por separado dos campos de cuentas sigue sin convertir una transferencia entre ellos en una transacción atómica; la relación entre los campos también necesita protección.

Un mutex es un cerrojo que permite que un hilo a la vez posea una región protegida. Un hilo lo adquiere antes de acceder a los datos protegidos y lo libera después. Si otro hilo lo posee, una llamada bloqueante para adquirirlo espera.

Inicializa el mutex compartido

Usa pthread_mutex_t de <pthread.h>. Un mutex estático puede empezar con pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;. Un objeto creado dinámicamente puede inicializar su campo con pthread_mutex_init(&obj->lock, NULL). La inicialización debe terminar antes de que cualquier hilo use el mutex.

Este es un ejemplo de operación sobre un contador que usa un mutex compartido inicializado de forma estática. La función auxiliar comprueba los valores devueltos por pthread, que son directamente números de error:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static long counter = 0;  // guarded by m

static void check(int rc) {
    if (rc != 0) {
        fprintf(stderr, "pthread error: %d\n", rc);
        exit(EXIT_FAILURE);
    }
}

void increment(void) {
    check(pthread_mutex_lock(&m));
    counter = counter + 1;
    check(pthread_mutex_unlock(&m));
}

Cada lectura o actualización concurrente de counter debe seguir esta misma regla. Una función independiente que use otro mutex no se coordinaría con increment.

¿Qué ocurre mientras se posee el mutex?

T1 adquiere m, carga el contador, calcula y guarda el resultado. Si T2 llama a pthread_mutex_lock(&m) durante ese intervalo, no puede superar la llamada hasta adquirir el mutex después de que T1 lo libere. A T1 aún se le puede expropiar la CPU: un mutex impide la entrada de otros hilos, no los cambios de contexto.

Para la regla del saldo, adquiere el mutex antes de evaluar balance >= amount. Resta solo si se cumple, registra el éxito o el fallo y después libera el cerrojo. Un saldo de 100 con dos solicitudes de 80 permite exactamente un éxito y deja 20.

Elige cómo esperar

pthread_mutex_trylock(&m) retorna inmediatamente: 0 significa que quien llamó adquirió el mutex; EBUSY significa que no lo hizo porque el mutex estaba ocupado. La ruta en la que está ocupado puede realizar otro trabajo y no debe acceder a los datos protegidos. pthread_mutex_timedlock espera hasta un plazo absoluto. Estas interfaces siguen requiriendo comprobar los códigos de retorno y liberar un cerrojo solo después de adquirirlo correctamente.

Respeta la propiedad y el tiempo de vida

El hilo propietario libera un mutex. Un mutex normal no recursivo bloquea si su propietario intenta adquirirlo de nuevo. Un mutex con comprobación de errores informa de fallos como volver a adquirirlo mediante EDEADLK o que un hilo no propietario lo libere mediante EPERM. Un mutex recursivo cuenta las adquisiciones repetidas de su propietario y requiere el mismo número de liberaciones. No dependas de un mutex predeterminado para detectar usos incorrectos: su comportamiento depende del tipo al que lo asigna la implementación y de la operación.

Cuando todos los hilos hayan dejado de usar el mutex y esté desbloqueado, llama a pthread_mutex_destroy. Destruir o liberar un objeto mientras otro hilo todavía puede adquirir su mutex rompe el tiempo de vida del mutex. Pasar el mutex mediante un puntero conserva su identidad; copiarlo no crea otro identificador válido para el mismo cerrojo.

La granularidad de los cerrojos es la cantidad de estado compartido que cubre un cerrojo. Determina qué operaciones deben esperarse unas a otras, incluso cuando se ejecutan en núcleos distintos.

¿Un cerrojo grande o varios más pequeños?

Un diseño de grano grueso coloca un mutex alrededor de toda una estructura o subsistema. Tiene una regla de protección sencilla, pero las operaciones sin relación entre sí se serializan. Un diseño de grano fino asigna mutex distintos a distintas cuentas, cubetas o regiones. Así, los hilos pueden trabajar en distintas regiones a la vez, a costa de más operaciones con cerrojos y reglas más complicadas.

Coloca el cerrojo junto al estado que protege:

struct account {
    pthread_mutex_t lock;
    long balance;
    unsigned id;
};

Una operación sobre una cuenta adquiere su mutex. Una transferencia entre dos cuentas distintas necesita ambos porque cambia la relación entre ellas. Elige un orden fijo, como el orden creciente de identificador de cuenta, y úsalo en todas las rutas. De lo contrario, un hilo puede poseer A y esperar B mientras otro posee B y espera A.

Un cerrojo pone un límite a la tasa de procesamiento

Supón que cada operación posee un único cerrojo global durante 2 µs. El trabajo protegido puede completar como máximo una operación cada 2 µs:

Añadir núcleos no puede hacer que dos operaciones posean el mismo mutex simultáneamente. La sobrecarga del cerrojo y otro trabajo pueden reducir aún más la tasa alcanzada. Por tanto, la duración de la parte protegida es un límite útil que calcular antes de esperar una aceleración.

Acorta la sección sin romper la operación

Prepara el trabajo privado antes de adquirir el mutex. Para insertar en una lista, asigna primero el nuevo nodo e inicializa su clave. Adquiere el mutex de la lista solo al leer el nodo inicial actual y enlazar el nodo. Si falla la asignación de memoria, no habrá ningún cerrojo adquirido.

Las operaciones lentas de entrada/salida, la impresión o una función de retorno desconocida pueden mantener detenidos a todos los hilos en espera. Traslada ese trabajo fuera cuando los datos puedan seguir siendo válidos allí. Mantén juntas una decisión y su actualización dependiente: acortar una retirada liberando el cerrojo entre la comprobación del saldo y la resta destruye la corrección.

Evalúa tres propiedades distintas

La exclusión mutua plantea si el diseño impide realmente la entrada de hilos que compiten. La equidad plantea si un hilo en espera acaba obteniendo un turno o puede sufrir inanición. El rendimiento plantea cuánto cuesta el cerrojo con un hilo, con varios hilos en una CPU y con hilos en varias CPU. Un cerrojo puede ser correcto y aun así ser injusto o lento.

La contención ocurre cuando los hilos compiten por un cerrojo ya ocupado. Con mucha contención, también trasladan líneas de caché compartidas del cerrojo y de los datos entre núcleos. Un experimento publicado con un contador tardó unos 0,03 s para un millón de actualizaciones de un hilo, pero más de 5 s para dos hilos que hacían un millón cada uno; son mediciones de esa configuración, no tiempos universales.

Para un experimento de escalabilidad, mantén fijo el trabajo de cada hilo. La escalabilidad ideal permite que N hilos en N núcleos hagan N veces el trabajo en el tiempo original. Empieza con una estructura sencilla y correcta, mide la espera y el tiempo total, y divide un cerrojo solo donde la concurrencia adicional compense su sobrecarga.

Un mutex puede estar implementado perfectamente y aun así un programa puede usarlo de forma incorrecta. Revisa toda la ruta de una función, incluidas las lecturas, los errores, las funciones de retorno y la destrucción de objetos.

Libera la propiedad en cada salida

Esta función deja el cerrojo adquirido en su ruta de fallo:

pthread_mutex_lock(&m);
if (failed) return -1;
update_shared_state();
pthread_mutex_unlock(&m);

El hilo que retorna puede terminar, pero el mutex sigue ocupado. Quien llame después esperará una liberación que nunca ocurrirá. Usa una sola ruta de liberación de recursos o coloca una liberación del cerrojo antes de cada retorno. Con llamadas a pthread comprobadas, la estructura puede ser:

int rc = -1;
check(pthread_mutex_lock(&m));
if (!failed) {
    update_shared_state();
    rc = 0;
}
check(pthread_mutex_unlock(&m));
return rc;

Es más fácil revisar un punto de liberación que muchos dispersos. La propiedad importante es que cada cerrojo adquirido correctamente se libere en cada salida ordinaria.

Sigue la regla de protección también en las lecturas

Una función de estado que «solo lee» puede tener una carrera con otra que actualiza. También puede observar campos relacionados en distintas etapas de una actualización. Si una operación de lista publica un nodo antes de completar sus campos, un lector sin protección puede seguir un puntero hacia datos sin terminar. Adquiere el cerrojo documentado para cada acceso cuya corrección dependa de él.

Usar mutex distintos para el mismo objeto no ayuda. Si T1 adquiere lockA y T2 adquiere lockB, ambas adquisiciones pueden tener éxito. Un mutex declarado como una variable local nueva dentro de cada trabajador hace que este error sea fácil de pasar por alto: cada hilo adquiere su propio objeto, por lo que no hay exclusión compartida.

Conserva tanto la identidad como los límites de la operación

No se puede copiar un pthread_mutex_t mediante una asignación o copiando la estructura que lo contiene y después usarlo como un segundo identificador de mutex. Usar la copia es un comportamiento indefinido. Pasa un puntero al mutex compartido original.

Comprueba también dónde se producen las liberaciones. Una función que adquiere el cerrojo para comprobar un saldo, lo libera y después vuelve a adquirirlo para restar ha protegido los accesos individuales, pero ha dejado que la decisión quede desactualizada. Mantén toda la secuencia de comprobar y actuar bajo una posesión continua del cerrojo.

Evita esperarte a ti mismo

Llamar a código desconocido mientras se posee un mutex puede volver a entrar inesperadamente en el mismo objeto protegido. Con un mutex normal, una segunda llamada de adquisición por parte del propietario lo bloquea. Un mutex con comprobación de errores informa de este fallo, mientras que un mutex recursivo permite la propiedad anidada y necesita las liberaciones correspondientes. Elige un tipo de forma deliberada; no uses la recursividad para ocultar un diseño de protección poco claro.

Mantén las operaciones lentas de entrada/salida y las suspensiones fuera de una sección crítica compartida cuando sea posible. Antes de destruir el mutex o liberar el objeto que lo contiene, asegúrate de que ningún hilo lo posee ni puede volver a acceder a él. La inicialización, el uso y la destrucción deben seguir un orden claro.

Usa herramientas de ejecución para revelar fallos observados

ThreadSanitizer, activado con -fsanitize=thread, y Helgrind de Valgrind pueden informar de carreras de datos y usos incorrectos de cerrojos en las ejecuciones que observan. Combina sus informes con una revisión de los accesos compartidos y de los posibles intercalados. Una ejecución sin informes establece que la herramienta no encontró problemas en esas ejecuciones; una ruta no probada sigue requiriendo razonamiento.

Un cerrojo necesita una forma fiable de elegir un único propietario. Una lectura ordinaria seguida de una escritura ordinaria deja un hueco en esa decisión, aunque el propio trabajo protegido sea muy corto.

El control de interrupciones tiene una función limitada

En una CPU, un núcleo puede desactivar brevemente las interrupciones alrededor de una sección crítica no bloqueante para impedir que una interrupción provoque una expropiación dentro de ella. Esto depende de permanecer en la CPU sin bloquearse ni cambiar de hilo voluntariamente. El núcleo usa la técnica para operaciones internas breves.

No es un mutex de aplicación de uso general. Las instrucciones de control de interrupciones son privilegiadas; permitir que una aplicación las use sin restricciones le permitiría monopolizar la CPU. Desactivar las interrupciones en un núcleo no impide que los demás accedan a los mismos datos. Los intervalos largos con interrupciones desactivadas también retrasan su atención y pueden provocar la pérdida de eventos en algunos dispositivos.

Sigue el cerrojo defectuoso basado en un indicador

Considera este pseudocódigo similar a C:

while (flag == 1) { }
flag = 1;
// critical section
flag = 0;

Empieza con flag en 0. T1 lo comprueba y sale del bucle; después se detiene antes de la asignación. T2 comprueba el mismo 0, lo pone en 1 y entra. T1 reanuda su ejecución, lo pone en 1 y también entra. Ambos superaron la comprobación antes de que cualquiera reclamara la propiedad.

Hacer atómicas por separado la lectura y la escritura eliminaría una carrera de datos sobre el indicador, pero seguiría dejando dos operaciones separadas en este protocolo. La adquisición de la propiedad necesita una lectura-modificación-escritura atómica o un algoritmo de sincronización más completo.

El bucle vacío es espera activa: una comprobación repetida que consume tiempo de CPU. En una CPU, un hilo que realiza espera activa después de que se haya expropiado la CPU al propietario no puede hacer que este la libere antes. Debe acabar permitiendo que el propietario se ejecute.

La solución de Peterson para dos hilos

El algoritmo de Peterson coordina dos hilos con un indicador de interés por hilo y un turno compartido. El hilo i realiza:

flag[i] = 1;
turn = 1 - i;
while (flag[1 - i] == 1 && turn == 1 - i) { }
// critical section
flag[i] = 0;

Anuncia su interés, da prioridad al otro hilo en caso de empate y espera solo mientras el otro esté interesado y tenga prioridad. Bajo consistencia secuencial, las operaciones de cada hilo conservan el orden del programa y todos los hilos observan un orden común. En ese modelo, el algoritmo de Peterson proporciona exclusión mutua, progreso y espera acotada para dos hilos.

El orden de memoria también importa

Los procesadores y compiladores modernos pueden hacer que las operaciones de memoria sean visibles en un orden distinto del código fuente. Un almacenamiento puede permanecer en un búfer mientras una carga posterior lee la memoria. Entonces ambos hilos pueden ver el indicador de interés del otro como 0 y entrar ambos. Los enteros compartidos ordinarios de C también introducen carreras de datos de C.

Una implementación válida necesita operaciones atómicas y una ordenación adecuadas, como operaciones atómicas de C11 con consistencia secuencial para los indicadores y el turno. volatile no proporciona esa sincronización. Los cerrojos prácticos combinan una operación indivisible de adquisición de propiedad con garantías de ordenación de memoria para que los accesos protegidos permanezcan en el lado correcto de la adquisición y la liberación.

Una lectura-modificación-escritura atómica combina la lectura de una ubicación y su actualización en una acción indivisible. Elimina el hueco que permite que dos hilos superen juntos la comprobación de un indicador ordinario.

Intercambia el indicador y examina su valor anterior

Comprobar y establecer, o intercambio atómico, escribe un valor nuevo y devuelve el anterior. Con un indicador inicialmente en 0, T1 intercambia el valor por 1 y recibe 0, por lo que entra. T2 intercambia el valor por 1 y recibe 1, por lo que espera. Hasta que la liberación escriba 0, ningún otro intercambio puede devolver 0.

Este es un cerrojo de espera activa de C11 que usa las operaciones atómicas predeterminadas con consistencia secuencial:

#include <stdatomic.h>

static atomic_flag held = ATOMIC_FLAG_INIT;

void lock(void) {
    while (atomic_flag_test_and_set(&held)) { }
}

void unlock(void) {
    atomic_flag_clear(&held);
}

La ordenación importa tanto como el indicador. La adquisición debe mantener los accesos posteriores de la sección crítica después de la adquisición exitosa; la liberación debe mantener los accesos anteriores de la sección crítica antes de la liberación. Borrar el indicador también debe ser atómico; mezclar almacenamientos ordinarios con accesos atómicos no implementa esta transferencia.

Compara antes de sustituir

Comparar e intercambiar, o CAS, cambia un valor solo cuando es igual a un valor esperado. Supón que dos hilos leen un contador con valor 7 y cada uno quiere sumar 1. T2 cambia correctamente 7 por 8. El intento de T1 de cambiar 7 por 8 falla ahora, por lo que T1 vuelve a intentarlo desde 8 y lo cambia por 9. El reintento conserva ambos incrementos.

atomic_compare_exchange_strong de C11 devuelve éxito o fallo y actualiza el argumento esperado en caso de fallo. En cambio, algún pseudocódigo de estilo hardware devuelve el valor anterior almacenado. Comprueba qué convención usa un seguimiento. En x86, xchg con memoria implementa el intercambio, mientras que lock cmpxchg proporciona comparar e intercambiar de forma atómica.

Otras piezas básicas de hardware

Carga enlazada y almacenamiento condicional, o LL/SC, lee mientras establece una reserva y después intenta escribir. La escritura condicional falla si otra escritura invalida la reserva; también puede fallar por otros motivos, por lo que pertenece a un bucle de reintentos. LDXR/STXR de ARM y lr/sc de RISC-V admiten este patrón.

Obtener y sumar suma atómicamente y devuelve el valor anterior. C11 lo ofrece como atomic_fetch_add; x86 proporciona lock xadd. Devolver el valor anterior lo hace útil para repartir números de boleto únicos.

C garantiza el comportamiento atómico de las operaciones de su biblioteca atómica. No exige que todos los tipos atómicos sean sin cerrojos; algunas operaciones usan un cerrojo interno de la biblioteca. atomic_flag tiene la garantía de funcionar sin cerrojos, y atomic_is_lock_free comprueba otros objetos.

Correcto no significa equitativo ni rápido

Un cerrojo con comprobar y establecer proporciona exclusión mutua, pero no orden de llegada: un hilo puede perder repetidamente la carrera después de la liberación y sufrir inanición. En una CPU, cuatro hilos con intervalos de 10 ms de planificación por turnos pueden desperdiciar 30 ms en espera activa entre tres hilos en espera antes de que el propietario al que se expropió la CPU vuelva a ejecutarse. En varios núcleos, con el propietario en ejecución y secciones cortas, una breve espera activa puede evitar la sobrecarga de suspender y despertar.

Un cerrojo con comprobar y establecer recuerda si está ocupado, pero no quién ha estado esperando. Un cerrojo por boletos añade un orden de llegada mediante un dispensador atómico de boletos y un contador de turno.

Toma un número y espera tu turno

Ambos contadores empiezan en 0. Cada hilo que llama incrementa atómicamente ticket y conserva su valor anterior como mine. Solo entra cuando turn es igual a mine. El propietario libera el cerrojo incrementando turn una vez.

#include <stdatomic.h>

static atomic_uint ticket = 0;
static atomic_uint turn = 0;

void lock(void) {
    unsigned mine = atomic_fetch_add(&ticket, 1);
    while (atomic_load(&turn) != mine) { }
}

void unlock(void) {
    atomic_fetch_add(&turn, 1);
}

Estas operaciones atómicas predeterminadas de C11 proporcionan tanto atomicidad como ordenación con consistencia secuencial. Cada hilo que llama conserva mine en su propia variable local. El contador compartido de boletos dispensa números únicos para los boletos pendientes.

Sigue tres llegadas

A toma el boleto 0 y entra porque turn es 0. B toma el boleto 1 y espera. C toma el boleto 2 y espera. El siguiente boleto sin usar es ahora el 3, mientras que el turno actual sigue siendo 0.

Cuando A libera el cerrojo, turn pasa a 1, por lo que B entra. C sigue esperando el 2. La liberación de B hace avanzar turn a 2 y C entra. Un hilo que llega después obtiene el boleto 3 y no puede adelantarse a C.

Esta distinción importa al seguir el funcionamiento: ticket registra el siguiente número que se entregará; turn registra el número que se está atendiendo. Tomar un boleto solo cambia el dispensador. La liberación hace avanzar la atención.

Qué garantiza la equidad

Un hilo espera detrás de los hilos con boletos anteriores. Si cada propietario acaba liberando el cerrojo y los hilos que tiene delante pueden ejecutarse, las llegadas posteriores no pueden adelantarlo. El número de secciones críticas de otros hilos que tiene delante está limitado por los boletos anteriores pendientes. Esto proporciona espera acotada y evita la inanición bajo esas condiciones de progreso.

La garantía se refiere al orden de entrada, no al tiempo transcurrido. Un propietario que se detiene durante mucho tiempo puede hacer que todos los que llegan después también esperen mucho tiempo. Un número de boleto no puede obligar al planificador a ejecutar a su propietario.

Costes que permanecen con el orden por boletos

Cada hilo en espera sigue realizando espera activa. Si el hilo al que le toca entrar a continuación deja de ejecutarse, los hilos posteriores que están listos esperan aunque ningún hilo ocupe actualmente la sección crítica. Este es un coste de planificación del orden estricto.

Los hilos en espera también leen una única ubicación compartida turn. Cada liberación cambia la línea de caché que todos observan, lo que produce tráfico entre núcleos. Los cerrojos de espera activa basados en colas reducen ese tráfico al permitir que cada hilo observe una ubicación local separada; Linux pasó de cerrojos de espera activa por boletos a diseños basados en colas.

Los contadores de boletos reales usan aritmética sin signo. Las comprobaciones de igualdad pueden funcionar tras el retorno cíclico cuando el número de boletos pendientes se mantiene por debajo del rango de valores del contador. Reutilizar un número mientras un boleto anterior igual aún está pendiente destruiría la unicidad y la exclusión.

Un cerrojo correcto puede desperdiciar la mayor parte de una CPU en esperas. La estrategia de espera adecuada depende de si el propietario puede ejecutarse y de cuánto tiempo poseerá el cerrojo.

Ceder la CPU abandona un turno

Un hilo en espera puede llamar a yield() después de un intento fallido de adquirir la propiedad. La cesión lo pasa del estado de ejecución al estado listo para que el planificador pueda seleccionar otro hilo. Sigue estando listo para ejecutarse, por lo que puede ser seleccionado de nuevo pronto y volver a fallar. Con 100 hilos en una CPU, hasta 99 hilos en espera pueden ejecutarse y ceder la CPU antes de que el propietario al que se expropió la CPU reciba otro turno. La cesión reduce la espera activa, pero no proporciona un orden de entrada equitativo.

El bloqueo retira al hilo del trabajo listo para ejecutarse

Un cerrojo que suspende hilos coloca en una cola de espera al hilo que no consigue adquirirlo. No consume CPU mientras está bloqueado. Al liberar el cerrojo se despierta a un hilo en espera para que pueda volver a ejecutarse. Un pequeño cerrojo protector interno de espera activa puede proteger el indicador y la cola; ese protector solo se posee durante breves operaciones de gestión.

Separar «decidir suspenderse» de «suspenderse realmente» crea un riesgo de despertar perdido:

1. Un hilo en espera se coloca en la cola y libera el protector.
2. Se detiene antes de llamar a park().
3. El propietario libera el cerrojo y llama a unpark() para ese hilo.
4. Si se descarta ese despertar, el hilo se suspende después sin que quede nadie para despertarlo.

setpark() de Solaris anuncia la intención de suspenderse. Un unpark que intervenga antes hace que el park posterior retorne inmediatamente. El protocolo conecta la decisión con el bloqueo real.

Linux usa una comparación y bloqueo atómicos

Un futex combina una palabra en memoria de usuario con soporte del núcleo para la espera. futex_wait(addr, expected) bloquea solo si la palabra sigue siendo igual al valor esperado; la comprobación y la decisión de bloquear son atómicas con respecto a las operaciones sobre esa palabra de futex. Si una liberación ya la cambió, el hilo que llama no se suspende basándose en la expectativa desactualizada.

futex_wake(addr, n) despierta hasta n hilos en espera. Un cerrojo sin contención puede adquirirse y liberarse con instrucciones atómicas en el espacio de usuario, evitando una llamada al sistema. Los mutex de pthread de glibc de Linux usan futexes para las esperas con contención. Un despertar deja a un hilo listo para ejecutarse; su protocolo de cerrojo aún debe establecer la propiedad antes de acceder a los datos protegidos.

Realiza una breve espera activa y después suspéndete

Un cerrojo de dos fases primero realiza una breve espera activa y después se bloquea si la espera continúa. La espera activa puede merecer la pena cuando el propietario se ejecuta en otro núcleo y la espera prevista es más corta que suspender y despertar. El bloqueo es preferible para esperas largas o cuando hay más hilos listos para ejecutarse que núcleos. En una CPU, un hilo en espera activa no puede ayudar a terminar a un propietario que ha dejado de ejecutarse.

La prioridad de planificación puede detener el progreso

En la inversión de prioridades, un hilo de alta prioridad espera un mutex que posee un hilo de baja prioridad mientras el trabajo de prioridad media impide que el propietario use la CPU. Suspender al hilo de alta prioridad evita la espera activa, pero no elimina ese retraso de planificación.

La herencia de prioridades eleva temporalmente la prioridad del propietario a la del hilo en espera de mayor prioridad, permitiéndole terminar y liberar el cerrojo. El Mars Pathfinder de la NASA sufrió reinicios por inversión de prioridades en 1997; activar la herencia de prioridades del mutex corrigió el problema. Un hilo de alta prioridad en espera activa en una única CPU con planificación estricta por prioridades puede ser peor: puede impedir por completo que el propietario de baja prioridad se ejecute.

Un contador compartido es fácil de proteger con un mutex. Sus operaciones increment, decrement y get adquieren el mismo cerrojo, actúan y lo liberan. Es exacto, pero todas las actualizaciones pasan por un único punto compartido.

Por qué el contador exacto se convierte en un cuello de botella

En varios núcleos, un mutex serializa las operaciones del contador. Los núcleos también transfieren la propiedad de las líneas de caché del cerrojo y del contador. Añadir trabajadores puede aumentar la espera más rápido de lo que aumenta el trabajo útil. Sustituir el mutex por atomic_fetch_add elimina la sobrecarga explícita del cerrojo en procesadores habituales, pero cada actualización sigue escribiendo en la misma ubicación compartida.

Un contador aproximado distribuye las actualizaciones entre contadores locales y las transfiere a un contador global por lotes. El valor global que comunica omite deliberadamente los incrementos locales recientes.

Construye la actualización de local a global

Mantén un contador y un mutex por núcleo, un contador global con su propio mutex y un umbral S. Para cada incremento:

1. Elige la posición local para esta actualización y adquiere su mutex.
2. Suma 1 al recuento local.
3. Si alcanza S, adquiere el mutex global mientras aún posees el local.
4. Suma ese recuento local al global, restablece el recuento local a 0 y libera el mutex global.
5. Libera el mutex local.

Mantén estable la posición elegida durante toda la actualización. Los hilos que usan distintas posiciones suelen acceder a distintos cerrojos y solo adquieren el mutex global durante una transferencia. La lectura del recuento global también sigue su regla de protección.

Sigue una transferencia por lotes

Con cuatro núcleos y S igual a 5, supón que sus totales de actualizaciones son 7, 3, 4 y 0. El núcleo 1 transfiere 5 en su quinto incremento y deja 2 incrementos locales después. Los recuentos locales finales son 2, 3, 4 y 0. El recuento global es 5 y el total real es 14: nueve incrementos permanecen en los contadores locales.

Después de completar actualizaciones de un incremento cada una, cada recuento local está entre 0 y S − 1, ambos incluidos. Con P núcleos, el total global puede quedar retrasado como máximo en:

Para cuatro núcleos y S igual a 5, el límite es 16. Este límite se refiere a actualizaciones completadas y a sus recuentos locales restantes; no lo apliques a mitad de una transferencia.

Elige el umbral para el trabajo

Un umbral menor mejora la actualidad del valor, pero requiere más adquisiciones del cerrojo global. Con S igual a 1, cada incremento se transfiere globalmente, añadiendo la sobrecarga del cerrojo local sin evitar el cuello de botella global. Un umbral mayor mejora la escalabilidad de las actualizaciones, pero aumenta el posible retraso. En un experimento publicado, S igual a 1024 permitió que cuatro hilos realizaran cuatro millones de actualizaciones en casi el mismo tiempo que un hilo necesitó para un millón.

Una instantánea exacta debe poseer todos los mutex locales en un orden fijo y después el mutex global antes de sumar los recuentos. Ese orden concuerda con el de las actualizaciones, que adquieren un cerrojo local antes del global. La instantánea detiene las transferencias concurrentes mientras lee; leer cada campo por separado podría contar dos veces una transferencia o no contarla.

Los contadores aproximados sirven para estadísticas que toleran una visibilidad diferida. Un contador de referencias que determina cuándo puede liberarse la memoria necesita un método exacto: un recuento inferior al real podría liberar un objeto que aún está en uso.

Una lista enlazada compartida necesita preservar tanto sus enlaces como el tiempo de vida de sus nodos. Un mutex alrededor de cada operación es un primer diseño útil porque todos los recorridos y modificaciones compartidos siguen una sola regla.

Cómo dos inserciones pierden un nodo

Supón que la lista empieza en A. T1 prepara el nodo X y T2 prepara el nodo Y. Sin un cerrojo compartido, ambos pueden leer head == A, asignar A al next de su nuevo nodo y después guardar su propio nodo en head. La asignación posterior de la cabecera oculta el primer nodo insertado. Ese nodo queda inaccesible, se pierde una inserción y se produce una fuga de su memoria.

La secuencia protegida debe incluir la lectura de la cabecera actual, el establecimiento del nuevo enlace y la publicación de la nueva cabecera. Un cerrojo solo alrededor de la asignación final permitiría que ambos hilos construyeran enlaces a partir de la misma cabecera desactualizada.

Prepara los datos privados antes de adquirir el cerrojo

Un nodo nuevo permanece privado hasta que se enlaza en la lista compartida. La asignación de memoria y la inicialización de la clave pueden hacerse antes de la adquisición. Usando la función auxiliar de pthread con comprobación de errores anterior, la inserción puede escribirse así:

int insert(list_t *list, int key) {
    node_t *node = malloc(sizeof(*node));
    if (node == NULL) return -1;
    node->key = key;

    check(pthread_mutex_lock(&list->lock));
    node->next = list->head;
    list->head = node;
    check(pthread_mutex_unlock(&list->lock));
    return 0;
}

Si falla la asignación de memoria, se retorna antes de adquirir ningún mutex. La sección compartida sigue siendo pequeña mientras la comprobación de head y la actualización del enlace permanecen juntas. Que la asignación de memoria sea segura entre hilos no hace que la propia lista lo sea; sus enlaces siguen necesitando su propia protección.

Los lectores participan en la misma regla

Una búsqueda adquiere el mutex de la lista antes de leer head y lo conserva durante el recorrido. Esto la coordina con la inserción y la eliminación. Asigna una variable de resultado antes del bucle, actualízala si hay una coincidencia y sal del bucle hacia un único punto de liberación antes de retornar. De lo contrario, un retorno anticipado por éxito dentro del bucle protegido necesitaría su propia liberación.

En este diseño, la eliminación posee el mismo mutex mientras desenlaza un nodo. Otros recorridos no pueden estar en ese nodo porque también necesitan el mutex. Libéralo solo cuando ninguna otra operación pueda seguir accediendo a él. Si una API permite que quien llama conserve un puntero al nodo después de liberar el cerrojo, ese uso adicional necesita su propio acuerdo sobre el tiempo de vida; el cerrojo de la lista por sí solo ya no lo cubre.

Decide si compensa usar cerrojos por nodo

El acoplamiento de cerrojos adquiere el cerrojo del siguiente nodo antes de liberar el del nodo actual. Ese solapamiento conserva una ruta protegida a medida que avanza el recorrido. Así, varias operaciones pueden ocupar distintas regiones de la lista.

La concurrencia adicional tiene un precio: cada nodo visitado añade operaciones de adquisición y liberación, incluso cuando no hay ningún otro hilo cerca. Una carga de trabajo con muchos recorridos puede ser más lenta que la versión con un solo mutex. Proteger grupos de nodos es una solución intermedia. Compara el diseño más complicado con el sencillo bajo la carga de trabajo real, incluidas las búsquedas fallidas y las rutas de eliminación.

Un mutex por estructura es un punto de partida sensato, pero puede serializar operaciones que acceden a distintas regiones. Dos mejoras útiles son un cerrojo por extremo de la cola y un cerrojo por cubeta de la tabla hash.

Mantén un nodo ficticio al principio de la cola

Una cola con dos cerrojos empieza con un nodo ficticio D y head == tail == D. D no contiene ningún elemento actual de la cola. El primer elemento real, si existe, está en head->next. Un mutex del principio serializa las extracciones; un mutex del final serializa las inserciones. Por tanto, una inserción y una extracción pueden avanzar juntas.

La inserción prepara de forma privada el valor de un nodo nuevo y su enlace siguiente nulo. Bajo el mutex del final, publica ese nodo mediante el campo next del último nodo anterior y mueve tail al nuevo nodo. La extracción usa el mutex del principio para leer el enlace siguiente del nodo ficticio anterior. Si es nulo, libera el cerrojo e indica que la cola está vacía. De lo contrario, copia el primer valor real, mueve head a ese nodo, libera el cerrojo y libera el nodo ficticio anterior.

El nodo que contenía el valor devuelto se convierte en el siguiente nodo ficticio. Liberar ese nodo inmediatamente dejaría head como puntero colgante.

Sigue el desplazamiento del nodo ficticio

Empieza con D. Insertar 5 crea N5 y enlaza D -> N5, con tail == N5. Insertar 8 añade N8 y produce D -> N5 -> N8. Una extracción devuelve 5, mueve head a N5 y libera D. N5 es ahora el nodo ficticio; solo queda 8 como valor en la cola. Después de otra extracción, N8 se convierte en el nodo ficticio y la cola queda vacía.

Los dos extremos siguen compartiendo un enlace

Cuando la cola está vacía, una inserción puede escribir en next del nodo ficticio actual mientras una extracción lo lee bajo un mutex distinto. Los dos mutex por sí solos no sincronizan esos accesos. En C11, declara next como puntero atómico y publícalo y léelo con la ordenación adecuada; bastan los almacenamientos y las cargas atómicas predeterminadas con consistencia secuencial. La publicación debe hacer visible el valor preparado del nodo antes de que la extracción lo lea.

Esperar a un elemento requiere un mecanismo de señalización además del cerrojo.

Aplica hash a la clave y después adquiere el cerrojo de la cubeta

Una tabla hash de tamaño fijo puede usar una lista segura entre hilos en cada cubeta, cada una con su propio mutex. Con 101 cubetas y bucket = key % 101, las claves 7 y 50 usan cerrojos distintos. Las claves 7 y 108 se asignan ambas a la cubeta 7 y deben serializarse allí. Las colisiones afectan tanto a la contención como a la longitud de la búsqueda.

Todos los accesos a la lista de una cubeta siguen la regla de protección de esa cubeta, incluidas las lecturas. El redimensionamiento cambia la asignación de cubetas y mueve entradas, por lo que este diseño sencillo necesita acceso exclusivo a toda la tabla durante el redimensionamiento. Un mutex de cubeta por sí solo no puede proteger un cambio que afecta a todas las cubetas.

Mejora el diseño solo después de encontrar el cuello de botella

Empieza con un mapa del estado compartido: qué campos se comparten, qué mutex u operación atómica protege cada uno y cuándo los nodos pasan a ser accesibles o pueden liberarse. Comprueba todas las rutas de retorno y de fallo de asignación. Razona sobre los intercalados, prueba bajo carga con un detector de carreras y mide la contención antes de añadir cerrojos de grano más fino.