Os contêineres concorrentes são estruturas de dados seguras para uso em ambientes multi-thread. Eles implementam o controle de concorrência, garantindo comportamento correto sob acesso simultâneo. Embora estratégias baseadas em travas (pessimistas) sejam comuns, o uso de algoritmos CAS (Compare-And-Swap) oferece uma abordagem sem bloqueio (otimista). Apesar de serem mais complexos de implementar e analisar, os contêineres sem bloqueio apresentam vantagens:

• Evitam Deadlocks: Como não há travas, não existe a possibilidade de deadlock.
• Reduzem Overhead: Eliminam custos associados à contenção, bloqueio e desbloqueio de threads.
• Maior Paralelismo: Não convertem código paralelo em serial, respeitando a Lei de Amdahl e proporcionando melhor escalabilidade com mais recursos computacionais.

Este artigo explora a construção manual de pilhas e filas concorrentes sem bloqueio usendo CAS em Java.

Definindo a Interface para uma Pilha Sem Bloqueio

Uma pilha é definida por suas operações básicas: inserir (push) e remover (pop).

public interface StackConcorrenteSemBloqueio<E> {
    boolean push(E e);
    E pop();
}

Implementação com Array

A implementação com array usa um índice atômico para rastrear o topo. O array tem capacidade fixa. O push coloca o elemento na posição topo + 1 e então tenta atualizar atomicamente o índice topo. Se a atualização CAS falhar (porque outro thread alterou o topo), a operação é repetida.

import java.util.concurrent.atomic.AtomicInteger;

public class PilhaArrayConcorrente<E> implements StackConcorrenteSemBloqueio<E> {
    private final Object[] elementos;
    private final int capacidade;
    private final AtomicInteger indiceTopo = new AtomicInteger(-1);

    public PilhaArrayConcorrente(int capacidade) {
        this.capacidade = capacidade;
        this.elementos = new Object[capacidade];
    }

    @Override
    public boolean push(E e) {
        while (true) {
            int topoAtual = indiceTopo.get();
            if (topoAtual + 1 >= capacidade) {
                return false;
            }
            // Tenta "reservar" a posição topoAtual+1
            if (indiceTopo.compareAndSet(topoAtual, topoAtual + 1)) {
                // Reserva bem-sucedida, agora podemos inserir com segurança
                elementos[topoAtual + 1] = e;
                return true;
            }
            // Se CAS falhou, repete o loop
        }
    }

    @Override
    public E pop() {
        while (true) {
            int topoAtual = indiceTopo.get();
            if (topoAtual == -1) {
                return null; // Pilha vazia
            }
            // Tenta "reservar" o elemento no topoAtual
            if (indiceTopo.compareAndSet(topoAtual, topoAtual - 1)) {
                // Reserva bem-sucedida, podemos ler o elemento com segurança
                E elemento = (E) elementos[topoAtual];
                elementos[topoAtual] = null; // Ajuda no GC
                return elemento;
            }
        }
    }
}

Nota: Nesta versão revisada, o push primeiro garante a reserva da posição atualizando o indiceTopo via CAS. Só então insere o valor no array. Isso evita um problema de visibilidade onde outro thread poderia ler uma posição parcialmente escrita.

Implementação com Lista Encadeada

Uma lista encadeada oferece flexibilidade ilimitada. O topo é uma referência atômica para o nó. A inserção (push) cria um novo nó, aponta seu proximo para o nó atual do topo, e tenta atualizar atomicamente a referência do topo para o novo nó.

import java.util.concurrent.atomic.AtomicReference;

public class PilhaListaConcorrente<E> implements StackConcorrenteSemBloqueio<E> {
    private static class No<E> {
        final E valor;
        No<E> proximo;

        No(E valor) {
            this.valor = valor;
        }
    }

    private final AtomicReference<No<E>> topo = new AtomicReference<>();

    @Override
    public boolean push(E e) {
        No<E> novoNo = new No<>(e);
        while (true) {
            No<E> topoAtual = topo.get();
            novoNo.proximo = topoAtual;
            if (topo.compareAndSet(topoAtual, novoNo)) {
                return true;
            }
        }
    }

