Informações iniciais sobre SMPs para Android

As versões 3.0 e posteriores da plataforma Android são otimizadas para compatibilidade com arquiteturas de multiprocessador. Este documento apresenta problemas que podem surgir ao escrever códigos com várias linhas de execução para sistemas multiprocessadores simétricos em C, C++ e na linguagem de programação Java, chamada simplesmente de “Java” a partir de agora por questão de brevidade. Trata-se de uma introdução para desenvolvedores de apps Android, não uma discussão completa sobre o assunto.

Introdução

SMP é um acrônimo em inglês para “Multiprocessador simétrico”. Ele descreve um design em que dois ou mais núcleos de CPU idênticos compartilham o acesso à memória principal. Até alguns anos atrás, todos os dispositivos Android tinham processador único (UP, na sigla em inglês).

A maioria dos dispositivos Android (se não todos) sempre teve várias CPUs, mas apenas uma delas era usada para executar aplicativos, enquanto as outras gerenciavam várias partes do hardware do dispositivo (por exemplo, o rádio). As CPUs podiam ter arquiteturas diferentes, e os programas executados nelas não poderiam usar a memória principal para se comunicar entre si.

A maioria dos dispositivos Android vendida atualmente é baseada em designs de SMP, o que deixa as coisas um pouco mais complicadas para os desenvolvedores de software. As disputas em um programa com várias linhas de execução podem não causar problemas visíveis em um processador único, mas elas podem falhar regularmente quando duas ou mais linhas estão em execução simultaneamente em diferentes núcleos. Além disso, o código pode ser mais ou menos propenso a falhas quando executado em diferentes arquiteturas de processador ou mesmo em diferentes implementações da mesma arquitetura. O código que foi completamente testado na x86 pode apresentar muitas falhas na ARM. Ele pode começar a falhar quando recompilado com um compilador mais moderno.

O restante deste documento explicará os motivos e informará o que você precisa fazer para garantir que seu código tenha o comportamento adequado.

Modelos de consistência de memória: por que os SMPs são um pouco diferentes

Esta é uma visão geral rápida e superficial sobre um assunto complexo. Ainda que algumas áreas possam estar incompletas, não há informações erradas ou enganosas. Como você poderá ver na próxima seção, os detalhes aqui não costumam ser importantes.

Consulte Leia mais no final do documento para ver indicações de informações mais completas sobre o assunto.

Os modelos de consistência de memória, ou apenas “modelos de memória”, descrevem as garantias que a linguagem de programação ou a arquitetura de hardware faz sobre os acessos à memória. Por exemplo, se você escrever um valor no endereço A e depois um valor no endereço B, o modelo poderá garantir que cada núcleo da CPU veja essas gravações acontecerem nessa ordem.

O modelo com o qual a maioria dos programadores está acostumada é a consistência sequencial, que é descrita desta forma (Adve & Gharachorloo):

  • Todas as operações de memória parecem ser executadas uma de cada vez.
  • Todas as operações em uma única linha de execução parecem ser executadas na ordem descrita pelo programa desse processador.

Vamos supor temporariamente que temos um compilador ou interpretador muito simples que não introduz surpresas: ele traduz atribuições no código-fonte para carregar e armazenar instruções exatamente na ordem correspondente, uma instrução por acesso. Também vamos supor, para simplificar, que cada linha é executada no próprio processador.

Se você observar um pouco do código e perceber que ele faz algumas leituras e gravações da memória, você saberá que, em uma arquitetura de CPU com consistência sequencial, o código fará essas leituras e gravações na ordem esperada. É possível que a CPU esteja, na verdade, reordenando as instruções e atrasando as leituras e gravações, mas não há como o código em execução no dispositivo dizer que a CPU está fazendo outra coisa além de executar as instruções de maneira direta. Ignoraremos a E/S do driver de dispositivo mapeado na memória.

Para ilustrar esses pontos, é útil considerar pequenos snippets de código, comumente chamados de parâmetros.

Veja a seguir um exemplo simples, com código em execução em duas linhas:

Linha de execução 1 Linha de execução 2
A = 3
B = 5
reg0 = B
reg1 = A

Neste e em todos os futuros exemplos de parâmetro, as localizações da memória são representadas por letras maiúsculas (A, B, C), e os registos da CPU começam com “reg”. Toda a memória é inicialmente zero. As instruções são executadas de cima para baixo. Aqui, a linha de execução 1 armazena o valor 3 no local A e, em seguida, o valor 5 no local B. A linha de execução 2 carrega o valor do local B em reg0 e, em seguida, carrega o valor do local A em reg1. Observe que estamos gravando em uma ordem e lendo em outra.

Espera-se que a linha de execução 1 e 2 sejam executadas em diferentes núcleos da CPU. Sempre faça essa suposição ao considerar um código com várias linhas de execução.

A consistência sequencial garante que, após a conclusão das duas linhas de execução, os registros estejam em um dos seguintes estados:

Registros Estados
reg0=5, reg1=3 possível (linha 1 executada primeiro)
reg0=0, reg1=0 possível (linha 2 executada primeiro)
reg0=0, reg1=3 possível (execução simultânea)
reg0=5, reg1=0 nunca

Para entrar em uma situação em que vemos B=5 antes de vermos o armazenamento em A, as leituras ou as gravações teriam que acontecer fora de ordem. Em uma máquina com consistência sequencial, isso não pode acontecer.

Os processadores únicos, incluindo x86 e ARM, costumam ter consistência sequencial. As linhas de execução parecem ser executadas de forma intercalada, já que o kernel do SO alterna entre elas. A maioria dos sistemas com SMP, incluindo x86 e ARM, não tem consistência sequencial. Por exemplo, é comum que o hardware crie armazenamentos em buffer no caminho para a memória, para que eles não cheguem à memória imediatamente e fiquem visíveis para outros núcleos.

Os detalhes variam bastante. Por exemplo, a x86, embora não seja consistente sequencialmente, ainda garante que reg0 = 5 e reg1 = 0 permaneçam impossíveis. Os armazenamentos são feitos em buffer, mas sua ordem é mantida. Por sua vez, a ARM não faz o mesmo. A ordem de armazenamentos feitos em buffer não é mantida, e os armazenamentos podem não chegar a todos os outros núcleos ao mesmo tempo. Essas diferenças são importantes para os programadores de Assembly. No entanto, como veremos a seguir, os programadores de C, C++ ou Java podem e devem programar de uma maneira que oculte essas diferenças de arquitetura.

Até agora, presumimos irrealisticamente que apenas o hardware reordena as instruções. Na realidade, o compilador também reordena instruções para melhorar o desempenho. No nosso exemplo, o compilador pode decidir que algum código posterior na linha de execução 2 precisa do valor de reg1 antes de precisar de reg0 e, portanto, carregar reg1 primeiro. Ou algum código anterior pode já ter carregado A, e o compilador pode decidir reutilizar esse valor em vez de carregar A novamente. Em ambos os casos, os carregamentos em reg0 e reg1 podem ser reordenados.

A reordenação de acessos a diferentes locais de memória, seja no hardware ou no compilador, é permitida porque não afeta a execução de uma linha única e pode melhorar significativamente o desempenho. Como veremos, com um pouco de cuidado, também podemos evitar que a reordenação afete os resultados de programas com várias linhas de execução.

