O que é programação lock-free e CAS? Explique o problema ABA e quando usá-lo.

Question

IT Interview Practice · Accepted Answer

**Programação lock-free coordena threads sem mutexes, usando loops atômicos de compare-and-swap (CAS) para que ao menos uma thread sempre progrida mesmo se outras travarem.** Nenhuma thread pode ser bloqueada por outra segurando um lock.

## CAS

**Compare-and-swap** define atomicamente uma posição para um novo valor apenas se ela ainda contém o valor antigo esperado; caso contrário falha e você retenta. É a primitiva por trás de stacks, filas e contadores lock-free.

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # atomic, indivisible
  else: return false
```

```java
// Lock-free increment via CAS retry loop
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // retry if someone else won
```

## O problema ABA

O CAS só verifica que o valor ainda é o esperado — não que ele nunca mudou. Se ele foi de A → B → A entre sua leitura e o CAS, o CAS tem sucesso mas o mundo se moveu por baixo de você (ex.: um nó liberado e reutilizado).

```text
Thread 1: read A ............... CAS(A→X) succeeds ✗ (but list changed!)
Thread 2:      pop A, push B, push A again
```

**Correção**: emparelhe o ponteiro com um contador de versão (`AtomicStampedReference`, tagged pointers) para que A-com-tag-1 ≠ A-com-tag-2, ou use hazard pointers / epoch reclamation para segurança de memória.

## Quando usar

- **Use** para estado compartilhado quente e de granularidade fina (contadores, filas single-producer) onde a contenção de locks domina, ou onde uma thread nunca pode bloquear (tempo real, signal handlers).
- **Evite** como padrão: é difícil de acertar, fácil de introduzir bugs de ABA e de ordenação de memória, e frequentemente não é mais rápido que um bom mutex sob baixa contenção.

## Por que isso importa

Estruturas lock-free dão garantias de progresso e evitam deadlock e inversão de prioridade, mas a barra de correção é alta. Conhecer CAS, ABA e o problema de reclamação sinaliza que você sabe raciocinar no nível do modelo de memória — e, crucialmente, saber quando *não* recorrer a ele.

CAS

O problema ABA

Quando usar

Por que isso importa

Perguntas relacionadas