Informações iniciais sobre SMPs para Android

As versões 3.0 e mais recentes da plataforma Android são otimizadas para oferecer 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 em linguagem de programação Java, chamada simplesmente de "Java" a partir de agora por questão de brevidade. Ele é uma introdução para desenvolvedores de apps para Android e 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 acesso à memória principal. Até alguns anos atrás, todos os dispositivos Android tinham processador único (UP, na sigla em inglês).

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

A maior parte dos dispositivos Android vendidos atualmente são baseados em designs de SMP, o que complica um pouco as coisas 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 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 até em diferentes implementações da mesma arquitetura. O código que foi minuciosamente 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 precisa ser feito 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ê verá na próxima seção, nesse caso, os detalhes 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 oferecem sobre os acessos à memória. Por exemplo, se você gravar 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 nessa ordem.

O modelo ao que a maioria dos programadores está acostumada é a consistência sequencial, que é descrita da seguinte 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 do processador.

Suponhamos temporariamente que temos um compilador ou interpretador muito simples que não apresenta surpresas: ele traduz atribuições no código-fonte para carregar e armazenar as instruções na ordem correspondente exata, 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, 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 esteja fazendo outra coisa além de executar as instruções de maneira direta. Vamos ignorar 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

Nesse e em todos os futuros exemplos de parâmetro, os locais da memória são representados 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 escrevendo em uma ordem e lendo em outra.

Espera-se que as linhas 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 chegar a 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 os armazenamentos em buffer a caminho da 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, embora x86 não seja sequencialmente consistente, ela 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 precisam programar de uma forma que oculte essas diferenças de arquitetura.

Até agora, estávamos supondo de forma irrealista que somente 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, é possível que esse problema nunca fosse notado caso o compilador não reordenasse os carregamentos. 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 forma fácil de evitar a preocupação com todos esses detalhes. Seguindo algumas regras simples, é relativamente 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ê quebrar essas regras acidentalmente.

As linguagens modernas de programação incentivam o que é conhecido como um estilo de programação "livre de disputa de dados". Os resultados do compilador e do hardware serão sequencialmente consistentes, desde que você não introduza "disputas de dados" e evite algumas construções que orientem o compilador de forma diferente. Isso não significa que a reordenação do acesso à memória será evitada. Significa que, se você seguir as regras, a reordenação dos acessos à memória não será perceptível. É como falar que salsicha é uma comida deliciosa, desde que você não visite a fábrica. As disputas de dados expõem a verdade sobre a reordenação 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. "Dados comuns" significa que não se trata especificamente de um objeto de sincronização destinado à comunicação entre 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 disputas de dados em outros objetos.

Para determinar se duas linhas de execução acessam o mesmo local de memória simultaneamente, podemos ignorar a discussão sobre reordenação de memória acima e presumir que há consistência sequencial. Não haverá disputa de dados no programa a seguir, desde que A e B sejam variáveis booleanas comuns 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 regravando-a como "B = true; if (!A) B = false". Isso seria como produzir salsichas no centro da cidade em plena luz do dia.

As disputas de dados são oficialmente definidas em tipos básicos incorporados, como números 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 existam acessos simultâneos ao mesmo contêiner e que pelo menos um dos acessos o atualize. Atualizar um set<T> em uma linha de execução enquanto ele é simultaneamente lido em outra linha permite que a biblioteca introduza uma disputa de dados. Portanto, isso pode ser informalmente considerado uma "disputa de dados no nível da biblioteca". Por outro lado, atualizar um set<T> em uma linha de execução enquanto outro é simultaneamente lido em outra linha não resulta em uma disputa de dados, porque a biblioteca não introduz uma disputa de dados (de baixo nível) nesse caso.

Normalmente, 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 reescrever 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 disputas de dados. As ferramentas mais básicas são as seguintes:

Bloqueios ou mutexes
Mutexes (std::mutex ou pthread_mutex_t de 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 acessam os mesmos dados. Chamaremos esses e outros recursos semelhantes genericamente de "bloqueios". Adquirir um bloqueio específico de forma consistente 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 deles. 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 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 códigos mais antigos geralmente a usem 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 na linha de execução 1, e não simultaneamente. 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 códigos como o parâmetro precedente se comportem da maneira esperada. Isso normalmente torna os acessos voláteis/atômicos de memória consideravelmente mais caros que os acessos comuns.

Embora o exemplo anterior seja de um caso 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 espera em repetição nem gasto de bateria.

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 reordenação 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 esquecessêmos de declarar a flag volátil no exemplo anterior, a linha de execução 2 poderia ter uma A não inicializada. Ou o compilador poderia decidir que a sinalização não poderia ser modificada durante a repetição 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; enquanto (!reg0) {}
    ... = A
    Ao depurar, é possível que a repetição continue para sempre, apesar de flag ser verdadeiro.
  2. 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, mais especificamente lazySet(). Além disso, 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. Isso será brevemente discutido 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 atuais, em que variáveis volatile são usadas em vez das atomic, e a ordenação de memória é explicitamente proibida por meio da inserção dos chamados limites ou barreiras. Isso requer uma justificativa explícita sobre o reordenação 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 para 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. Caso uma declaração atomic, volatile ou de bloqueio ausente faça com que algum código leia dados desatualizados, pode não ser possível descobrir o motivo analisando os despejos de 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 e 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 linhas 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 a reordenação de acesso pelo hardware. Portanto, por si só, ela é 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.

Muitos 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 ordem da memória não seja importante. Contudo, não há garantia de funcionamento correto com futuros compiladores.

Exemplos

Na maioria dos casos, seria melhor usar um bloqueio (como pthread_mutex_t ou std::mutex do C++11) em vez de uma operação atômica. No entanto, usaremos a segunda opção 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 em outros casos, mas são 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

Começaremos abordando alguns recursos relevantes da linguagem Java que ainda não foram discutidos.

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, programar esses códigos é extremamente complicado. Isso será brevemente discutido a seguir. Para piorar, os especialistas que especificaram o significado desse 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 a que o Java oferece essencialmente as mesmas garantias que C e C++. Novamente, a linguagem oferece alguns primitivos que liberam explicitamente a consistência sequencial, mais especificamente 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, caso a linha de execução 1 grave em um campo volatile e a linha de execução 2 leia esse mesmo campo posteriormente e veja 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, programar em uma volátil é comparável a uma liberação de monitor e ler uma volátil é como uma aquisição monitor.

Há uma grande diferença em comparação à atomic do C++: se escrevermos volatile int x; em Java, 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. Ao contrário 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

Veja a seguir 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++, na verdade, representa 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. Uma disputa de dados ainda existe, em que get() pode acessar mValue ao mesmo tempo 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 sequência, os resultados poderão parecer inconsistentes, porque as chamadas de get() foram reordenadas pelo hardware ou pelo compilador. Podemos corrigir o problema declarando get() como "synchronized". 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 "synchronized", poderíamos declarar mValue com “volatile”. incr() ainda precisa usar synchronize, porque mValue++ não é uma operação atômica. Como isso também evita todas as disputas de dados, 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 será uma ganho 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 "synchronized".

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
            ....
        }
    }
}

O exemplo apresenta 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á da forma esperada.

