Estruturas de dados sem bloqueio: guia completo com exemplos em C++, Java e .NET

Um mutex é simples. Você o bloqueia, modifica o estado compartilhado e o desbloqueia. Cada thread que deseja acesso espera sua vez. O problema é essa "espera", pois em sistemas com grande número de núcleos e alta taxa de transferência, a serialização se torna o limite. Uma thread que detém um bloqueio pode ser interrompida, fazendo com que todas as outras threads fiquem ociosas. A inversão de prioridade pode fazer com que threads de baixa prioridade bloqueiem as de alta prioridade. Em sistemas que processam milhões de operações por segundo em dezenas de núcleos, a contenção de mutexes não apenas torna o processo mais lento; ela reduz drasticamente a taxa de transferência.

Estruturas de dados sem bloqueio substituem a exclusão mútua por operações atômicas. Em vez de prevenir conflitos, elas os toleram e se recuperam deles. Uma thread que falha em uma operação de comparação e troca tenta novamente com o estado atualizado. Nenhuma thread jamais bloqueia outra. Pelo menos uma thread sempre progride. O resultado é uma melhoria drástica na taxa de transferência sob alta contenção, latência previsível sem efeitos de comboio e a eliminação de impasses e inversão de prioridade por projeto. O preço é a complexidade de implementação: o problema ABA, os riscos de recuperação de memória, o compartilhamento falso e os requisitos sutis de ordenação de memória são armadilhas que não existem em código baseado em bloqueio. Este artigo aborda todas elas com exemplos concretos.

Lock-Free vs Wait-Free vs Mutex: Qual usar?

Antes de escolher uma abordagem de implementação, a pergunta certa é qual garantia de progresso o sistema realmente precisa. Os três modelos diferem no que prometem quando as threads competem.

Modelo	Garantia de progresso	Latência típica	Complexidade	Mais Adequada Para
Mutex / baseado em bloqueio	Bloqueio, threads aguardam	Imprevisível em situações de disputa	Baixo	Estado compartilhado com baixa contenção, requisitos de correção simples.
Sem fechadura	Em todo o sistema, pelo menos uma thread progride.	Baixo sob disputa	Alto	Filas de alto rendimento, pilhas, contadores
Sem espera	Por thread, cada thread termina em etapas delimitadas.	Pior caso limitado	Muito alto	Sistemas em tempo real, críticos para a segurança, SLAs de latência rigorosos
Sem obstruções	Progresso individual, somente quando não contestado.	Baixo sem contestação	Suporte:	Protótipos de memória transacional, contextos de pesquisa

Em sistemas de produção com alta concorrência, o protocolo sem bloqueio (lock-free) é o padrão prático. A fila Michael-Scott, a pilha Treiber e a maioria dos buffers circulares MPMC de produção são livres de bloqueio. Threads individuais podem sofrer inanição sob extrema contenção, mas o sistema como um todo continua progredindo.

A garantia de progresso limitado por thread é garantida pela ausência de espera, mas requer algoritmos significativamente mais complexos. Existem construções universais, mas elas apresentam alta sobrecarga. Os algoritmos sem espera são apropriados para contextos de tempo real rígido, onde a latência de cauda é mais importante do que a taxa de transferência média.

O conceito de "sem obstrução" raramente é usado diretamente em produção. Ele aparece em algumas implementações de memória transacional e serve como um passo intermediário na comprovação da correção de algoritmos.

Para a maioria dos sistemas de alta concorrência: use um mutex quando a contenção for baixa e a correção for simples, use um mecanismo sem bloqueio quando a taxa de transferência sob contenção for importante e use um mecanismo sem espera somente quando a latência por thread no pior caso for um requisito essencial.

O que é uma estrutura de dados sem bloqueio?

Uma estrutura de dados é livre de bloqueios se garantir que pelo menos uma thread, dentre todas as threads que operam sobre ela, concluirá sua operação em um número finito de passos, independentemente do que as outras threads estejam fazendo ou de como estejam agendadas. Essa definição formal tem uma implicação precisa: nenhum algoritmo livre de bloqueios pode entrar em deadlock. Se uma thread for interrompida, suspensa ou estiver executando lentamente, as outras threads continuarão a progredir.

O mecanismo consiste em operações atômicas, instruções da CPU que são executadas como uma única unidade indivisível. A primitiva universal é a Comparação e Troca (CAS) :

CAS(location, expected, new_value):
  if *location == expected:
    *location = new_value
    return true
  else:
    return false  // someone else changed it first

O CAS é atômico no nível de hardware. Em x86, é o CMPXCHG instrução. Em ARM, isso é implementado por meio de LDXR/STXR (load-exclusive/store-exclusive), que é a variante LL/SC (Load-Linked/Store-Conditional). Uma thread lê um valor, calcula um novo valor e usa CAS para instalá-lo somente se ninguém mais o tiver alterado nesse intervalo. Se o CAS falhar, a thread tenta novamente com o novo valor.

Em C++11 e versões posteriores, isso é exposto através de std::atomic:

cpp

#include <atomic>

// Atomic increment using CAS loop
void atomic_add(std::atomic<int>& counter, int delta) {
    int expected = counter.load(std::memory_order_relaxed);
    while (!counter.compare_exchange_weak(
        expected,
        expected + delta,
        std::memory_order_release,
        std::memory_order_relaxed))
    {
        // expected is updated on failure -- retry with fresh value
    }
}

compare_exchange_weak é a primitiva CAS. Em caso de falha, ela atualiza. expected para o valor atual automaticamente, tornando o loop de repetição idiomático.

O Problema da ABA: A Armadilha Mais Perigosa do Lock-Free

O problema ABA é o risco de correção mais contraintuitivo na programação sem bloqueio. O CAS verifica se uma posição de memória ainda contém o valor esperado antes de instalar uma nova. Ele não consegue detectar se esse valor foi alterado e revertido entre a leitura e o CAS. A posição ainda parece conter o valor original, mas o estado subjacente do sistema mudou de maneiras que o CAS não consegue perceber.

O cenário passo a passo

Considere uma pilha sem bloqueio usando um único ponteiro. top:

1. O tópico A diz: top = Node1O próximo ponteiro do Node1 é o Node2.
2. A thread A é interrompida antes de completar sua operação de descompressão.
3. A thread B remove o Node1 (o nó superior se torna o Node2) e, em seguida, remove o Node2 (o nó superior se torna nulo).
4. A thread B insere um novo nó, que por acaso é alocado no mesmo endereço de memória que o Nó 1 (comum em alocadores de lista livre). Topo = Nó 1 (mesmo ponteiro, conteúdo diferente).
5. A thread A é retomada. Seu CAS vê top == Node1 (valor esperado), tem sucesso e define top = Node2Mas o Node2 já estava liberado. Desastre.

O problema ABA se manifesta de forma diferente em cada estrutura de dados:

• CorMonitorO CAS é bem-sucedido, mas instala um ponteiro next obsoleto, causando uso após liberação (use-after-free).
• FilaO indicador de cabeça ou cauda parece inalterado, mas a estrutura mudou.
• Lista vinculadaUm nó parece ainda estar em posição, mas foi removido e realocado.

Será que a LL/SC evita o problema da ABA?

Sim, LL/SC (Load-Linked/Store-Conditional) oferece uma semântica mais robusta que CAS e, naturalmente, evita ABA. LL marca o endereço de memória carregado como "vinculado". SC no mesmo endereço falha se qualquer armazenamento nesse endereço ocorreu desde o LL, mesmo que o valor tenha sido restaurado ao seu estado original. O histórico de modificações é rastreado no nível do hardware, não apenas o valor atual.

No entanto, as implementações de LL/SC em hardware real têm limitações práticas. Em ARM e POWER, falhas espúrias de LL/SC podem ocorrer mesmo sem contenção (trocas de contexto, remoções de cache). O código deve levar em conta os loops de repetição, mesmo sem conflitos reais. Em x86, não existe LL/SC nativo; o CAS é a primitiva de hardware. Para código x86, o ABA deve ser evitado por software.

Corrigindo a ABA: Três abordagens

1. Contadores de versão (ponteiros marcados)

Empacote um contador de versões na mesma palavra atômica que o ponteiro. Cada operação CAS bem-sucedida incrementa o contador. Mesmo que um ponteiro retorne ao seu valor original, o contador permanece diferente:

cpp

#include <atomic>
#include <cstdint>

struct TaggedPtr {
    uintptr_t ptr : 48;  // pointer (48-bit virtual address space)
    uintptr_t tag : 16;  // version counter
};

std::atomic<TaggedPtr> top;

bool cas_with_tag(std::atomic<TaggedPtr>& loc,
                  TaggedPtr expected,
                  void* new_ptr) {
    TaggedPtr desired = { (uintptr_t)new_ptr, expected.tag + 1 };
    return loc.compare_exchange_strong(expected, desired);
}

