El mutex por dentro: futex

1. Qué es un futex

Un futex (fast userspace mutex) es una primitiva de sincronización del núcleo de Linux que permite bloquear y despertar hilos eficientemente. La idea es hacer el trabajo en espacio de usuario con operaciones atómicas y solo entrar al núcleo cuando hay contención.

El futex fue introducido en Linux 2.6 (2003) por Hubertus Franke. Es la base de los mutexes, semáforos y variables de condición de glibc.

El futex se basa en una variable entera compartida en espacio de usuario. El núcleo solo interviene cuando un hilo necesita bloquearse o despertar a otro.

2. El problema que resuelve

Antes de los futexes, los mutexes de POSIX se implementaban completamente en el núcleo: cada lock y unlock era una syscall. Esto era lento porque cada syscall implica un cambio de modo (usuario → núcleo → usuario) que consume ~1 μs.

El futex resuelve esto haciendo el caso común (sin contención) en espacio de usuario con operaciones atómicas. Solo el caso raro (con contención) entra al núcleo.

El resultado es que un mutex sin contención se adquiere en ~20 ns (una operación atómica), mientras que uno con contención tarda ~1-10 μs (una syscall).

3. El fast path (sin contención)

El fast path es el caso común: el mutex está libre. Se adquiere con una sola operación atómica (CAS) en espacio de usuario:

/* Pseudocódigo del fast path de pthread_mutex_lock. */
int lock = atomic_load(&mutex->lock);
if (lock == 0) {
    /* Mutex libre: intentar adquirir con CAS. */
    if (atomic_compare_exchange_strong(&mutex->lock, &lock, 1)) {
        return 0;  /* éxito, sin entrar al núcleo */
    }
}
/* Si falla, ir al slow path. */

En el fast path, no se llama al núcleo. La operación es una sola instrucción atómica (LOCK CMPXCHG en x86), que tarda ~20 ns.

El 99 % de las adquisiciones de mutex en programas reales son fast path (sin contención). Por eso, los mutexes son tan rápidos.

4. El slow path (con contención)

El slow path es el caso raro: el mutex está ocupado. El hilo debe bloquearse en el núcleo:

/* Pseudocódigo del slow path. */
/* El mutex está ocupado. Bloquear el hilo. */
futex_wait(&mutex->lock, 1);  /* esperar a que el valor cambie de 1 */
/* Al despertar, reintentar adquirir. */

El slow path llama a futex(FUTEX_WAIT), que bloquea el hilo en el núcleo. El hilo se duerme y cede la CPU. Cuando el mutex se libera, el núcleo despierta al hilo con futex(FUTEX_WAKE).

El slow path es más lento: implica dos syscalls (FUTEX_WAIT y FUTEX_WAKE) y dos cambios de contexto. Tarda ~1-10 μs.

5. El unlock

El unlock también tiene fast path y slow path:

/* Pseudocódigo del unlock. */
atomic_store(&mutex->lock, 0);  /* liberar el mutex */
/* Si hay hilos esperando, despertar uno. */
futex_wake(&mutex->lock, 1);

El unlock siempre establece el mutex a 0 con una operación atómica (fast path). Si hay hilos bloqueados, llama a futex(FUTEX_WAKE) para despertar a uno (slow path).

En el caso sin contención, futex_wake retorna inmediatamente (no hay hilos bloqueados). En el caso con contención, despierta al primer hilo bloqueado.

6. Implementación en glibc

La implementación de pthread_mutex en glibc usa futexes. El código (simplificado) es:

/* Estructura del mutex. */
typedef struct {
    int lock;       /* 0 = libre, 1 = ocupado, 2 = ocupado con waiters */
} pthread_mutex_t;

int pthread_mutex_lock(pthread_mutex_t *mutex) {
    int c;
    /* Fast path: intentar adquirir con CAS. */
    c = atomic_load(&mutex->lock);
    if (c == 0 && atomic_compare_exchange_strong(&mutex->lock, &c, 1)) {
        return 0;  /* éxito */
    }
    /* Slow path: bloquear en el núcleo. */
    return __pthread_mutex_lock_slow(mutex);
}

int pthread_mutex_unlock(pthread_mutex_t *mutex) {
    /* Establecer a libre. */
    if (atomic_exchange(&mutex->lock, 0) == 1) {
        return 0;  /* no había waiters */
    }
    /* Hay waiters: despertar uno. */
    futex_wake(&mutex->lock, 1);
    return 0;
}

El fast path usa atomic_compare_exchange_strong (CAS). Si tiene éxito, retorna sin entrar al núcleo. Si falla, va al slow path.

El valor 2 en el lock indica que hay hilos esperando (waiters). Esto permite al unlock decidir si necesita llamar a futex_wake.

7. El costo del futex

El fast path es tan rápido como una operación atómica. El slow path es 50-500× más lento. Por eso, los mutexes son eficientes cuando no hay contención.

8. Cómo lo usa Linux

Linux usa futexes extensivamente:

• pthread_mutex: implementado con futexes.
• pthread_cond: implementado con futexes.
• sem_t: implementado con futexes.
• pthread_rwlock: implementado con futexes.
• Internamente: el núcleo usa futexes para sincronizar hilos del núcleo.

El futex es la primitiva de sincronización fundamental de Linux. Todo lo demás se construye sobre él.

9. Simulador interactivo

Este simulador muestra el fast path y el slow path del mutex:

10. Resumen

• Un futex es una primitiva que hace el trabajo en espacio de usuario con operaciones atómicas.
• El fast path (sin contención) usa una operación atómica (CAS) y no entra al núcleo.
• El slow path (con contención) llama a futex(FUTEX_WAIT) y bloquea el hilo.
• El unlock establece el mutex a 0 y despierta a un hilo si hay waiters.
• El fast path tarda ~20 ns; el slow path ~1-10 μs.
• glibc implementa pthread_mutex, pthread_cond y sem_t con futexes.
• El futex es la primitiva de sincronización fundamental de Linux.

11. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Usa strace para observar las syscalls de futex con y sin contención.
2. Mide el costo del mutex con perf (ciclos) sin contención.
3. Mide el costo del mutex con perf con contención.
4. Explica por qué el fast path no entra al núcleo.
5. Investiga cómo se implementa el futex en el núcleo de Linux.
6. Explica por qué el valor 2 en el lock indica waiters.