Sem futex não faz sentido

• É levantada a crítica de que o livro The Art of Multiprocessor Programming não aborda o conceito de futex, o que é lamentável
• O futex é um componente central da sincronização eficiente na programação paralela moderna, com desempenho superior aos locks tradicionais baseados em System V
• O futex tem uma estrutura que separa a aquisição do lock das funções de espera/despertar, reduzindo chamadas de sistema desnecessárias e overhead
• Estão incluídos exemplos e técnicas para implementar diretamente vários primitivos de concorrência com base em futex, como spinlock, mutex e lock recursivo
• O autor aponta um distanciamento entre a academia e o mercado ao criticar que o livro não trata de metodologias modernas de sincronização essenciais para a prática de engenharia

---

Introdução

• Phil Eaton iniciou um clube de leitura de The Art of Multiprocessor Programming, 2nd Edition
• Embora esse livro seja considerado uma referência na área de programação paralela, o autor aponta a falta de utilidade prática do conteúdo
• Em especial, critica o fato de que, apesar de dizer que se destina a alunos do último ano da graduação e da pós-graduação, ele não trata do futex, uma técnica central de sincronização

O que é futex — e por que isso importa

• Futex é a abreviação de “fast user space mutex”, mas na prática é menos um mutex e mais um primitivo de sincronização com suporte do SO para implementações modernas de lock
• No passado, a maioria dos locks era implementada com base em semáforos do System V IPC, o que trazia limitações de eficiência e escalabilidade
• Com a introdução do futex no Linux em 2002, ele apresentou desempenho de 20 a 120 vezes superior aos locks do System V em ambientes com 1000 tarefas simultâneas
• Outros sistemas operacionais, como Windows (2012) e macOS (2016), também adotaram mecanismos semelhantes
• Hoje, os locks de bibliotecas de sistema amplamente usadas, como pthreads, utilizam futex

Como o futex funciona e o que o diferencia

• Os semáforos tradicionais combinavam lock e espera, mas o futex separa a aquisição do lock do esperar/despertar
• Isso reduz delays e chamadas de sistema desnecessárias, e ao liberar o lock, se for certo que não há threads esperando, nem é preciso entrar no kernel
• A chamada de espera (wait) do futex faz com que a thread espere “somente quando o valor em um endereço de memória específico estiver no estado desejado”, além de oferecer suporte a timeout
• A chamada de despertar (wake) do futex acorda a quantidade desejada de threads a partir de uma lista interna de espera associada a um endereço de memória específico
• Como exige a verificação do valor real no endereço de memória, evita esperas desnecessárias quando o estado já mudou

Uso prático do futex — implementação direta

• Como o futex é um primitivo de baixo nível, usam-se tipos atomic levando em conta questões de ordem das operações de memória do compilador e do hardware
• No Linux, é preciso chamar diretamente a system call de futex via syscall; no macOS, usa-se a interface __ulock (mais recentemente, foi adicionada uma API mais simples)
• Em termos básicos, uma espera de futex retorna 0 em caso de sucesso e um código de erro em caso de falha (como timeout)
• Operações centrais baseadas em futex:
  • h4x0r_futex_wait_timespec() : espera se o valor esperado coincidir, com possibilidade de aplicar timeout
  • h4x0r_futex_wake() : acorda 1 ou todos os waiters

Exemplos práticos de implementação de mutex/spinlock/lock recursivo

Spinlock

• A forma mais simples de lock, funcionando apenas com um único bit (atomic_fetch_or)
• Fica em loop infinito (“spin”) até obter o lock, mas em cenários de alta contenção desperdiça CPU e tem problemas estruturais, como unlock incorreto e risco de deadlock em chamadas recursivas

Mutex híbrido (“unsafe” mutex)

• Em geral, tenta primeiro com spinlock e, após certo número de falhas, muda para futex para fazer bloqueio eficiente
• Se não houver waiters, evita chamadas de sistema desnecessárias, e para quem está esperando também é possível minimizar as chamadas de sistema de wake
• Como não tem verificação rigorosa de ownership nem tratamento de recursão, recebe o nome de “unsafe”

Mutex com contador de waiters

• Um bit representa o estado do lock, e o restante é usado para contabilizar o número de waiters, com o objetivo de reduzir chamadas de sistema de wake desnecessárias
• Ainda não há tratamento de ownership nem de recursão

Mutex com gerenciamento de ownership

• Com o valor de pthread_t, é possível rastrear claramente o dono do lock e seu estado, detectando problemas em unlocks incorretos ou uso recursivo
• Aquisição, liberação e gerenciamento de waiters do lock são todos controlados com operações atômicas rigorosas

Lock recursivo

