Concorrência: Volatilidade e Atomicidade — Linearização em Java: Volatile, CAS e Lock
Recentemente eu me deparei com esse exemplo que demonstra um dos conceitos, que talvez, ainda seja de muita confusão entre os iniciantes:
Esse código, apesar de executar uma operação de incrementar um valor de uma variável em paralelo, não funciona como o esperado, mesmo com a presença do keyword volatile, mas por qual motivo?
O motivo é mais simples do que parece: tornar uma variável volátil aumenta sua visibilidade, mas não garante atomicidade em operações que vão além de leitura e/ou escrita.
Isso tem muito a ver com a forma que a memória da máquina virtual funciona, e em como o compilador transforma o código fonte em bytecode, e isso que vai nos mostrar o motivo da volatile não nos ajudar nesse cenário.
O que é Bytecode?
Bytecode se refere a linguagem binária: é uma representação não amigável a humanos de qualquer informação. A JVM tem sua própria linguagem binária, utilizada para compilação, interpretação e execução das classes Java.
A linguagem binária traz várias vantagens, ela produz um arquivo final pequeno (bem menor que os “binários nativos”), que contém mais informações que o código-fonte, é mais rápido de ser interpretado e recompilado (utilizando JIT ou AOT), é modificável (pode ser instrumentado antes de ser carregado, ou após ser carregado), é recarregável e poder ser dinamicamente carregado (por meio de ClassLoaders), e é facilmente manipulável.
Inclusive, por muito tempo os compiladores da SDK do Android utilizavam um compilador que recompilava o código binário da JVM (conhecido como JVM Bytecode) em um código binário chamado DEX (Para o interpretador Dexter).
Onde isso entra na questão?
Aproximadamente em Maio de 2016, eu fiz meu primeiro commit de uma estrutura AST, que futuramente viria ser o intermédio para um compilador tanto para JVM Bytecode quanto um transpilador Java, poucos anos depois eu fui capaz de implementar ambos com suporte a todos recursos do Java 8.
O propósito inicial era implementar mecanismo de Mixin no Java por meio de geração de código, o que no futuro veio a ser bem feito por esse projeto, ao mesmo tempo que caminhei com o meu projeto para criar um framework para EDD, que não só suporta Mixins (por meio do que chamo de Extensões), como gera implementação automática das classes de eventos, esse projeto também foi utilizado para a criação de um sistema de geração de Proxy super performático.
Na caminhada para essa conquista, eu estudei grande parte da especificação da máquina virtual Java, principalmente o set de instruções, e quando eu vi esse comportamento enquanto lia a documentação do Kotlin Coroutines sobre estado compartilhado, me veio na mente o questionamento, “a nível de bytecode”, como uma operação de incremento funcionava, e por qual motivo resultaria nesse comportamento.
Para exploração inicial, reescrevi esse caso totalmente em Java, utilizando Threads:
Esse código tem o mesmo efeito que o escrito em Kotlin, agora vamos ao ponto importante aqui: a operação de incrementar um variável é dividida nos seguintes passos:
- Carregar o valor da variável na stack
- Carregar o valor a ser adicionado na stack (nesse caso 1)
- Somar os valores
- Armazenar o resultado de volta na variável
Para isso, são necessárias 4 instruções, isso pois, a máquina virtual Java é stack-based (enquanto a Dalvik, por exemplo, é register-based). No entanto, o mesmo comportamento pode ocorrer em uma máquina virtual baseada em registros, apenas alguns detalhes irão mudar.
No modelo baseado em pilhas (stack), a implementação precisa carregar os valores em um região da memória chamada stack, e as instruções trabalham valores removidos da stack.
Vejamos abaixo uma representação dos dois primeiros valores sendo armazenados na stack, primeiro o valor do campo count depois a constante 1, que é o valor que será somado:
Agora, duas outras instruções vão entrar em cena para operar esse valor:
Como podemos notar, aqui entrou em ação a instrução iadd e putstatic (para campos estáticos, porém para campos regulares quem entra em ação é o putfield). A instrução iadd pega dois valores da stack, executa uma operação de soma, e armazena o resultado na stack. Enquando o putstatic pega apenas um valor da stack e armazena no campo (que fica armazenado na heap). Lembrando que sempre que uma instrução pega um valor da stack, esse valor é removido da mesma.
Ainda não entendi! Como isso afeta os campos voláteis?
Esses campos funcionam da mesma forma que qualquer outro campo, porém, os campos marcados como volatile, se comportam diferente com relação a visibilidade entre diferentes threads.
O que o volatile faz é garantir que qualquer escrita para um campo volátil estará visível para qualquer thread que fizer a leitura, mas isso não garante a consistência das operações sobre este valor (mas em alguns casos, pode ajudar a reduzir esses problemas).
Voltando para o assunto principal, esse comportamento afetam os campos, sejam eles voláteis, ou não, de uma forma bem óbvia: duas ou mais threads podem carregar ao mesmo tempo o mesmo campo, antes mesmo que esses valores sejam atualizados.
Isso quer dizer que, por exemplo, digamos que o valor atual do campo count é 20, e que agora duas Threads vão incrementar esse valor, digamos que serão a Thread 1 e a Thread 2.
No cenário ideal, primeiro a Thread 1 carrega o valor, incrementa e salva, e depois disso, a Thread 2 pode então carregar o valor, incrementar e salvar. Porém, sem as medidas corretas de sincronização, utilizando apenas volatile, esse comportamento não pode ser garantido.
Então digamos que a Thread 1 carregou o valor ao mesmo tempo que a Thread 2, vejamos como, teoricamente, estaria a stack dessas duas threads:
Provavelmente você já captou o problema logo de cara, mas vamos continuar.
Nota que, ambas Threads estão trabalhando com o valor 20, que é o valor que está armazenado no nosso campo, mas o que acontecerá depois que incrementarmos 1 a esses valores na stack?
Bom, a conta está correta, o problema acontece quando a instrução putstatic ou putfield entrar em ação, para gravar esse valor no campo, já que ambas vão escrever exatamente o mesmo valor, que, no entanto, é o resultado de duas somas, com apenas uma efetivada. Sempre a última Thread que escrever irá ter seu valor “efetivado” (uma irá sobrescrever a outra), e iremos perder o valor de uma das threads, já que houve “concorrência” na operação como um todo.
É basicamente isso que explica o motivo do código — que vimos lá no começo — nos dar o resultado incorreto, apesar de visualmente aparentar estar certo.
Isso não é uma particularidade apenas do Java
Apesar de parecer ser uma particularidade apenas do Java, isso não é. Esse comportamento depende muito do modelo de memória implementado, e ter uma máquina virtual baseada em registros não irá automaticamente resolver esse problema, já que, nesse caso, uma operação de incrementar um valor, se expande para três operações: ler, modificar, escrever. Uma máquina baseada em registros terá a vantagem de poder modificar os valores direto no registro, mas ainda pode ocorrer de duas threads lerem “ao mesmo tempo”.
Como resolver?
A nível de instrução, poderia sim ser implementada uma instrução capaz de implementar uma soma “atômica”, porém isso seria a solução para um único caso, em um contexto bem especifico, não escalável e provavelmente com implicações, tanto de compatibilidade quanto de desempenho, não desejadas.
Já a nível de linguagem, para contornar esse problema, normalmente é fornecido, em suas bibliotecas padrões, estruturas de dados que implementam atomicidade em diferentes tipos. O Java, por exemplo, permite isso por meio de classes especializadas, como AtomicInteger, AtomicLong, AtomicReference.
Essas implementações normalmente já fornecem operações de incremento, compare-and-swap e operações de update com retry.
Importante notar que, no Java, as implementações do pacote java.util.concurrent.atomic sempre utilizam compare-and-swap para fazer sua operação, devido a isso, elas são muito mais performáticas do que a utilização de Lock ou Mutex (ou outras alternativas, como Semaphore).
O que acontece nas implementações que utilizam compare-and-swap, é que, elas carregam o valor da memória, executam a operação, e depois compara se o valor que está na memória no momento de fazer write é exatamente o mesmo valor que foi lido lá no começo da operação, se o valor for diferente (ou seja, outra thread atualizou enquanto o valor era operado), ela tenta fazer a operação novamente, esse retry pode acontecer até um ponto onde todas operações atômicas já foram completadas e sobrou apenas uma, ai não resta nenhuma thread para interferir no valor.
No Java, isso é aplicável também as coleções concorrentes, como ConcurrentHashMap, que também é implementado utilizando compare-and-swap.
Veja abaixo como ficaria o código utilizando AtomicInteger:
Compare-and-Swap vs Lock
Como já foi levantado, no Java, normalmente é utilizado compare-and-swap para se alcançar atomicidade, no entanto, existe uma outra forma muito comum de implementar linearização (termo técnico para atomicidade): utilizando Lock.
No Java, normalmente utilizamos a classe ReentrantLock para implementar o mecanismo de lock. Esse tipo permite que a mesma Thread adquira o lock quantas vezes ela quiser, e, enquanto uma Thread estiver segurando esse lock, qualquer outra que tentar adquirir irá entrar em estado de WAIT, ou seja, ficará esperando o lock ser liberado para continuar seu trabalho.
Vantagens e desvantagens
Em linhas gerais, um sistema de lock (ou mutex) trabalha com o mecanismo completo de locking que depende de uma implementação totalmente especial e bem construída, podendo utilizar queues FIFO para implementar o mecanismo.
Já no caso do compare-and-swap, tende a ser um algoritmo muito mais simples, que se baseia em mecanismo de retry e comparação, já que ele repete a operação sempre que percebe que o valor atual de um campo mudou antes de completar a operação, e esse valor é diferente do que ele apurou no começo. Apesar de depender de alguns mecanismos especiais da máquina virtual Java para funcionar corretamente (como garantir que uma operação de escrita não vá ocorrer no exato momento após a apuração final do valor), essa técnica tende a ter uma implementação muito mais fácil de otimizar.
Ou seja, normalmente o mecanismo de locking tende a ser menos intensivo em questão de recursos de CPU (por não utilizar loops infinitos, e sim “suspender” threads, que faz com que elas não consumam recursos), mas costuma também ser menos performático em diferentes casos.
Já o compare-and-swap é extremamente performático, mas perde em outros cenários, como, por exemplo, em estruturas mais complexas ou quando uma operação de update desencadeia uma outra operação de update no mesmo campo, já que isso faz com que, toda vez que o retry ocorra, outra operação escreva no campo, e ai ao tentar de novo, desencadeia a mesma operação, resultando em um loop infinito (por isso a documentação diz explicitamente para a função de update ser side-effect free).
Por ser extremamente performático, o compare-and-swap é utilizado em coleções, como mapas e listas, mas não é tão simples de implementar em todas estruturas, diferente do lock, que é muito mais “direto ao ponto”: quero exclusividade desse recurso durante esse tempo/execução nesse contexto (thread).
No Java, os Locks tem um comportamento quase igual ao synchronized , com a diferença que o Lock você pode adquirir em um método, e liberar em outro, já com o synchronized, você adquire e libera no mesmo método.
No entanto, com as diversas otimizações que o ecossistema do Java é capaz de fazer, principalmente nessa base já muito bem consolidada, acaba que no final, a diferença de latência não costuma ser extremamente grande para isso se tornar uma decisão tão difícil.
Lock vs Mutex
A diferença varia muito de linguagem para linguagem, por exemplo, em Kotlin um Mutex funciona quase da mesma forma que um Lock (mas diferente do ReentrantLock, você não consegue adquirir mais de uma vez, tentar isso resultaria em “dead lock”), porém, é utilizado no contexto de Coroutines. Já no Rust, Mutex é uma estrutura que contém um Lock para um objeto, que está armazenado dentro desse mesmo Mutex, com a vantagem de não precisar de unlock (devido ao trait Drop).
Geralmente, Mutex é definido por ser uma estrutura que obtém o lock para um objeto e pode ser system-wide (utilizado entre aplicações para um mesmo recurso), enquanto o Lock normalmente é usado dentro de um contexto especifico e não compartilhado entre aplicações.
Semaphore, Spin Lock, StampedLock
Todos esses são outros mecanismos utilizados para alcançar a tão desejada linearização, em meio a tanta concorrência. Cada um com uma abordagem diferente e com propósitos diferentes (você pode ler mais aqui).
Wait e notify
Em Java também temos outros mecanismos, como o wait e notify, que são recursos muito antigos, que existem desde as primeiras versões e eram muito utilizados para trabalhar com concorrência, ao mesmo tempo que também eram a fonte de muitos deadlocks e bugs indesejados (por introduzirem pouca segurança pela forma que funcionam), em um momento onde tínhamos poucas ferramentas para detecção de deadlocks (se é que tínhamos alguma).