Como os compiladores também podem reordenar os acessos à memória, esse problema não é novo para os SMPs. Mesmo em um processador único, um compilador poderia reordenar os carregamentos em reg0 e reg1, no nosso exemplo, e a linha de execução 1 poderia ser programada entre as instruções reordenadas. No entanto, caso nosso compilador não as reordene, talvez nunca observemos esse problema. Na maioria dos SMPs de ARM, mesmo sem que o compilador execute o reordenamento, é provável que ele aconteça após um número muito grande de execuções bem-sucedidas. A menos que você esteja programando em linguagem Assembly, os SMPs normalmente aumentam as chances de você perceber problemas que estavam lá o tempo todo.

Programação sem disputa de dados

Felizmente, costuma haver uma maneira fácil de evitar a preocupação com todos esses detalhes. Se você seguir algumas regras simples, costuma ser seguro esquecer toda a seção anterior, exceto a parte sobre "consistência sequencial". Infelizmente, as outras complicações poderão se tornar visíveis se você acidentalmente quebrar essas regras.

As linguagens modernas de programação incentivam o que é conhecido como um estilo de programação "livre de disputa de dados". Desde que você não introduza "disputas de dados" e evite alguns constructos que digam o contrário ao compilador, os resultados do compilador e do hardware serão consistentes sequencialmente. Isso não significa que o reordenamento do acesso à memória será evitado. Significa que, se você seguir as regras, a reordenação dos acessos à memória não será perceptível. É como dizer a você que a salsicha é uma comida deliciosa e apetitosa, desde que você prometa não visitar a fábrica de salsichas. As disputas de dados expõem a verdade sobre o reordenamento da memória.

O que é uma "disputa de dados"?

Uma disputa de dados ocorre quando pelo menos duas linhas de execução acessam simultaneamente os mesmos dados comuns e pelo menos uma delas os modifica. Com "dados comuns", queremos dizer que não se trata especificamente de um objeto de sincronização destinado à comunicação de linhas de execução. Mutexes, variáveis de condição, voláteis de Java ou objetos atômicos C++ não são dados comuns, e os respectivos acessos podem conter disputa. Na verdade, eles são usados para impedir disputa de dados em outros objetos.

Para determinar se duas linhas de execução acessam simultaneamente o mesmo local de memória, podemos ignorar a discussão sobre reordenação de memória acima e presumir a consistência sequencial. Não haverá disputa de dados no programa a seguir, desde que A e B sejam variáveis booleanas comuns que são inicialmente falsas:

Linha de execução 1 Linha de execução 2
if (A) B = true if (B) A = true

Como as operações não são reordenadas, as duas condições serão avaliadas como falsas, e nenhuma variável será atualizada. Portanto, não pode haver disputa de dados. Não é necessário se preocupar com o que poderia acontecer se o carregamento de A e o armazenamento em B na linha de execução 1 fossem reordenados de alguma forma. O compilador não tem permissão para reordenar a linha de execução 1 reescrevendo-a como "B = true; if (!A) B = false". Isso seria como fazer salsichas no centro da cidade em plena luz do dia.

As disputas de dados são definidas oficialmente em tipos básicos incorporados, como inteiros e referências ou ponteiros. Fazer a atribuição a um int enquanto a leitura dele é feita simultaneamente em outra linha de execução é claramente uma disputa de dados. Porém, tanto a biblioteca padrão C++ quanto as bibliotecas Java Collections foram escritas para permitir que você também justifique disputas de dados no nível da biblioteca. Elas não introduzem disputas de dados a menos que haja acessos simultâneos ao mesmo contêiner e que pelo menos um dos acessos o atualize. A atualização de um set<T> em uma linha de execução e a leitura simultânea dele em outra linha permitem que a biblioteca introduza uma disputa de dados e, portanto, podem ser consideradas informalmente como uma "disputa de dados no nível da biblioteca". Por outro lado, a atualização de um set<T> em uma linha de execução e a leitura simultânea de um diferente em outra linha não tem como resultado uma disputa de dados, porque a biblioteca não introduz uma disputa de dados (de baixo nível) nesse caso.

Normalmente, os acessos simultâneos a diferentes campos em uma estrutura de dados não podem introduzir uma disputa de dados. No entanto, há uma exceção importante a essa regra: sequências contíguas de campos de bits em C ou C++ são tratadas como um único "local de memória". O acesso a qualquer campo de bits nessa sequência é tratado como acesso a todos eles para determinar a existência de uma disputa de dados. Isso reflete a incapacidade do hardware comum de atualizar bits individuais sem ler e regravar bits adjacentes. Os programadores de Java não têm preocupações parecidas.

Como evitar disputas de dados

As linguagens de programação modernas oferecem vários mecanismos de sincronização para evitar as disputas de dados. As ferramentas mais básicas são as seguintes:

Bloqueios ou mutexes
Mutexes (pthread_mutex_t ou std::mutex do C++11) ou blocos synchronized em Java podem ser usados para garantir que certas seções de código não sejam executadas ao mesmo tempo em que outras seções acessem os mesmos dados. Chamaremos essas e outras instalações semelhantes genericamente de "bloqueios". Adquirir consistentemente um bloqueio específico antes de acessar uma estrutura de dados compartilhada e liberá-la posteriormente evita disputas ao acessar a estrutura de dados. Isso também garante que atualizações e acessos sejam atômicos, ou seja, nenhuma outra atualização na estrutura de dados pode ser executada no meio delas. Essa é, de longe, a ferramenta mais comum para evitar disputa de dados. O uso de blocos synchronized do Java ou lock_guard ou unique_lock do C++ garante que os bloqueios sejam liberados adequadamente no caso de uma exceção.
Variáveis voláteis/atômicas
O Java oferece campos volatile, que são compatíveis com acesso simultâneo sem introduzir as disputas de dados. Desde 2011, C e C++ são compatíveis com variáveis atomic e campos com semântica parecida. Normalmente, eles são mais difíceis de usar do que os bloqueios, uma vez que garantem apenas que os acessos individuais a uma única variável sejam atômicos. Em C++, isso normalmente se estende a operações simples de leitura-modificação-gravação, como incrementos. No Java, chamadas de método especiais são necessárias para isso. Ao contrário dos bloqueios, variáveis volatile ou atomic não podem ser usadas diretamente para evitar que outras linhas de execução interfiram em sequências de código mais longas.

É importante notar que volatile tem significados muito diferentes em C++ e Java. Em C++, volatile não impede as disputas de dados, embora o código mais antigo geralmente a use como uma solução alternativa para a falta de objetos atomic. Isso não é mais recomendado. Em C++, use atomic<T> para variáveis que podem ser acessadas simultaneamente por várias linhas de execução. A volatile do C++ é destinada a registros de dispositivos e afins.

Variáveis atomic do C/C++ ou variáveis volatile do Java podem ser usadas para evitar disputas de dados em outras variáveis. Se flag for declarada como tendo tipo atomic<bool> ou atomic_bool (C/C++) ou volatile boolean (Java) e for inicialmente falsa, o seguinte snippet será livre de disputa de dados:

Linha de execução 1 Linha de execução 2
A = ...
  flag = true
while (!flag) {}
... = A

Como a linha de execução 2 espera que flag seja definida, o acesso a A na linha de execução 2 precisa acontecer depois da atribuição a A na linha de execução 1, e não simultaneamente a ela. Assim, não há disputa de dados em A. A disputa em flag não conta como uma disputa de dados, uma vez que os acessos voláteis/atômicos não são "acessos de memória comum".

A implementação é necessária para evitar ou ocultar a reordenação de memória o suficiente para fazer com que o código como o parâmetro precedente se comporte da maneira esperada. Isso normalmente torna os acessos voláteis/atômicos de memória substancialmente mais caros que os acessos comuns.

Embora o exemplo precedente esteja livre de disputas de dados, bloqueios junto a Object.wait() em Java ou variáveis de condição em C/C++ geralmente oferecem uma solução mais adequada e que não envolve a espera em um loop nem o gasto de bateria relacionado.