Apenas a referência sGoodies é volátil. Os acessos aos campos dentro dela não são. Depois que sGoodies é volatile e a ordem da memória está corretamente preservada, os campos não podem ser acessados simultaneamente. A declaração z = sGoodies.x executará um carregamento volátil de MyClass.sGoodies, seguido de 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. Como temos que criá-la apenas uma vez, nós a criamos e a 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 "synchronized" em todas as chamadas. Por esse motivo, essa parte só será feita se 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' Declaration" no apêndice ou o Item 71 ("Use lazy initialization judiciously") do livro Effective Java, 2ª edição, 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 de helper nunca seja examinado fora de um bloco "synchronized".
  2. Declare helper volátil. Com essa pequena alteração, o código no Exemplo J-3 funcionará corretamente no Java 1.5 e versões mais recentes. 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, ela não 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.

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 só poderá ser usada para evitar disputas de dados executando o código quando outra linha de execução atender a 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 (sequencialmente consistente, 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, portanto, precisam aparecer em repetição.

É 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 única ausência no cache. Se não houver contençã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 exigem 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, liberar a ordenação com memory_order ou lazySet() poderá oferecer vantagens de desempenho, mas exigirá uma compreensão mais profunda do que as informações apresentadas até agora. Foi descoberto que uma grande parte do código já 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 de forma mais adequada 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 em “Item 15: Minimize Mutability”. Observe especificamente a importância de declarar os campos "finais" do Java (Bloch).

Mesmo que um objeto seja imutável, lembre-se que comunicá-lo a outra linha de execução sem qualquer tipo de sincronização é uma disputa de dados. Isso pode ser aceitável no Java ocasionalmente (veja abaixo), mas é necessário cuidado. Além disso, é provável que o resultado seja instabilidade do código. Adicione uma declaração volatile, se isso não for atrapalhar muito o desempenho. Em 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 já existente e uma classe imutável não forem adequadas, a instrução synchronized do Java ou lock_guard / unique_lock do C++ precisará 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 tenha muito cuidado 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 será 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". Ele 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 mais informações.

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

O C++11 e versões mais recentes 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 memory_order_seq_cst, normalmente implícito. 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 bem implementado ou 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, é necessário 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 gera 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 de linguagem, o que não será abordado aqui. Por 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 e liberação de bloqueio. 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 demais como 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++.

Considerando esse aviso, apresentamos 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 protegida pelo mesmo bloqueio não poderá disputar, já que não pode haver gravações simultâneas. Em uma situação como essa, o acesso não disputado (carregamento, nesse 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 é permitido não impor nenhuma 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, não há problemas se a ordenação de memória não é garantida e o carregamento é 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 usa 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 é incrementado atomicamente (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.

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

Contadores de eventos simples são um exemplo comum disso. Vale a pena fazer algumas observações sobre esse caso, já que ele é bastante incomum:

  • 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 todas as vezes 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 contadores locais de linha de execução e somando-os no final, por exemplo.
  • Essa 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 um código anterior. Quanto ao caso semelhante que mencionamos anteriormente, o C++ garante que um segundo carregamento desse 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ódigos que tentem 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 mais comum é 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. Um 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 posteriormente 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, nossas melhorias 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 (consistente sequencialmente) a helper. Na verdade, a otimização mais benéfica 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 estará 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 fazer a leitura 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 podem ser visíveis. Para Java, o campo não precisa 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 a 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 pode 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 não são aceitáveis pelo mesmo motivo, 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 que acontecem "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++. Ainda 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 em C++. A especificação atual do Java define apenas o lazySet() de forma bastante 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.
  • Descubra 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, 2ª edição. Por exemplo, evite chamar métodos que precisem ser modificados 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 carregado no mesmo local. Por isso, noções básicas de "atomicidade" são fornecidas sem custo financeiro.

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. 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. Por esse motivo, 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 abordaremos esses detalhes.

O tipo mais básico de garantia de ordenação é o fornecido pelas operações atômicas memory_order_acquiree 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 posteriores. 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 forma 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 flagn 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, nenhum dos dois será reordenado. Normalmente, isso é aplicando adicionando-se 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 a carregamentos consistentes sequencialmente. 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 será como o seguinte:

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 ver mais detalhes, consulte a página da Universidade de Cambridge com os mapeamentos coletados de atômicas em processadores reais (link em inglês).

Em algumas arquiteturas, especialmente a x86, as barreiras "acquire" e "release" (aquisição e liberação, respectivamente) 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 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, este é um bom ponto de partida se você quiser se aprofundar nos modelos de consistência de memória.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
Memory Barriers
Artigo pequeno que resume os problemas.
https://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. Uma discussão sobre disputas 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 qualquer pessoa que programa 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 ultrapassado, especialmente quando aborda 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 para o 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.
java.util.concurrent Resumo do pacote
Java Theory and Practice: Safe Construction Techniques in Java
Este artigo examina em detalhes os perigos das referências que escapam durante a construção do objeto e fornece diretrizes 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 é possível ou não 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 or atomic. Inclui 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ê achou os exemplos nesta página muito não específicos ou se quiser ler a descrição formal da instrução de DMB, leia este 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 informações.
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 arte 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 C++14, que inclui pequenas alterações nessa área em relação a C++11.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(intro: 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 mais detalhes, verifique 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 na programação simultânea". 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 de SMP.
https://pt.wikipedia.org/wiki/algoritmo_dekker
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 a 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. Infelizmente, descrições precisas do modelo de memória do ARM são muito mais complicadas.
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf