Original Article: Using JDK 9 Memory Order Modes
Author: Doug Lea

Usando Modos de Ordem de Memória JDK 9

por Doug Lea.

Introdução

Este guia destina-se principalmente a programadores experientes familiarizados com a concorrência Java, mas não familiarizados com os modos de ordem da memória disponíveis no JDK 9 fornecidos pela VarHandles. Principalmente, ele se concentra em como pensar nos modos ao desenvolver software paralelo. Sinta-se à vontade para ler primeiro o Resumo. (Também sinta-se livre para ajustar o formato de exibição deste documento usando, por exemplo, Vista do leitor do Firefox.)

Para obter os detalhes sintáticos surpreendentemente feios com: Um VarHandle pode ser associado a qualquer campo, elemento de matriz ou estático, permitindo o controle sobre os modos de acesso. VarHandles deve ser declarado como campos finais estáticos e inicializado explicitamente em blocos estáticos. Por convenção, damos VarHandles para nomes de campos que são versões maiúsculas dos nomes dos campos. Por exemplo, em uma classe Point:

import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
class Point {
   volatile int x, y;
   private static final VarHandle X;
   static {
     try {
       X = MethodHandles.lookup().
           findVarHandle(Point.class, "x",
                         int.class);
     } catch (ReflectiveOperationException e) {
       throw new Error(e);
     }
   }
   // ...
}
  
Dentro de algum método Point, o campo x pode ser lido, por exemplo, no modo Acquire usando int v = X.getAcquire(this). Para mais detalhes, veja a Documentação API e JEP 193. Por uma questão de boas práticas, todos os campos destinados a ser acessados simultaneamente devem ser declarados como volatile, que fornece os padrões menos surpreendentes quando eles são acessados diretamente sem VarHandles. Isso não pode ser expresso ao usar VarHandles com elementos de matriz, de modo que as declarações da matriz devem ser documentadas manualmente para suportar o acesso simultâneo.

Além disso, as versões JDK 9 das classes java.util.concurrent.atomic incluem métodos correspondentes a essas construções VarHandle, aplicados aos elementos únicos ou arrays armazenados pelos objetos atômicos associados.

Um acompanhamento planejado apresentará exemplos mais detalhados de usos VarHandle e outras diretrizes de codificação.

Fundo

Nos primeiros dias da programação simultânea (anterior a Java), os computadores eram dispositivos muito mais simples. Os Uniprocessadores passaram por instruções de acesso às células de memória e emulavam a concorrência através da troca de contexto através de threads. Embora muitas das idéias pioneiras sobre coordenação e interferência na programação concorrente estabelecida durante esta era continuem, outros se revelam mal adaptados para sistemas que empregam três formas de paralelismo que surgiram desde então:

  1. Paralelismo da tarefa. Sob a emulação de uniprocessador, se dois threads executam as ações básicas A e B, respectivamente, então, A precede B ou B precede A. Mas com múltiplos núcleos, A e B podem estar desordenados - nem precedem o outro.
  2. O paralelismo da memória. Quando a memória é gerenciada por vários agentes paralelos (especialmente incluindo caches), as variáveis não precisam ser diretamente representadas por nenhum dispositivo físico. Portanto, a noção de uma variável é uma questão de concordância entre threads sobre valores associados a um endereço, que pode ser descrito em termos de "memória" ou "mensagens". Além disso, os processadores e a memória executam operações em unidades de mais de um bit de cada vez (paralelismo no bit a bit), embora nem sempre sejam atômicas.   desordenado - nem precede o outro.
  3. Paralelismo de instrução. Ao invés de um único passo, as CPUs processam as instruções de forma sobreposta, então várias instruções podem estar em processo ao mesmo tempo.

Os conceitos e técnicas para lidar com essas formas de paralelismo estão a amadurecer ao ponto de que as mesmas ideias aparecem regularmente em diferentes linguagens de programação, arquiteturas de processadores e até mesmo sistemas de memória não compartilhada (distribuídos). Este guia se concentra em Java, mas também inclui algumas observações breves sobre outros idiomas, notas sobre problemas de nível de processador que são abstraídos no nível de linguagem e também alguns vínculos com modelos de consistência distribuídos (cluster e nuvem) que de outra forma diferem principalmente com respeito a problemas de tolerância a falhas que normalmente não ocorrem em sistemas de memória compartilhada.

Através destes, nenhuma regra ou modelo único faz sentido para todos os códigos em todos os programas. Portanto, deve haver vários modelos, ou modos, juntamente com as contas de como eles se inter-relacionam. Isso foi visto mesmo nos primeiros dias de concorrência. A idéia de um Monitor introduzido na década de 1960 implicitamente estabeleceu dois modos, levando a regras para código "normal" aparecendo em corpos protegidos por bloqueio e outras regras para acessar e encomendar bloqueios. Na década de 1990, Java introduziu outro modo, volatile, isso não foi formalmente bem especificado até JSR133 em 2004.

A experiência com multicores mostrou que são necessários mais alguns modos para lidar com problemas comuns de programação concorrente. Sem eles, alguns programadores sobre-sincronizam o código, o que pode tornar os programas lentos, alguns programadores são sincronizados com o código, o que pode fazer programas errados, e outros programadores trabalham em torno de limitações usando operações não padronizadas disponíveis em JVMs e processadores particulares, o que pode fazer programas insegura.

Os novos modos de ordem da memória são definidos com efeito cumulativo, do mais fraco ao mais forte: Plain, Opaque, Release / Acquire e Volatile. Os modos Plain e Volatile existentes são definidos de forma compatível com os formulários pré-JDK 9. Qualquer propriedade garantida de um modo mais fraco, mais mais, é válida para um modo mais forte. (Por outro lado, as implementações podem usar um modo mais forte do que o solicitado para qualquer acesso). No JDK 9, estes são fornecidos sem uma especificação formal completa. Este documento não inclui uma especificação de modos de ordem da memória. Em vez disso, discute o uso em termos de suas propriedades (principalmente: comutatividade, coerência, causalidade e consenso) que se construem um sobre o outro. As regras de consistência de memória resultantes podem ser pensadas em termos de protocolos de cache cada vez mais restritivos.

Como os modos mais fortes impõem mais restrições de ordenamento, eles reduzem o potencial paralelismo, em pelo menos um dos sentidos acima - se as operações forem realizadas em paralelo, o pedido pode exigir que um bloco de atividade (reduzindo o paralelismo total e adicionando despesas gerais) esperando a conclusão de outro . Mas o pedido também pode fornecer garantias em que os programas dependem. Quando você não impõe restrições necessárias, eles podem se manter de qualquer maneira às vezes, mas nem sempre, resultando em erros de software difíceis de replicar.

Quando as construções de sincronização e ordenação mais fortes, como os monitores, foram criadas pela primeira vez, as restrições resultantes sobre o paralelismo não causaram muito problema porque não havia muito paralelismo disponível de qualquer maneira. Mas agora, as escolhas geralmente implicam compromissos de engenharia. Ativar o paralelismo geralmente melhora a escalabilidade. Nos programas paralelos mais rápidos mas menos controlados, cada segmento acessa apenas variáveis locais e encontra nenhuma solicitação ou restrições de recursos. Mas outros casos podem encontrar problemas de tempo, espaço, energia e complexidade que nem sempre resultam em melhor desempenho em qualquer programa ou plataforma.

O uso de múltiplos modos de consistência também pode tornar a correção mais difícil de estabelecer. A existência de uma "corrida de dados" nem sempre é um sim / não importa, mas é o resultado de usar um modo mais fraco do que você precisava para preservar a correção. Além disso, muitos erros de concorrência têm pouco a ver com os modos em si. Por exemplo, nenhuma escolha de modo irá corrigir erros de verificação e depois do formulário if (v != null) use(v), onde v é uma variável atualizada simultaneamente que pode tornar-se nula entre a verificação e o uso. As ferramentas de concorrência existentes não fazem essas distinções finas, de modo que a análise e o teste podem ser mais difíceis. Além disso, os detalhes do uso de modos mais fracos, especialmente na programação sem bloqueio, podem entrar em conflito com regras e convenções estabelecidas em bloqueio, de modo que alguns cuidados podem ser necessários ao escolher entre formas equivalentes de expressar restrições. Mas se você está lendo isso, provavelmente você está interessado em explorar os compromissos encontrados ao organizar e explorar o paralelismo.