Quando a reordenação de memória fica visível

A programação livre de disputa de dados normalmente evita o trabalho de tratar explicitamente os problemas de reordenamento de acesso à memória. No entanto, existem vários casos em que a reordenação se torna visível:
  1. Se o programa tiver um bug que causa uma disputa de dados não intencional, as transformações do compilador e do hardware poderão se tornar visíveis, e poderá haver surpresas no comportamento do seu programa. Por exemplo, se nos esquecermos de declarar a flag volátil no exemplo anterior, a linha de execução 2 poderá ter uma A não inicializada. Ou o compilador poderá decidir que a sinalização não pode ser alterada durante o loop da linha de execução 2 e transformar o programa da seguinte maneira
    Linha de execução 1 Linha de execução 2
    A = ...
      flag = true
    reg0 = flag; while (!reg0) {}
    ... = A
    Quando você fizer a depuração, poderá ver que o loop continua para sempre, apesar do fato de que a flag é verdadeira.
  2. O C++ oferece recursos para liberar a consistência sequencial explicitamente, mesmo se não houver disputas. As operações atômicas podem receber argumentos memory_order_ explícitos. Da mesma forma, o pacote java.util.concurrent.atomic oferece um conjunto mais restrito de recursos semelhantes, notavelmente lazySet(). E os programadores de Java às vezes usam disputas de dados intencionais para conseguir um efeito semelhante. Todos esses recursos oferecem melhorias de desempenho mas causam um grande impacto na complexidade da programação. Falamos disso brevemente abaixo.
  3. Alguns códigos C e C++ são escritos em um estilo mais antigo, não inteiramente consistente com os padrões de linguagem corrente, em que variáveis volatile são usadas em vez das atomic, e a ordenação de memória é explicitamente proibida pela inserção dos famosos limites ou barreiras. Isso requer uma justificativa explícita sobre o reordenamento de acesso e a compreensão dos modelos de memória de hardware. Um estilo de programação parecido ainda é usado no kernel do Linux. Ele não deve ser usado em novos aplicativos Android e também não é discutido aqui.

Prática

A depuração de problemas de consistência de memória pode ser muito difícil. Se uma declaração atomic, volatile ou de bloqueio ausente fizer com que algum código leia dados desatualizados, pode não ser possível descobrir o motivo pelo exame dos despejos da memória com um depurador. No momento em que for possível enviar uma consulta ao depurador, todos os núcleos da CPU poderão ter observado o conjunto completo de acessos, e o conteúdo da memória e os registros da CPU poderão estar em um estado “impossível”.

O que não fazer em C

Nesta seção, apresentamos alguns exemplos de código incorreto, juntamente com maneiras simples de corrigi-los. Antes de fazermos isso, precisamos discutir o uso de um recurso de linguagem básico.

C/C++ e "volátil"

Declarações volatile do C e C++ são uma ferramenta de propósito muito especial. Elas impedem o compilador de reordenar ou remover acessos voláteis. Isso pode ser útil para o código que acessa registros de dispositivos de hardware, memória mapeada para mais de um local ou em conexão com setjmp. No entanto, a volatile do C e C++, ao contrário da volatile do Java, não foi projetada para comunicação de linha de execução.

Em C e C++, os acessos a dados volatile podem ser reordenados com acesso a dados não voláteis, e não há garantias de atomicidade. Dessa forma, a volatile não pode ser usada para compartilhar dados entre linhas de execução em código portátil, mesmo em um processador único. A volatile do C geralmente não impede o reordenamento de acesso pelo hardware, portanto, por si só, é ainda menos útil em ambientes de SMP com várias linhas de execução. Essa é a razão pela qual C11 e C++11 são compatíveis com objetos atomic. Use esses objetos.

Vários códigos C e C++ mais antigos ainda usam muito a volatile para comunicação de linhas de execução. Isso geralmente funciona corretamente para dados que se encaixam em um registro de máquina, desde que seja usado com limites explícitos ou em casos em que a ordenação da memória não seja importante. Porém, não há garantia de funcionamento correto com futuros compiladores.

Exemplos

Na maioria dos casos, seria melhor usar um bloqueio (como um pthread_mutex_t ou um std::mutex do C++11) em vez de uma operação atômica, mas usaremos essa última para ilustrar como essas operações seriam usadas em uma situação prática.

MyThing* gGlobalThing = NULL;  // Wrong!  See below.
    void initGlobalThing()    // runs in Thread 1
    {
        MyStruct* thing = malloc(sizeof(*thing));
        memset(thing, 0, sizeof(*thing));
        thing->x = 5;
        thing->y = 10;
        /* initialization complete, publish */
        gGlobalThing = thing;
    }
    void useGlobalThing()    // runs in Thread 2
    {
        if (gGlobalThing != NULL) {
            int i = gGlobalThing->x;    // could be 5, 0, or uninitialized data
            ...
        }
    }

A ideia aqui é alocar uma estrutura, inicializar os campos dela e, no final, "publicá-la" armazenando-a em uma variável global. Nesse momento, qualquer outra linha de execução pode vê-la, mas isso não é um problema, já que ela está totalmente inicializada.

O problema é que o armazenamento em gGlobalThing pode ser observado antes dos campos serem inicializados, normalmente porque o compilador ou o processador reordenou os armazenamentos em gGlobalThing e thing->x. Outra linha de execução que estivesse lendo thing->x poderia ver 5, 0 ou mesmo dados não inicializados.

O problema principal aqui é uma disputa de dados em gGlobalThing. Se a linha de execução 1 chamar initGlobalThing() enquanto a linha de execução 2 chamar useGlobalThing(), gGlobalThing poderá ser lido enquanto estiver sendo gravado.

Isso pode ser corrigido declarando gGlobalThing como atômico. Em C++11:

atomic<MyThing*> gGlobalThing(NULL);

Isso garante que as gravações se tornem visíveis para outras linhas de execução na ordem correta. Também garante a prevenção de alguns outros modos de falha que seriam permitidos de outra forma, mas improváveis em hardware Android real. Por exemplo, isso garante que não seja possível ver um ponteiro gGlobalThing que tenha sido apenas parcialmente gravado.

O que não fazer em Java

Ainda não discutimos alguns recursos relevantes da linguagem Java, então, falaremos deles primeiro.

Tecnicamente, Java não requer que o código seja livre de disputa de dados. E há uma pequena quantidade de código Java muito bem escrito que funciona corretamente na presença de disputa de dados. No entanto, escrever esse código é extremamente complicado, e falamos disso brevemente abaixo. Para piorar, os especialistas que especificaram o significado de tal código não acreditam mais que a especificação esteja correta. Essa especificação é adequada para código sem disputa de dados.

Por enquanto, vamos aderir ao modelo livre de disputa de dados, para o qual o Java oferece essencialmente as mesmas garantias que C e C++. Novamente, a linguagem oferece alguns primitivos que liberam explicitamente a consistência sequencial, notavelmente as chamadas lazySet() e weakCompareAndSet() em java.util.concurrent.atomic. Assim como com C e C++, isso será ignorado por enquanto.

Palavras-chave "synchronized" e "volatile" do Java

A palavra-chave “synchronized” oferece o mecanismo de bloqueio incorporado da linguagem Java. Cada objeto tem um “monitor” associado, que pode ser usado para oferecer acesso mutuamente exclusivo. Se duas linhas de execução tentarem sincronizar no mesmo objeto, uma delas aguardará até que a outra seja concluída.