• Adiciona um contador de profundidade (depth) por thread, permitindo que a mesma thread adquira o lock repetidamente
• No unlock, o depth é reduzido e, quando chega a 0, ocorre o unlock real e o despertar das threads
• Cada operação é implementada com operações atômicas e verificação rigorosa de ownership

Desafios restantes e a realidade da engenharia

• Quando a thread dona do lock termina de forma anormal ou morre, o gerenciamento do lock exige gestão adicional, como uma lista de controle separada e callbacks de encerramento
• Mesmo ao usar mutexes compartilhados entre processos, é preciso considerar de forma adicional como lidar com mudanças de estado
• O RW lock do POSIX não define o comportamento de aninhamento recursivo, e isso varia entre implementações, o que dificulta garantir segurança na prática
• O autor critica o fato de que o livro não inclui no currículo temas de concorrência realmente importantes na prática, como futex, locks recursivos e runtimes assíncronos

Conclusão

• The Art of Multiprocessor Programming está inclinado demais à perspectiva histórica ou teórica e não traz adequadamente conhecimentos práticos modernos importantes de programação paralela
• Se não tratar corretamente de componentes centrais de sincronização como o futex, que de fato operam nos sistemas reais, isso pode causar prejuízo prático aos futuros profissionais
• O autor enfatiza a necessidade de refletir conceitos mais atuais e complementar o conteúdo com material mais prático

Referências

• O exemplo completo de código pode ser visto no codeberg

[GN⁺]

Comentários do Hacker News

• O Windows tem um recurso chamado WaitForMultipleObjects, e o Linux também o introduziu no 5.16 (fim de 2021) com o Futex2
  Link relacionado
  Recentemente, várias melhorias vêm sendo feitas no Futex2
  O suporte a NUMA finalmente também foi adicionado
  Link NUMA 1
  Link NUMA 2
  NUMA é um fator muito importante para desempenho
  O io_uring passou a se aplicar ao futex no 6.7 (2024), o que ajudou a melhorar o desempenho de AIO no PostgreSQL
  Artigo relacionado
  No 6.7, também foram adicionados os recursos de small requeue e single wait
  Link relacionado

  • O Windows não adicionou o recurso WaitForMultipleObjects recentemente; ele já o tinha desde o começo, há mais de 30 anos
    O WaitForMultipleObjects era uma vantagem do Windows NT em relação ao UNIX, mas o IBM PL/I já tinha funcionalidade semelhante em 1965
    A função wait no UNIX era uma versão simplificada do wait do IBM PL/I e, assim como vários recursos herdados do Multics, era mais fraca que o modelo original
    O WaitForSingleObject e o WaitForMultipleObjects da MS também não eram implementações eficientes, então no fim foi necessário introduzir o WaitOnAddress, equivalente ao futex do Linux
    O futex do Linux tem as limitações de ser restrito a 32 bits e só poder esperar por um único evento
    É possível implementar espera por vários eventos usando operações atômicas de bits, mas isso não é eficiente, o que torna o problema do tamanho de 32 bits mais relevante
    É bem-vinda a tentativa de combinar ao menos parte das vantagens do WaitForMultipleObjects com o futex
    Esse tipo de tentativa não é copiar o Windows, e sim reimplementar uma técnica clássica, bem conhecida há mais de 50 anos e muito mais antiga que a própria Microsoft

  • É uma pena que ainda não exista a funcionalidade futex_swap
    Discussão relacionada 1
    Material relacionado 2

  • Futex não tem relação com WFMO (WaitForMultipleObjects); na verdade, é mais equivalente a keyed events
    No Linux, o que corresponde a WFMO é select/poll/epoll

  • O suporte a futex no io_uring é realmente um recurso excelente
    Usei isso ao trabalhar com Ruby fibers para implementar mutex e queue
    Veja o código-fonte

• O livro diz explicitamente que, em vez de implementar estruturas de sincronização diretamente, deve-se usar as estruturas fornecidas pela biblioteca/linguagem/sistema
  O foco principal do livro está nos conceitos gerais de concorrência, não em uma plataforma específica
  É uma pena que o autor do artigo tenha escrito em um tom de confronto um tanto exagerado
  Teria sido melhor se este texto tivesse abordado o tema por uma ótica colaborativa, como em “o que o TAoMP não diz”
  Também chama atenção o fato de esse blog ser novo, de o Phil ter publicado esse texto e de também ter promovido outros textos

  • Fui eu que escrevi o artigo, e escrevi porque fiquei decepcionado ao ler o livro
    Senti que o problema é a realidade em que nem na academia nem na indústria se aprende algo realmente útil na prática
    Então a intenção não era algo como “vamos conhecer futex!”
    Na prática, fiquei tão decepcionado com o livro que adiei outros textos para publicar este primeiro
    Já trabalhei com o Phil no passado e mantenho contato com ele, mas até agora nunca tive grande dificuldade para encontrar leitores para o que escrevo

  • Pensando melhor, aquela parte em que eu disse que nem sequer compararia o estilo sysv a dinossauros foi pesada demais
    É uma área em que eu preciso de mais humildade