Encomendar Relações

Os modos de ordem da memória descrevem as relações entre a memória acessos (lê, escreve e atualizações atômicas), e apenas restringe incidentalmente outros cálculos. Essas relações são definidas sobre acessos como leitura, gravação e atualização eventos, não os valores acessados. As relações se concentram em encomendando porque eles restringem o potencial paralelismo que seria permitido pela falta de restrições de pedidos. Os eventos de acesso podem ter durações observáveis, mas são limitados em termos de pontos de "confirmação" instantâneos.

Aqui está uma terminologia sobre ordenando relações como aplicado aos eventos: Strict ordens irreflexivas agem como menos do que, não menos do que iguais. Em uma (rigorosa) ordem total cada evento é ordenado em relação a qualquer outro evento, resultando em uma cadeia de eventos linear (seqüencial). Em uma (rigorosa) ordem parcial, nenhum dos eventos não precisa estar relacionado (por isso pode ser concorrente), mas não há ciclos (circularidades). Uma extensão linear (também conhecido como um tipo topológico) de uma ordem parcial é uma das possivelmente muitas sequencializações (ordens totais) que obedecem a todas as suas restrições de pedidos. Em uma ordem parcial, dois eventos podem não ser ordenados, mas em qualquer extensão linear, um precede o outro.

A maioria das propriedades de pedidos de memória são, em última instância, baseadas em apenas duas (rigorosas) relações, uma dentro de threads e uma entre threads. Conforme descrito abaixo, intratread precedência local indica que o acesso A precede o acesso B no mesmo segmento. O leitura ordens de relação intercurso acessos: Para a variável x, se Read Rx lê da escrita de Write Wx, então Wx deve ocorrer antes de Rx. O correspondente lê-de funciona de cada leitura para a origem. A escrita tem a direcionalidade oposta e pode ser mais simples de usar nas especificações porque é uma função, e não apenas uma relação.

Essas duas relações podem ser usadas em conjunto para definir a antecedência relação que liga as ordenações temporais nos tópicos com aqueles em tópicos. Isso assume a mesma forma que o original acontece antes relação definida por Leslie Lamport em 1978. Mas porque acontece-antes também foi definido de várias maneiras sutilmente diferentes quando aplicado às especificações do modelo de memória, usaremos esse termo mais neutro para evitar a confusão. (A definição do dicionário comum de "antecedentes" é, apropriadamente, "precede no tempo", e assim pode ser um termo melhor de qualquer maneira.)

O acesso A antecede o acesso B se:

  • [Intrathread] Um local precede B (dentro de um segmento), ou
  • [Interthread] A é lido por B (em outro segmento), ou
  • [Transitivity] Para algum acesso eu, (A antecede I) e (I antecede B)

Conforme definido aqui, a antecedência é apenas uma relação sem quaisquer propriedades garantidas além da transitividade (a cláusula final) - as ordens intrataveis e interthread não são necessárias para serem consistentes entre si. Os modos de ordem da memória impõem restrições à antecedência e / ou ordem de execução -- a ordem (parcial) de acessos em uma execução de programa sem consideração para antecedência, bem como restrições (projeções) dessas ordens para eventos selecionados, por exemplo substituidores para eventos selecionados, por exemplo para a mesma variável.

Quando representados como gráficos com eventos como nós e relações como links, ordens totais formam listas lineares e formulários de pedidos parciais DAGs -- gráficos acíclicos dirigidos. Outra maneira de representar eventos ordenados é dar-lhes tags numéricas. Estes podem corresponder a números de versão ou timestamps que pode ser usado e comparado como Relógios vetoriais.

As garantias sobre as propriedades de pedidos não implicam necessariamente que qualquer observador possa conhecer as ordens antecipadamente ou validá-las após o fato. Eles são invariantes em que os programadores podem confiar e / ou fornecer para ajudar a estabelecer a correção (ou pelo menos a possibilidade de correção) dos programas. Por exemplo, alguns erros de corrida de dados resultam quando não há restrições suficientes para ter certeza de que uma determinada leitura tenha apenas uma possível escrita que possa ler.

Modo simples

ModoSimples aplica-se a acessos sintáticos de campos de objetos simples (não voláteis) (como em int v = aPoint.x), bem como estática e elementos de matrizes. Também se aplica ao padrão VarHandle get e set acesso. Mesmo que se comporta da mesma maneira que sempre, suas propriedades interagem com os novos modos e operações VarHandle de maneiras melhor explicadas em termos de uma rápida revisão de aspectos relevantes do design do processador e do compilador.

O modo simples amplia o modo "Local", de outra forma, sem nome em que todos os acessos são para argumentos e variáveis de método-local; por exemplo, o código para expressões e funções puras. O modo simples mantém precedência local ordem para acessos, que não precisa combinar a ordem de declaração de código-fonte ou a ordem de instrução da máquina e não é, em geral, até uma ordem total (seqüencial). Para ilustrar, considere esta declaração baseada em expressão, onde todas as variáveis são ints do método-local:

  d = (a + b) * (c + b);
  
Isso pode ser compilado em instruções de máquina baseadas no registro do formulário (onde os r são registros):
  1: load a, r1
  2: load b, r2
  3: add r1, r2, r3
  4: load c, r4
  5: load b, r5
  6: add r4, r5, r6
  7: mul r3, r6, r7
  8: store r7, d
  
Mas os compiladores podem fazer algumas escolhas diferentes ao mapear a expressão original semelhante a uma árvore (e paralelizada) em um fluxo de instruções seqüencial. Entre várias opções legais seria reordenar as duas primeiras instruções. Esta é uma aplicação de paralelo Comutatividade: neste contexto, essas operações têm o mesmo efeito, seja executadas em qualquer ordem, ou mesmo ao mesmo tempo (independentemente das regras de avaliação de expressão do Java para a esquerda para a direita).

Tais decisões dos compiladores sobre a ordem das instruções podem não importar muito, porque os próprios processadores de commodities realizam execução de instruções paralela ("fora de ordem"). A maioria dos processadores controla a execução seguindo as dependências de conclusão, usando as mesmas técnicas observadas ao programar as Funções Complementares. Por exemplo, todas as cargas podem ser iniciadas cedo, desencadeando as instruções de adição (possivelmente em paralelo em CPUs superscalares) quando os valores estão disponíveis em registros e, de forma semelhante, desencadeiam a multiplicação quando as somas forem completadas. Mesmo que duas instruções sejam iniciadas em ordem seqüencial, elas podem completar (confirmar) em uma ordem diferente, ou ao mesmo tempo. Portanto, a precedência local, definida com relação a esses pontos de confirmação, não precisa incluir nenhuma relação de ordem prévia / posterior entre algumas ações. Por exemplo, uma possível execução pode parecer (onde as instruções na mesma linha operam em paralelo):

 load a, r1 | load b, r2 | load c, r4 | load b, r5
 add r1, r2, r3 | add r4, r5, r6
 mul r3, r6, r7
 store r7, d
  

As operações que aparecem em cada linha não precisam realmente ser executadas em paralelo; também é permitida qualquer permutação seqüencial de cada linha; As instruções emitidas por um compilador podem ser devidamente ordenadas. Qualquer uma dessas execuções pode ocorrer mesmo se a fonte original dividir a avaliação como:

  tmp = (a + b);
  d = tmp * (c + b);
  
Em outras palavras, o uso de ponto-e-vírgula como separadores de instruções não precisa ter um impacto direto no seqüenciamento da execução. Isso incomoda algumas pessoas (veja O semicolon silencioso de mudança). Mas é um meio eficaz de recuperar algum paralelismo de grão fino que existe no código-fonte, mas, de outra forma, se perde no código da máquina. E se o seu objetivo é maximizar o paralelismo, torna-se útil que o paralelismo seja ativado automaticamente no menor nível de processamento. A maioria dos usuários está feliz o suficiente sobre as conseqüentes melhorias de desempenho para comprar e usar sistemas com uma execução cada vez mais agressiva fora de ordem, devido aos esforços combinados de compiladores, ferramentas, compiladores JIT e processadores, principalmente para reduzir o impacto de latência da memória.

