Lock-free programming: atomics e memory ordering

1. Fundamentos do Lock-free Programming

Lock-free programming é um paradigma de concorrência onde múltiplas threads podem operar sobre dados compartilhados sem utilizar mecanismos de exclusão mútua tradicionais, como mutexes. A propriedade fundamental de um algoritmo lock-free é que pelo menos uma thread sempre faz progresso em um número finito de passos, independentemente do escalonamento do sistema operacional.

Diferentemente de mutexes, que podem causar deadlocks, inversão de prioridade e contenção de kernel, algoritmos lock-free operam inteiramente em espaço de usuário. Spinlocks, embora evitem chamadas de sistema, ainda sofrem com busy-waiting e podem desperdiçar ciclos de CPU.

Os principais desafios do lock-free incluem:
- Race conditions: múltiplas threads acessando simultaneamente a mesma variável
- Reordenação de instruções: tanto o compilador quanto o processador podem reordenar operações de memória
- Visibilidade: uma thread pode não ver imediatamente as escritas de outra thread devido a caches de CPU

2. Tipos Atômicos em C11 (stdatomic.h)

A biblioteca stdatomic.h introduzida no C11 fornece tipos e operações atômicas portáteis. Os principais tipos são:

#include <stdatomic.h>

atomic_int counter = ATOMIC_VAR_INIT(0);
atomic_flag flag = ATOMIC_FLAG_INIT;
atomic_bool ready = false;

Operações básicas:

atomic_store(&counter, 42);        // Escrita atômica
int val = atomic_load(&counter);   // Leitura atômica
int old = atomic_exchange(&counter, 100); // Troca atômica

Operações de leitura-modificação-escrita (RMW):

int prev = atomic_fetch_add(&counter, 5);  // counter += 5, retorna valor anterior

int expected = 42;
int desired = 100;
if (atomic_compare_exchange_weak(&counter, &expected, desired)) {
    // counter era 42, agora é 100
}

atomic_compare_exchange_weak pode falhar esporadicamente mesmo quando o valor esperado é igual ao atual (spurious failure), sendo mais eficiente que atomic_compare_exchange_strong em loops.

3. Memory Ordering: O Modelo de Memória do C11

O modelo de memória do C11 define seis modos de ordenação que controlam como operações atômicas interagem com outras operações de memória:

memory_order_relaxed    // Sem garantias de ordenação
memory_order_consume    // Dependência de dados (uso limitado)
memory_order_acquire    // Leituras posteriores não podem ser reordenadas antes
memory_order_release    // Escritas anteriores não podem ser reordenadas depois
memory_order_acq_rel    // Combina acquire e release
memory_order_seq_cst    // Ordenação sequencial consistente (padrão)

Exemplo prático demonstrando a diferença entre relaxed e seq_cst:

#include <stdatomic.h>
#include <threads.h>
#include <stdio.h>

atomic_int x = ATOMIC_VAR_INIT(0);
atomic_int y = ATOMIC_VAR_INIT(0);
int r1, r2;

int thread1(void *arg) {
    atomic_store_explicit(&x, 1, memory_order_relaxed);
    r1 = atomic_load_explicit(&y, memory_order_relaxed);
    return 0;
}

int thread2(void *arg) {
    atomic_store_explicit(&y, 1, memory_order_relaxed);
    r2 = atomic_load_explicit(&x, memory_order_relaxed);
    return 0;
}

// Com memory_order_seq_cst, o resultado r1==0 && r2==0 é impossível
// Com memory_order_relaxed, este resultado pode ocorrer

Com relaxed, ambas as threads podem ler 0 porque as escritas podem ser atrasadas ou reordenadas. Com seq_cst, o modelo garante uma ordem total consistente entre todas as operações.

4. Acquire e Release Semantics

Acquire e release são os modos mais importantes para sincronização prática:

  • Acquire semantics (memory_order_acquire): garante que todas as leituras e escritas subsequentes não sejam reordenadas antes da operação atômica.
  • Release semantics (memory_order_release): garante que todas as leituras e escritas anteriores não sejam reordenadas após a operação atômica.

Padrão produtor-consumidor:

atomic_bool data_ready = false;
int shared_data = 0;