Como mencionado acima, a volatile T do Java é análoga da atomic<T> do C++11. Acessos simultâneos a campos volatile são permitidos e não causam disputa de dados. Ignorando lazySet() (entre outros) e disputas de dados, é tarefa da VM do Java garantir que o resultado ainda pareça consistente sequencialmente.

Especificamente, se a linha de execução 1 gravar em um campo volatile e a linha de execução 2 subsequentemente ler esse mesmo campo e vir o valor recém-gravado, a linha de execução 2 também verá todas as gravações feitas anteriormente pela linha de execução 1. Em termos de efeito na memória, gravar em uma volátil é comparável a uma liberação de monitor, e a leitura de uma volátil é como uma aquisição de monitor.

Há uma diferença grande em comparação com a atomic do C++: se gravarmos volatile int x; em Java, então x++ será o mesmo que x = x + 1. Ele executa um carregamento atômico, incrementa o resultado e, em seguida, executa um armazenamento atômico. De maneira diferente do C++, o incremento como um todo não é atômico. Operações de incremento atômico são oferecidas pelo java.util.concurrent.atomic.

Exemplos

Esta é uma implementação simples e incorreta de um contador monotônico (Java theory and practice: Managing volatility):

class Counter {
        private int mValue;
        public int get() {
            return mValue;
        }
        public void incr() {
            mValue++;
        }
    }

Vamos supor que get() e incr() sejam chamados a partir de várias linhas de execução e queremos ter certeza de que cada linha de execução veja a contagem atual quando get() for chamado. O problema mais notável é que mValue++ representa na verdade três operações:

  1. reg = mValue
  2. reg = reg + 1
  3. mValue = reg

Se duas linhas de execução forem executadas em incr() simultaneamente, uma das atualizações poderá ser perdida. Para tornar o incremento atômico, precisamos declarar incr() “synchronized”.

Ainda há um problema, no entanto, especialmente no SMP. Existe uma disputa de dados, em que get() pode acessar mValue ao mesmo tempo em que incr(). De acordo com as regras de Java, a chamada de get() pode parecer reordenada em relação a outro código. Por exemplo, se dois contadores forem lidos em uma linha, os resultados poderão parecer inconsistentes, porque as chamadas de get() foram reordenadas, seja pelo hardware ou pelo compilador. Podemos corrigir o problema declarando que get() é sincronizado. Com essa alteração, o código está obviamente correto.

Infelizmente, introduzimos a possibilidade de contenção de bloqueio, o que poderia prejudicar o desempenho. Em vez de declarar get() como sincronizado, poderíamos declarar mValue com “volátil”. O incr() ainda precisa usar synchronize, porque mValue++ não é uma operação atômica. Isso também evita todas as disputas de dados, então a consistência sequencial é preservada. O incr() será um pouco mais lento, uma vez que causa sobrecarga de entrada/saída do monitor e sobrecarga associada a um armazenamento volátil, mas get() será mais rápido. Portanto, mesmo na ausência de contenção, isso é uma vitória se o número de leituras for muito superior ao de gravações. Consulte também AtomicInteger para ver uma maneira de remover completamente o bloco sincronizado.

Este é outro exemplo de formato semelhante aos exemplos C anteriores:

class MyGoodies {
        public int x, y;
    }
    class MyClass {
        static MyGoodies sGoodies;
        void initGoodies() {    // runs in thread 1
            MyGoodies goods = new MyGoodies();
            goods.x = 5;
            goods.y = 10;
            sGoodies = goods;
        }
        void useGoodies() {    // runs in thread 2
            if (sGoodies != null) {
                int i = sGoodies.x;    // could be 5 or 0
                ....
            }
        }
    }

Isso traz o mesmo problema que o código C, ou seja, existe uma disputa de dados em sGoodies. Assim, a atribuição sGoodies = goods pode ser observada antes da inicialização dos campos em goods. Se você declarar sGoodies com a palavra-chave volatile, a consistência sequencial será restaurada e tudo funcionará conforme o esperado.

Observe que apenas a referência sGoodies é volátil. Os acessos aos campos dentro dela não são. Uma vez que sGoodies é volatile, e a ordem da memória é preservada adequadamente, os campos não podem ser acessados simultaneamente. A declaração z = sGoodies.x executará um carregamento volátil de MyClass.sGoodies seguido por um carregamento não volátil de sGoodies.x. Se você fizer uma referência local MyGoodies localGoods = sGoodies, uma z = localGoods.x subsequente não executará carregamentos voláteis.

Uma expressão mais comum na programação Java é o infame bloqueio duplamente verificado (double-checked locking):

class MyClass {
        private Helper helper = null;
        public Helper getHelper() {
            if (helper == null) {
                synchronized (this) {
                    if (helper == null) {
                        helper = new Helper();
                    }
                }
            }
            return helper;
        }
    }

A ideia é ter uma única instância de um objeto Helper associada a uma instância de MyClass. Devemos criá-la apenas uma vez, então nós a criamos e retornamos por meio de uma função getHelper() dedicada. Para evitar uma disputa em que duas linhas de execução criam a instância, precisamos sincronizar a criação do objeto. No entanto, não queremos sobrecarga do bloco "sincronizado" em todas as chamadas, então só faremos essa parte se o helper for nulo atualmente.

Nesse caso, há uma disputa de dados no campo helper. Ele pode ser definido ao mesmo tempo em que helper == null em outra linha de execução.

Para ver como isso pode falhar, considere o mesmo código levemente reescrito, como se fosse compilado em uma linguagem semelhante a C (adicionei alguns campos de inteiros para representar a atividade do construtor Helper’s):

if (helper == null) {
        synchronized() {
            if (helper == null) {
                newHelper = malloc(sizeof(Helper));
                newHelper->x = 5;
                newHelper->y = 10;
                helper = newHelper;
            }
        }
        return helper;
    }

Não há nada que impeça o hardware ou o compilador de reordenar o armazenamento em helper com aqueles nos campos x/y. Outra linha de execução poderia ter o helper não nulo, mas os campos ainda não estariam definidos nem prontos para uso. Para ver mais detalhes e mais modos de falha, consulte o link “Double Checked Locking is Broken" no apêndice, ou o Item 71 (“Use lazy initialization judiciously”) do livro Effective Java, 2nd Edition, de Josh Bloch.

Existem duas opções para corrigir isso:

  1. Faça o mais simples, excluindo a verificação externa. Isso garante que o valor do helper nunca seja examinado fora de um bloco sincronizado.
  2. Declare que helper é volátil. Com essa pequena alteração, o código no Exemplo J-3 funcionará corretamente no Java 1.5 e posterior. (Pode levar alguns minutos para você se convencer de que isso é verdade.)

Esta é outra ilustração do comportamento volatile:

class MyClass {
        int data1, data2;
        volatile int vol1, vol2;
        void setValues() {    // runs in Thread 1
            data1 = 1;
            vol1 = 2;
            data2 = 3;
        }
        void useValues() {    // runs in Thread 2
            if (vol1 == 2) {
                int l1 = data1;    // okay
                int l2 = data2;    // wrong
            }
        }
    }

Analisando useValues(), se a linha de execução 2 ainda não tiver observado a atualização para vol1, não será possível saber se data1 ou data2 já foi definido. Depois de ver a atualização para vol1, a linha de execução sabe que data1 pode ser acessado com segurança e lido corretamente sem introduzir uma disputa de dados. No entanto, ela não pode fazer nenhuma suposição sobre data2, porque esse armazenamento foi executado após o armazenamento volátil.

Observe que volatile não pode ser usada para evitar a reordenação de outros acessos à memória que disputam entre si. Não há garantia de que uma instrução de limite de memória da máquina será gerada. Ela poderá ser usada para evitar disputas de dados pela execução de código somente quando outra linha de execução atender uma determinada condição.