Com a ajuda da otimização de compiladores, os processadores podem eliminar cálculos e acessos desnecessários em um corpo de código usando análises de fluxo de dados e podem remover dependências desnecessárias usando transformações como SSA e renomeação. Diferentes processadores e compiladores variam em quão extensivamente eles executam tais otimizações. Por exemplo, alguns podem executar especulativamente o código dentro de um efeito condicional condicional, desfazendo e descartando os efeitos, se a condição for falsa. E assim por diante. Os limites do método não precisam definir os limites de tais transformações. Os métodos podem ser inlined ou otimizado interproceduralmente, mesmo na medida em que um segmento inteiro é um corpo de código.

Embora a computação possa ser paralela por padrão no nível da instrução, no modo Local, os resultados observáveis da execução desencadeada por dependência são sempre equivalentes aos da execução seqüencial puramente passo a passo, independentemente de qualquer otimização permitida realmente ocorrer. As relações exatas entre ordem de instrução e ordem de execução que mantêm o associado semântica do uniprocessador não importa, e nem pode ser detectado (exceto possivelmente por ferramentas como debugers). Não há controles de programador de nível de fonte disponíveis para alterar esses relacionamentos.

Isso também se mantém isolado confinado variáveis - as criadas e usadas apenas pela linha atual. Uma variável confinada em thread não possui acessos no interthread leitura relação, como pode ser descoberto pela análise do escape do compilador, caso em que a variável pode então ser tratada como se fosse local.

Propriedades semelhantes mantêm em modo Plain completo quando todas as variáveis são acessadas por apenas um segmento ao longo de uma região de código; por exemplo, quando todos estão corretamente protegidos por um bloqueio em um métodosynchronized. Todos os acessos simples na região, possivelmente exceto as leituras iniciais e as gravações finais, estão dentro do segmento e podem agir de forma transitória como se houvesse confinamento. As definições dos modos mais fortes abaixo são expressas apenas em termos de acessos interthread, porque as restrições por variável que adicionam são subsumidas por semânticas de uniprocessador que ocupam acessos estritamente locais.

No entanto, quando o modo liso é usado com variáveis acessadas simultaneamente por vários segmentos (ou seja, na presença de corridas de dados), as correspondências entre a ordem da instrução e a ordenação (ou a falta) de acessos variáveis são muitas vezes observáveis. Não só os acessos podem ocorrer de forma detectável em diferentes pedidos, eles podem não ocorrer de forma alguma. Por exemplo, a execução otimizada de int a = p.x; ... int b = p.x pode substituir a segunda leitura por int b = a, e execução de p.x = 1; ... p.x = 2 pode eliminar a primeira escrita e até a segunda se p não é usado novamente em um corpo de fio. Não há ocorrências extras que não estão presentes no código-fonte, mas as gravações podem parecer "prescientes" - obtidas de forma observável antes de serem programadas para ocorrer: entre os casos de aparência mais louca resultantes de "riscos de gravação pós-leitura (WAR)" Onde r1 = x; y = r2; age como se fosse reordenado para y = r2; r1 = x; quando o valor de y afeta o valor atribuído a x em outro segmento. Além disso, quando vários outros tópicos lêem o modo Planície, alguns podem vê-los em ordens diferentes do que outros.

Os possíveis resultados incluem aqueles em que parece que os processadores cometem erros assumindo a presença de execuções (agendamentos multiprocessados) que na verdade não ocorrem; por exemplo (mas não limitado a) execuções em que nenhum outro segmento executa simultaneamente, bem como aqueles decorrentes de análises e otimizações de compilação inter-thread. Por outro lado, erros de corrida de dados podem resultar de programadores assumindo a ausência de (ou não percebendo a possível presença de) execuções que realmente ocorrem. Alguns desses problemas são comuns o suficiente para receber nomes. Por exemplo, nos sistemas de transações, os erros de "leitura não recorrível" ocorrem quando duas leituras da mesma variável em um corpo de transação obtêm valores diferentes, mas a correção depende dos valores sendo os mesmos.

Além disso, enquanto o Java Plain acessa int, char, short, float, byte, e os tipos de referência são atômico primitivamente bitwise, para os outros, long, double, bem como tipos de valor compostos planejados para lançamentos futuros do JDK, é possível ler com raza um valor com alguns bits de uma escrita por um segmento, e outros bits de outro, com resultados inutilizáveis.

Devido a qualquer combinação destes mecanismos, em programas racy, pode haver apenas uma relação observada fraca e complicada entre o código fonte e a ordem dos acessos variáveis. Infelizmente, as especificações do modelo de memória formal devem caracterizar os limites desta relação, que continua a ser um problema não resolvido (embora existam algumas abordagens prometidas em progresso). Se as especificações são muito fracas, elas permitem involuntariamente execuções perigosamente erradas, incluindo "fora do ar" que lê que violaria as garantias de segurança e segurança Java. Mas se muito forte, eles inadvertidamente não permitem otimizações válidas. (E, na ausência de corridas de dados, eles devem manter a propriedade "uniprocessador" que os efeitos são equivalentes à execução na ordem do programa de origem).

No entanto, os detalhes dificilmente são importantes. Nenhuma das restrições de acesso para variáveis compartilhadas necessárias em programas multiprocessados é mantida de forma confiável sem controle explícito. A falta de controle pode levar a resultados quase inexplicáveis. Com algumas exceções observadas abaixo, você pode tratar dois acessos de modo simples em um corpo de código como se não estivessem desordenados uns com os outros e, em seguida, sujeitos a otimização adicional. A experiência mostrou que as suposições sobre as encomendas garantidas no modo liso são muitas vezes erradas, o que é uma base para o bom conselho para evitar corridas de dados em modo simples, a menos que os programas possam ser exibidos permanecendo corretos, mesmo que racy Plain lê retorna aleatoriamente qualquer valor potencialmente gravável. Se um programa requer ordem (e / ou atomicidade) para a correção, organize o acesso variável compartilhado de forma explícita e restrinja o modo liso para a computação local em valores.

Notas e leitura adicional

O modo simples é utilizável nos mesmos contextos que o modo "não atômico" em C / C ++ 11. Java e C / C ++ têm muitas diferenças semânticas, algumas decorrentes do fato de que em C / C ++, a falha ao usar uma construção de linguagem de maneiras especificadas (incluindo permitir corridas de dados no modo Planal) pode resultar em Comportamento Indefinido, que pode incluir falhas no programa . Em Java, os efeitos podem ser surpreendentes (e atualmente incompletamente especificados), mas ainda estão circunscritos. Essas diferenças não afetam a maioria dos usos dos modos de pedidos de memória, que de outra forma são definidos de forma semelhante (com algumas diferenças de nomeação) em todos os idiomas.

Ao contrário do caso para linguagens de programação, os modelos de memória de hardware podem definir o análogo de precedência local ("ordem de programa preservada") enumerando exaustivamente os efeitos das instruções. Por exemplo, veja "Um Tutorial Introdução aos Modelos de Memória Relaxada ARM e POWER" por Luc Maranget, Susmit Sarkar e Peter Sewell. As GPUs estendem essas regras a instruções que operam em variáveis múltiplas (contíguas) ao mesmo tempo, e muitas vezes incluem tipos de memória ou modos em que as variáveis não podem ser compartilhadas entre threads.

As técnicas baseadas em dependências são vistas em um nível superior em córregos paralelos de Java, Fontes Complementares, Fluxos e outras APIs fluentes com base em expressões que descrevem cálculos possivelmente paralelos. Através destes, automatizar o paralelismo depende de representar (ou reconstruir) fragmentos do programa como DAG, e não de seqüências. Algumas linguagem de fluxo de dados oferecem sintaxe mais diretamente correspondente ao DAG. Como APIs fluentes, eles podem evitar confusão sobre questões como se os pontos-e-vírgula indicam sequenciação, mas encontre outros sobre escopos e contextos. (Se houvesse uma maneira perfeita de expressar paralelismo e ordem, todos estaríamos usando isso).

