Locks, mutex e condições de corrida

Em 1965, o matemático holandês Edsger Dijkstra publicou em Eindhoven um manuscrito interno chamado Cooperating Sequential Processes. O texto, distribuído a alunos e colegas antes de virar publicação formal em 1968, definia o problema central de concorrência com clareza inédita: como múltiplos processos sequenciais podem cooperar acessando recursos compartilhados sem atropelar uns aos outros? Para responder, Dijkstra introduziu uma primitiva que ele chamou de P-V semaphore — duas operações atômicas que, combinadas, resolviam mutual exclusion. Essa primitiva, sob o nome moderno de mutex, é hoje a ferramenta mais comum (e mais mal-utilizada) de concorrência em sistemas reais.

O que torna mutex difícil não é a teoria — quatro linhas de código bastam para a versão básica. É o conjunto de questões derivadas: deadlock quando dois threads esperam um ao outro, starvation quando um thread nunca consegue o lock, livelock quando todos cedem e ninguém progride, e a categoria mais perniciosa de todas — a race condition silenciosa que produz resultados incorretos sem nunca quebrar o programa visivelmente. Race conditions são bugs que atravessam testes (que rodam em máquina menos carregada que produção), passam revisões de código (porque o defeito é semântico, não sintático), e aparecem só sob carga, no horário errado, no cliente errado.

Este conceito vai a fundo nesses problemas. Começa pela mecânica da race condition, segue para o catálogo de primitivas de sincronização (mutex, RWLock, semáforo, condition variable), passa pelos modos clássicos de falha (deadlock e seus parentes), e termina nas ferramentas modernas que detectam o que olhos humanos perdem (TSan, race detector do Go, Helgrind). O módulo todo se baseia em internalizar essas armadilhas — o conceito 09 trata atomics como alternativa de menor granularidade, e o conceito 10 explica por que memory ordering complica ainda mais o quadro.

Os modelos vistos antes (async/await, structured concurrency, CSP, actor) atacam o problema por evitação: minimizam estado compartilhado para que mutex raramente seja necessário. Mas mesmo nesses modelos, mutex aparece — em estruturas de dados compartilhadas, em pools de conexão, em caches concorrentes. Saber usar mutex bem é não-negociável para qualquer desenvolvedor sênior.

O problema — race condition em três passos

A race condition mais clássica em concorrência é também a mais simples. Considere duas threads incrementando um contador compartilhado:

// Pseudocódigo — cuidado: bug deliberado
contador = 0

// Thread A                      // Thread B
contador = contador + 1          contador = contador + 1
contador = contador + 1          contador = contador + 1
// ...mil vezes                   // ...mil vezes

Resultado esperado: 2.000. Resultado real: algo entre 1.000 e 2.000, variando a cada execução. Para entender por quê, lembre-se que contador = contador + 1 não é uma instrução atômica em hardware — é três:

1. LOAD contador para registrador
2. ADD 1 ao registrador
3. STORE registrador em contador

Como o scheduler pode preempted qualquer thread em qualquer instrução (lembrando do conceito 02), a interleaving das duas threads pode produzir sequências como:

Thread A: LOAD contador (=42)
Thread A: [preemption — scheduler troca para B]
Thread B: LOAD contador (=42)
Thread B: ADD 1   (=43)
Thread B: STORE contador (=43)
Thread A: ADD 1   (registrador ainda tem 42, vira 43)
Thread A: STORE contador (=43)   ← deveria ser 44!

Uma das atualizações foi perdida. O fenômeno é chamado lost update, e é o caso particular mais comum de race condition. A "race" é entre as duas threads chegando primeiro ao STORE — quem chegar último escreve por cima do outro. Se isso acontecesse só ocasionalmente, seria fácil detectar. O problema é que sob baixa carga (laboratório), a interleaving patológica raramente acontece — o teste passa. Em produção, sob centenas de threads em multi-core, ela acontece o tempo todo, e a soma final fica errada de forma silenciosa.