• O aspecto mais legal do futex é sua estrutura sem handle
  Ele fornece um comportamento básico muito útil como observador de memória baseado no kernel, sem precisar de alocação/liberação via syscall
  Se não houver threads esperando, tudo é limpo de forma elegante, e se não houver contenção, o kernel nem percebe a existência do mutex
  Tenho curiosidade sobre uma análise detalhada de como o kernel gerencia futex com alto desempenho
  Hoje foi a primeira vez que ouvi falar de futex2
  Documentação relacionada

  • Exato, e além disso ninguém quer um modelo que chame malloc() do kernel para alocar dados toda vez que uma thread bloqueia em um lock
    Para evitar isso, muitos sistemas operacionais alocam um “queue object” para cada thread no momento em que ela é criada, e então esse objeto é associado ao lock quando a thread encontra um lock em contenção
    Ou seja, forma-se uma linked list de queue objects associados ao lock, um por thread, e cada thread leva um deles consigo ao ser acordada
    Ao encerrar, a thread não tem garantia de recuperar o objeto que ela mesma criou inicialmente; os objetos se misturam no caminho
    O Solaris introduziu primeiro essa estrutura (turnstile), e os BSDs também adotaram esse método
    Referência de Solaris internals
    Material PDF de BSD

  • As filas de espera do kernel Unix inicial também funcionavam assim

• Já no artigo original sobre futex, de 2002, a eficiência do futex foi demonstrada claramente, com desempenho 20 a 120 vezes melhor que locks sysv em testes com 1000 tarefas paralelas
  Mas, na prática, sysv locks não são a baseline correta
  Na prática, ao implementar locks sem futex, quase sempre não há entrada no kernel no caminho rápido, e só no caminho lento se entra no kernel para bloquear; a única melhoria do futex é que a estrutura de dados em user space que representa o estado de espera do lock ficou menor
  Outras alternativas incluem thin locks (como os usados na JVM) e ParkingLot (implementação totalmente em userland), que também funcionam sem futex do SO

  • Pela minha experiência, a maioria das pessoas aprende de fato os primitives básicos fornecidos para uso no trabalho, então o foco acaba sendo no que a biblioteca padrão da linguagem oferece
    Ou seja, a transição dominante foi de sysv para futex, e mais recentemente existem abordagens customizadas, mas futex continua sendo o padrão dominante
    Se alguém for criar um scheduler em userland por conta própria, talvez seja possível implementar outra coisa, mas imagino que a maioria acabaria escrevendo em file descriptors e gerenciando as filas manualmente
    Fico em dúvida sobre quanto ganho real isso traria

  • Na prática, qualquer lock moderno acaba usando futex internamente, se houver suporte
    Como futex é a forma mais eficiente de espera no Linux, é sempre desejável usá-lo no caminho lento (down)
    Até algo como thread.park() em uma linguagem provavelmente acaba funcionando sobre futex

  • Fico curioso se a JVM ainda usa thin lock
    Já encontrei no passado referências de que a JVM chamava futex, então queria saber se isso foi migrado para thin lock
    Discussão relacionada no Stack Overflow

• A implementação real de [recursive locks] não é consistente nem entre padrões, e muitas vezes nem chega a ser definida por ser considerada difícil
  Essa postura é bastante frustrante
  É como dizer: “como o implementador do SO ou da linguagem talvez não consiga implementar corretamente o recurso X, então vamos deixar o desenvolvedor da aplicação resolver sozinho”
  No fim, para quem está downstream, não há muito o que fazer além de trocar de fornecedor

  • Restrições excessivas no padrão podem fechar a porta para implementações melhores
    Por exemplo, a hash table e o regex da biblioteca padrão de C++ são muito mais lentos que alternativas de terceiros justamente por terem muitas restrições
    Se você impõe certas restrições específicas — por exemplo, usar apenas chaining — ou garante determinadas funcionalidades, você bloqueia implementações alternativas de alto desempenho
    No caso de recursive rwlock, também é possível ter implementações que sacrificam desempenho ou fazem menos verificações, então não vejo necessidade de bloquear essa variedade de abordagens

  • Pessoalmente, acho melhor simplesmente não usar recursive lock desde o começo, então não vejo necessidade de incluir esse suporte na especificação padrão

  • Se quiser entender mais o fenômeno worse is better, vale consultar a wiki
    Não gosto muito disso, mas é a realidade inevitável