O que fazer

Em C/C++, prefira classes de sincronização do C++ 11, como std::mutex. Caso contrário, use as operações pthread correspondentes. Essas operações incluem os limites adequados da memória, gerando o comportamento correto (consistente sequencialmente, a menos que especificado de outra forma) e eficiente em todas as versões da plataforma Android. Use-as corretamente. Por exemplo, lembre-se de que as esperas da variável de condição podem retornar ilegitimamente sem sinalização e precisam, portanto, aparecer em um loop.

É melhor evitar usar funções atômicas diretamente, a menos que a estrutura de dados que você está implementando seja extremamente simples, como um contador. Bloquear e desbloquear um mutex pthread requer uma única operação atômica e, muitas vezes, custa menos do que uma ausência única no cache. Se não houver contenção, então as substituições das chamadas mutex por operações atômicas não trarão muita economia. Designs livres de bloqueio para estruturas de dados não triviais requerem muito mais cuidado para garantir que operações de nível mais alto na estrutura de dados apareçam atômicas (como um todo, não apenas as partes explicitamente atômicas).

Se você usar operações atômicas, a ordem de liberação com memory_order ou lazySet() poderá oferecer vantagens de desempenho, mas exigirá uma compreensão mais profunda do que a que mostramos até agora. Foi descoberto que uma grande parte do código existente que usa essas operações apresenta bugs após o fato. Se possível, evite-as. Se seus casos de uso não se enquadrarem exatamente na seção a seguir, você precisa ser ou consultar um especialista.

Evite usar volatile para comunicação de linha de execução em C/C++.

Em Java, os problemas de simultaneidade geralmente são resolvidos mais adequadamente usando uma classe de utilitário apropriada do pacote java.util.concurrent. O código está bem escrito e bem testado no SMP.

Talvez o mais seguro a se fazer seja tornar seus objetos imutáveis. Objetos de classes como String e Integer do Java armazenam dados que não podem ser alterados depois que um objeto é criado, evitando todo o potencial de disputa de dados nesses objetos. O livro Effective Java, 2nd Ed. tem instruções específicas no “Item 15: Minimize Mutability”. Em especial, observe a importância de declarar os campos "finais" do Java (Bloch).

Mesmo que um objeto seja imutável, tenha em mente que comunicá-lo a outra linha de execução sem qualquer tipo de sincronização é uma disputa de dados. Pode acontecer de isso ser aceitável no Java (veja abaixo), mas muito cuidado é necessário. Além disso, é provável que o resultado seja instabilidade do código. Se não for atrapalhar muito o desempenho, adicione uma declaração de volatile. No C++, comunicar um ponteiro ou referência a um objeto imutável sem a devida sincronização, como toda disputa de dados, é um bug. Nesse caso, é bem provável que o resultado sejam falhas intermitentes, já que a linha de execução receptora, por exemplo, pode ver um ponteiro de tabela de método não inicializado devido à reordenação de armazenamento.

Se uma classe de biblioteca existente e uma classe imutável não forem apropriadas, a instrução synchronized do Java ou lock_guard / unique_lock do C++ precisa ser usada para proteger acessos a qualquer campo que possa ser acessado por mais de uma linha de execução. Se as mutexes não funcionarem para sua situação, você precisará declarar campos compartilhados como volatile ou atomic, mas muito cuidado será necessário para entender as interações entre as linhas de execução. Essas declarações não livram você de erros comuns de programação simultânea, mas ajudam a evitar as falhas misteriosas associadas a compiladores de otimização e erros do SMP.

Evite "publicar" uma referência a um objeto, ou seja, disponibilizá-lo para outras linhas de execução no construtor dele. Isso é menos grave em C++ ou se você seguir nosso conselho de "nenhuma disputa de dados" em Java. No entanto, esse conselho é sempre útil e será essencial se o código Java for executado em outros contextos em que o modelo de segurança Java é importante, e um código não confiável pode introduzir uma disputa de dados usando essa referência de objeto "vazada". Também será essencial se você optar por ignorar nossos avisos e usar algumas das técnicas da próxima seção. Consulte Safe Construction Techniques in Java para ver detalhes.

Um pouco mais sobre ordenações fracas de memória

O C++11 e posteriores oferecem mecanismos explícitos para liberar as garantias de consistência sequencial em programas livres de disputa de dados. Cada um dos argumentos explícitos memory_order_relaxed, memory_order_acquire (apenas carregamentos) e memory_order_release(apenas armazenamentos) para operações atômicas oferece garantias estritamente mais fracas do que o padrão, normalmente implícito, memory_order_seq_cst. memory_order_acq_rel oferece garantias memory_order_acquire e memory_order_release para operações atômicas de leitura-modificação-gravação. memory_order_consume ainda não está suficientemente implementado ou bem especificado para ser usado e deve ser ignorado por enquanto.

Os métodos lazySet em Java.util.concurrent.atomic são semelhantes aos armazenamentos memory_order_release do C++. As variáveis comuns do Java às vezes são usadas para substituir acessos memory_order_relaxed, embora sejam ainda mais fracas. Ao contrário do C++, não existe um mecanismo real para acessos não ordenados a variáveis declaradas como volatile.

Em geral, você precisa evitá-las, a menos que haja motivos de desempenho muito relevantes para usá-las. Em arquiteturas de máquina com ordenação fraca, como a ARM, usá-las normalmente traz economia à ordem de alguns ciclos de máquina para cada operação atômica. Na x86, o ganho de desempenho é limitado aos armazenamentos e provavelmente menos perceptível. Ainda que não seja muito intuitivo, o benefício pode diminuir com maiores contagens do núcleo, já que o sistema de memória se torna mais um fator limitante.

A semântica completa de atômicas com ordenação fraca é complicada. No geral, ela exige um entendimento preciso das regras da linguagem, o que não será tratado aqui. Exemplo:

  • O compilador ou hardware pode mover os acessos memory_order_relaxed para dentro (mas não para fora) de uma seção crítica limitada por uma aquisição de bloqueio e liberação. Isso significa que dois armazenamentos memory_order_relaxed podem se tornar visíveis fora da ordem, mesmo que estejam separados por uma seção crítica.
  • Uma variável Java comum, quando usada em demasiado como um contador compartilhado, pode aparecer em outra linha de execução para ser diminuída, mesmo que seja incrementada apenas por outra linha de execução única. No entanto, isso não é verdade para memory_order_relaxed atômica do C++.

Observado esse aviso, aqui está um pequeno número de expressões que parecem cobrir muitos dos casos de uso para atômicas com ordenação fraca. Muitas delas são aplicáveis apenas ao C++.

Acessos não disputados

É bastante comum que uma variável seja atômica, porque às vezes ela é lida simultaneamente com uma gravação, mas nem todos os acessos têm esse problema. Por exemplo, uma variável pode precisar ser atômica porque é lida fora de uma seção crítica, mas todas as atualizações são protegidas por um bloqueio. Nesse caso, uma leitura que esteja protegida pelo mesmo bloqueio não poderá disputar, já que não pode haver gravações simultâneas. Em uma situação dessa, o acesso não disputado (carregamento, neste caso), pode ser anotado com memory_order_relaxed sem alterar a precisão do código C++. A implementação de bloqueio já impõe a ordenação de memória necessária com relação ao acesso por outras linhas de execução. Além disso, memory_order_relaxed especifica que essencialmente nenhuma outra restrição de ordenação precisa ser imposta para o acesso atômico.

Não há algo parecido no Java.

A correção do resultado não é imprescindível