Race conditions tomam várias formas além do contador clássico: check-then-act (verificar se chave existe, depois usar — entre os dois passos outra thread modifica), read-modify-write (qualquer operação composta), iteração sem isolamento (modificar coleção enquanto outra thread itera). O denominador comum é o mesmo: um padrão de "ler estado, decidir, agir" sem garantia de atomicidade.

Mutex — exclusão mútua via lock

A solução mais direta é serializar o acesso ao recurso compartilhado: garantir que apenas uma thread por vez execute a seção crítica. Mutex (mutual exclusion) é a primitiva canônica. Sintaxe e mecânica idênticas em todas as linguagens — o que muda é só a aparência:

mutex = Mutex()
contador = 0

# em qualquer thread:
mutex.acquire()         # bloqueia até ninguém ter o lock
try:
    contador = contador + 1
finally:
    mutex.release()

acquire bloqueia a thread chamadora se o lock já estiver tomado. Quando a thread que tem o lock chamar release, uma das threads esperando é acordada e ganha o lock. A região entre acquire e release é a seção crítica — e a propriedade que mutex garante é que apenas uma thread está em qualquer seção crítica protegida pelo mesmo mutex em qualquer momento.

Implementação por baixo

Mutex moderno tem implementação engenhosa em duas camadas. No caso comum (sem contenção), a aquisição usa instruções atômicas de hardware — tipicamente LOCK CMPXCHG em x86 ou LDXR/STXR em ARM — para mudar uma flag em memória sem syscall. Custa dezenas de nanossegundos. Quando há contenção e a thread precisa esperar, o mutex chama o kernel via futex (em Linux) — uma syscall que coloca a thread em sleep até o lock liberar. Isso custa microssegundos mas evita CPU spinning vazio.

Em Go, sync.Mutex é particularmente bem desenhado: faz spin curto antes de chamar futex, dando boa performance em contenção baixa sem desperdiçar CPU em contenção alta. Em C#, lock { } compila para Monitor.Enter/ Monitor.Exit, que tem otimização de "thin lock" similar — JIT inlineia o caso comum em código nativo. Em Python, o GIL elimina muitas necessidades de mutex em código Python puro, mas threading.Lock existe para coordenar acesso a estruturas onde a atomicidade do GIL não basta (operações compostas).

Reentrância — o lock que pode ser adquirido pela mesma thread

Mutex simples não permite a mesma thread adquirir o lock duas vezes — vai resultar em deadlock consigo mesma. Mutex reentrant (também chamado de recursive) permite, contando quantas aquisições aninhadas você fez e exigindo número equivalente de releases. Java synchronized é reentrant por design. Python threading.RLock é a versão reentrant. C# lock usa Monitor que é reentrant. Go sync.Mutex não é reentrant — decisão deliberada do design para evitar abstrações que escondem complexidade.

RWMutex — múltiplos leitores, um escritor

Um mutex regular trata leitura e escrita igualmente: ambos adquirem o mesmo lock, ambos serializam totalmente. Mas muitas estruturas de dados são lidas com frequência muito maior que escritas — caches, mapas de configuração, hash tables read-mostly. Para esses casos, reader-writer lock permite múltiplos leitores simultâneos, ou um escritor exclusivo (não ambos).

Em todos os principais runtimes existem como primitiva: Go sync.RWMutex com RLock/RUnlock e Lock/Unlock; C# ReaderWriterLockSlim com EnterReadLock/EnterWriteLock; Python threading.Condition compondo manualmente, ou bibliotecas extras. Java ReentrantReadWriteLock.

RWMutex parece sempre melhor que mutex regular, mas tem armadilhas. Primeira: a contabilidade interna (counter de leitores, fila de escritores) custa mais que mutex simples, então em workload com poucas leituras concorrentes, RWMutex pode ser mais lento. Segunda: starvation de escritores é possível em algumas implementações — se leitores chegam continuamente, escritor pode esperar para sempre. Algumas implementações priorizam escritores (writer-preferring) ou fazem lock ordering para evitar starvation; outras não. Terceira: upgrade de read lock para write lock não é suportado seguramente — você precisa liberar o read e adquirir o write, com janela onde o estado pode mudar.

Semáforos — exclusão para N usuários

Semáforo é generalização do mutex de Dijkstra. Em vez de "binário" (livre ou ocupado), é um contador. P (wait, ou acquire) decrementa; bloqueia se for zero. V (signal, ou release) incrementa, possivelmente acordando alguém. Semáforo binário (counter máximo de 1) é equivalente a mutex; semáforo contado é útil para limitar concorrência: "no máximo N threads simultâneas consultando esta API externa", "no máximo M conexões abertas".

# Python — semáforo limitando concorrência
import threading
import requests

# Permite só 5 requisições HTTP simultâneas
sem = threading.Semaphore(5)

def buscar(url):
    with sem:           # acquire/release automático
        return requests.get(url)

# Lança 100 threads — só 5 ficam executando ao mesmo tempo.
threads = [threading.Thread(target=buscar, args=(u,)) for u in urls]
for t in threads: t.start()
for t in threads: t.join()

Semáforos estão presentes em virtualmente toda linguagem com threads: C# SemaphoreSlim, Go via channel buffered (idiomático: sem := make(chan struct{}, N)), Java Semaphore, Python threading.Semaphore. Em sistemas async, há versões que cooperam com event loop: asyncio.Semaphore em Python, SemaphoreSlim.WaitAsync em C#.

Condition variables — esperando por uma condição lógica

Mutex resolve "garantir que apenas uma thread acesse este recurso por vez". Mas há um padrão diferente: "esperar até que a estrutura compartilhada esteja em determinado estado". Exemplo clássico: produtor-consumidor com fila bounded — produtor espera quando fila está cheia; consumidor espera quando fila está vazia. Mutex sozinho não resolve elegantemente; condition variable, sim.

O conceito vem de Hoare e Hansen, anos 1970, em monitors — estruturas que combinam dados, mutex e condições. Uma condition variable é sempre associada a um mutex, e oferece três operações: wait (libera o mutex e dorme até ser sinalizada; ao acordar, reaquire o mutex); signal ou notify (acorda uma thread esperando); broadcast ou notify_all (acorda todas).

# Python — produtor-consumidor com bounded queue
from collections import deque
import threading

class FilaBounded:
    def __init__(self, capacidade):
        self.cap = capacidade
        self.fila = deque()
        self.mutex = threading.Lock()
        self.nao_cheia = threading.Condition(self.mutex)
        self.nao_vazia = threading.Condition(self.mutex)

    def colocar(self, item):
        with self.nao_cheia:
            while len(self.fila) == self.cap:
                self.nao_cheia.wait()       # libera mutex e dorme
            self.fila.append(item)
            self.nao_vazia.notify()         # acorda um consumidor

    def tirar(self):
        with self.nao_vazia:
            while len(self.fila) == 0:
                self.nao_vazia.wait()
            item = self.fila.popleft()
            self.nao_cheia.notify()         # acorda um produtor
            return item

Note duas decisões importantes. Primeira: o while ao redor do wait. É essencial — você precisa reverificar a condição depois de acordar, porque pode ter sido um spurious wakeup (acordada sem motivo) ou outra thread já ter consumido o estado favorável. if em vez de while é bug clássico, sutil em laboratório, desastroso em produção. Segunda: o uso de duas conditions separadas (nao_cheia e nao_vazia) evita acordar threads errado — produtor quer saber quando há espaço, consumidor quer saber quando há item.

Em sistemas de fluxo bem-desenhados, condition variables são raramente necessárias — channels (CSP) e queues thread-safe já encapsulam o padrão produtor-consumidor. Mas para implementar uma estrutura de dados concorrente do zero, cv é a primitiva certa.

Deadlock — as quatro condições de Coffman

Em 1971, Edward Coffman, Melvin Elphick e Arie Shoshani publicaram System Deadlocks, que enumera quatro condições necessárias e suficientes para deadlock acontecer. Decorar isso evita 80% dos deadlocks em prática:

1. Mutual exclusion: pelo menos um recurso precisa ser adquirido em modo exclusivo. (Mutex satisfaz sempre.)
2. Hold and wait: thread mantém um recurso e espera por outro.
3. No preemption: o sistema não força a thread a liberar o recurso — ela libera voluntariamente.
4. Circular wait: existe um ciclo de threads onde cada uma espera por recurso da próxima.

Quebre qualquer uma das quatro e deadlock fica impossível. O "dining philosophers" de Dijkstra (1965) é a ilustração canônica:

// Cinco filósofos sentados em mesa redonda; cinco garfos.
// Cada filósofo precisa dos garfos esquerdo E direito para comer.

void filosofo(int i) {
    for (;;) {
        pensar();
        garfo[i].lock();             // pega esquerdo
        garfo[(i+1) % 5].lock();     // pega direito
        comer();
        garfo[(i+1) % 5].unlock();
        garfo[i].unlock();
    }
}
// Cenário deadlock: todos pegam o esquerdo simultaneamente.
// Todos esperam o direito que está com o vizinho.

Soluções clássicas:

• Lock ordering global. Cada lock recebe um id numérico. Threads sempre adquirem locks em ordem crescente. No exemplo, em vez de "pegue esquerdo então direito", "pegue o de menor id então o de maior id". O quinto filósofo (que teria esquerdo=4, direito=0) inverte a ordem, quebra o ciclo.
• Try-lock com retry. Em vez de bloquear, tente adquirir; se falhar, libere o que tem e tente de novo. Quebra "no preemption". Custa CPU em retry e pode levar a livelock se mal feito.
• Lock único de granularidade maior. Em vez de cinco garfos, um lock para "a mesa inteira". Elimina o problema mas serializa tudo — mata throughput.
• Resource hierarchy. Particione recursos em categorias com ordem fixa entre categorias. Dentro de cada categoria, ordem livre.

Detectando deadlock em produção

Java tem jstack que mostra threads bloqueadas com indicação de qual lock cada uma espera, e detecta ciclos automaticamente. Go tem detector de deadlock embutido — se todas as goroutines do programa estão bloqueadas, runtime crasha com mensagem. C# tem WinDbg ou Visual Studio's "Parallel Stacks" para inspeção. Em produção real, tooling de observabilidade (Datadog, OpenTelemetry) com tracing de mutex acquisition expõe contenção alta antes que vire deadlock — o sintoma precoce.

Livelock e starvation — falhas mais sutis

Deadlock para o sistema visivelmente. Livelock e starvation são mais sutis — o sistema parece estar fazendo trabalho, mas não progride.

Livelock

Threads tomam ações continuamente, mas nenhuma faz progresso útil. Exemplo: dois threads tentando passar por uma porta estreita. Cada um cede o passo para o outro educadamente; os dois cedem; nenhum passa; repetem para sempre. Em sincronização, acontece com try-lock + backoff mal calibrado: threads tentam adquirir, falham, esperam, tentam de novo, falham de novo. Solução: backoff aleatório (jitter) para quebrar a simetria, ou eventualmente alguma forma de prioridade.

Starvation

Uma thread nunca consegue progredir porque outras estão sempre na frente. Causa típica: scheduler unfair, ou política de lock que prefere alguns threads sobre outros (RWLock que sempre prefere readers, em workload com leituras constantes, starva writers). Tooling: profilers que mostram tempo de espera por thread (perf, Java Mission Control) revelam threads que estão sempre na fila e nunca executando.

Race detectors — encontrando o que olhos perdem

Race conditions são notoriamente difíceis de detectar manualmente. Por sorte, ferramental moderno é poderoso. Os principais:

ThreadSanitizer (TSan)

Implementado em LLVM/Clang e GCC, TSan instrumenta cada acesso de memória em tempo de compilação. Em runtime, mantém grafo de happens-before e detecta acessos concorrentes a mesma variável sem sincronização. Compila com -fsanitize=thread e roda; quando encontra race, imprime relatório com stack trace de ambos os acessos. Custo: programa fica 5–15× mais lento; uso de memória 5–10× maior. Não é para produção; é para CI ou bateria de testes dedicada.

Go race detector

Mesmo conceito, integrado ao runtime. go run -race, go test -race, go build -race. É rodado em CI por padrão na maioria dos projetos Go sérios. Encontra a esmagadora maioria das races antes do código chegar a produção. Foi um dos motivos pelos quais Go ganhou reputação rápida de "linguagem boa para concorrência" — não por ter mais ferramentas que C, mas por integrá-las de forma que ninguém esquece.

Helgrind / DRD (Valgrind)

Análise dinâmica via instrumentação binária — não precisa recompilar. Mais lenta que TSan, mas funciona em código pré-compilado. Adequada para investigar bugs em libraries de terceiros sem fonte.

C# / Java analyzers estáticos

Microsoft.CodeAnalysis.NetAnalyzers e Roslynator em C#, SpotBugs e FindBugs em Java, fazem análise estática de patterns suspeitos: campo mutável acessado sem lock, lock adquirido em ordem inconsistente, double-checked locking sem volatile. Não pegam tudo, mas pegam armadilhas óbvias antes do código rodar.

O mesmo padrão nas três linguagens

Para concretizar, considere uma estrutura comum: cache thread-safe com hit count. Múltiplas threads leem; menos threads escrevem. Vamos ver a implementação canônica em cada linguagem.

using System.Collections.Generic;
using System.Threading;

public class CacheConcorrente<K, V> {
    private readonly Dictionary<K, V> mapa = new();
    private readonly ReaderWriterLockSlim lockao = new();

    public bool TryGet(K chave, out V valor) {
        lockao.EnterReadLock();
        try {
            return mapa.TryGetValue(chave, out valor);
        } finally {
            lockao.ExitReadLock();
        }
    }

    public void Set(K chave, V valor) {
        lockao.EnterWriteLock();
        try {
            mapa[chave] = valor;
        } finally {
            lockao.ExitWriteLock();
        }
    }
}

// Para uso em produção, prefira ConcurrentDictionary do .NET, que
// usa lock-free para a maior parte das operações.

import threading
from typing import TypeVar, Generic

K = TypeVar('K'); V = TypeVar('V')

class CacheConcorrente(Generic[K, V]):
    def __init__(self):
        self._mapa: dict[K, V] = {}
        self._lock = threading.RLock()

    def get(self, chave: K) -> V | None:
        with self._lock:
            return self._mapa.get(chave)

    def set(self, chave: K, valor: V) -> None:
        with self._lock:
            self._mapa[chave] = valor

    def get_or_compute(self, chave: K, computar) -> V:
        with self._lock:
            if chave in self._mapa:
                return self._mapa[chave]
            valor = computar()       # cuidado: dentro do lock
            self._mapa[chave] = valor
            return valor

package cache

import "sync"

type Cache[K comparable, V any] struct {
    mu   sync.RWMutex
    mapa map[K]V
}

func New[K comparable, V any]() *Cache[K, V] {
    return &Cache[K, V]{mapa: make(map[K]V)}
}

func (c *Cache[K, V]) Get(chave K) (V, bool) {
    c.mu.RLock()
    defer c.mu.RUnlock()
    v, ok := c.mapa[chave]
    return v, ok
}

func (c *Cache[K, V]) Set(chave K, valor V) {
    c.mu.Lock()
    defer c.mu.Unlock()
    c.mapa[chave] = valor
}

// Em Go 1.9+, sync.Map também é opção — otimizado para padrões
// específicos (escrito raramente, lido muito).

Anti-patterns clássicos em uso de mutex

Mutex é simples na superfície e fácil de errar de várias formas. Algumas armadilhas merecem atenção explícita.

Granularidade errada — too coarse ou too fine

Lock que protege estrutura inteira quando só pequena parte é acessada (coarse) → contenção alta. Lock por campo, exigindo coordenação entre múltiplos locks (fine) → complexidade, risco de deadlock. Equilíbrio: lock por estrutura lógica coerente. Em sistemas críticos, lock striping divide uma estrutura grande em N segmentos com locks independentes — ConcurrentHashMap de Java fez isso historicamente.

Holding locks durante I/O ou computação cara

Já mencionado, vale repetir: lock só para manipular estrutura em memória. I/O, computação pesada, chamada externa — fora do lock.

Lock convoy

Padrão patológico: múltiplas threads competem pelo mesmo lock em hot path. O lock vira gargalo serial, e adicionar mais threads piora performance porque elas só esperam. Sintoma: CPU baixa, latência alta. Solução: identifique o lock, reduza granularidade, ou substitua por estrutura lock-free ou canal.

Double-checked locking sem volatile/memory barrier

Padrão de "verifique sem lock, se não tiver, adquira lock e verifique de novo, então crie". Aparece em singletons lazy-initialized. Sem garantia de visibilidade entre threads (memory model — conceito 10), o segundo verificador pode ver objeto parcialmente construído. Em Java é o famoso bug do DCL pré-1.5; em C# precisa volatile ou Lazy<T>; em Go, use sync.Once.

Forgetting to release

Lock adquirido sem liberação em alguma branch (exceção, return antecipado). Em qualquer linguagem, prefira a forma com cleanup automático: using/lock em C#, defer mu.Unlock() em Go, with em Python. Em Java, try-finally manual com ReentrantLock, ou bloco synchronized (que libera automaticamente).

Quando usar mutex — e quando evitar

Mutex é apropriado quando: o estado compartilhado é pequeno; a seção crítica é curta (microssegundos); contenção é moderada; alternativas (channels, atomics, immutability) não cabem na semântica do problema. Estrutura de dados compartilhada protegida por mutex é solução clássica e respeitável; não há vergonha nisso.

Mutex é problemático quando: a seção crítica é longa (vai serializar throughput); contenção é alta (vira gargalo); múltiplos locks precisam ser coordenados (deadlock spectacle); o estado é simples o bastante para atomic (próximo conceito). Antes de adicionar mutex, pergunte: posso evitar compartilhamento via canal? Posso usar estrutura imutável com swap atômico? Posso usar apenas atomic counter?

A arquitetura mais robusta combina técnicas: actors ou goroutines isolam estado por padrão; mutex protege as poucas estruturas que precisam ser compartilhadas; atomics cobrem counters e flags simples. Quem usa apenas mutex em sistema grande tipicamente tem mais bugs de concorrência do que quem escolhe a primitiva certa para cada caso.

Como praticar

1. Reproduza um lost update. Em Python (com threading) ou Go: incremente um contador em 100 threads, 1000 vezes cada, sem lock. Compare o resultado com o esperado. Em Go, use go test -race e veja a saída. Em Python, observe que sob GIL o problema pode não aparecer com operações simples — mas operações compostas (contador += 1) ainda fazem race.
2. Construa uma fila bounded com condition variables. Não use a primitiva pronta da linguagem; reimplemente com mutex + duas conditions. Teste com 4 produtores e 4 consumidores em paralelo, milhares de itens, capacidade baixa (forçar bloqueio). Confirme que ordem é preservada e nenhum item se perde.
3. Provoque um deadlock e diagnostique. Crie duas funções, cada uma adquirindo dois locks em ordens opostas. Rode até travar. Em Java, dispare jstack <pid> e observe a saída de "Found Java-level deadlock". Em Go, deixe rodar até o detector embutido crashar com diagnóstico. Aplique lock ordering global e confirme que o problema some.