Nas abordagens transacionais de concorrência, os corpos de códigos de transações são explicitamente delimitados por programadores, em vez de implícitos na estrutura de um programa. Eles encontram os mesmos problemas subjacentes, às vezes descritos usando uma terminologia diferente. Por exemplo, as corridas são geralmente categorizadas em termos de níveis de isolamento, não solicitando restrições.

Muitas APIs de nível superior podem ser projetadas em termos de operações comutativas que permitem mais paralelismo, exigindo menos controle de pedidos, conforme discutido em "A regra de comutatividade escalável: projetando software escalável para processadores Multicore" por Clements et al, TOCS 2015.

Abordagens para evitar a má especificação da relação entre a ordem do programa fonte e o modo liso incluem semanticas "promissoras", em que as escrituras são atribuídas conceitualmente números de versão do timestamp, e as regras operacionais evitam atribuir as impossíveis. (A abordagem operacional para formular tais regras é semelhante à do original Modelo de memória JLS versão 1, mas não o JMM atual (JLS5-9), que é expresso em termos de relações de pedidos.)

Modo opaco

Modo opaco, obtido usando VarHandle getOpaque e setOpaque, adiciona restrições sobre o modo liso que fornecem uma consciência mínima de um assunto variável para acesso interthread quando todos os acessos usam o modo Opaque (ou mais forte):

  • Coerência. As substituições visíveis para cada variável são totalmente ordenadas.

    O pedido de substituição por variável é garantido para ser consistente tanto com a relação de leitura (relacionando Escritos com as Lições posteriores) quanto com a "antidependência" (de-ler) relação de lê para escritas posteriores - uma leitura de uma determinada escrita deve preceder uma sobregravação observada dessa gravação. Isso pode ser expresso formalmente estabelecendo uma restrição de ordem parcial (acíclica) nos eventos correspondentes, e exigindo que as escritas observadas ocorram em uma extensão linear (total) dessa ordem.

    Se o modo Opaque (ou qualquer mais forte) for usado para todos os acessos, as atualizações não aparecem fora de ordem. Observe que isso não se manteria necessariamente se apenas as leituras (mas não as gravações) fossem realizadas no modo Opaque, o Modo liso pode ignorar, adiar ou reordenar algumas gravações.

  • Progresso. Os escritos são eventualmente visíveis.

    Esta é uma propriedade definidora de arquiteturas multiprocessador compatíveis com cache (às vezes definidas como um aspecto de coerência em si) e também (através de mensagens explícitas) de armazenamento de dados distribuídos. As garantias de progresso podem ser formalizadas em termos de consistência quiescente, consistência final, e/ou liberdade de obstrução. Todos eles têm o mesmo impacto de uso. Por exemplo, nas construções em que a única modificação de alguma variável x é para uma thread escrever no modo Opaque (ou mais forte), X.setOpaque(this, 1), qualquer outro fio girando em while(X.getOpaque(this)!=1){} terminará eventualmente.

    Observe que esta garantia NÃO se mantém no modo liso, em que os loops de rotação podem (e costumam fazer) infinitamente loop - eles não são obrigados a notar que uma gravação já ocorreu em outro segmento se não fosse visto no primeiro encontro.

  • Atomicidade Bitwise. Se o modo Opaque (ou qualquer mais forte) for usado para todos os acessos, lê de todos os tipos, incluindo long e double, são garantidos para não misturar os bits de múltiplas gravações.

O nome "opaco" decorre da idéia de que as variáveis compartilhadas não precisam ser lidas ou escritas apenas pelo segmento atual, portanto, os valores atuais ou seus usos podem não ser conhecidos localmente, exigindo interação com os sistemas de memória. No entanto, o modo Opaque não impõe diretamente quaisquer restrições de ordenação em relação a outras variáveis além do modo liso. Portanto, você nem sempre pode dizer quando o modo Opaque acessará uma variável em relação a outros acessos simples, e ler um valor no modo Opaque não precisa dizer nada sobre os valores de quaisquer outras variáveis. Além disso, embora a coerência garanta um determinado pedido, não garante, por si só, ordens específicas, em particular sobre os pares de leitura e gravação (as operações de RMW e CAS descritas abaixo ampliam a coerência para fazê-lo). Apesar dessas limitações, o modo opaco ainda às vezes se aplica de forma útil. Por exemplo, ao monitorar e coletar indicadores de progresso emitidos por vários segmentos, pode ser aceitável que os resultados sejam eventualmente precisos após quiescência.

O modo opaco também se aplica quando as restrições de ordenação envolventes descritas abaixo são fortes o suficiente para que o controle de pedidos adicional não tenha impacto, embora apenas o uso do modo Plain aqui também esteja OK para variáveis atômicas primitivas. Em outros casos, outras restrições de pedidos em um programa, combinadas com requisitos de pedidos por variável, podem fornecer limites aceitáveis sobre quando os acessos ocorrem e / ou seus possíveis valores.

Quando aplicado a variáveis de thread-confined (isto é, aqueles sem acessos na relação de leitura interthread), nenhuma das restrições acima pode afetar o comportamento observável, portanto, o acesso no modo Opaque pode ser implementado da mesma maneira que o acesso Local Plain (que também atua coerente da perspectiva do fio de execução).

Notas e leitura adicional

O modo opaco foi inspirado pelo Linux "ACCESS_ONCE". É utilizável nos mesmos contextos que C ++ atomic memory_order_relaxed. Enquanto outras implementações do modo Opaque são possíveis, nas plataformas atuais, as JVMs lêem ou escrevem atômicamente a variável na ordem do programa e dependem dos mecanismos subjacentes de coerência do cache para manter as propriedades acima, desabilitando o cache secundário de valores nos locais e registros permitidos na planície modo. (Mesmo que as restrições das camadas do modo Opaque sobre o modo liso, em modo implementação, o modo liso pode ser pensado como estendendo otimizações de cache locais adicionais em relação ao modo Opaque.) Como subproduto, o modo Opaque às vezes é útil heuristicamente para desativar artificialmente algumas otimizações em microbenchmarks. As implementações de hardware (bem como especificações detalhadas) de coerência variam em plataformas e continuam a evoluir. Alguns processadores e GPUs suportam modos especiais não coerentes projetados principalmente para transferência em massa que não são atualmente acessíveis a partir de Java, mas podem ser usados ​​quando aplicável pelas JVMs.

Nunca é uma boa idéia usar rotações nulas esperando por valores de variáveis. Use Thread.onSpinWait, Thread.yield e / ou bloqueando a sincronização para melhor lidar com o fato de que "eventualmente" pode ser um longo tempo, especialmente quando há mais threads do que núcleos em um sistema.

A maioria das apresentações de consistência e técnicas que o exploram, especialmente em configurações distribuídas, aplicam-no a modos mais fortes (onde também é válido). Veja, por exemplo: "Coordination Avoidance in Database Systems" por Peter Bailis et al. VLDB 2015.

Modo Liberar / Adquirir (RA)

O modo Liberar / Adquirir (ou RA) é obtido usando VarHandle setRelease, getAcquire e métodos relacionados, e adiciona uma causalidade restrição ao modo Opaque. Isso pode ser expresso como uma propriedade de acessos interthread:

Para cada variável, a relação de antecedência, restrita aos acessos de Liberação / Adquirir (ou mais forte) interthread, é uma ordem parcial.
Mais regras intratorelas que se estendem (acumulam) propriedades de antecedência para os acessos de modo possivelmente mais fracos possíveis, dentro do mesmo Thread T (veja abaixo algumas ressalvas sobre o modo Plain):
  • Se o acesso A preceder o modo de liberação de intertorno (ou mais forte), escreva W na ordem do programa de origem, então A precede W na ordem de precedência local para o segmento T
  • Se o modo de acesso interthread (ou mais forte), ler R precede o acesso A na ordem do programa de origem, então R precede A na ordem de precedência local para Thread T.

