Lock-free, atomics e CAS

Em fevereiro de 1986, R. Kent Treiber publicou no IBM Almaden Research Center um relatório técnico curto, classificado internamente como RJ 5118, com título técnico: Systems Programming: Coping with Parallelism. O texto, hoje considerado seminal, descrevia uma estrutura de dados simples — uma stack — que múltiplas threads podiam manipular simultaneamente sem usar lock algum. A construção, hoje conhecida como Treiber stack, foi a primeira estrutura de dados lock-free praticamente útil. Ela não usa mutex, não bloqueia threads, e ainda assim garante consistência. Como? Usando uma única instrução de hardware: compare-and-swap.

Lock-free é a tradição que persegue uma promessa: concorrência onde nenhuma thread pode bloquear todas as outras. Em mutex (visto no conceito anterior), se a thread que tem o lock for preempted indefinidamente, todas as threads esperando ficam paradas. Em sistemas real-time, em hot paths com contenção altíssima, em código onde mínima latência tail importa, isso é inaceitável. Lock-free oferece garantia matemática: pelo menos uma thread sempre faz progresso, independentemente do que outras threads estejam fazendo.

Esse conceito é onde a engenharia de concorrência fica verdadeiramente difícil. As primitivas — atomics, CAS — são simples na descrição. As consequências — ABA problem, memory ordering, hazard pointers — são profundas. Estruturas lock-free são notórias por: (a) serem escritas erradas pela primeira vez em quase todas as tentativas; (b) terem bugs que não aparecem em testes mas aparecem em produção sob carga; (c) serem mais lentas que mutex em workload com pouca contenção. Por isso, a recomendação prática é dura: quase nunca escreva estruturas lock-free próprias. Use as oferecidas pela stdlib ou bibliotecas testadas. Mas entender como elas funcionam é não-negociável para sêniores trabalhando com concorrência.

Este conceito apresenta os fundamentos: a hierarquia de garantias de progresso (wait-free, lock-free, obstruction-free), a operação CAS como base universal, atomics como primitiva mínima, o problema ABA como armadilha clássica, e técnicas modernas (hazard pointers, RCU) que o resolvem. Memory ordering, que aparece como preview aqui, é tratado em detalhe no conceito 10.

Garantias de progresso — uma escada

Um algoritmo concorrente pode fornecer diferentes garantias sobre quem progride e quando. Maurice Herlihy formalizou essa hierarquia em Wait-Free Synchronization (TOPLAS, 1991), e ela organiza o vocabulário da área:

Wait-free — a garantia mais forte

Cada thread completa sua operação em um número finito de passos, independentemente do que outras threads estejam fazendo. É a garantia ideal: nenhuma thread pode ser starved. É também a mais difícil de obter — algoritmos wait-free para estruturas não-triviais são raros e tipicamente complexos. Aplicações em sistemas hard real-time (aeroespacial, automotivo crítico) onde pior caso de latência é restrição absoluta.

Lock-free — pelo menos um progride

Garante que alguma thread sempre progride, mas não necessariamente todas. Sob contenção, threads podem retentar indefinidamente; só uma vence por vez. É a garantia mais comum em estruturas lock-free reais (Treiber stack, Michael-Scott queue, ConcurrentQueue de .NET). Mais barata de implementar que wait-free, e suficiente em quase todos os casos práticos.

Obstruction-free — a mais fraca não-bloqueante

Uma thread isolada (todas as outras paradas) sempre progride. Quando há contenção, nada é garantido — pode haver livelock. Algoritmos obstruction-free dependem de mecanismos externos (backoff, helpers) para evitar livelock em prática. Tradeoff: mais simples de implementar, garantia mais fraca.

Blocking — a tradição com mutex

Algoritmos baseados em lock são bloqueantes por design: qualquer thread pode bloquear todas as outras se ela mesmo for bloqueada (por scheduler, por syscall, por crash, por qualquer motivo). É a categoria mais comum em código de aplicação, e o que estruturas lock-free buscam superar.