Essa é a abordagem padrão na prática. A tag de 16 bits dá a volta após 65,536 operações, o que é teoricamente inseguro, mas praticamente adequado para a maioria dos sistemas; é extremamente improvável que uma thread seja interrompida por exatamente 65,536 ciclos CAS no mesmo local.

2. Indicadores de perigo

Cada thread mantém um pequeno conjunto de "ponteiros de risco", ponteiros para nós que ela está acessando no momento. Antes de liberar qualquer nó, uma thread verifica todos os registros de ponteiros de risco para confirmar que nenhuma outra thread está acessando-o. Um nó que aparece em um ponteiro de risco é adiado até que esse ponteiro seja limpo.

cpp

// Simplified hazard pointer pattern
thread_local void* hazard_ptr = nullptr;

void* safe_load(std::atomic<void*>& head) {
    void* ptr;
    do {
        ptr = head.load(std::memory_order_acquire);
        hazard_ptr = ptr;                          // announce we are using this
        // memory fence ensures announcement is visible before validation
        std::atomic_thread_fence(std::memory_order_seq_cst);
    } while (ptr != head.load(std::memory_order_acquire)); // validate still valid
    return ptr;
}

void safe_release() {
    hazard_ptr = nullptr;
}

Os ponteiros de risco impedem a otimização baseada em algoritmos (ABA) no nível de recuperação de memória: um nó não pode ser reutilizado enquanto qualquer thread mantiver um ponteiro de risco para ele. Isso exige a verificação de todos os ponteiros de risco das threads antes de liberá-los, o que adiciona uma sobrecarga proporcional ao número de threads.

3. Recuperação baseada em épocas (EBR)

Os threads operam em "épocas" rastreadas globalmente. Os nós desativados são armazenados em buffer por época e liberados somente quando todos os threads avançaram além da época em que o nó foi desativado. O EBR é mais simples de usar do que os ponteiros de risco e tem uma sobrecarga por operação menor, ao custo de um crescimento de memória limitado, porém imprevisível, durante períodos de inatividade.

Em Java, AtomicStampedReference Aborda diretamente o problema ABA ao associar uma referência a um número inteiro:

Java

import java.util.concurrent.atomic.AtomicStampedReference;

AtomicStampedReference<Node> top =
    new AtomicStampedReference<>(null, 0);

void push(Node newNode) {
    int[] stamp = new int[1];
    Node current;
    do {
        current = top.get(stamp);
        newNode.next = current;
    } while (!top.compareAndSet(current, newNode, stamp[0], stamp[0] + 1));
}

Implementações de filas sem bloqueio

As filas são a estrutura sem bloqueio mais comumente necessária. A fila sem bloqueio canônica é a fila de Michael-Scott, que usa dois ponteiros (cabeçalho e cauda) e um nó sentinela para permitir operações simultâneas de enfileiramento e desenfileiramento.

Fila SPSC: Desempenho máximo com sincronização mínima

Uma fila de produtor único e consumidor único elimina toda a contenção de escrita-escrita e leitura-leitura. Uma thread escreve no final da fila; uma thread lê do início. Apenas o ponteiro do início é compartilhado entre produtor e consumidor.

cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class SPSCQueue {
    std::array<T, Capacity> buffer;
    alignas(64) std::atomic<size_t> head{0}; // consumer reads head
    alignas(64) std::atomic<size_t> tail{0}; // producer writes tail
    // alignas(64) puts each on a separate cache line -- prevents false sharing

public:
    bool push(const T& item) {
        size_t t = tail.load(std::memory_order_relaxed);
        size_t next = (t + 1) % Capacity;
        if (next == head.load(std::memory_order_acquire))
            return false; // full
        buffer[t] = item;
        tail.store(next, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t h = head.load(std::memory_order_relaxed);
        if (h == tail.load(std::memory_order_acquire))
            return false; // empty
        item = buffer[h];
        head.store((h + 1) % Capacity, std::memory_order_release);
        return true;
    }
};

O alignas(64) A utilização de cache na cabeça e na cauda é crucial. Sem ela, ambas cabem na mesma linha de cache. Cada escrita na cauda aciona uma invalidação da linha de cache visível para o núcleo que lê a cabeça, e vice-versa, um compartilhamento falso que serializa o que deveriam ser operações independentes.

Fila MPMC: Multiprodutor Multiconsumidor

Uma fila MPMC totalmente concorrente é significativamente mais complexa. Implementações de produção usam um número de sequência por slot para coordenar produtores e consumidores sem um bloqueio:

cpp

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class MPMCQueue {
    struct Slot {
        std::atomic<size_t> sequence;
        T data;
    };

    alignas(64) std::array<Slot, Capacity> slots;
    alignas(64) std::atomic<size_t> enqueue_pos{0};
    alignas(64) std::atomic<size_t> dequeue_pos{0};

public:
    MPMCQueue() {
        for (size_t i = 0; i < Capacity; ++i)
            slots[i].sequence.store(i, std::memory_order_relaxed);
    }

    bool push(const T& item) {
        size_t pos = enqueue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        // wait for the slot to be ready for writing
        while (seq != pos) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        slot.data = item;
        slot.sequence.store(pos + 1, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t pos = dequeue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        while (seq != pos + 1) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        item = slot.data;
        slot.sequence.store(pos + Capacity, std::memory_order_release);
        return true;
    }
};

ConcurrentQueue do .NET: Como funciona internamente

.NET ConcurrentQueue<T> No .NET 5+, utiliza-se uma estrutura de matriz segmentada. Cada segmento é uma matriz de tamanho fixo com índices de cabeça e cauda gerenciados com Interlocked operações (que mapeiam para CAS no hardware subjacente). Os segmentos são vinculados por meio de um volátil _nextSegment ponteiro. Enfileirar anexa ao segmento final atual, aumentando a cadeia de segmentos quando estiver cheia. Desenfileirar lê do segmento inicial e avança o índice inicial atomicamente.

A principal decisão de design é evitar um bloqueio global. Os produtores competem apenas no índice de cauda do segmento atual. Os consumidores competem apenas no índice de cabeça. Nenhum produtor jamais compete com um consumidor. Isso torna ConcurrentQueue<T> Altamente eficiente para dutos produtor-consumidor:

csharp

using System.Collections.Concurrent;
using System.Threading;

// .NET ConcurrentQueue -- lock-free, thread-safe, FIFO
var queue = new ConcurrentQueue<int>();

// Producer thread
var producer = Task.Run(() => {
    for (int i = 0; i < 1_000_000; i++)
        queue.Enqueue(i);
});

// Consumer thread
var consumer = Task.Run(() => {
    long sum = 0;
    while (!queue.IsEmpty || !producer.IsCompleted) {
        if (queue.TryDequeue(out int item))
            sum += item;
        else
            Thread.SpinWait(1);  // brief spin before retry
    }
    return sum;
});

await Task.WhenAll(producer, consumer);

Coerência de cache e compartilhamento falso em código sem bloqueio

A coerência de cache é a variável de desempenho invisível em implementações sem bloqueio. Quando um núcleo escreve em um endereço de memória, toda a linha de cache de 64 bytes que contém esse endereço é invalidada nos caches de todos os outros núcleos. Eles precisam buscar a linha atualizada antes de ler. Em código sem bloqueio com atualizações atômicas frequentes, essa invalidação da linha de cache pode se tornar o custo dominante.

O compartilhamento falso ocorre quando duas threads modificam variáveis ​​diferentes que por acaso compartilham uma linha de cache. Nenhuma das threads está acessando os mesmos dados, mas o protocolo de coerência de cache trata toda a linha de cache como disputada.

cpp

// BAD: head and tail on the same cache line
struct BadQueue {
    std::atomic<size_t> head;   // bytes 0-7
    std::atomic<size_t> tail;   // bytes 8-15
    // both fit in the same 64-byte cache line
    // producer writing tail invalidates head in consumer's cache
};

// GOOD: head and tail on separate cache lines
struct GoodQueue {
    alignas(64) std::atomic<size_t> head;
    alignas(64) std::atomic<size_t> tail;
    // each on its own cache line -- no false sharing
};

O protocolo MESI (Modificado, Exclusivo, Compartilhado, Inválido) descreve como as CPUs x86 coordenam a propriedade das linhas de cache. Quando um núcleo deseja escrever em um local que compartilha com outros núcleos (estado Compartilhado), ele deve transmitir uma solicitação de escrita, aguardar a confirmação de todos os núcleos que compartilham o local e, em seguida, transitar para o estado Modificado. Essa ida e volta ao protocolo de coerência leva de 50 a mais de 300 ciclos em um sistema com múltiplos soquetes. O compartilhamento falso transforma operações independentes locais de thread em tráfego de coerência de cache, comprometendo o desempenho que deveria escalar linearmente com o número de núcleos.

Detecção de compartilhamento falso: usar perf stat -e cache-misses,L1-dcache-load-misses no Linux ou no analisador de desempenho de CPU do Visual Studio no Windows. Uma alta taxa de falhas de cache L1 em ​​um programa multithread que cabe no cache é um forte indicador de compartilhamento falso.

Ordenação da memória: por quê? memory_order_relaxed Nem sempre é suficiente.

C + + std::atomic As operações expõem toda a gama de ordenação de memória do modelo de memória C++11. Escolher a ordenação errada é o segundo erro mais comum em código sem bloqueio, depois do problema ABA.

cpp

// The five memory orderings and when each applies:

// relaxed: no synchronization, only atomicity
// Use for: counters where only the final value matters
counter.fetch_add(1, std::memory_order_relaxed);

// acquire: reads see all writes by threads that released this location
// Use for: reading shared state protected by a flag
if (ready.load(std::memory_order_acquire)) {
    use(data); // guaranteed to see all writes made before ready was set
}

// release: writes are visible to threads that acquire this location
// Use for: publishing shared state
data = compute();
ready.store(true, std::memory_order_release);

// acq_rel: acquire + release in one operation
// Use for: read-modify-write operations like CAS in the middle of a chain
node.compare_exchange_strong(expected, desired,
    std::memory_order_acq_rel,   // success
    std::memory_order_acquire);  // failure

// seq_cst: total order across all seq_cst operations, all cores
// Use for: when you need a global consistent view (but slowest)
flag.store(true, std::memory_order_seq_cst);

Um erro comum: usar relaxed para um sinalizador de lançamento. Uma thread que define ready = true com as relaxed a ordem não garante que as escritas anteriores para data são visíveis para outros tópicos que leem readyO par aquisição/liberação cria a relação de precedência que conecta escritor e leitor.

A pilha de Treiber: uma pilha sem bloqueio em C++

A pilha de Treiber é a estrutura de dados não trivial sem bloqueio mais simples. Ela utiliza um laço CAS em uma única instância. top ponteiro:

cpp

#include <atomic>

template<typename T>
class TreiberStack {
    struct Node {
        T data;
        Node* next;
        explicit Node(T d) : data(std::move(d)), next(nullptr) {}
    };

    std::atomic<Node*> top{nullptr};

public:
    void push(T data) {
        Node* node = new Node(std::move(data));
        node->next = top.load(std::memory_order_relaxed);
        while (!top.compare_exchange_weak(
            node->next,          // expected -- updated on failure
            node,                // desired
            std::memory_order_release,
            std::memory_order_relaxed))
        { /* retry */ }
    }

    bool pop(T& result) {
        Node* node = top.load(std::memory_order_acquire);
        while (node) {
            if (top.compare_exchange_weak(
                node,
                node->next,      // new top
                std::memory_order_acquire,
                std::memory_order_relaxed))
            {
                result = std::move(node->data);
                // WARNING: cannot free node here safely without hazard pointers or EBR
                // delete node; -- ABA hazard if another thread reads node->next
                return true;
            }
        }
        return false; // empty
    }
};

O comentário sobre delete node É crucial: a exclusão ingênua é o risco ABA descrito anteriormente. Em uma pilha Treiber de produção, a recuperação de nós requer ponteiros de risco, recuperação baseada em época ou coleta de lixo (Java/C# lida com isso automaticamente).

Estruturas de dados sem bloqueio em Java

A biblioteca padrão do Java fornece implementações sem bloqueio de qualidade de produção em java.util.concurrent:

Aula	Estrutura	Progresso	Notas
AtomicReference<T>	Valor unico	Sem fechadura	CAS em referência de objeto
AtomicStampedReference<T>	Valor + selo	Sem fechadura	Prevenção de ABA por meio de contador de versões
ConcurrentLinkedQueue<T>	fila Michael-Scott	Sem fechadura	FIFO, ilimitado
ConcurrentLinkedDeque<T>	Deque sem trava	Sem fechadura	Ambos os finais
LongAdder	Contador	Sem fechadura	Contagem listrada de alto rendimento

LongAdder Vale a pena notar especificamente o seguinte: em vez de um único contador atômico competindo entre todas as threads, ele mantém uma matriz de contadores distribuída ao longo das faixas, cada uma acessada por um subconjunto de threads. A disputa é distribuída pelas faixas, em vez de se concentrar em um único local. O total é somado de forma preguiçosa. sum()Para operações de incremento de alta frequência em várias threads, LongAdder supera dramaticamente AtomicLong.incrementAndGet():

Java

import java.util.concurrent.atomic.LongAdder;

// BAD for high-concurrency counting: all threads contend on one location
AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet(); // single CAS -- all threads collide

// GOOD for high-concurrency counting: contention distributed across stripes
LongAdder adder = new LongAdder();
adder.increment();  // updates thread-local stripe -- minimal contention
long total = adder.sum(); // sum all stripes lazily

Como SMART TS XL Suporta o desenvolvimento de sistemas sem bloqueio.

O código sem bloqueio está entre os mais difíceis de implementar corretamente. Os erros são não determinísticos, aparecem apenas sob intercalações específicas e, frequentemente, apenas em produção em larga escala. A análise estática resolve esse problema examinando as propriedades estruturais do código antes da execução, em vez de esperar que uma condição de corrida se manifeste.

SMART TS XL Analisa os caminhos de execução completos do código concorrente, rastreando como as operações atômicas se relacionam com os locais de memória que elas protegem. Para sistemas que misturam código sem bloqueio com componentes legados ou arquiteturas multilíngues, fornece a visibilidade entre fronteiras que as ferramentas de linguagem única não conseguem: como uma região de memória compartilhada acessada por um componente C++ sem bloqueio se relaciona com o serviço Java que lê dela, ou como uma fila concorrente alimenta um pipeline de processamento baseado em COBOL.

A funcionalidade de análise estática de código identifica padrões associados a riscos de concorrência: carregamentos atômicos sem a semântica de aquisição correspondente, loops CAS que não atualizam o valor esperado em caso de falha, estruturas de dados compartilhadas onde campos acessados ​​por diferentes threads estão localizados no mesmo local sem o preenchimento de alinhamento. A funcionalidade de análise de impacto rastreia quais componentes subsequentes dependem de uma estrutura de dados concorrente compartilhada, de modo que as alterações na interface da estrutura ou na estratégia de recuperação possam ser corretamente dimensionadas antes de serem implementadas.

Para sistemas empresariais onde componentes sem bloqueio devem coexistir com processamento em lote legado, middleware de filas de mensagens e camadas de serviço modernas, SMART TS XL'S mapeamento de dependência Fornece a visão arquitetural de como os caminhos de dados concorrentes conectam componentes escritos em diferentes linguagens em toda a pilha do sistema.

Quando a opção sem fechadura é a escolha errada

A ausência de bloqueio nem sempre é melhor que um mutex. A justificativa para estruturas sem bloqueio depende do perfil de contenção da carga de trabalho. Com um número baixo de threads ou baixa contenção, um mutex bem implementado é mais rápido porque evita a sobrecarga de loops de repetição atômica e invalidação de linhas de cache entre núcleos.

Utilize um mutex quando:

• A contagem de fios é baixa (abaixo de 4 a 8) ou a contenção é pouco frequente.
• A seção crítica é longa e complexa (os loops sem trava tornam-se dispendiosos em relação à seção).
• A precisão é mais importante que a capacidade de processamento, e o algoritmo é mais simples com um bloqueio.
• A plataforma possui um sistema de bloqueio eficiente baseado em futex (Linux). pthread_mutex, Windows SRWLOCK)

Use sem trava quando:

• A contagem de fios é alta e a contenção é constante.
• As operações são curtas (a sobrecarga do loop CAS é pequena em relação à operação).
• O bloqueio é inaceitável (threads em tempo real, manipuladores de interrupção, manipuladores de sinal).
• Compondo com outras estruturas sem bloqueio onde um bloqueio introduziria dependências de ordem de bloqueio.

Use wait-free quando:

• Cada thread deve ser concluída dentro de um limite de tempo, independentemente das outras threads.
• Requisitos críticos de tempo real ou de segurança em que a inanição é inaceitável.
• O algoritmo pode ser estruturado para suportar a conclusão de um número limitado de passos por thread.

A disciplina da programação sem bloqueios não consiste em escolhê-la em todos os lugares, mas sim em escolhê-la precisamente onde suas propriedades — progresso não bloqueante, eliminação de impasses (deadlocks) e tolerância à preempção — correspondem aos requisitos reais do sistema.