Esta é a principal idéia por trás causalmente consistente sistemas, incluindo a maioria das lojas de dados distribuídos. Causalidade (no sentido de ordenamento parcial mais acumulação) é essencial na maioria das formas de comunicação. Por exemplo, se eu fizer o jantar, e depois digo que o jantar está pronto, e você me ouve, então você pode ter certeza de que o jantar existe. Preservar a consistência causal significa que, ao ouvir "pronto", você tem acesso à sua causa, "jantar". Claro, o modo RA não tem conhecimento desta relação; apenas preserva as ordens. A propriedade de ordem parcial significa que a causalidade não é cíclica. Como um exemplo de código mínimo, supondo que os únicos acessos de variáveis sejam os exibidos:

 volatile int ready; // Initially 0, with VarHandle READY
 int dinner;         // mode does not matter here

 Thread 1                   |  Thread 2
 dinner = 17;               |  if (READY.getAcquire(this) == 1)
 READY.setRelease(this, 1); |    int d = dinner; // sees 17
Isso não se manteria necessariamente se ready foram usados em um modo mais fraco. A maioria dos usos não emprega um sinal pronto; Em vez disso, o produtor escreve uma referência aos dados, e o consumidor lê a referência e dereferencia-lo. Como em:
 class Dinner {
   int desc;
   Dinner(int d) { desc = d; }
 }
 volatile Dinner meal; // Initially null, with VarHandle MEAL

 Thread 1                   |  Thread 2
 Dinner f = new Dinner(17); |  Dinner m = MEAL.getAcquire();
 MEAL.setRelease(f);        |  if (m != null)
                            |    int d = m.desc; // sees 17

A garantia de causalidade do modo RA é necessária em projetos de consumidores de produtores, projetos de passagem de mensagens e muitos outros. Quase todos os componentes java.util.concurrent incluem especificações de consistência causais ("acontece-antes") em sua documentação API.

O modo RA raramente é suficientemente forte para garantir resultados sensíveis quando é possível que dois ou mais threads criem a mesma variável ao mesmo tempo. A maioria dos usos recomendados podem ser descritos em termos de propriedade, em que apenas o proprietário pode escrever, mas outros podem ler. Como base para esse raciocínio, quando uma discussão inicialmente constrói um objeto, é o único proprietário até mesmo torná-lo disponível para outros segmentos. Os projetos podem, adicionalmente, contar com um par de liberação-aquisição que atua como uma propriedade transferir -- depois de tornar acessível um objeto, o proprietário (anterior) nunca o usa novamente. A aplicação automática desta regra constitui a base da maioria das diferenças entre as abordagens de "passagem de mensagem" versus "memória compartilhada" para a concorrência. Alguns componentes de mensagens de propósito especial, como filas de produtor único, impõem essa restrição como uma condição que os usuários do componente devem obedecer. Além disso, os bloqueios podem ser usados para garantir a propriedade transitória e, nesse sentido, estender as técnicas de Liberação / Adquirir. No entanto, muitos usos do modo RA são conceitualmente mais próximos de "transmissões" não ordenadas com vários leitores.

Cercas RA

É possível utilizar o modo RA de forma mais explícita, que também ilustra como fortalece as restrições de pedidos locais. Ao invés de X.setRelease(this, v), você pode usar o modo Opaque (ou o Modo liso se x for primariamente atômico no bit a bit), precedido de uma Liberação: VarHandle.releaseFence(); x = v;. E, da mesma forma, em vez de int v = X.getAcquire(this), você pode seguir um acesso em modo liso ou opaco com uma aquisição: int v = x; VarHandle.acquireFence().

Um releaseFence garante que todos os acessos contínuos (não locais escrevem e lêem) completem antes de executar outra gravação. É uma "vedação" no sentido de separar todos os acessos anteriores versus todas as seguintes escritas. Da mesma forma, um adquirente assegura que todas as leituras em curso sejam concluídas antes de realizar outro acesso. Se um adquirente separar duas leituras, a segunda leitura não pode reutilizar um valor antigo que viu antes da vedação - uma adquirência "invalida" (tudo) lê anterior. Note-se que as declarações do método de vedação estão entre os poucos contextos em que o uso de um ponto-e-vírgula afeta a seqüência. No entanto, os efeitos podem ser entrelaçados com acessos e computação estritamente locais, portanto ainda não funcionam literalmente na ordem do código-fonte. Da mesma forma, em uma expressão como X.getAcquire() + Y.get() a ordem de avaliação da esquerda para a direita é preservada.

Esta codificação mostra que, tratadas como eventos, as cercas RA se conformam com a ordem parcial primária (confiando quando necessário em protocolos inter-core de nível de hardware) e os acessos são "carregados" pelas regras de precedência locais. No entanto, os acessos do modo RA não são necessariamente implementados usando cercas. Em vez disso, são definidos para permitir o uso de instruções de acesso para fins especiais quando disponíveis, bem como para permitir várias otimizações possíveis. Em particular, os acessos RA de acesso interno podem ser implementados do mesmo modo que o modo Planície local, ou mesmo eliminados inteiramente, desde que todas as restrições necessárias sejam mantidas.

Modos mistos e especializações

As operações de liberação e aquisição garantem modos relativamente baratos de permitir a comunicação entre os tópicos. As pessoas descobriram técnicas e idiomas que podem fazer alguns desses efeitos ainda mais baratos para obter.

Ao preservar a consistência causal em um componente de software, geralmente não é necessário usar o modo Liberar / Adquirir para cada acesso. Por exemplo, se você ler uma referência a um nó com campos imutáveis no modo de aquisição, você pode usar o modo liso para acessar os campos do nó.

Outros casos podem exigir mais cuidados para obter os efeitos pretendidos. Geralmente, é recomendável ler um valor usando getAcquire (uma vez) em uma variável local (possivelmente marcando isso final por ênfase) antes de usar em cálculos de modo simples, garantindo que cada uso tenha o mesmo valor; O código java.util.concurrent usa esta convenção baseada em SSA (atribuição única estática) para melhorar a confiança sobre a sua correção. Cuidado com as otimizações do compilador que podem eliminar a necessidade de acessar variáveis. Por exemplo, se um compilador de otimização determinar que alguma variável x não pode ser zero, então if (X.getAcquire(this)!=0) pode não ter qualquer efeito de pedido. Da mesma forma, se um compilador de otimização pode pré-computar algumas ou todas as partes de uma expressão de acesso ao modo liso (por exemplo, uma matriz de matriz indexada), então, colocar o próprio acesso depois de uma operação de Adquirir pode não ter o efeito esperado. Observe também que uma gravação em modo Liberação não garante que a escrita seja emitida "imediatamente"; não é necessariamente encomendado em relação a escritas subseqüentes.

Em geral, os acessos modificados tendem a ser mais fáceis para os compiladores serem otimizados do que as cercas quando são locais de thread e, portanto, podem reduzir a sobrecarga quando um código seguro e seguro é executado em contextos de um único segmento. Por outro lado, cercas explícitas são mais fáceis de otimizar manualmente e aplicar nos casos em que o controle de pedidos não está vinculado ao acesso de uma determinada variável. Por exemplo, em alguns projetos otimistas, uma série de possíveis leituras lisas devem ser seguidas por uma adquirida antes de executar uma etapa de validação. E em alguns projetos de fábrica, um número possivelmente de modo simples escreve a construção de um conjunto de objetos deve ser seguido por um releaseFence antes de serem publicados. Estes correspondem à otimização de movimentação adquiridas o mais cedo possível, e releaseFences o mais tarde possível, em ambos os casos às vezes permitindo que eles sejam mesclados com outros. Uma forma comum de içamento se aplica em muitas estruturas de dados vinculadas (incluindo listas e árvores de mopst), onde basta usar uma única veda de aquisição ou acesso ao ler a cabeça, desde que todos os outros nós sejam garantidos (transitivamente) somente da cabeça. Além disso, se cada link for qualificado para ser lido apenas uma vez durante o percurso, o modo simples é suficiente. Este é um aspecto das técnicas baseadas em RCU descritas por McKenney.