Quando usamos um carregamento disputado apenas para gerar uma dica, normalmente não é permitido impor qualquer ordem de memória para o carregamento. Se o valor não é confiável, também não podemos usar o resultado de maneira confiável para inferir algo sobre outras variáveis. Portanto, tudo bem se a ordenação de memória não for garantida e o carregamento for fornecido com um argumento memory_order_relaxed.

Um exemplo comum disso é o uso de compare_exchange do C++ para substituir atomicamente x por f(x). O carregamento inicial de x para calcular f(x) não precisa ser confiável. Se errarmos, compare_exchange falhará, e tentaremos novamente. Não há problema se o carregamento inicial de x usar um argumento memory_order_relaxed. Apenas a ordem da memória para o compare_exchange real é importante.

Dados modificados atomicamente, mas não lidos

Às vezes, os dados são modificados em paralelo por várias linhas de execução, mas não são examinados até que a computação paralela seja concluída. Um bom exemplo disso é um contador que é atomicamente incrementado (por exemplo, usando fetch_add() em C++ ou atomic_fetch_add_explicit() em C) por várias linhas de execução em paralelo, mas o resultado dessas chamadas é sempre ignorado. O valor resultante é lido apenas no final, após todas as atualizações serem concluídas.

Nesse caso, não há como saber se os acessos a esses dados foram reordenados e, portanto, o código C++ pode usar um argumento memory_order_relaxed.

Contadores de eventos simples são um exemplo comum disso. Por ser muito comum, vale a pena fazer algumas observações sobre esse caso:

  • O uso de memory_order_relaxed melhora o desempenho, mas pode não resolver o problema de desempenho mais importante: toda atualização requer acesso exclusivo à linha de cache que contém o contador. Isso causa uma ausência de cache toda vez que uma nova linha de execução acessa o contador. Se as atualizações forem frequentes e alternarem entre as linhas de execução, será muito mais rápido evitar a atualização do contador compartilhado todas as vezes usando, por exemplo, contadores locais de linha de execução e somando-os no final.
  • Esta técnica pode ser combinada com a seção anterior: é possível ler simultaneamente valores aproximados e não confiáveis enquanto eles estão sendo atualizados, com todas as operações usando memory_order_relaxed. No entanto, é importante tratar os valores resultantes como totalmente não confiáveis. Só porque a contagem parece ter sido incrementada uma vez, não significa que outra linha de execução possa ser contada para chegar ao ponto em que o incremento foi realizado. Em vez disso, o incremento pode ter sido reordenado com código anterior. Quanto ao caso semelhante que mencionamos anteriormente, o C++ garante que um segundo carregamento de tal contador não retornará um valor menor que um carregamento anterior na mesma linha de execução. Exceto, é claro, se o limite do contador for excedido.
  • É comum encontrar código que tente calcular valores aproximados de contadores executando leituras e gravações individuais atômicas (ou não), mas sem fazer do incremento como um todo atômico. O argumento usual é que isso "chega perto o suficiente" dos contadores de desempenho ou algo parecido. Normalmente, não é o caso. Quando as atualizações são frequentes o suficiente (um caso que pode ser importante para você), uma grande parte das contagens costuma se perder. Em um dispositivo quad-core, mais da metade das contagens pode ser perdida. Exercício simples: crie um cenário de duas linhas de execução em que o contador é atualizado um milhão de vezes, mas o valor final do contador é um.

Comunicação de sinalização simples

Um armazenamento memory_order_release (ou operação de leitura-modificação-gravação) garante que, se subsequentemente um carregamento memory_order_acquire (ou operação de leitura-modificação-gravação) ler o valor gravado, ele também observará todos os armazenamentos (comuns ou atômicos) que precederam o armazenamento memory_order_release A. Por outro lado, todos os carregamentos que antecedem memory_order_release não observarão nenhum armazenamento que tenha acontecido depois do carregamento memory_order_acquire. Ao contrário de memory_order_relaxed, isso permite que essas operações atômicas sejam usadas para comunicar o progresso de uma linha de execução para a outra.

Por exemplo, podemos reescrever o exemplo de bloqueio duplamente verificado acima em C++ da seguinte forma

    class MyClass {
      private:
        atomic<Helper*> helper {nullptr};
        mutex mtx;
      public:
        Helper* getHelper() {
          Helper* myHelper = helper.load(memory_order_acquire);
          if (myHelper == nullptr) {
            lock_guard<mutex> lg(mtx);
            myHelper = helper.load(memory_order_relaxed);
            if (myHelper == nullptr) {
              myHelper = new Helper();
              helper.store(myHelper, memory_order_release);
            }
          }
          return myHelper;
        }
    };
    

O carregamento de aquisição e o armazenamento de liberação garantem que, se um helper não nulo for visualizado, os campos dele corretamente inicializados também serão visualizados. Incorporamos também a observação anterior de que carregamentos que não são disputados podem usar memory_order_relaxed.

Um programador Java poderia representar o helper como um java.util.concurrent.atomic.AtomicReference<Helper> e usar lazySet() como o armazenamento de liberação. As operações de carregamento continuariam usando chamadas get() simples.

Em ambos os casos, nossos ajustes de desempenho se concentraram no caminho de inicialização, o que provavelmente não é essencial para o desempenho. Um meio termo mais legível poderia ser:

        Helper* getHelper() {
          Helper* myHelper = helper.load(memory_order_acquire);
          if (myHelper != nullptr) {
            return myHelper;
          }
          lock_guard&ltmutex> lg(mtx);
          if (helper == nullptr) {
            helper = new Helper();
          }
          return helper;
        }
    

Isso oferece o mesmo caminho rápido, mas recorre às operações padrão sequencialmente consistentes no caminho lento em que o desempenho não é crítico.

Mesmo aqui, o helper.load(memory_order_acquire) provavelmente gerará o mesmo código nas arquiteturas atualmente compatíveis com o Android como uma referência simples (sequencialmente consistente) ao helper. Realmente, a otimização mais benéfica aqui pode ser a introdução do myHelper para eliminar um segundo carregamento, embora um futuro compilador possa fazer isso automaticamente.

A ordem de aquisição/liberação não impede que os armazenamentos fiquem visivelmente atrasados e não garante que eles fiquem visíveis para outras linhas de execução em uma ordem consistente. Como resultado, ela não é compatível com um padrão de codificação complicado, mas bastante comum, exemplificado pelo algoritmo de exclusão mútua de Dekker: todas as linhas de execução definem primeiro uma sinalização indicando que querem fazer alguma coisa. Se uma linha de execução t perceber que nenhuma outra linha de execução está tentando fazer alguma coisa, ela poderá prosseguir com segurança, sabendo que não haverá interferência. Nenhuma outra linha de execução poderá prosseguir porque a sinalização de t ainda está definida. Isso falhará se a sinalização for acessada usando a ordem de aquisição/liberação, já que ela não impede que a sinalização de uma linha de execução fique visível para as outras com atraso, depois que elas já tiverem prosseguido erroneamente. O memory_order_seq_cst padrão evita isso.

Campos imutáveis