// Thread produtora
void producer(void) {
    shared_data = 42;  // Escrita não-atômica
    atomic_store_explicit(&data_ready, true, memory_order_release);
}

// Thread consumidora
void consumer(void) {
    while (!atomic_load_explicit(&data_ready, memory_order_acquire)) {
        thrd_yield();
    }
    // Garantido: shared_data == 42
    printf("Dado recebido: %d\n", shared_data);
}

A release semantics garante que a escrita em shared_data seja visível antes do flag, e acquire garante que a leitura do flag ocorra antes da leitura de shared_data.

5. Construindo Estruturas Lock-free Simples

Lock-free stack com atomic_compare_exchange:

#include <stdatomic.h>
#include <stddef.h>

typedef struct node {
    int value;
    struct node *next;
} node_t;

atomic_node_ptr head = ATOMIC_VAR_INIT(NULL);

void push(int val) {
    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = val;

    node_t *old_head;
    do {
        old_head = atomic_load(&head);
        new_node->next = old_head;
    } while (!atomic_compare_exchange_weak(&head, &old_head, new_node));
}

int pop(void) {
    node_t *old_head;
    node_t *new_head;

    do {
        old_head = atomic_load(&head);
        if (old_head == NULL) return -1; // Pilha vazia
        new_head = old_head->next;
    } while (!atomic_compare_exchange_weak(&head, &old_head, new_head));

    int val = old_head->value;
    free(old_head);
    return val;
}

Armadilhas comuns:

  1. ABA problem: ocorre quando um ponteiro é lido, outro thread modifica e restaura o valor original, fazendo com que o CAS seja bem-sucedido em um estado inválido. Soluções incluem tags atômicas (contadores de 64 bits) ou hazard pointers.

  2. Gerenciamento de memória: em C, sem garbage collection, é difícil determinar quando um nó pode ser liberado com segurança. Hazard pointers ou epoch-based reclamation são técnicas necessárias.

6. Considerações de Performance e Portabilidade

O impacto do memory ordering varia significativamente entre arquiteturas:

  • x86/x86_64: todas as operações de load têm acquire semantics implícito, e stores têm release semantics. memory_order_seq_cst requer barreiras mfence ou lock prefix, sendo mais caro.
  • ARM: requer barreiras explícitas para todos os modos de ordenação, exceto relaxed. A diferença entre relaxed e seq_cst é mais pronunciada.

Barreiras de memória explícitas:

atomic_thread_fence(memory_order_acquire);  // Barreira de acquire
atomic_thread_fence(memory_order_release);  // Barreira de release
atomic_signal_fence(memory_order_seq_cst);  // Barreira para sinais no mesmo thread

Limitações importantes em C:
- Sem garbage collector, gerenciamento de memória lock-free é complexo
- Algoritmos lock-free frequentemente requerem suporte a double-word CAS (DCAS), que não é universal
- A ausência de exceções/longjmp em operações atômicas simplifica o design

7. Casos de Uso e Alternativas

Quando usar lock-free:
- Alta contenção em sistemas multicore (evita contenção de kernel)
- Sistemas de tempo real onde latência determinística é crítica
- Aplicações de baixa latência (trading financeiro, jogos)
- Interrupções de hardware onde mutexes não podem ser usados

Alternativas:
- RCU (Read-Copy-Update): excelente para workloads predominantemente de leitura, usado no kernel Linux
- Transactional Memory: abordagem de hardware (Intel TSX) ou software que simplifica a programação concorrente
- Hazard Pointers: técnica para gerenciamento seguro de memória em estruturas lock-free

Integração com ferramentas:

// Compilação com AddressSanitizer para detectar data races
// gcc -fsanitize=thread -g programa.c -o programa

O AddressSanitizer pode detectar data races em código lock-free, mas requer anotações manuais para operações atômicas intencionais.

Lock-free programming em C oferece desempenho e escalabilidade superiores em cenários de alta contenção, mas exige compreensão profunda do modelo de memória e cuidado com gerenciamento de memória. Comece com padrões simples de acquire/release e evolua gradualmente para estruturas mais complexas, sempre testando com ferramentas de detecção de data races.

Referências