Como eles impõem menos restrições de pedidos, os acessos de RA e as cercas devem ser mais baratos do que as operações de modo volátil, tanto em relação à sobrecarga como às oportunidades de paralelismo quando mapeadas para processadores. Os compiladores devem emitir código que mantém restrições em relação aos modelos de memória no nível da plataforma. Pode ser bom se todos os processadores tenham instruções ou regras correspondentes exatamente aos modos de ordem da memória, mas nenhum, então os detalhes dos efeitos em todos eles podem ser diferentes. Nos sistemas TSO (incluindo x86), o uso não precisa resultar em instruções adicionais da máquina. Em alguns outros sistemas, as aquisições podem ser implementadas usando instruções de controle de acordo com as regras de dependência do nível da máquina. Alguns processadores (incluindo ARM) suportam uma vedação StoreStore que é mais barata do que uma releaseFence, mas pode ser usada no modo Release / Acquire somente quando se sabe que a cerco da loja de carga não pode (ou não é obrigado) fazer uma diferença; ou seja, que é impossível ou aceitável para uma leitura anterior retornar um valor que foi modificado como conseqüência da gravação posterior. A classe VarHandle inclui StoreStoreFence, bem como métodos loadLoadFence simétricos que podem afrouxar as restrições de ordenação RA associadas quando aplicável. Esses métodos existem para permitir micro-otimizações que podem melhorar o desempenho em algumas plataformas, sem impactar outras de uma maneira ou de outra.

Como um caso especial delicado (mas comumente explorado) das considerações acima, as leituras de estilo adquirível de campos imutáveis de objetos recém-construídos não requerem uma vedação explícita ou acesso modificado. O modo simples lê é suficiente: se o consumidor não viu o novo antes, não pode ter valores obsoletos que deve ignorar ou descartar e não pode executar a leitura até que conheça o endereço. Em encontros subseqüentes, a reutilização de valores antigos está OK, porque eles não podem ter mudado. Este raciocínio baseia-se na única exceção defendida e reconhecida à regra de nunca fazer suposições sobre ordem de precedência local: a referência (endereço) de um objeto new é assumido nunca ser conhecido e impossível especular até a criação. Este pressuposto também é dependente de outros requisitos de segurança Java.

As técnicas resultantes são usadas em Java final implementações de campo e são a razão pela qual as garantias especificadas para os campos finais estão condicionadas a que os construtores não vazem referências a objetos antes do retorno do construtor. Classes com campos finais são normalmente implementados através da emissão de uma forma de vedação de lançamento após o retorno do construtor. Além disso, porque nada precisa ser garantido sobre as interações com leituras do construtor, basta uma StoreStoreFence. Técnicas similares podem ser aplicadas em outros contextos, mas podem ser inaceitavelmente frágeis. Por exemplo, o código que funciona quando os objetos associados são sempre recém construídos pode, sem mais salvaguardas, falhar em alterações posteriores para, em vez disso, reciclar os objetos dos pools.

Notas e leitura adicional

As gravações do modo de liberação são compatíveis com a memória atômica C ++_order_release e as leituras de modo de aquisição são compatíveis com memory_order_acquire. Especificações detalhadas subjacentes a algumas das otimizações descritas acima aguardam a revisão do modelo de memória formal. Em classes java.util.concurrent.atomic, método setRelease substitui o equivalente, mas mal chamado lazySet (e similarmente Unsafe.putOrderedX). A linguagem Rust impõe o rastreamento da propriedade que pode ajudar a garantir o uso adequado das construções da RA. O raciocínio por trás dos campos finais também é visto em C ++ memory_order_consume, que não está disponível como um modo distinto em Java. A definição temporal da causalidade em termos de antecedência é apenas uma faceta de tratamentos mais amplos de causalidade (veja a Wikipédia, por exemplo).

Modo volátil

O modo volátil é o modo de acesso padrão para campos qualificados como volatile, ou usado com VarHandle setVolatile, getVolatile e métodos relacionados. Adiciona ao modo Release / Acquire a restrição:

(Interthread) Os acessos de modo volátil são totalmente pedidos.

Quando todos os acessos usam o modo Volátil, a execução do programa é sequencialmente consistente, caso em que, para dois modos voláteis, acessa A e B, deve ser o caso de A preceder a execução de B ou vice-versa. No modo RA, eles podem estar desordenados e concorrentes. As principais conseqüências são observadas em um exemplo famoso que passa pelos nomes "Dekker", "SB" e "write skew". Usando "M" para variar nos modos:

    volatile int x, y; // initially zero, with VarHandles X and Y

    Thread 1               |  Thread 2
    X.setM(this, 1);       |  Y.setM(this, 1);
    int ry = Y.getM(this); |  int rx = X.getM(this);
  
Se o modo M for Volátil, então, em todas as ordens sequenciais possíveis de acessos pelos dois segmentos, pelo menos um de rx e ry deve ser 1. Mas, em algumas das execuções permitidas no modo RA, ambos podem ser 0.

Cercas voláteis

É possível obter os efeitos do modo Volatile usando cercas. O método VarHandle.fullFence () separa todos os acessos antes da vedação vs todos os acessos após a vedação. Além disso, fullFences são globalmente totalmente ordenados. Portanto, os efeitos de uma gravação volátil podem ser organizados usando uma gravação de modo de liberação (ou sua versão manual usando um releaseFence), seguido de FullFence (). E uma leitura volátil como uma FullFence () seguida de um modo de aquisição. Esta codificação garante que os acessos voláteis sejam totalmente ordenados, separando-os com cercas totalmente ordenadas, que são, em geral, mais caras que as cercas RA. Qualquer par de acessos de modo volátil precisa de apenas uma FullFence (não dois) entre eles, o que pode tornar os usos difíceis de otimizar de forma modular quando os acessos podem ocorrer em diferentes métodos. A convenção de "cercadura de fachada" reduz a sobrecarga sempre codificando gravações (para atômico primariamente bit a bit x) como releaseFence(); x = v; fullFence(); e lê como int v = x; fullFence(); (fullfence inclui os efeitos da aquisiçãoFence; usando apenas adquirirFence aqui imitaria o modo de aquisição; ver abaixo). Esta convenção coincide com a tendência geral para as lendas serem muito mais comuns do que as escritas. A convenção líder ou posterior deve, naturalmente, ser usada consistentemente para ser efetiva; em casos de incerteza (por exemplo, na presença de chamadas de função estrangeiras), use ambas as cercas.

Os acessos de modo volátil não são necessariamente implementados dessa maneira. Alguns processadores suportam instruções especiais de leitura e gravação que não exigem o uso de cercas. Outros podem suportar instruções que são menos dispendiosas do que a separação usando FullFence. Além disso, os métodos de acesso são definidos para permitir o mesmo tipo de otimizações do modo RA. Em particular, os acessos internos podem ser implementados da mesma forma que o modo Planície local, ou mesmo eliminados inteiramente, desde que todas as outras restrições sejam seguras. Em alguns contextos, o uso do acesso volátil com uma variável confinada pode indicar um erro conceitual.

Consenso

As restrições de ordem total fornecem uma base para garantir o consenso -- acordo momentâneo entre os tópicos sobre o estado do programa, como se um bloqueio foi adquirido, se todo um conjunto de threads atingiu um ponto de barreira ou se um elemento existe em uma coleção. (Se isso não for imediatamente óbvio para você, você pode ser reconfortado que levou vários anos e erros antes da descoberta do algoritmo de Dekker que estende a construção acima para fornecer uma forma simples de bloqueio de dois fatos e mais anos para generalizar a idéia. ) As implementações de métodos de atualização na maioria dos componentes concorrentes de propósito geral exigem pelo menos uma operação de consenso (incluindo casos em que é necessário apenas para obter um bloqueio), conforme explicado em "The Laws of Order" por Hagit Attiya et al, POPL 2011.

Conforme discutido no livro de Herlihy e Shavit The Art of Multiprocessor Programming, existe uma hierarquia de operações em que cada operação de número de consenso superior pode ser usada para garantir alguma forma de concordância que é impossível no tempo / espaço limitado "sem espera" usando apenas operações de número de consenso inferior. As três categorias mais úteis estão disponíveis:

  • As técnicas Consensus-1 apenas usam acessos voláteis e / ou cercas explícitas. Os usos estão limitados a problemas em que basta organizar que os acessos ocorram em alguma ordem total sem exigir qualquer pedido particular para manter. Isso geralmente não se aplica quando uma variável pode ser escrita com valores diferentes por mais de um segmento ao mesmo tempo.
  • As operações do Consensus-2 incluem getAndSet, getAndAdd, e propósito específico relacionado RMW (Read-Modify-Write) operações que estendem o suporte de coerência para garantir que nenhuma outra gravação ocorre entre a leitura e gravação da operação, forçando assim um determinado comando de leitura-gravação para segurar. Quando disponíveis, os métodos Consensus-2 são normalmente os meios mais eficientes para resolver problemas comuns, como incrementar com segurança um contador compartilhado usando getAndAdd, que é serialmente comutativo em relação aos valores de uma variável.
  • As operações de Consenso Universal compareAndSet (CAS) e compareAndExchange estendem a idéia de RMWs a gravações condicionais - escrevendo um novo valor se estiver atualmente combinando um valor esperado. Por exemplo, tentar adquirir um bloqueio usando LOCK.compareAndSet(this, 0, 1). Em parte, porque eles podem operar em referências a objetos, essas operações atuam como variantes atômicas de "ifs", que fornecem mecanismos sem bloqueio para resolver qualquer problema de verificação-e-ação de uma única variável e constituem a base da maioria dos não-bloqueadores algoritmos concorrentes. Mesmo quando não é estritamente necessário, as operações de CAS e RMW não avaliadas podem ser bastante baratas para serem preferíveis às técnicas baseadas em ordenamentos mais fracos que exigem mais tempo e / ou espaço para eventualmente obter efeitos semelhantes.
As restrições de ordenação total também podem ser usadas para controlar essas operações em múltiplas variáveis. Por exemplo, as construções semelhantes a Dekker surgem nas implementações da maioria dos bloqueios de bloqueio (em fila) e sincronizadores relacionados: um thread de liberação grava o status de bloqueio X e depois lê de uma fila Y para ver se deve sinalizar um servidor de mesa. Um thread de garçom primeiro faz com que uma entrada na fila Y se adicione e, em seguida, (re) verifica e tenta CAS X para adquirir o bloqueio, suspendendo a falha. O uso de acessos voláteis e / ou cercas aqui evita erros de vivacidade em que o releaser perde ver que um servidor precisa de sinalização, e o garçom também não consegue ver se o bloqueio está disponível antes de suspender. A ideia subjacente foi usada em uma das primeiras construções de controle de concorrência já inventadas (no início dos anos 1960), Semaphores. Ele ainda se aplica na maioria dos componentes concorrentes que executam o gerenciamento de recursos.

Modos mistos e especializações

As garantias de pedidos totais podem ser excessivamente constrangedoras em alguns contextos, como ilustrado por outro exemplo famoso que passa pelos nomes "IRIW" (leituras independentes de gravações independentes) e "garfo longo". Novamente usando "M" para variar nos modos:

    volatile int x, y; // initially zero, with VarHandles X and Y

    Thread 1                |  Thread 2                | Thread 3               | Thread 4
    X.setVolatile(this, 1); |  Y.setVolatile(this, 1); | int r1 = X.getM(this); |  int r3 = Y.getM(this);
                            |                          | int r2 = Y.getM(this); |  int r4 = X.getM(this);
  
Se o modo M for volátil, os tópicos 3 e 4 devem ver as gravações dos segmentos 1 e 2 na mesma ordem, por isso é impossível que a execução resulte em r1 == 1, r2 == 0, r3 == 1 e r4 == 0. Mas se M é Adquirir, isso atomicidade não multicopia é permitido. Não parece haver aplicações práticas de construções semelhantes a IRIW, nas quais essa restrição de pedido é necessária ou desejável. Nesse caso, as leituras de modo de aquisição podem ser usadas em vez disso. Nos processadores TSO, incluindo o x86, os usos de Volatile-read e Acquire-read podem ter a mesma implementação, mas em outros, espera-se que o modo de aquisição seja mais barato.

Combinações de atualizações de modo volátil (escritas, RMW, CAS, cercas) com leituras de modo de aquisição aplicam-se na maioria dos componentes concorrentes. Isso permite o pedido parcial (versus total) somente quando as leituras não são comparadas com atualizações, o que corresponde à intenção da maioria das estruturas de dados simultaneamente legíveis e outras classes de leitura principalmente em métodos que anunciam e mantêm a consistência causal, mas às vezes empregam internamente pedidos mais fortes devido a a necessidade algorítmica de operações de consenso. Isso também corresponde a objetivos comuns ao lidar com corridas: conflitos Write-Write e conflitos Read-Write devem ser controlados, mas geralmente não são Read-Read conflitos. Esta é a mesma idéia por trás dos bloqueios Read-Write, mas sem bloqueio explícito. Também é visto em sistemas de memória de hardware em que as linhas de cache podem estar no modo "compartilhado" em diferentes processadores somente se não houver escritores de modo "exclusivo".

Em modo misto usa em que linearização Os pontos em que as threads devem concordar com o resultado de uma operação de consenso dependem da presença de operações de FullFence, demarcando pontos de compromisso, o uso explícito de cercas pode simplificar a implementação e a análise. Em particular, enquanto Volatile escreve e lê um ato variável como se estivessem separados por uma FullFence, não há nenhum requisito sobre quando essa vedação pode ocorrer (se for o caso, no caso de confinamento de thread). Por exemplo, a construção de Dekker acima não está garantida para funcionar usando a gravação de modo volátil e o modo de aquisição. No entanto, seria suficiente usar a gravação do modo Release, seguida de uma FullFence explícita, seguida do modo de aquisição. Ou, quando aplicável, o modo volátil CAS, seguido pelo modo de aquisição, lê. Além disso, o modo de leitura opaca pode ser suficiente quando os clientes repetidamente enquadram o status antes de tentar uma operação volátil baseada em CAS,

As operações RMW e CAS também estão disponíveis no modo RA, apoiando os formulários somente de Adquira ou Liberação. Esses formulários mantêm a forte garantia de pedidos por variável da operação, mas restrições de relaxamento para acessos circundantes. Estes podem ser aplicados, por exemplo, ao incrementar um contador global no modo Liberação e lê-lo no modo Adquirir. Nem todos os processadores suportam essas formas mais fracas, caso em que (inclusive no x86) são implementadas usando formas mais fortes. Além disso, em princípio, os compiladores podem combinar RMW serialmente comutativos como getAndAdd como se fossem paralelos (quando os valores de retorno individuais não são usados), como em "fusing" adjacente getAndAdd (_, 1) em getAndAdd (_, 2 ).

Em algumas plataformas, as operações RMW e CAS são implementadas usando um par de instruções genericamente conhecido como LL / SC - "link-link" e "store conditional". Estes fornecem apenas as propriedades de coerência da operação: gravações condicionais na loja e retorna true se a gravação for garantida para seguir diretamente a leitura ligada em carga na ordem de coerência. (Se retornar falso, o hardware não pode garantir que nenhuma outra escrita intermediária tenha ocorrido). Nessas plataformas (incluindo POWER e a maioria das versões do ARM), as operações de RMW ou de CAS podem se encaminhar. Para habilitar o ajuste fino, o método VarHandle weakCompareAndSet (weakCAS) é inoperante quando implementado usando LL / SC, retornando falso se o failover da loja falhou (geralmente devido a contenção) ou o valor atual não coincide com o valor esperado. Nos usos em que as tentativas são necessárias em ambos os casos, o uso de weakCAS pode ser mais eficiente. Em outras plataformas (como x86), o método é equivalente a CAS simples. Além disso, em processadores que não suportam diretamente as operações de RMW, eles são implementados usando CAS ou weakCAS.

Notas e leitura adicional

O modo volátil é compatível com C ++ atomic memory_order_seq_cst. Como o pedido total de leituras geralmente não é desejado, houve controvérsias entre os implementadores sobre como suportá-lo. A introdução do modo RA permite que os programadores escolham. Alternativas a provas de linearizabilidade aplicáveis a todos estes são objeto de pesquisa ativa; veja, por exemplo, trabalho por o MPI-SWS Verification group.

A idéia de consenso pode ser estendida a múltiplas variáveis. Alguns sistemas de memória transacional de hardware fornecem extensões de CAS e LL / SC que operam atomicamente em mais de uma variável por vez. Estes ainda não estão disponíveis no Java.

As lojas de dados distribuídos não possuem mecanismos de consenso baseados em coerência de hardware, portanto, devem contar com protocolos como o Paxos. Nestes sistemas, algumas variantes do modo volátil (mais frequentemente aplicadas a transações, acessos não únicos) geralmente são chamadas de "consistência forte", algumas variantes da RA "consistência fraca" e outras variantes que posteriormente detectam e reparam conflitos em operações fracamente consistentes são "fortes e consistentes". Para uma pesquisa que tente esclarecer algumas dessas terminologias, veja "Consistency in Non-Transactional Distributed Storage Systems" por Paolo Viotti e Marko Vukolic, ACM Computing Surveys 2016. Para uma aproximação extremamente áspera, o modo RA é o modo Volatile, o que o UDP é para o TCP.

Fechaduras

Os modos bloqueados correspondem ao uso de built-in synchronized blocos, bem como o uso de bloqueios java.util.concurrent como ReentrantLock.

Em termos de pedidos, a aquisição de bloqueios tem as mesmas propriedades que o modo Acquire lê e liberando bloqueios do mesmo modo que o modo Liberação grava. Quando aplicados aos bloqueios, as restrições de pedidos associadas são algumas vezes conhecidas como regras de "motel de barata" - elas permitem leituras anteriores e depois escreve para "mover-se" para bloquear regiões, mas as que estão dentro de uma região não podem sair.

Os usos de bloqueio não podem depender de detalhes, que podem variar em todas as implementações de bloqueio. Supondo a ausência de deadlock, as regiões exclusivamente bloqueadas são serializável: Eles executam sob exclusão mútua em alguma ordem seqüencial. A maioria dos bloqueios de rotação simples podem usar as operações do modo RA para controlar isso (por exemplo, compareAndSetAcquire e setRelease). No entanto, como observado acima, a maioria dos bloqueios de uso geral exigem a colocação volátil após a liberação e / ou aquisição de bloqueio para controle de bloqueio e sinalização. Além disso, sob bloqueio tendencioso, quando um bloqueio é inicialmente usado por um único segmento, operações mais pesadas, permitindo que outros acessem o bloqueio podem ser adiadas até que as threads atinjam pontos seguros que de outra forma são usados principalmente para desencadear coleta de lixo. E synchronized(x) blocos onde x é local ou thread-confined pode ser totalmente otimizado.

Transformações permitidas adicionais incluem bloqueio mais grosseiro: Duas regiões adjacentes bloqueadas no mesmo bloqueio podem ser combinadas, como em synchronized(p) { b1; };synchronized(p) { b2; } transformado em synchronized(p) { b1; b2; }. Isso funciona como se os acessos que executam o desbloqueio do primeiro bloco e a aquisição do segundo sejam garantidos dentro do segmento, o que lhes permite ser otimizados. O bloco resultante pode ser combinado mais um número finito de vezes com outros blocos adjacentes. (Isso deve ser finitamente limitado para manter as garantias de progresso descritas acima).

Uso correto de bloqueios de exclusão mútua, como synchronized blocos e ReentrantLock mantém a ordem total de regiões bloqueadas. StampedLocks e outros otimistas seqlock-como bloqueios, também impõem pedidos totais de escritores, mas podem permitir leitores simultâneos de modo de aquisição (parcialmente encomendados).

As operações de bloqueio introduzem políticas de bloqueio (suspensão) e agendamento, que estão fora do escopo deste documento. Para obter as especificações do principal primitivo de bloqueio acessível, consulte a documentação do parque / desativar na classe LockSupport. Consulte, por exemplo, a documentação da API para ReentrantLock, StampedLock e outros componentes java.util.concurrent para obter especificações mais detalhadas das políticas de agendamento usadas no JDK.

O ciclo de volta, os bloqueios de vários tipos podem ser usados para estabelecer a exclusão mútua, que por sua vez, permite o uso confiável do modo liso em corpos de código bloqueados. Dependendo dos custos relativos dos bloqueios versus instruções de controle de pedidos, o código baseado no bloqueio não contado pode ser mais rápido do que o código sem bloqueio explicitamente encomendado, embora com os riscos adicionais de impasse e escalabilidade mais fraca sob contenção. (Em outras palavras, às vezes um gargalo seqüencial é a melhor solução disponível sem o redesenho).

As técnicas e componentes acima também são usados na implementação de Threads próprios para organizar que os corpos de thread começam com Adquirir e finalizar as operações de Liberação. Da mesma forma, os chamadores do Thread.start executam uma operação Release e chamadores do Thread.join uma operação de Adquirir.

Resumo

As contas deste guia são compatíveis com (e estendem) o JSR133 (JLS5-8) Specification (exceto para as correções necessárias mesmo na ausência de resspecificação). Mas em vez de descrições de fraseamentos em termos de desvios da consistência sequencial, abordam questões de programação sob a perspectiva de controlar o paralelismo. Isso reflete o impacto de uso principal dos modos de ordem da memória VarHandle, que podem ser descritos em termos de restrições sobre camadas (possivelmente comutativo) Regras de acesso ao modo simples:

  • O modo opaco suporta designs com base em coerência: a garantia de que o visível sobrescreve para cada variável é ordenada, juntamente com as garantias associadas sobre a atomicidade e o progresso do acesso, garante a conscientização das variáveis entre os tópicos.
  • O modo Liberação / Adquirência também suporta projetos com base em causalidade: A ordenação parcial rigorosa da relação de antecedência permite a comunicação entre threads.
  • O modo volátil também suporta projetos que dependem de consenso: A ordem total dos acessos permite que os segmentos alcancem um acordo sobre os estados do programa.

Pontos intermédios através destes estão disponíveis usando modos mistos e / ou cercas explícitas, mas requerem mais atenção às interações entre os modos. Conforme indicado ao discutir definições de modo, alguns detalhes estão pendentes de especificação formal completa, mas nenhum deles deverá afetar o uso.

Em conjunto, estes formam blocos de construção para criar consistência de memória personalizada e protocolos de cache. Mas eles não oferecem soluções. Como atribuído a Phil Karlton by Martin Fowler "Existem apenas duas coisas difíceis em Computer Science: invalidação de cache e nomes de coisas. "Espera-se que os desenvolvedores de componentes simultâneos solucionem os dois, para que seus usuários não precisem.

Como um guia geral para desenvolvedores que manipulam esta mistura potencialmente explosiva de C4 (Commutativity, Coherence, Causality, Consensus): a maioria dos componentes concorrentes devem manter garantias de causalidade para serem utilizáveis. Mas alguns precisam de restrições mais fortes por razões algorítmicas, e alguns são capazes de empregar modos mais fracos (talvez de forma transitória) providenciando isolamento parcial ou relaxando invariantes internos, ou quando ainda são úteis, enfraquecendo as promessas de "agora" para "eventualmente". Além disso, entre os principais requisitos de componentes simultâneos (incluindo especialmente java.util.concurrent), os usuários de componentes estão satisfeitos com as APIs e implementações resultantes e, portanto, não precisam de nenhuma das técnicas apresentadas aqui.

Reconhecimentos

Obrigado por comentários e sugestões de Aleksey Shipilev, Martin Buchholz, Paul Sandoz, Brian Goetz, David Holmes, Sanjoy Das, Hans Boehm, Paul McKenney, Joe Bowbeer, Stephen Dolan, Heinz Kabutz, Viktor Klang, Tim Peierls,

Este trabalho é lançado no domínio público, como explicado em Creative Commons.