No tiene sentido sin futex

 (h4x0r.org)
4 puntos por GN⁺ 2025-08-21 | 1 comentarios | Compartir por WhatsApp
  • Se plantea la crítica de que el libro de texto The Art of Multiprocessor Programming no aborda el concepto de futex, algo lamentable.
  • Futex es un componente clave de la sincronización eficiente en la programación paralela moderna y ofrece un rendimiento superior al de los locks tradicionales basados en System V.
  • Futex tiene una estructura que separa la adquisición del lock de las funciones de espera/despertar, reduciendo llamadas al sistema y sobrecarga innecesarias.
  • Se incluyen ejemplos y técnicas para implementar directamente varios primitivos de concurrencia basados en futex, como spinlocks, mutexes y locks recursivos.
  • El autor señala la brecha entre la academia y la práctica profesional, ya que el libro no cubre metodologías modernas de sincronización esenciales en la ingeniería real.

Introducción

  • Phil Eaton inició un club de lectura de The Art of Multiprocessor Programming, 2nd Edition.
  • Aunque este libro es considerado un texto de referencia en programación paralela, el autor critica la falta de utilidad práctica de su contenido.
  • En particular, cuestiona que, pese a estar dirigido a estudiantes avanzados de licenciatura y posgrado, no trate futex, una técnica central de sincronización.

Qué es futex y por qué importa

  • Futex significa “fast user space mutex”, pero en realidad, más que un mutex, es un bloque primitivo de sincronización con soporte del sistema operativo para implementar locks modernos.
  • En el pasado, la mayoría de los locks se implementaban con semáforos de System V IPC, lo que tenía límites de eficiencia y escalabilidad.
  • Cuando Linux introdujo futex en 2002, mostró un rendimiento 20 a 120 veces más rápido que los locks de System V en entornos con 1000 tareas concurrentes.
  • Otros sistemas operativos como Windows (2012) y macOS (2016) también adoptaron mecanismos similares.
  • Hoy en día, los locks de bibliotecas del sistema ampliamente usadas, como pthreads, utilizan futex.

Cómo funciona futex y en qué se diferencia

  • Los semáforos tradicionales combinaban lock y espera, pero futex separa la adquisición del lock de la espera/despertar.
  • Gracias a esto, se pueden reducir demoras y llamadas al sistema innecesarias, y si está claro que no hay hilos esperando al liberar el lock, ni siquiera hace falta entrar al kernel.
  • La llamada de espera de futex (wait) hace que solo se espere cuando el valor de una dirección de memoria específica está en el estado deseado, y también soporta timeout.
  • La llamada de despertar de futex (wake) despierta la cantidad deseada de hilos desde una lista interna de espera asociada con una dirección de memoria específica.
  • Como exige validar el valor real de la dirección de memoria, evita esperas innecesarias cuando el estado ya cambió.

Uso práctico de futex: implementación directa

  • Como futex es una primitiva de bajo nivel, se usan tipos de datos atomic teniendo en cuenta los problemas de orden de operaciones de memoria del compilador y del hardware.
  • En Linux, hay que invocar directamente la syscall de futex con syscall; en macOS, se usa la interfaz __ulock (recientemente se agregó una API más simple).
  • Básicamente, la espera de futex devuelve 0 en caso de éxito y un código de error en caso de falla (por ejemplo, timeout).
  • Operaciones clave basadas en futex:
    • h4x0r_futex_wait_timespec() : espera si el valor esperado coincide; puede aplicar timeout
    • h4x0r_futex_wake() : despierta a 1 o a todos los hilos en espera

Ejemplos prácticos de implementación de mutex/spinlock/lock recursivo

Spinlock

  • La forma más simple de lock, funciona solo con un único bit (atomic_fetch_or).
  • Hace un bucle infinito (“spin”) hasta obtener el lock, pero en situaciones de alta contención desperdicia CPU y tiene problemas estructurales, como desbloqueos incorrectos y riesgo de deadlock en llamadas recursivas.

Mutex híbrido (“unsafe” mutex)

  • Normalmente intenta primero con un spinlock y, tras cierto número de fallos, cambia a futex para bloquear de forma eficiente.
  • Si no hay hilos esperando, se pueden evitar llamadas al sistema innecesarias; y para quienes esperan, se pueden minimizar las syscalls de despertar.
  • Como no valida estrictamente la propiedad ni maneja bien la recursión, se usa el nombre “unsafe”.

Mutex con contador de hilos en espera

  • Un bit representa el estado del lock y el resto se usa para contar la cantidad de hilos en espera, con el objetivo de reducir syscalls de despertar innecesarias.
  • Aun así, sigue sin manejar propiedad ni recursión.

Mutex con gestión de propiedad

  • Mediante el valor pthread_t, rastrea claramente al propietario del lock y su estado, detectando problemas como unlock incorrectos o uso recursivo indebido.
  • La adquisición del lock, su liberación y la gestión de hilos en espera se controlan todas con operaciones atómicas estrictas.

Lock recursivo

  • Agrega un contador de profundidad por hilo, permitiendo que el mismo hilo adquiera el lock varias veces de forma anidada.
  • Al hacer unlock, la profundidad disminuye, y cuando llega a 0 se realiza el desbloqueo real y el despertar correspondiente.
  • Cada operación se implementa con operaciones atómicas y validación estricta de propiedad.

Tareas pendientes y realidad de la ingeniería

  • Si el hilo dueño del lock termina de forma anormal o muere, hace falta gestión adicional, como listas de control separadas o callbacks de finalización, para administrar el lock.
  • También se requieren consideraciones adicionales para gestionar cambios de estado cuando se usan mutexes compartidos entre procesos.
  • En los locks RW de POSIX, el comportamiento de anidación recursiva no está definido y varía según la implementación, por lo que en la práctica es difícil garantizar la seguridad.
  • El autor critica que el libro no incluya en el plan de estudios problemas de concurrencia realmente importantes en la práctica (futex, locks recursivos, runtimes asíncronos, etc.).

Conclusión

  • The Art of Multiprocessor Programming está demasiado sesgado hacia la historia o la teoría y no incorpora adecuadamente conocimientos prácticos modernos de programación paralela.
  • Si no se tratan bien componentes clave de sincronización como futex, que son los que realmente funcionan en los sistemas, eso podría causar un perjuicio real a quienes se están formando.
  • El autor enfatiza la necesidad de reflejar conceptos actuales y complementar el contenido con aspectos prácticos.

Material de referencia

  • El código de ejemplo completo puede consultarse en codeberg

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-08-21
Opiniones en Hacker News

  • Windows tiene una función llamada WaitForMultipleObjects, y Linux también la incorporó con Futex2 en 5.16 (a finales de 2021)
    Enlace relacionado
    Recientemente se le han hecho varias mejoras a Futex2
    Por fin también se añadió soporte para NUMA
    Enlace NUMA 1
    Enlace NUMA 2
    NUMA es un factor muy importante para el rendimiento
    io_uring se aplicó a futex en 6.7 (2024), lo que ayudó a mejorar el rendimiento de AIO en PostgreSQL
    Artículo relacionado
    En 6.7 también se añadieron las funciones small requeue y single wait
    Enlace relacionado

    • Windows no agregó recientemente la función WaitForMultipleObjects; la ha tenido desde el principio, desde hace más de 30 años
      WaitForMultipleObjects sí era una ventaja de Windows NT frente a UNIX, pero IBM PL/I ya tenía una función similar en 1965
      La función wait en UNIX era una versión simplificada del wait de IBM PL/I y, como muchas otras funciones heredadas de Multics, era más débil que el modelo original
      Las funciones WaitForSingleObject y WaitForMultipleObjects de Microsoft tampoco tenían una implementación eficiente, así que al final tuvieron que introducir WaitOnAddress, equivalente a futex en Linux
      El futex de Linux tiene las limitaciones de ser de 32 bits y de solo poder esperar un único evento
      Usando operaciones atómicas sobre bits se puede implementar la espera de múltiples eventos, pero no es eficiente, así que el problema del tamaño de 32 bits se vuelve más serio
      Es bueno ver intentos de combinar en futex algunas de las ventajas de WaitForMultipleObjects
      Este tipo de intento no es copiar a Windows, sino reimplementar una técnica clásica bien conocida desde hace más de 50 años, mucho más antigua que Microsoft

    • Sigue siendo una lástima que todavía no exista la función futex_swap
      Discusión relacionada 1
      Material relacionado 2

    • Futex no tiene relación con WFMO (WaitForMultipleObjects); más bien es equivalente a los keyed events
      En Linux, lo equivalente a WFMO sería select/poll/epoll

    • El soporte de futex en io_uring es una función realmente muy buena
      Lo usé al trabajar con Ruby fibers para implementar mutex y colas
      Referencia del código fuente

  • El libro deja claro que, en lugar de implementar estructuras de sincronización directamente, se deben usar las que proveen la biblioteca, el lenguaje o el sistema
    El enfoque principal del libro está en los conceptos generales de concurrencia, no en una plataforma específica
    Es una pena que el autor del artículo lo haya planteado con una oposición algo exagerada
    Habría sido mejor tratarlo desde una perspectiva colaborativa, como "lo que TAoMP no dice"
    Llama la atención que este blog sea nuevo, que Phil haya publicado este artículo y que también haya promocionado otros textos

    • Yo escribí ese artículo, y lo hice porque me decepcionó el libro al leerlo
      Sentí que tanto en la academia como en la industria existe el problema de no aprender cosas realmente útiles en la práctica
      Así que la intención no era algo como "¡vamos a aprender sobre futex!"
      De hecho, me decepcionó tanto el libro que dejé otros textos en pausa para escribir primero este artículo
      Conozco a Phil de haber trabajado juntos antes, pero hasta ahora no he tenido mucha dificultad para encontrar lectores para mis textos

    • Ahora pienso que la parte donde antes dije que ni siquiera compararía el estilo sysv con dinosaurios fue excesiva
      Es un punto donde hace falta más humildad

  • Lo más genial de futex es que es una estructura sin handles (handle-less)
    Ofrece un comportamiento básico muy útil como monitor de memoria basado en kernel, sin necesidad de asignación/liberación vía syscall
    Si no hay hilos esperando, todo queda limpio, y si no hay contención, el kernel ni siquiera sabe que el mutex existe
    Me da curiosidad un análisis detallado de si el kernel administra futex con alto rendimiento
    Hoy me enteré por primera vez de futex2
    Documentación relacionada

    • Exacto, y además no quieres un enfoque donde se llame a malloc() del kernel para asignar datos cada vez que un hilo se bloquea en un lock
      Para evitar eso, muchos sistemas operativos asignan un "queue object" por cada hilo al momento de crearlo, y cuando ese hilo encuentra un lock con contención, asignan ese objeto al lock
      Es decir, varios hilos forman una linked list de queue objects conectados al lock, y cada vez que un hilo despierta se lleva uno consigo
      Cuando el hilo termina, no hay garantía de que recupere el objeto que creó originalmente; los objetos se mezclan en el camino
      Solaris introdujo primero esta estructura (turnstile), y los BSD también adoptaron este método
      Referencia de Solaris Internals
      Material PDF de BSD

    • Las primeras colas de espera dentro del kernel de Unix también funcionaban de esta manera

  • El artículo original sobre futex de 2002 ya demostraba claramente su eficiencia, y en pruebas con 1000 tareas en paralelo mostró un rendimiento entre 20 y 120 veces superior al de los locks sysv
    Pero en realidad el baseline no es el lock sysv
    En la práctica, al implementar locks en un entorno sin futex, casi siempre no hay entrada al kernel en la ruta rápida, y solo se pasa a espera en el kernel en la ruta lenta; la única mejora de futex es que se redujo el tamaño de la estructura de datos en espacio de usuario que representa el estado de espera del lock
    Otras alternativas, como thin locks (como los que usa la JVM) o ParkingLot (implementación totalmente en userland), pueden funcionar sin el futex del SO

    • En mi experiencia, la mayoría en realidad aprende las primitivas básicas que se ofrecen en el trabajo real, así que uno termina enfocándose en qué ofrece la biblioteca estándar de su lenguaje
      Es decir, ha predominado la transición de sysv a futex, y aunque últimamente existen enfoques personalizados, la corriente principal sigue siendo futex
      Si alguien fuera a construir directamente un scheduler en userland, quizá podría implementar algo aparte, pero creo que la mayoría usaría un enfoque de escribir en file descriptors y manejar sus propias colas
      No estoy seguro de cuánto beneficio real daría ese enfoque

    • En la práctica, casi cualquier lock moderno termina usando futex internamente, si está disponible
      Como futex es la forma más eficiente de esperar en Linux, siempre conviene usarlo en la ruta lenta (down)
      Incluso algo como thread.park() en un lenguaje probablemente termine funcionando sobre futex

    • Me pregunto si la JVM sigue usando thin lock
      Antes encontré referencias a que la JVM llamaba a futex; me interesa saber si migró a thin lock o no
      Discusión relacionada en Stack Overflow

  • La implementación real de [recursive locks] no es consistente ni siquiera entre estándares, y muchas veces ni siquiera se define por considerarse difícil
    Esa actitud es bastante frustrante
    Es como decir: "como el implementador del SO o del lenguaje probablemente no podrá implementar bien la feature X, mejor que la maneje directamente el desarrollador de aplicaciones"
    Al final, el usuario downstream realmente no tiene mucho margen de maniobra aparte de cambiar de proveedor

    • Si se imponen demasiadas restricciones al estándar, se puede cerrar la puerta a mejores implementaciones
      Por ejemplo, la tabla hash y las expresiones regulares de la biblioteca estándar de C++ son mucho más lentas que alternativas de terceros por tantas restricciones
      Si se garantizan ciertas restricciones concretas —por ejemplo, usar solo chaining— o ciertas features, se bloquean implementaciones alternativas de alto rendimiento
      También en el caso de recursive rwlock puede haber implementaciones que sacrifiquen rendimiento o hagan menos comprobaciones, así que no creo que sea necesario bloquear distintas direcciones posibles

    • Personalmente, creo que es mejor no usar recursive lock desde el inicio, así que no veo necesidad de incluir su especificación de soporte en el estándar

    • Si quieres saber más sobre el fenómeno de worse is better, revisa la wiki
      No me gusta mucho, pero es una realidad inevitable

  • Me dio curiosidad la limitación de que futex en Linux solo soporte int de 32 bits, así que estuve investigando
    En una discusión sobre soporte de 64 bits, Linus comentó que en espacio de usuario se puede usar un atómico de 64 bits y usar solo los 32 bits bajos para futex
    Pero en C/C++ eso se considera undefined behavior con atómicos de tamaño mixto, y de hecho así funciona la implementación de semáforos en glibc
    En un entero de 64 bits, los 32 bits altos se usan como contador de waiters y los 32 bajos como valor del semáforo, y futex solo usa los 32 bits bajos
    Me pregunto si eso es comportamiento definido en gcc, o si no importa por el cruce de proceso (kernel), o si incluso glibc está usando undefined behavior

  • También recomiendo C++ Concurrency in Action de Anthony Williams; no cubre futex ni cómo implementar directamente primitivas de sincronización, pero sí trata temas más cercanos a la práctica como el orden de memoria y el SMR necesario para estructuras lock-free
    Si necesitas una perspectiva más centrada en hardware, también recomiendo el libro gratuito de Paul McKenney, "Is Parallel Programming Hard, And, If So, What Can You Do About It?"
    Ese libro tampoco entra a fondo en futex, pero remite a "Futexes Are Tricky" de Ulrich Drepper
    TAOMPP sirve bien para tratar conceptos de concurrencia de alto nivel, y no le corresponde incluir detalles de implementación a nivel SO
    En cualquier caso, Peterson o bakery lock no sirven para uso real, pero aprender siquiera sus demostraciones ayuda mucho a entender algoritmos de concurrencia en la práctica

    • Bakery lock es bueno para spin lock y es amigable con la caché
      También se puede implementar un reader/writer spin lock, pero queda con FIFO estricto
      Se puede conectar futex al spin wait de bakery lock en espacio de usuario, pero sería muy ineficiente
      Futex no fue diseñado desde el inicio para ese tipo de uso (espera por spin)
      Las estructuras lock-free, hazard pointer, RCU* y similares siguen siendo complicadas
      Incluso se pueden hacer hazard pointers wait-free en la práctica
      *En el caso de RCU, copy-on-write es intuitivo, pero si hay muchas actualizaciones el costo aumenta

  • Así como en Windows 8 se introdujo algo similar a futex, originalmente Win32 critical section se basaba en semáforos del kernel
    Pero me da curiosidad qué estructura usa el SRW lock introducido en Vista

    • Tanto CRITICAL_SECTION como SRWLock no entran al kernel si no hay contención
      SRWLock se basa en keyed events, y CRITICAL_SECTION, cuando falla, crea un objeto del kernel on-demand y hace fallback a keyed event

  • Entre las vulnerabilidades descubiertas por Pinkie Pie en la implementación de futex de Linux en 2014, la regla requeue-once solo se permite para el futex pasado a futex_wait_requeue_pi
    No se puede hacer requeue de A a B y luego otra vez de B a C, aunque sí se puede reasignar de B a B
    En ese caso hay un bug donde, si se pasan ciertas condiciones, no se llama a la función de cleanup y el puntero queda dangling
    Se puede ver un caso relacionado
    Issue relacionado

  • Hay gente a la que no le preocupa la consistencia de los datos cuando un hilo crashea, pero mientras no muera todo el proceso, el problema de limpiar locks sigue existiendo
    La solución para eso es robust lock
    Se registra en el kernel la lista de futex retenidos, y con sys_set_robust_list, al terminar el hilo, se procesa ese bit y se despierta al lado que está esperando (waiter)

    • La mayor desventaja de robust lock es que el recurso protegido por el lock probablemente ya esté en un estado inconsistente
      Si no sabes con certeza por qué crasheó el hilo, es posible que los datos ya no sean íntegros y que recuperarlos sea imposible
      Por eso, puede ser más práctico matar toda la app junto con él
      La funcionalidad de cleanup/recovery con robust lock es genial, pero probablemente el 95% de los ingenieros no diseñará correctamente una estructura de datos robusta
      Otro 4% no tendrá tiempo para hacerlo, y solo el 1% restante lo hará bien y obtendrá una gran recompensa

    • Cuando se usan futex entre múltiples procesos (estado cross-process), se puede usar un enfoque donde un proceso watchdog abre un Unix domain socket (SOCK_STREAM o SOCK_SEQPACKET) para cada proceso, detecta crashes y limpia el estado por proceso

    • Yo también limité la discusión sobre mutex al límite del proceso porque me preocupaba que, si profundizaba más, la discusión se volviera interminable