Se um campo de objeto for inicializado no primeiro uso e nunca for alterado, talvez seja possível inicializá-lo e depois lê-lo usando acessos com ordenação fraca. Em C++, isso poderia ser declarado como atomic e acessado usando memory_order_relaxed, ou, em Java, ele poderia ser declarado sem volatile e acessado sem medidas especiais. Isso requer que todas as seguintes condições sejam atendidas:

  • Deve ser possível dizer, a partir do valor do próprio campo, se ele já foi inicializado. Para acessar o campo, o valor de teste e retorno do caminho rápido precisa ler o campo apenas uma vez. Em Java, essa última condição é essencial. Mesmo se o resultado do teste do campo for inicializado, um segundo carregamento poderá ler o valor não inicializado anterior. Em C++, a regra "ler uma vez" é meramente uma prática recomendada.
  • A inicialização e os carregamentos subsequentes precisam ser atômicos, porque atualizações parciais não devem ser visíveis. Para Java, o campo não deve ser long nem double. Para C++, uma atribuição atômica é necessária. No entanto, construí-la no lugar não funcionará, já que a construção de uma atomic não é atômica.
  • As inicializações repetidas precisam ser seguras, já que várias linhas de execução podem ler o valor não inicializado simultaneamente. Em C++, isso geralmente parte do requisito "trivialmente copiável" imposto para todos os tipos atômicos. Os tipos com ponteiros de propriedade aninhados exigiriam desalocação no construtor de cópia e não seriam trivialmente copiáveis. Para Java, certos tipos de referência são aceitáveis.
  • As referências de Java são limitadas a tipos imutáveis que contêm apenas campos finais. O construtor do tipo imutável não deve publicar uma referência ao objeto. Nesse caso, as regras de campo final do Java garantem que, se um leitor visualizar a referência, ele também verá os campos finais inicializados. O C++ não tem nenhuma regra análoga a essas, e os ponteiros para objetos de propriedade são inaceitáveis também por essa razão, além de violarem os requisitos "trivialmente copiáveis".

Notas de encerramento

Ainda que este documento não seja totalmente superficial, ele representa apenas a ponta do iceberg. Este é um assunto muito amplo e profundo. Veja algumas áreas que podem ser mais aprofundadas:

  • Os modelos reais de memória Java e C++ são expressos em termos de uma relação o que acontece antes, que especifica quando existe a garantia de que duas ações ocorrerão em uma determinada ordem. Quando definimos uma disputa de dados, falamos de maneira informal sobre dois acessos de memória acontecendo "simultaneamente". Oficialmente, a disputa é definida como nenhum dos dois acessos acontecendo um antes do outro. É esclarecedor saber mais sobre as definições reais de o que acontece antes e de sincronização com no modelo de memória do Java ou C++. Anda que a noção intuitiva de "simultaneamente" seja boa o bastante, essas definições são informativas, especialmente se você estiver contemplando o uso de operações atômicas com ordem fraca no C++. A especificação atual do Java define apenas o lazySet() de maneira bem informal.
  • Pesquise sobre o que os compiladores podem e não podem fazer ao reordenar o código. A especificação JSR-133 tem alguns ótimos exemplos de transformações legais que levam a resultados inesperados.
  • Veja como escrever classes imutáveis em Java e C++. Isso vai muito além de "não mudar nada após a construção".
  • Internalize as recomendações na seção "Concurrency" do livro Effective Java, 2nd Edition. Por exemplo, evite chamar métodos que precisem ser substituídos dentro de um bloco sincronizado.
  • Leia integralmente as APIs java.util.concurrent e java.util.concurrent.atomic para ver o que está disponível. Considere o uso de anotações de simultaneidade, como @ThreadSafe e @GuardedBy (de net.jcip.annotations).

A seção Leia mais no apêndice apresenta links para documentos e sites com mais informações sobre esses temas.

Apêndice

Como implementar armazenamentos de sincronização

Isso não é algo que a maioria dos programadores precise implementar, mas a discussão é esclarecedora.

Para pequenos tipos integrados como int e hardware compatível com o Android, as instruções comuns de carregamento e armazenamento garantem que um armazenamento seja inteiramente visível ou invisível para outro processador sendo carregado no mesmo local. Por isso, alguma noção básica de "atomicidade" é fornecida gratuitamente.

Como vimos anteriormente, isso não é suficiente. Para garantir a consistência sequencial, também precisamos evitar a reordenação das operações e garantir que as operações de memória se tornem visíveis para outros processos em uma ordem consistente. Acontece que essa última condição é automática em hardware compatível com o Android, desde que façamos escolhas criteriosas para impor a primeira condição, então não tratamos disso aqui.

A ordem das operações de memória é preservada evitando a reordenação pelo compilador e pelo hardware. Aqui, estamos nos concentrando no hardware.

A ordenação de memória em ARMv7, x86 e MIPS é aplicada com instruções de "limite" que praticamente impedem que as instruções que estão depois do limite se tornem visíveis antes das instruções que o precedem. Elas também são comumente conhecidas como instruções de "barreira", mas isso pode gerar confusão com as barreiras de estilo pthread_barrier, que fazem muito mais do que isso. O significado exato das instruções de limite é um assunto bastante complicado, que precisa abordar a maneira como as garantias oferecidas por vários tipos diferentes de limites interagem e como elas se combinam com outras garantias de ordenação geralmente fornecidas pelo hardware. Este é um apanhado geral, então não trataremos desses detalhes.

O tipo mais básico de garantia de ordenação é o fornecido pelas operações atômicas memory_order_acquire e memory_order_release do C++: operações de memória anteriores a um armazenamento de liberação precisam ser visíveis após um carregamento de aquisição. Na ARMv7, isso é imposto pelas seguintes condições:

  • Uma instrução de limite adequada precisa preceder a instrução de armazenamento. Isso impede que todos os acessos de memória anteriores sejam reordenados com a instrução de armazenamento. Também evita a reordenação desnecessária com instruções de armazenamento posteriores.
  • A instrução de carregamento precisa ser seguida por uma instrução de limite adequada, evitando que o carregamento seja reordenado com os acessos subsequentes. E também fornecendo ordenações desnecessárias com, pelo menos, os carregamentos anteriores.

Juntas, essas condições são suficientes para a ordem de aquisição/liberação do C++. Elas são necessárias, mas não suficientes, para volatile do Java ou atomic sequencialmente consistente do C++.

Para ver o que mais é necessário, considere o fragmento do algoritmo de Dekker que mencionamos anteriormente de maneira breve. flag1 e flag2 são variáveis atomic do C++ ou volatile do Java, ambas inicialmente falsas.

Linha de execução 1 Linha de execução 2
flag1 = true
if (flag2 == false)
    critical-stuff
flag2 = true
if (flag1 == false)
    critical-stuff

A consistência sequencial implica que uma das atribuições para flag n precisa ser executada primeiro e ser vista pelo teste na outra linha de execução. Assim, nunca veremos essas linhas executando o “material crítico” simultaneamente.

No entanto, o limite necessário para a ordem de aquisição-liberação acrescenta limites apenas no início e no final de cada linha de execução, o que não ajuda aqui. Além disso, precisamos garantir que, se um armazenamento volatile/atomic for seguido por um carregamento volatile/atomic, os dois não serão reordenados. Normalmente, isso é imposto pela adição de um limite não apenas antes de um armazenamento sequencialmente consistente, mas também depois dele. Isso é muito mais do que o necessário, já que esse limite costuma ordenar todos os acessos de memória anteriores em relação a todos os posteriores.

Em vez disso, é possível associar o limite extra aos carregamentos sequencialmente consistentes. Como os armazenamentos são menos frequentes, a convenção que descrevemos é mais comum e usada no Android.

Como já visto anteriormente, precisamos inserir uma barreira de armazenamento/carregamento entre as duas operações. O código executado na VM para um acesso volátil terá esta aparência:

carregamento volátil armazenamento volátil
reg = A
fence for "acquire" (1)
fence for "release" (2)
A = reg
fence for later atomic load (3)