A hierarquia é estritamente decrescente em força: wait-free ⊃ lock-free ⊃ obstruction-free ⊃ blocking. Saber em que categoria seu algoritmo está orienta decisões: para sistema hard real-time, mutex é proibido; para hot path em servidor web, lock-free pode valer a complexidade; para CRUD comum, mutex é suficiente.

CAS — a primitiva universal

Compare-and-swap é a instrução atômica que, sozinha, é suficiente para construir virtualmente qualquer estrutura lock-free. A semântica em pseudocódigo:

// Tudo isto acontece atomicamente, em uma única instrução de hardware:
bool CAS(addr, esperado, novo) {
    if (*addr == esperado) {
        *addr = novo;
        return true;
    }
    return false;
}

A operação compara o conteúdo do endereço com o valor esperado; se igual, escreve o novo valor e retorna sucesso; senão, retorna falha. O ponto é que essa comparação e escrita acontecem atomicamente — nenhuma outra thread pode intervir no meio. Em hardware, isso é implementado de forma diferente em cada arquitetura:

• x86 / x86-64: instrução LOCK CMPXCHG (compare and exchange). O prefixo LOCK garante que o barramento de memória é exclusivo durante a operação.
• ARM (32 e 64 bit): par LDXR/STXR (load-exclusive / store-exclusive) — uma sequência onde o store falha se outra thread tocou no endereço entre os dois. É load-linked / store-conditional, equivalente funcional a CAS.
• RISC-V: extensão A oferece tanto amocas (CAS direto) quanto LR/SC.

Maurice Herlihy provou em 1991 que CAS tem número de consenso infinito — pode resolver consenso entre qualquer número de threads. Em contraste, primitivas mais simples (test-and-set, fetch-and-add) só resolvem consenso entre 2 threads. Isso justifica matematicamente por que toda CPU moderna oferece CAS: é a primitiva atômica mínima necessária para implementar concorrência sem locks de forma genérica.

Atomic operations — primitivas além de CAS

Embora CAS seja a base teórica, hardware moderno oferece um catálogo de operações atômicas para casos comuns:

• Load / Store atômicos: leitura/escrita de uma palavra inteira sem tearing. Crítico em arquiteturas onde loads/stores normais podem ser parciais.
• Add / Sub atômicos: incremento/decremento sem leitura intermediária visível. Em x86, LOCK XADD.
• Exchange atômico: troca conteúdo do endereço pelo valor novo, retorna o antigo, atomicamente.
• Bit operations atômicas: AND, OR, XOR sobre flags em bitmask.
• CAS: a já vista. A mais poderosa.

Para um contador concorrente, você não precisa de CAS — basta atomic add. Em C#: Interlocked.Increment(ref contador). Em Go: atomic.AddInt64(&contador, 1). Em Java: AtomicLong.incrementAndGet(). Em C++: std::atomic<int64_t> counter; counter.fetch_add(1). Cada um compila para uma única instrução de hardware (LOCK XADD em x86), executando em dezenas de nanossegundos sob contenção moderada — ordens de magnitude mais barato que mutex.

Python merece nota especial. Antes de Python 3.13, não havia atomic operations na stdlib. Operações no Python que parecem atômicas (contador += 1) só são para tipos específicos sob GIL — e mesmo assim, operações compostas podem race. Python 3.13 (out/2024) introduziu tentativamente um runtime sem GIL onde atomic operations ganham relevância nova. Em 2026, ecossistema ainda está se adaptando; bibliotecas como atomic e numpy.atomic oferecem alternativas para quando Python sem GIL for adotado em escala.

O CAS loop — padrão fundamental

A maioria das estruturas lock-free é construída em cima de um padrão recorrente: CAS loop. A ideia é "leia o estado; calcule novo estado; tente substituir via CAS; se falhou (alguém modificou no meio), retente". Concorrência otimista — assuma que ninguém vai interferir; trate o caso onde interferiram.

// Pseudocódigo: incremento via CAS loop
fn incrementar_atomico(contador: *atomic_int) {
    loop {
        let antigo = atomic_load(contador);     // 1: lê valor atual
        let novo = antigo + 1;                  // 2: calcula novo
        if CAS(contador, antigo, novo) {        // 3: tenta atualizar
            return;                              //    sucesso!
        }
        // CAS falhou — outra thread modificou. Tente de novo.
    }
}

O loop tipicamente roda 1–2 iterações sob contenção normal, raramente mais. Sob contenção altíssima (muitas threads competindo pelo mesmo endereço), pode demorar — mas alguma thread sempre vence em cada iteração, garantindo lock-freedom.

Para counter, esse padrão é desnecessário (atomic add resolve diretamente). Mas para qualquer transformação não-trivial (compare e modifique se condição; insere se ainda não presente; atualize com função pura), CAS loop é a estrutura idiomática. AtomicInteger.updateAndGet(IntUnaryOperator) em Java, Interlocked.CompareExchange em C# com loop manual, atomic.CompareAndSwapInt64 em Go — todos expõem a mesma idéia.

O ABA problem — a armadilha que todo lock-free conhece

O ABA é um bug clássico em algoritmos lock-free com ponteiros. O nome vem da sequência: thread 1 lê valor A; threads 2 e 3 mudam o valor para B e depois de volta para A; thread 1 faz CAS comparando com A, sucesso — mas o estado não é o mesmo. Algo aconteceu entre as observações.

Em counter, ABA é inofensivo (incremento é incremento, não importa quantas vezes voltou). Em estruturas com ponteiros, pode ser desastroso. Considere a Treiber stack:

fn pop(stack: *atomic_node_ptr) -> *Node {
    loop {
        let topo_antigo = atomic_load(stack);
        if topo_antigo == null { return null; }
        let novo_topo = topo_antigo.proximo;
        if CAS(stack, topo_antigo, novo_topo) {
            return topo_antigo;
        }
    }
}

Cenário ABA:

1. Thread 1 carrega topo_antigo = X (apontando para nó X cujo próximo é Y).
2. Thread 1 lê X.proximo = Y.
3. Thread 1 é preempted antes do CAS.
4. Thread 2 dá pop em X (estado: topo = Y).
5. Thread 2 dá pop em Y (estado: topo = ... outro Z).
6. Thread 2 dá push de novo X (memória reciclada por allocator!). Estado: topo = X, mas X.proximo agora é Z, não Y.
7. Thread 1 retoma, faz CAS(stack, X, Y). Sucesso! O topo vira Y — mas Y já não está na stack; foi removido no passo 5.
8. Estado corrompido. Pop posteriores tocam em memória liberada ou retornam nó errado.

O ABA não acontece se o nó X ficasse vivo entre os passos 1 e 7 — mas linguagens com gerenciamento manual de memória (C, C++, ou Go com pool de objetos) podem reciclar X. O bug é especialmente sutil em Go porque o garbage collector tipicamente protege contra ele, mas se o programador adicionar pool com sync.Pool e reusar nós, ABA volta.

Soluções para ABA

Várias técnicas atacam o problema em ângulos diferentes:

• Tagged pointers: anexar um contador (tag) ao ponteiro; cada modificação incrementa a tag. CAS compara ponteiro+tag, então mesmo que o ponteiro volte ao valor A, a tag diferente faz CAS falhar. Em x86-64, tags usam bits altos do endereço (não usados por nenhum endereço real) ou instrução CMPXCHG16B que opera em 128 bits.
• Hazard pointers (Maged Michael, 2004): cada thread anuncia em uma estrutura compartilhada quais nós ela está atualmente acessando. A reciclagem só pode liberar nós que nenhuma thread está protegendo. Adiciona overhead de leitura mas resolve elegantemente. Patenteado pela IBM até 2024, hoje livre.
• RCU (Read-Copy-Update): leitores nunca bloqueiam; escritores criam cópia, modificam, e agendam liberação da versão antiga após um período de carência onde garantidamente nenhum leitor anterior ainda esteja lendo. Inventado por Paul McKenney nos anos 1990, dominante no kernel Linux para estruturas read-mostly.
• Garbage collection: em linguagens com GC (Java, Go, C#), nós só são liberados quando ninguém mais tem referência, evitando reciclagem precoce. Resolve ABA quase de graça — uma das razões pelas quais lock-free em Java/Go é mais simples que em C++.

Estruturas lock-free clássicas

Vale conhecer pelo nome as estruturas lock-free canônicas — não necessariamente para implementá-las, mas para reconhecer no catálogo da stdlib quando precisar de uma.

Treiber stack (1986)

A primeira estrutura lock-free praticamente útil. CAS no ponteiro de topo. Push: aloca nó, aponta seu próximo para o topo atual, CAS. Pop: lê topo, lê próximo, CAS para substituir por próximo. Sofre de ABA em ambientes sem GC. É a estrutura mais didática para entender lock-free.

Michael-Scott queue (1996)

Maged Michael e Michael Scott publicaram Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms no PODC 1996 — paper canônico em queue concorrente. A construção tem ponteiros para cabeça e cauda separados, com CAS em ambos coordenados via "auxiliary node". É a base de virtualmente toda queue concorrente em stdlib moderna — java.util.concurrent.ConcurrentLinkedQueue, System.Collections.Concurrent.ConcurrentQueue em .NET.

Lock-free hash table

Mais complexa que stack/queue. Cliff Click apresentou em 2007 uma implementação lock-free de hash table para JVM (parte do Azul Zing) que escala em centenas de cores. Java 8+ ConcurrentHashMap usa técnicas relacionadas (lock striping com paths lock-free para leituras). Hash tables verdadeiramente lock-free são raras na stdlib — a maioria das "concurrent hash maps" usa locks finos.

Read-Copy-Update (RCU)

Não é estrutura, é técnica. Permite leituras lock-free arbitrariamente complexas — o leitor simplesmente desreferencia ponteiros. O escritor faz cópia da estrutura toda, modifica, faz CAS no ponteiro raiz, e agenda liberação da versão antiga. Domina o kernel Linux para tabelas de roteamento, lista de processos, namespaces — qualquer estrutura lida muito mais que escrita.

Memory ordering — preview

Atomic operations não têm apenas semântica de "essa instrução é indivisível". Têm também semântica de ordering: como essa operação se relaciona com outras leituras e escritas antes e depois dela, da perspectiva de outras threads. Esse é o tópico do conceito 10 e exige tratamento dedicado, mas vale o overview agora.

Há cinco modos típicos de ordering em APIs modernas (Java memory model, C++11, Go, Rust):

• Sequentially consistent: todas as operações atômicas têm uma ordem total, observada igualmente por todas as threads. Mais simples de raciocinar, mais lento.
• Acquire: leituras subsequentes não podem ser reordenadas para antes desta. Forma um "release-acquire pair" com a operação correspondente.
• Release: escritas anteriores não podem ser reordenadas para depois desta.
• Acquire-release: combinação dos dois para operações como CAS que fazem load+store.
• Relaxed: sem garantia de ordering em relação a outras operações. Útil para counters monotônicos onde só a atomicidade interessa, não a ordem com o resto.

A escolha errada de ordering produz bugs sutilíssimos — escreve para X, escreve flag pronto = true, outra thread vê pronto = true mas X ainda com valor antigo. Por isso C++ default para std::atomic é seq_cst; Java segue similar; Go sync/atomic é seq_cst. Você só baixa o ordering quando mediu e provou que é seguro — código performance-critical onde a diferença entre seq_cst e relaxed é mensurável.

O mesmo padrão nas três linguagens

Para concretizar, considere o problema clássico: contador atômico (caso simples) e flag de inicialização única (CAS-based). Veja como cada linguagem expressa.

using System.Threading;

// Contador atômico simples
public class ContadorAtomico {
    private long valor;

    public long Incrementar() => Interlocked.Increment(ref valor);
    public long Ler() => Interlocked.Read(ref valor);
    public void Resetar() => Interlocked.Exchange(ref valor, 0);
}

// CAS loop manual — atualizar com função pura
public long AtualizarSe(ref long destino, Func<long, long> transformar) {
    long original, novo;
    do {
        original = Interlocked.Read(ref destino);
        novo = transformar(original);
    } while (Interlocked.CompareExchange(ref destino, novo, original) != original);
    return novo;
}

// Para inicialização única — preferir Lazy<T> (que usa CAS internamente)
private static readonly Lazy<Servico> instancia = new(() => new Servico());
public static Servico Instancia => instancia.Value;

import threading

# Pré 3.13: não há primitivas atômicas reais na stdlib.
# Use threading.Lock para qualquer operação composta:

class ContadorThreadSafe:
    def __init__(self):
        self._valor = 0
        self._lock = threading.Lock()

    def incrementar(self):
        with self._lock:
            self._valor += 1

    def ler(self):
        with self._lock:
            return self._valor

# Inicialização única — use threading.Lock + double-checked, ou
# functools.cache (que é thread-safe em CPython graças ao GIL):
from functools import cache

@cache
def get_servico():
    return Servico()

# Python 3.13+ (no-GIL experimental): atomic ops na stdlib são
# work-in-progress. Bibliotecas como `atomic-py` preenchem o gap.

package main

import (
    "sync/atomic"
)

// Contador moderno (Go 1.19+) com tipos genéricos
type Contador struct {
    valor atomic.Int64
}

func (c *Contador) Incrementar() int64 {
    return c.valor.Add(1)
}

func (c *Contador) Ler() int64 {
    return c.valor.Load()
}

// CAS loop para transformação
func atualizarSe(destino *atomic.Int64, transformar func(int64) int64) int64 {
    for {
        antigo := destino.Load()
        novo := transformar(antigo)
        if destino.CompareAndSwap(antigo, novo) {
            return novo
        }
    }
}

// Inicialização única — sync.Once é a ferramenta certa
var instancia *Servico
var once sync.Once

func GetServico() *Servico {
    once.Do(func() { instancia = NewServico() })
    return instancia
}

Quando lock-free vence — e quando perde

Lock-free brilha em três cenários específicos. Primeiro: contadores e flags em hot path. Métricas incrementadas milhares de vezes por segundo em servidor de alta carga. Atomic add custa nanossegundos; mutex em mesma situação vira gargalo visível em profile. Segundo: sistemas real-time, onde latência tail máxima é requisito (trading, controle industrial). Mutex pode ser bloqueado por preempção arbitrária; lock-free não. Terceiro: estruturas read-mostly com técnicas como RCU, onde leitores são extremamente leves e escritores raros.

Lock-free perde em três cenários simétricos. Primeiro: operações compostas em estado complexo. Atualizar três campos de uma struct atomicamente exige CAS de 128 bits ou estrutura de double-word — complexa, restrita. Mutex protegendo o struct é mais simples. Segundo: baixa contenção. Mutex moderno em região curta sem contenção custa dezenas de nanossegundos. Lock-free via CAS loop pode ter overhead similar quando não há contenção. O ganho de lock-free aparece sob carga pesada. Terceiro: código onde correção precisa de revisão humana fácil. Lock-free é notoriamente difícil de revisar; bugs sutis passam. Mutex em código claro é mais defensável em produção.

Como praticar

1. Implemente atomic counter via CAS loop. Em Go, sem usar atomic.Int64.Add; só CompareAndSwap e Load. Compare a performance com atomic.Add (que internamente é LOCK XADD) e com sync.Mutex. Use testing.B. Documente os números com 1, 2, 4, 8 threads concorrentes. A diferença de comportamento sob contenção é a evidência mais forte do que o conceito tenta explicar.
2. Demonstre o ABA problem. Em C ou Rust com unsafe (linguagens sem GC), implemente uma Treiber stack ingênua. Force ABA usando alocador customizado que recicla nós em pool. Observe o estado corrompido. Depois adicione tagged pointers (counter no ponteiro) e veja o bug sumir. Em Go ou C# isso é difícil de reproduzir porque o GC protege — o que é ensinamento próprio.
3. Microbenchmark mutex vs atomic vs RWMutex. Em qualquer linguagem, escreva três implementações de contador concorrente: mutex, atomic, RWMutex (lê 99% das vezes, escreve 1%). Rode com 1, 4, 16 threads em workload configurável. Plote os resultados. Identifique em que regime cada um vence — vai ver que não há vencedor universal, e isso é o ponto.