• Fiquei curioso sobre a limitação do futex no Linux de suportar apenas int de 32 bits e fui pesquisar
  Na discussão sobre suporte a 64 bits, o Linus comentou que basta usar atômicos de 64 bits em user space e usar apenas os 32 bits inferiores com futex
  Mas em C/C++, mixed-size atomic é considerado undefined behavior, e na prática a implementação de semáforo da glibc funciona assim
  Em um inteiro de 64 bits, os 32 bits altos são usados como contagem de waiters, e os 32 bits baixos como valor do semáforo, usando futex apenas nos 32 bits inferiores
  Fico na dúvida se isso é comportamento definido no gcc, se o fato de atravessar a fronteira de processo (kernel) torna isso irrelevante, ou se até a glibc está usando undefined behavior

• Também recomendo C++ Concurrency in Action, de Anthony Williams; ele não cobre futex nem como implementar primitives de sincronização diretamente, mas trata de temas mais próximos da prática, como ordenação de memória e SMR necessária para estruturas lock-free
  Se você quiser uma perspectiva mais voltada para hardware, também recomendo o livro gratuito de Paul McKenney, "Is Parallel Programming Hard, And, If So, What Can You Do About It?"
  Esse livro também não entra fundo em futex, mas aponta para "Futexes Are Tricky", de Ulrich Drepper
  O TAOMPP é adequado para tratar bem conceitos de concorrência em alto nível, e não faz sentido exigir que cubra detalhes de implementação no nível de SO
  De toda forma, Peterson lock ou bakery lock não servem para uso real, mas aprender as provas já ajuda muito a entender algoritmos de concorrência na prática

  • Bakery lock é bom para spin lock e é amigável ao cache
    Também dá para implementar reader/writer spin lock, mas ele vira FIFO estrito
    É possível integrar futex ao spin wait de bakery lock em user space, mas isso é muito ineficiente
    Futex não foi projetado para esse tipo de uso (espera por spin)
    Estruturas lock-free, hazard pointer, RCU* etc. continuam sendo tricky
    Inclusive é possível criar hazard pointer wait-free
    *No caso de RCU, copy-on-write é intuitivo, mas o custo cresce quando há muitas atualizações

• Assim como um equivalente a futex foi introduzido no Windows 8, a critical section original do Win32 era baseada em semáforo do kernel
  Mas fiquei curioso sobre qual é a estrutura do SRW lock, introduzido no Vista

  • Tanto CRITICAL_SECTION quanto SRWLock não entram no kernel quando não há contenção
    SRWLock é baseado em keyed event, enquanto CRITICAL_SECTION, em caso de falha, cria um objeto de kernel sob demanda e o chama, com fallback para keyed event

• Entre as vulnerabilidades encontradas por Pinkie Pie na implementação de futex do Linux em 2014, a regra de requeue-once só é permitida para o futex passado a futex_wait_requeue_pi
  Não é possível fazer requeue de A para B e depois novamente de B para C, mas é possível redirecionar de B para B
  Nisso, existe um bug em que, se certas condições forem satisfeitas, a função de cleanup não é chamada, deixando um ponteiro em estado dangling
  É possível verificar um caso relacionado
  Issue relacionada

• Algumas pessoas não se preocupam com integridade de dados causada por thread com crash, mas a menos que o processo inteiro morra, o problema de limpeza do lock continua existindo
  A solução para isso é o robust lock
  Registra-se no kernel a lista de futex mantidos, e com sys_set_robust_list, quando a thread termina, o kernel trata esse bit e acorda o lado que estava esperando (waiter)

  • A maior desvantagem da abordagem de robust lock é que o próprio recurso protegido pelo lock pode já estar em estado inconsistente
    Se você não souber com certeza por que a thread deu crash, pode ser impossível recuperar os dados por falta de integridade
    Por isso, matar a aplicação inteira junto pode ser mais prático
    A funcionalidade de cleanup/recovery usando robust lock é interessante, mas provavelmente 95% dos engenheiros não projetariam corretamente estruturas de dados robustas
    Outros 4% talvez não tenham tempo para isso, e só 1% faria direito e teria grande retorno por isso

  • Ao usar futex entre múltiplos processos (estado compartilhado entre processos), é possível adotar uma abordagem em que um processo watchdog abre um Unix domain socket (SOCK_STREAM ou SOCK_SEQPACKET) para cada processo para detectar crashes e limpar o estado por processo

  • Eu mesmo limitei a discussão sobre mutex à fronteira do processo porque temi que, se fosse além, a discussão ficaria sem fim