    @Override
    public E pop() {
        while (true) {
            No<E> topoAtual = topo.get();
            if (topoAtual == null) {
                return null;
            }
            No<E> proximoNo = topoAtual.proximo;
            if (topo.compareAndSet(topoAtual, proximoNo)) {
                return topoAtual.valor;
            }
        }
    }
}

Construindo uma Fila Concorrente Sem Bloqueio

Uma fila (FIFO) exige dois ponteiros: cabecalho (head) e cauda (tail). A complexidade aumenta porque inserções e remoções ocorrem em extremidades diferentes, exigindo coordenação. Usaremos uma lista duplamente encadeada.

import java.util.concurrent.atomic.AtomicReference;

public class FilaConcorrenteSemBloqueio<E> {
    private static class No<E> {
        final E valor;
        volatile No<E> anterior;
        volatile No<E> proximo;

        No(E valor) {
            this.valor = valor;
        }
    }

    private final AtomicReference<No<E>> cabecalho = new AtomicReference<>(null);
    private final AtomicReference<No<E>> cauda = new AtomicReference<>(null);

    // ... métodos enqueue e dequeue ...
}

Operação de Enfileirar (Enqueue)

A inserção é complexa. Primeiro, lê-se a referência atual da cauda. Se a fila estiver vazia, tenta-se atualziar o cabecalho via CAS para o novo nó e, em seguida, atualiza-se a cauda de forma não-atômica (pois, nesse ponto, o thread tem exclusividade lógica). Se a fila não estiver vazia, o novo nó é ligado ao nó da cauda atual, e a cauda é atualizada via CAS para apontar para o novo nó.

    public boolean enqueue(E e) {
        No<E> novoNo = new No<>(e);
        while (true) {
            No<E> caudaAtual = cauda.get();
            if (caudaAtual == null) { // Fila vazia
                if (cabecalho.compareAndSet(null, novoNo)) {
                    cauda.set(novoNo); // Atualização não atômica é segura aqui
                    return true;
                }
            } else {
                novoNo.anterior = caudaAtual;
                if (cauda.compareAndSet(caudaAtual, novoNo)) {
                    caudaAtual.proximo = novoNo; // Atualização não atômica é segura aqui
                    return true;
                }
            }
        }
    }

Operação de Desenfileirar (Dequeue)

A remoção é mais delicada. Três cenários:

1. Fila Vazia: Retorna null.
2. Um único elemento: cabecalho e cauda apontam para o mesmo nó. É necessário atualizar ambos para null via CAS. A ordem das atualizações (primeiro a cauda, depois o cabeçalho com uma escrita simples) é crucial para a segurança.
3. Múltiplos elementos: Apenas a cauda é atualizada via CAS para apontar para o nó anterior. O nó removido é então desconectado.

    public E dequeue() {
        while (true) {
            No<E> caudaAtual = cauda.get();
            No<E> cabecalhoAtual = cabecalho.get();
            if (caudaAtual == null) {
                return null;
            } else if (cabecalhoAtual == caudaAtual) { // Um elemento
                if (cauda.compareAndSet(caudaAtual, null)) {
                    cabecalho.set(null); // Escrita simples após CAS bem-sucedido na cauda
                    return caudaAtual.valor;
                }
            } else { // Múltiplos elementos
                No<E> noAnterior = caudaAtual.anterior;
                if (cauda.compareAndSet(caudaAtual, noAnterior)) {
                    noAnterior.proximo = null; // Desconecta e ajuda no GC
                    return caudaAtual.valor;
                }
            }
        }
    }

Testes de desempenho comparando essas implementações sem bloqueio com contrapartidas baseadas em travas (como java.util.concurrent.LinkedBlockingQueue) mostram que, embora a implementação manual CAS possa ser mais rápida em certos cenários, as implementações otimizadas da JDK frequentemente oferecem desempenho comparável ou superior devido a otimizações profundas. A escolha entre bloqueio e sem bloqueio deve considerar fatores como complexidade de implementação, risco de deadlock e características específicas da carga de trabalho.