Arquiteturas de máquinas reais geralmente oferecem vários tipos de limites, que ordenam diferentes tipos de acessos e podem ter custos diferentes. A escolha entre eles é sutil e influenciada pela necessidade de garantir que os armazenamentos fiquem visíveis para outros núcleos em uma ordem consistente e que a ordem da memória imposta pela combinação de vários limites seja composta corretamente. Para mais ver detalhes, consulte a página da Universidade de Cambridge com os mapeamentos coletados de atômicas em processadores reais (em inglês).

Em algumas arquiteturas, especialmente a x86, as barreiras de "aquisição" e "liberação" são desnecessárias, já que o hardware sempre impõe, de maneira implícita, uma ordenação suficiente. Assim, na x86, somente o último limite (3) é realmente gerado. Da mesma forma, na x86, operações atômicas de leitura-modificação-gravação incluem implicitamente um limite forte. Assim, elas nunca precisam de nenhum limite. Na ARMv7, todos os limites discutidos acima são necessários.

A ARMv8 oferece instruções LDAR e STLR que aplicam diretamente os requisitos de carregamentos e armazenamentos sequencialmente consistentes do C++ ou voláteis do Java. Elas evitam as restrições de reordenação desnecessárias que mencionamos acima. O código Android de 64 bits na ARM usa essas instruções. Escolhemos nos concentrar no posicionamento de limite da ARMv7 aqui porque isso esclarece os requisitos reais.

Leia mais

Páginas da Web e documentos em inglês que oferecem maior profundidade ou são mais abrangentes. Os artigos mais úteis de maneira geral estão mais próximos do topo da lista.

Shared Memory Consistency Models: A Tutorial
Escrito em 1995 por Adve & Gharachorloo, esse artigo é um bom começo se você quiser entender mais profundamente os modelos de consistência de memória.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
Memory Barriers
Artigo curto e bem escrito que resume os problemas.
http://en.wikipedia.org/wiki/Memory_barrier
Threads Basics
Uma introdução à programação com várias linhas de execução em C++ e Java, por Hans Boehm. Discussão sobre disputa de dados e métodos básicos de sincronização.
http://www.hboehm.info/c++mm/threadsintro.html
Java Concurrency In Practice
Publicado em 2006, esse livro abrange muitos temas com riqueza de detalhes. Altamente recomendado para quem escreve código com várias linhas de execução em Java.
http://www.javaconcurrencyinpractice.com
JSR-133 (Java Memory Model) FAQ
Uma introdução leve ao modelo de memória do Java, incluindo uma explicação sobre sincronização, variáveis voláteis e construção de campos finais. Um pouco desatualizado, especialmente ao discutir outras linguagens.
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html
Validity of Program Transformations in the Java Memory Model
Uma explicação bastante técnica dos problemas remanescentes no modelo de memória do Java. Esses problemas não se aplicam a programas sem disputa de dados.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.1790&rep=rep1&type=pdf
Overview of package java.util.concurrent
A documentação do pacote java.util.concurrent. Perto da parte inferior da página, há uma seção intitulada “Memory Consistency Properties”, que explica as garantias feitas pelas várias classes.
Resumo do pacote java.util.concurrent
Java Theory and Practice: Safe Construction Techniques in Java
Esse artigo examina em detalhes os perigos das referências que escapam durante a construção do objeto e oferece orientações para construtores seguros para a linha de execução.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html
Java Theory and Practice: Managing Volatility
Um bom artigo que descreve o que você pode e não pode realizar com campos voláteis em Java.
http://www.ibm.com/developerworks/java/library/j-jtp06197.html
The “Double-Checked Locking is Broken” Declaration
Explicação detalhada de Bill Pugh sobre as várias maneiras em que o bloqueio duplamente verificado é quebrado sem volatile ou atomic. Serve para C/C++ e Java.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[ARM] Barrier Litmus Tests and Cookbook
Uma discussão dos problemas do SMP da ARM, ilustrada com pequenos snippets do código da ARM. Se você não achou os exemplos deste documento muito específicos ou se quiser ler a descrição formal da instrução DMB, leia esse artigo. Também descreve as instruções usadas para barreiras da memória no código executável (possivelmente útil se você estiver gerando código em tempo real). Observe que o artigo é anterior à arquitetura ARMv8, que também é compatível com outras instruções de ordenação de memória e evoluiu para um modelo de memória um pouco mais forte. Consulte "ARM® Architecture Reference Manual ARMv8, for ARMv8-A architecture profile" para ver mais detalhes.
http://infocenter.arm.com/help/topic/com.arm.doc.genc007826/Barrier_Litmus_Tests_and_Cookbook_A08.pdf
Linux Kernel Memory Barriers
Documentação das barreiras de memória do kernel do Linux. Inclui alguns exemplos úteis e gráficos do ASCII.
http://www.kernel.org/doc/Documentation/memory-barriers.txt
ISO/IEC JTC1 SC22 WG21 (C++ standards) 14882 (C++ programming language), seção 1.10 e cláusula 29 (“Atomic operations library”)
Rascunho de padrão para recursos de operação atômica do C++. Essa versão está próxima do padrão do C++14, que inclui pequenas alterações nessa área em relação ao C++11.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
Introdução: http://www.hpl.hp.com/techreports/2008/HPL-2008-56.pdf
ISO/IEC JTC1 SC22 WG14 (C standards) 9899 (C programming language) capítulo 7.16 (“Atomics <stdatomic.h>”)
Rascunho do padrão para recursos de operação atômica do C ISO/IEC 9899-201x. Para ver detalhes, consulte também os relatórios de erros posteriores.
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
C/C++11 mappings to processors (Universidade de Cambridge)
A coleção de traduções de Jaroslav Sevcik e Peter Sewell das atômicas do C++ para vários conjuntos de instruções de processadores comuns.
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
Dekker’s algorithm
A “primeira solução correta e conhecida para o problema de exclusão mútua em programação concorrente”. O artigo da Wikipédia tem o algoritmo completo, com uma discussão sobre como ele precisaria ser atualizado para funcionar com compiladores de otimização modernos e hardware com SMP.
http://en.wikipedia.org/wiki/Dekker's_algorithm
Comments on ARM vs. Alpha and address dependencies
Uma mensagem na lista de e-mails sobre arm-kernel de Catalin Marinas. Inclui um bom resumo das dependências de endereço e controle.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html
What Every Programmer Should Know About Memory
Um artigo longo e detalhado sobre diferentes tipos de memória, particularmente caches de CPU, de Ulrich Drepper.
http://www.akkadia.org/drepper/cpumemory.pdf
Reasoning about the ARM weakly consistent memory model
Esse artigo foi escrito por Chong & Ishtiaq, da ARM, Ltd. Ele tenta descrever o modelo de memória SMP da ARM de maneira rigorosa, mas acessível. A definição de “observability” (capacidade de ser observado) usada aqui vem desse documento. Novamente, o texto é anterior à arquitetura ARMv8.
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll=&dl=&CFID=96099715&CFTOKEN=57505711
The JSR-133 Cookbook for Compiler Writers
Doug Lea escreveu isso como um complemento da documentação do JSR-133 (modelo de memória do Java). Contém o conjunto inicial de diretrizes de implementação para o modelo de memória do Java usado por muitos compiladores e que ainda é amplamente citado e provavelmente oferecerá insights. Infelizmente, as quatro variedades de limite discutidas aqui não são uma boa combinação para arquiteturas compatíveis com o Android. Atualmente, os mapeamentos posteriores ao C++ 11 são uma fonte mais adequada de receitas precisas, mesmo para Java.
http://g.oswego.edu/dl/jmm/cookbook.html
x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors
Uma descrição precisa do modelo de memória da x86. Descrições precisas do modelo de memória da ARM são, infelizmente, significativamente mais complicadas.
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf