O num ++ pode ser atômico para 'int num'?

153

Em geral, para int num, num++(ou ++num), como uma operação de leitura-modificação-gravação, não é atômica . Mas muitas vezes vejo compiladores, por exemplo o GCC , gerar o seguinte código ( tente aqui ):

Digite a descrição da imagem aqui

Como a linha 5, que corresponde a num++uma instrução, podemos concluir que num++ é atômica nesse caso?

E, nesse caso, significa que o gerado num++pode ser usado em cenários simultâneos (multiencadeados) sem qualquer risco de corrida de dados (ou seja, não precisamos fazê-lo, por exemplo, std::atomic<int>e impor os custos associados, pois é atômica de qualquer maneira)?

ATUALIZAR

Observe que esta questão não é se o incremento é atômico (não é e foi e é a linha de abertura da questão). É se pode ser em cenários específicos, ou seja, se a natureza de uma instrução pode, em certos casos, ser explorada para evitar a sobrecarga do lockprefixo. E, como a resposta aceita menciona na seção sobre máquinas uniprocessadoras, bem como esta resposta , explicam a conversa em seus comentários e outros, ela pode (embora não com C ou C ++).

Leo Heinsaar
fonte
65
Quem lhe disse que addé atômico?
Slava
6
dado que uma das características de atomics é a prevenção de tipos específicos de reordenação durante a otimização, não, independentemente da atomicidade da operação real
jaggedSpire
19
Gostaria também de salientar que, se isso é atômico na sua plataforma, não há garantia de que ele esteja em outra plataforma. Seja independente da plataforma e expresse sua intenção usando a std::atomic<int>.
precisa saber é o seguinte
8
Durante a execução dessa addinstrução, outro núcleo pode roubar esse endereço de memória do cache desse núcleo e modificá-lo. Em uma CPU x86, a addinstrução precisa de um lockprefixo se o endereço precisar ser bloqueado no cache durante a operação.
David Schwartz
21
É possível que qualquer operação seja "atômica". Tudo o que você precisa fazer é ter sorte e nunca executar nada que possa revelar que não é atômico. Atômica é valiosa apenas como garantia . Dado que você está analisando o código do assembly, a questão é se essa arquitetura específica fornece a garantia e se o compilador fornece uma garantia de que essa é a implementação no nível do assembly que eles escolherem.
Cort Ammon

Respostas:

197

Isso é absolutamente o que o C ++ define como uma corrida de dados que causa comportamento indefinido, mesmo que um compilador produza código que fez o que você esperava em alguma máquina de destino. Você precisa usar std::atomicpara obter resultados confiáveis, mas pode usá-lo memory_order_relaxedse não se importar em reordenar. Veja abaixo alguns exemplos de código e saída asm usando fetch_add.


Mas primeiro, a linguagem assembly faz parte da pergunta:

Como num ++ é uma instrução ( add dword [num], 1), podemos concluir que num ++ é atômico nesse caso?

As instruções de destino da memória (que não sejam armazenamentos puros) são operações de leitura, modificação e gravação que ocorrem em várias etapas internas . Nenhum registro arquitetural é modificado, mas a CPU precisa reter os dados internamente enquanto os envia pela ALU . O arquivo de registro real é apenas uma pequena parte do armazenamento de dados, mesmo na CPU mais simples, com travas segurando as saídas de um estágio como entradas para outro estágio, etc., etc.

As operações de memória de outras CPUs podem se tornar visíveis globalmente entre a carga e a loja. add dword [num], 1Ou seja, dois threads rodando em loop entrariam nas lojas um do outro. (Veja a resposta de @ Margaret para um bom diagrama). Após incrementos de 40k de cada um dos dois threads, o contador pode ter subido apenas ~ 60k (não 80k) no hardware x86 real com vários núcleos.


"Atômico", da palavra grega que significa indivisível, significa que nenhum observador pode ver a operação como etapas separadas. Acontecer fisicamente / eletricamente instantaneamente para todos os bits simultaneamente é apenas uma maneira de conseguir isso para uma carga ou armazenamento, mas isso nem é possível para uma operação de ALU. Entrei em muito mais detalhes sobre cargas puras e lojas puras na minha resposta ao Atomicity no x86 , enquanto essa resposta se concentra na leitura-modificação-gravação.

O lockprefixo pode ser aplicado a muitas instruções de leitura-modificação-gravação (destino da memória) para tornar toda a operação atômica em relação a todos os observadores possíveis no sistema (outros núcleos e dispositivos DMA, não um osciloscópio conectado aos pinos da CPU). É por isso que existe. (Veja também estas perguntas e respostas ).

O mesmo lock add dword [num], 1 é atômico . Um núcleo de CPU executando essa instrução manteria a linha de cache fixada no estado Modificado em seu cache L1 privado, desde quando a carga lê os dados do cache até que o armazenamento retorne ao cache o resultado. Isso impede que qualquer outro cache do sistema tenha uma cópia da linha de cache em qualquer momento do carregamento para o armazenamento, de acordo com as regras do protocolo de coerência de cache MESI (ou as versões MOESI / MESIF usadas pelo AMD / CPUs Intel, respectivamente). Assim, operações por outros núcleos parecem ocorrer antes ou depois, não durante.

Sem o lockprefixo, outro núcleo poderia se apropriar da linha de cache e modificá-la após nossa carga, mas antes de nossa loja, para que outra loja se tornasse visível globalmente entre nossa carga e loja. Várias outras respostas entendem isso errado e afirmam que, sem lockvocê, você obteria cópias conflitantes da mesma linha de cache. Isso nunca pode acontecer em um sistema com caches coerentes.

(Se uma lockinstrução ed opera em memória que abrange duas linhas de cache, é preciso muito mais trabalho para garantir que as alterações em ambas as partes do objeto permaneçam atômicas à medida que se propagam a todos os observadores, para que nenhum observador possa ver o rasgo. precisa bloquear todo o barramento de memória até que os dados cheguem à memória. Não desalinhe suas variáveis ​​atômicas!)

Observe que o lockprefixo também transforma uma instrução em uma barreira de memória completa (como MFENCE ), interrompendo toda a reordenação em tempo de execução e, assim, fornecendo consistência sequencial. (Veja a excelente publicação no blog de Jeff Preshing . Suas outras publicações também são excelentes e explicam claramente muitas coisas boas sobre programação sem bloqueio , do x86 e outros detalhes de hardware às regras do C ++.)


Em uma máquina uniprocessadora ou em um processo de thread único, uma única instrução RMW é realmente atômica sem um lockprefixo. A única maneira de outro código acessar a variável compartilhada é a CPU fazer uma alternância de contexto, o que não pode acontecer no meio de uma instrução. Portanto, uma planície dec dword [num]pode sincronizar entre um programa de thread único e seus manipuladores de sinal ou em um programa de múltiplos threads executando em uma máquina de núcleo único. Veja a segunda metade da minha resposta em outra pergunta e os comentários abaixo, onde explico isso com mais detalhes.


Voltar para C ++:

É totalmente falso usar num++sem informar ao compilador que você precisa compilar em uma única implementação de leitura-modificação-gravação:

;; Valid compiler output for num++
mov   eax, [num]
inc   eax
mov   [num], eax

Isso é muito provável se você usar o valor de nummais tarde: o compilador o manterá ativo em um registro após o incremento. Portanto, mesmo se você verificar como é num++compilado por conta própria, a alteração do código ao redor pode afetá-lo.

(Se o valor não for necessário posteriormente, inc dword [num]é preferível; as modernas CPUs x86 executam uma instrução RMW de destino da memória pelo menos com a mesma eficiência que usam três instruções separadas. Curiosidade: gcc -O3 -m32 -mtune=i586na verdade, emitirá isso , porque o pipeline superescalar do Pentium P5 não decodifique instruções complexas para várias micro-operações simples, como fazem as microarquiteturas P6 e posteriores. Consulte as tabelas de instruções / guia de microarquitetura da Agner Fog para obter mais informações, e marque o wiki para obter muitos links úteis (incluindo os manuais ISA x86 da Intel, disponíveis gratuitamente em PDF).


Não confunda o modelo de memória de destino (x86) com o modelo de memória C ++

A reordenação em tempo de compilação é permitida . A outra parte do que você obtém com o std :: atomic é o controle sobre a reordenação em tempo de compilação, para garantir que o seunum++se torne globalmente visível somente após alguma outra operação.

Exemplo clássico: armazenando alguns dados em um buffer para outro encadeamento examinar e definindo um sinalizador. Mesmo que o x86 adquira carregamentos / lançamentos de graça, você ainda precisa informar ao compilador para não reordenar usando flag.store(1, std::memory_order_release);.

Você pode esperar que esse código seja sincronizado com outros threads:

// flag is just a plain int global, not std::atomic<int>.
flag--;       // This isn't a real lock, but pretend it's somehow meaningful.
modify_a_data_structure(&foo);    // doesn't look at flag, and the compilers knows this.  (Assume it can see the function def).  Otherwise the usual don't-break-single-threaded-code rules come into play!
flag++;

Mas não vai. O compilador é livre para mover a flag++chamada de função (se ele incluir a função ou souber que ela não está olhando flag). Em seguida, ele pode otimizar completamente a modificação, porque flagnão é uniforme volatile. (E não, C ++ volatilenão é um substituto útil para std :: atomic. Std :: atomic faz o compilador assumir que os valores na memória podem ser modificados de forma assíncrona volatile, mas há muito mais que isso. Além disso, volatile std::atomic<int> foonão é o mesmo que std::atomic<int> foo, conforme discutido com @Richard Hodges.)

Definir corridas de dados em variáveis ​​não atômicas como Comportamento indefinido é o que permite que o compilador ainda carregue cargas e afunde armazenamentos fora de loops, e muitas outras otimizações de memória às quais vários segmentos podem ter uma referência. (Consulte este blog do LLVM para obter mais informações sobre como o UB permite otimizações do compilador.)


Como mencionei, o prefixo x86lock é uma barreira de memória completa; portanto, o uso num.fetch_add(1, std::memory_order_relaxed);gera o mesmo código no x86 que num++(o padrão é consistência sequencial), mas pode ser muito mais eficiente em outras arquiteturas (como o ARM). Mesmo no x86, o relaxado permite mais pedidos em tempo de compilação.

É o que o GCC realmente faz no x86, para algumas funções que operam em uma std::atomicvariável global.

Veja o código da fonte + assembly em formato bem formatado no Godbolt compiler explorer . Você pode selecionar outras arquiteturas de destino, incluindo ARM, MIPS e PowerPC, para ver que tipo de código de linguagem assembly você obtém dos atomics para esses destinos.

#include <atomic>
std::atomic<int> num;
void inc_relaxed() {
  num.fetch_add(1, std::memory_order_relaxed);
}

int load_num() { return num; }            // Even seq_cst loads are free on x86
void store_num(int val){ num = val; }
void store_num_release(int val){
  num.store(val, std::memory_order_release);
}
// Can the compiler collapse multiple atomic operations into one? No, it can't.

# g++ 6.2 -O3, targeting x86-64 System V calling convention. (First argument in edi/rdi)
inc_relaxed():
    lock add        DWORD PTR num[rip], 1      #### Even relaxed RMWs need a lock. There's no way to request just a single-instruction RMW with no lock, for synchronizing between a program and signal handler for example. :/ There is atomic_signal_fence for ordering, but nothing for RMW.
    ret
inc_seq_cst():
    lock add        DWORD PTR num[rip], 1
    ret
load_num():
    mov     eax, DWORD PTR num[rip]
    ret
store_num(int):
    mov     DWORD PTR num[rip], edi
    mfence                          ##### seq_cst stores need an mfence
    ret
store_num_release(int):
    mov     DWORD PTR num[rip], edi
    ret                             ##### Release and weaker doesn't.
store_num_relaxed(int):
    mov     DWORD PTR num[rip], edi
    ret

Observe como o MFENCE (uma barreira completa) é necessário após um armazenamento de consistência sequencial. O x86 é fortemente ordenado em geral, mas a reordenação do StoreLoad é permitida. Ter um buffer de armazenamento é essencial para um bom desempenho em uma CPU fora de ordem em pipeline. A Reordenação de Memória de Jeff Preshing Caught in the Act mostra as consequências de não usar o MFENCE, com código real para mostrar a reordenação acontecendo em hardware real.


Re: discussão nos comentários sobre a resposta de @Richard Hodges sobre os compiladores que mesclam num++; num-=2;operações std :: atomic em uma num--;instrução :

Perguntas e respostas separadas sobre o mesmo assunto: Por que os compiladores não mesclam redundantes std :: atomic write? , onde minha resposta reafirma muito do que escrevi abaixo.

Os compiladores atuais ainda não fazem isso (ainda), mas não porque não estão autorizados. C ++ WG21 / P0062R1: Quando os compiladores devem otimizar os átomos? discute a expectativa de muitos programadores de que os compiladores não farão otimizações "surpreendentes" e o que o padrão pode fazer para dar controle aos programadores. O N4455 discute muitos exemplos de coisas que podem ser otimizadas, incluindo este. Ele ressalta que inline e propagação constante podem introduzir coisas como as fetch_or(0)que podem se transformar em apenas uma load()(mas ainda adquirem e liberam semântica), mesmo quando a fonte original não possui operações atômicas obviamente redundantes.

Os motivos reais pelos quais os compiladores ainda não o fazem são: (1) ninguém escreveu o código complicado que permitiria ao compilador fazer isso com segurança (sem nunca errar) e (2) potencialmente viola o princípio de menos surpresa . O código sem bloqueio é difícil o suficiente para escrever corretamente em primeiro lugar. Portanto, não seja casual no uso de armas atômicas: elas não são baratas e não otimizam muito. std::shared_ptr<T>Porém, nem sempre é fácil evitar operações atômicas redundantes , já que não há uma versão não atômica (embora uma das respostas aqui forneça uma maneira fácil de definir uma shared_ptr_unsynchronized<T>para o gcc).


Voltando à num++; num-=2;compilação como se fosse num--: Compiladores podem fazer isso, a menos que numseja volatile std::atomic<int>. Se uma reordenação for possível, a regra como se permite que o compilador decida no tempo de compilação que sempre acontece dessa maneira. Nada garante que um observador possa ver os valores intermediários (o num++resultado).

Ou seja, se a ordem em que nada se torna globalmente visível entre essas operações é compatível com os requisitos de ordem da fonte (de acordo com as regras C ++ para a máquina abstrata, não a arquitetura de destino), o compilador pode emitir um único em lock dec dword [num]vez de lock inc dword [num]/ lock sub dword [num], 2.

num++; num--não pode desaparecer, porque ainda possui um relacionamento Sincronizar com com outros threads que examinam num, e é um carregamento de aquisição e um armazenamento de versão que não permite a reordenação de outras operações nesse segmento. Para x86, isso pode ser compilado em um MFENCE, em vez de em um lock add dword [num], 0(ie num += 0).

Conforme discutido no PR0062 , a fusão mais agressiva de operações atômicas não adjacentes em tempo de compilação pode ser ruim (por exemplo, um contador de progresso é atualizado apenas uma vez no final, em vez de cada iteração), mas também pode ajudar no desempenho sem desvantagens (por exemplo, pular o atômica inc / dec de ref conta quando uma cópia de a shared_ptré criada e destruída, se o compilador puder provar que shared_ptrexiste outro objeto durante toda a vida útil do temporário.)

Até a num++; num--mesclagem pode prejudicar a implementação de um bloqueio quando um thread é desbloqueado e bloqueado imediatamente. Se ele nunca for realmente liberado no asm, mesmo os mecanismos de arbitragem de hardware não darão a outro thread a chance de abrir o bloqueio naquele momento.


Com o gcc6.2 atual e o clang3.9, você ainda obtém lockoperações separadas , mesmo memory_order_relaxedno caso mais obviamente otimizável. ( Explorador do compilador Godbolt para que você possa ver se as versões mais recentes são diferentes.)

void multiple_ops_relaxed(std::atomic<unsigned int>& num) {
  num.fetch_add( 1, std::memory_order_relaxed);
  num.fetch_add(-1, std::memory_order_relaxed);
  num.fetch_add( 6, std::memory_order_relaxed);
  num.fetch_add(-5, std::memory_order_relaxed);
  //num.fetch_add(-1, std::memory_order_relaxed);
}

multiple_ops_relaxed(std::atomic<unsigned int>&):
    lock add        DWORD PTR [rdi], 1
    lock sub        DWORD PTR [rdi], 1
    lock add        DWORD PTR [rdi], 6
    lock sub        DWORD PTR [rdi], 5
    ret
Peter Cordes
fonte
1
"[usando instruções separadas] costumava ser mais eficiente ... mas as modernas CPUs x86 lidam novamente com as operações RMW com a mesma eficiência" - ainda é mais eficiente no caso em que o valor atualizado será usado posteriormente na mesma função e há um registro gratuito disponível para o compilador armazená-lo (e a variável não é marcada como volátil, é claro). Isso significa que é altamente provável que o fato de o compilador gerar uma única instrução ou várias para a operação depender do restante do código da função, não apenas da única linha em questão.
Periata Breatta 08/09/16
@PeriataBreatta: sim, bom ponto. No asm, você pode usar mov eax, 1 xadd [num], eax(sem prefixo de bloqueio) para implementar o pós-incremento num++, mas não é isso que os compiladores fazem.
Peter Cordes
3
@ DavidC.Rankin: Se você tem alguma edição que gostaria de fazer, fique à vontade. Eu não quero fazer essa CW, no entanto. Ainda é meu trabalho (e minha bagunça: P). Eu vou arrumar alguma depois do meu Ultimate Game [Frisbee] :)
Peter Cordes
1
Se não for um wiki da comunidade, talvez um link no wiki de tags apropriado. (as tags x86 e atômica?). Vale a pena um vínculo adicional, em vez de um retorno esperançoso de uma pesquisa genérica no SO (se eu soubesse melhor onde ele se encaixaria nesse sentido, eu o faria. Terei que me aprofundar mais na tag do que você deve ou não fazer) wiki linkage)
David C. Rankin
1
Como sempre - ótima resposta! Boa distinção entre coerência e atomicidade (onde alguns outros entendeu errado)
Leeor
39

... e agora vamos permitir otimizações:

f():
        rep ret

OK, vamos dar uma chance:

void f(int& num)
{
  num = 0;
  num++;
  --num;
  num += 6;
  num -=5;
  --num;
}

resultado:

f(int&):
        mov     DWORD PTR [rdi], 0
        ret

outro segmento de observação (mesmo ignorando os atrasos na sincronização do cache) não tem oportunidade de observar as alterações individuais.

comparado a:

#include <atomic>

void f(std::atomic<int>& num)
{
  num = 0;
  num++;
  --num;
  num += 6;
  num -=5;
  --num;
}

onde o resultado é:

f(std::atomic<int>&):
        mov     DWORD PTR [rdi], 0
        mfence
        lock add        DWORD PTR [rdi], 1
        lock sub        DWORD PTR [rdi], 1
        lock add        DWORD PTR [rdi], 6
        lock sub        DWORD PTR [rdi], 5
        lock sub        DWORD PTR [rdi], 1
        ret

Agora, cada modificação é: -

  1. observável em outro segmento, e
  2. respeitoso de modificações semelhantes acontecendo em outros threads.

A atomicidade não está apenas no nível da instrução, ela envolve todo o pipeline do processador, através dos caches, à memória e vice-versa.

Mais informações

Em relação ao efeito de otimizações de atualizações de std::atomics.

O padrão c ++ possui a regra 'como se', pela qual é permitido ao compilador reordenar o código e até reescrever o código, desde que o resultado tenha exatamente os mesmos efeitos observáveis (incluindo efeitos colaterais), como se ele tivesse simplesmente executado seu código . código.

A regra como se é conservadora, principalmente envolvendo atômicos.

considerar:

void incdec(int& num) {
    ++num;
    --num;
}

Como não há bloqueios mutex, atômicos ou quaisquer outras construções que influenciam o seqüenciamento entre segmentos, eu diria que o compilador é livre para reescrever essa função como um NOP, por exemplo:

void incdec(int&) {
    // nada
}

Isso ocorre porque no modelo de memória c ++, não há possibilidade de outro encadeamento observar o resultado do incremento. É claro que seria diferente se numfosse volatile(pode influenciar o comportamento do hardware). Mas, neste caso, esta função será a única função que modifica essa memória (caso contrário, o programa está mal formado).

No entanto, este é um jogo diferente:

void incdec(std::atomic<int>& num) {
    ++num;
    --num;
}

numé um atômico. As alterações devem ser observáveis ​​em outros segmentos que estão assistindo. As alterações feitas pelos próprios threads (como definir o valor para 100 entre o incremento e o decremento) terão efeitos de longo alcance no valor eventual de num.

Aqui está uma demonstração:

#include <thread>
#include <atomic>

int main()
{
    for (int iter = 0 ; iter < 20 ; ++iter)
    {
        std::atomic<int> num = { 0 };
        std::thread t1([&] {
            for (int i = 0 ; i < 10000000 ; ++i)
            {
                ++num;
                --num;
            }
        });
        std::thread t2([&] {
            for (int i = 0 ; i < 10000000 ; ++i)
            {
                num = 100;
            }
        });
        
        t2.join();
        t1.join();
        std::cout << num << std::endl;
    }
}

saída de amostra:

99
99
99
99
99
100
99
99
100
100
100
100
99
99
100
99
99
100
100
99
Richard Hodges
fonte
5
Isso não explica que nãoadd dword [rdi], 1 é atômico (sem o prefixo). A carga é atômica e a loja é atômica, mas nada impede que outro encadeamento modifique os dados entre a carga e a loja. Portanto, a loja pode passar por uma modificação feita por outro segmento. Consulte jfdube.wordpress.com/2011/11/30/understanding-atomic-operations . Além disso, os artigos livres de bloqueio de Jeff Preshing são extremamente bons e ele menciona o problema básico de RMW nesse artigo de introdução. lock
6266 Peter Cordes
3
O que realmente está acontecendo aqui é que ninguém implementou essa otimização no gcc, porque seria quase inútil e provavelmente mais perigosa do que útil. (Princípio da menor surpresa. Talvez alguém está esperando um estado temporário para ser visível algumas vezes, e são ok com o probabilty estatística. Ou eles estão usando hardware relógio de pontos para interromper em modificação.) Necessidades de código livre-lock de ser cuidadosamente trabalhada, portanto, não haverá nada para otimizar. Pode ser útil procurá-lo e imprimir um aviso, para alertar o codificador de que o código pode não significar o que eles pensam!
Peter Cordes
2
Talvez essa seja uma razão para os compiladores não implementarem isso (princípio da menor surpresa e assim por diante). Observando que isso seria possível na prática em hardware real. No entanto, as regras de ordenação de memória C ++ não dizem nada sobre a garantia de que as cargas de um encadeamento se misturam "uniformemente" com as operações de outros encadeamentos na máquina abstrata do C ++. Ainda acho que seria legal, mas hostil ao programador.
Peter Cordes
2
Experiência experimental: considere uma implementação C ++ em um sistema cooperativo de multitarefas. Ele implementa std :: thread, inserindo pontos de rendimento onde for necessário para evitar conflitos, mas não entre todas as instruções. Eu acho que você argumentaria que algo no padrão C ++ requer um ponto de rendimento entre num++e num--. Se você puder encontrar uma seção no padrão que exija isso, isso resolveria isso. Tenho certeza de que isso exige apenas que nenhum observador possa ver uma reordenação errada, o que não exige um rendimento lá. Então, acho que é apenas uma questão de qualidade de implementação.
Peter Cordes
5
Por uma questão de finalidade, perguntei na lista de discussão sobre std. Essa pergunta apresentou dois artigos que parecem concordar com Peter e aborda as preocupações que tenho com essas otimizações: wg21.link/p0062 e wg21.link/n4455 Meus agradecimentos a Andy, que me chamou a atenção.
Richard Hodges
38

Sem muitas complicações, uma instrução como esta add DWORD PTR [rbp-4], 1é muito semelhante ao estilo CISC.

Ele realiza três operações: carrega o operando da memória, incrementa-o, armazena o operando de volta na memória.
Durante essas operações, a CPU adquire e libera o barramento duas vezes, entre qualquer outro agente também pode adquiri-lo e isso viola a atomicidade.

AGENT 1          AGENT 2

load X              
inc C
                 load X
                 inc C
                 store X
store X

X é incrementado apenas uma vez.

Margaret Bloom
fonte
7
@LeoHeinsaar Para que isso aconteça, cada chip de memória precisará de sua própria Unidade Aritmética Lógica (ALU). Com efeito, exigiria que cada chip de memória fosse um processador.
Richard Hodges
6
@LeoHeinsaar: as instruções de destino da memória são operações de leitura, modificação e gravação. Nenhum registro arquitetural é modificado, mas a CPU precisa reter os dados internamente enquanto os envia pela ALU. O arquivo de registro real é apenas uma pequena parte do interior de armazenamento de dados até mesmo a CPU mais simples, com travas segurando saídas de um estágio como entradas para um outro estágio, etc. etc.
Peter Cordes
@ PeterCordes Seu comentário é exatamente a resposta que eu estava procurando. A resposta de Margaret me fez suspeitar que algo assim deveria acontecer por dentro.
Leo Heinsaar 08/09/16
Transformado esse comentário em uma resposta completa, incluindo o tratamento da parte C ++ da pergunta.
Peter Cordes
1
@ PeterCordes Obrigado, muito detalhado e em todos os pontos. Era obviamente uma corrida de dados e, portanto, um comportamento indefinido pelo padrão C ++, fiquei curioso para saber se, nos casos em que o código gerado era o que eu publiquei, alguém poderia assumir que isso poderia ser atômico, etc. Os manuais definem muito claramente a atomicidade em relação às operações de memória e não a indivisibilidade das instruções, como assumi: "As operações bloqueadas são atômicas em relação a todas as outras operações de memória e todos os eventos visíveis externamente".
Leo Heinsaar 08/09/16
11

A instrução add não é atômica. Ele faz referência à memória e dois núcleos de processador podem ter cache local diferente dessa memória.

IIRC a variante atômica da instrução add é chamada lock xadd

Sven Nilsson
fonte
3
lock xaddimplementa C ++ std :: atomic fetch_add, retornando o valor antigo. Se você não precisar disso, o compilador usará as instruções de destino da memória normal com um lockprefixo. lock addou lock inc.
Peter Cordes
1
add [mem], 1ainda não seria atômico em uma máquina SMP sem cache, veja meus comentários em outras respostas.
Peter Cordes
Veja minha resposta para muito mais detalhes sobre exatamente como não é atômico. Também o fim da minha resposta sobre esta questão relacionada .
Peter Cordes
10

Como a linha 5, que corresponde a num ++, é uma instrução, podemos concluir que num ++ é atômico nesse caso?

É perigoso tirar conclusões com base na montagem gerada pela "engenharia reversa". Por exemplo, você parece ter compilado seu código com a otimização desativada; caso contrário, o compilador jogaria fora essa variável ou carregaria 1 diretamente nela sem chamar operator++. Como o assembly gerado pode mudar significativamente, com base em sinalizadores de otimização, CPU de destino etc., sua conclusão é baseada na areia.

Além disso, sua ideia de que uma instrução de montagem significa que uma operação é atômica também está errada. Isso addnão será atômico em sistemas com várias CPUs, mesmo na arquitetura x86.

Slava
fonte
9

Mesmo se o seu compilador sempre o emitisse como uma operação atômica, o acesso a numpartir de qualquer outro encadeamento simultaneamente constituiria uma corrida de dados de acordo com os padrões C ++ 11 e C ++ 14 e o programa teria um comportamento indefinido.

Mas é pior que isso. Primeiro, como foi mencionado, a instrução gerada pelo compilador ao incrementar uma variável pode depender do nível de otimização. Em segundo lugar, o compilador pode reordenar outros acessos à memória ++numse numnão for atômico, por exemplo

int main()
{
  std::unique_ptr<std::vector<int>> vec;
  int ready = 0;
  std::thread t{[&]
    {
       while (!ready);
       // use "vec" here
    });
  vec.reset(new std::vector<int>());
  ++ready;
  t.join();
}

Mesmo se assumirmos otimisticamente que ++readyé "atômico" e que o compilador gera o loop de verificação conforme necessário (como eu disse, é UB e, portanto, o compilador é livre para removê-lo, substitua-o por um loop infinito etc.), o O compilador ainda pode mover a atribuição do ponteiro ou, pior ainda, a inicialização do vectorpara um ponto após a operação de incremento, causando caos no novo encadeamento. Na prática, eu não ficaria surpreso se um compilador de otimização removesse completamente a readyvariável e o loop de verificação, pois isso não afeta o comportamento observável sob as regras da linguagem (em oposição às suas esperanças particulares).

De fato, na conferência Meeting C ++ do ano passado, ouvi de dois desenvolvedores de compiladores que eles implementam com prazer otimizações que fazem com que programas multithread ingenuamente escritos se comportem mal, desde que as regras da linguagem o permitam, mesmo se houver uma pequena melhoria no desempenho em programas escritos corretamente.

Por fim, mesmo se você não se importava com a portabilidade e seu compilador era magicamente bom, a CPU que você está usando é muito provavelmente do tipo CISC superescalar e dividirá as instruções em micro-ops, reordenará e / ou executará especulativamente, até certo ponto, limitado pela sincronização de primitivas, como (na Intel) o LOCKprefixo ou a cerca de memória, para maximizar as operações por segundo.

Para resumir uma longa história, as responsabilidades naturais da programação com thread-safe são:

  1. Seu dever é escrever um código que tenha um comportamento bem definido sob as regras da linguagem (e em particular o modelo de memória padrão da linguagem).
  2. O dever do seu compilador é gerar código de máquina que tenha o mesmo comportamento bem definido (observável) no modelo de memória da arquitetura de destino.
  3. O dever da sua CPU é executar esse código para que o comportamento observado seja compatível com o modelo de memória da sua própria arquitetura.

Se você quiser fazer do seu jeito, pode funcionar em alguns casos, mas entenda que a garantia é nula e você será o único responsável por quaisquer resultados indesejados . :-)

PS: Exemplo corretamente escrito:

int main()
{
  std::unique_ptr<std::vector<int>> vec;
  std::atomic<int> ready{0}; // NOTE the use of the std::atomic template
  std::thread t{[&]
    {
       while (!ready);
       // use "vec" here
    });
  vec.reset(new std::vector<int>());
  ++ready;
  t.join();
}

Isso é seguro porque:

  1. As verificações de readynão podem ser otimizadas de acordo com as regras de idioma.
  2. O que ++ready acontece antes da verificação que readynão é zero e outras operações não podem ser reordenadas em torno dessas operações. Isso ocorre porque ++readya verificação é sequencialmente consistente , que é outro termo descrito no modelo de memória C ++ e que proíbe essa reordenação específica. Portanto, o compilador não deve reordenar as instruções e também deve informar à CPU que não deve, por exemplo, adiar a gravação vecpara após o incremento de ready. Sequencialmente consistente é a garantia mais forte em relação aos átomos no padrão da linguagem. Garantias menores (e teoricamente mais baratas) estão disponíveis, por exemplo, através de outros métodos destd::atomic<T>, mas estes são definitivamente apenas para especialistas e podem não ser muito otimizados pelos desenvolvedores do compilador, porque raramente são usados.
Arne Vogel
fonte
1
Se o compilador não pudesse ver todos os usos ready, provavelmente seria compilado while (!ready);em algo mais parecido if(!ready) { while(true); }. Voto positivo: uma parte essencial do std :: atomic está mudando a semântica para assumir modificações assíncronas a qualquer momento. Ter o UB normalmente é o que permite que os compiladores elevem cargas e afundem as lojas de loops.
Peter Cordes
9

Em uma máquina x86 de núcleo único, uma addinstrução geralmente será atômica em relação a outro código na CPU 1 . Uma interrupção não pode dividir uma única instrução no meio.

A execução fora de ordem é necessária para preservar a ilusão de instruções executadas uma de cada vez em ordem em um único núcleo, para que qualquer instrução executada na mesma CPU aconteça completamente antes ou completamente após a adição.

Os sistemas x86 modernos são multicore, portanto o caso especial do uniprocessador não se aplica.

Se alguém tiver como alvo um pequeno PC incorporado e não tiver planos de mover o código para outra coisa, a natureza atômica da instrução "add" poderá ser explorada. Por outro lado, plataformas nas quais as operações são inerentemente atômicas estão se tornando cada vez mais escassas.

(Porém, isso não ajuda você se estiver escrevendo em C ++. Os compiladores não têm a opção num++de compilar em um add ou xadd de destino de memória sem um lockprefixo. Eles podem optar por carregar numem um registro e armazenar o resultado do incremento com uma instrução separada e provavelmente fará isso se você usar o resultado.)


Nota de rodapé 1: O lockprefixo existia mesmo no 8086 original porque os dispositivos de E / S operam simultaneamente com a CPU; os drivers em um sistema de núcleo único precisam lock addincrementar atomicamente um valor na memória do dispositivo, se o dispositivo também puder modificá-lo ou com relação ao acesso ao DMA.

supercat
fonte
Nem sempre é atômico: outro encadeamento pode atualizar a mesma variável ao mesmo tempo e apenas uma atualização é retomada.
fuz 8/09/16
1
Considere um sistema com vários núcleos. Obviamente, dentro de um núcleo, a instrução é atômica, mas não é atômica em relação a todo o sistema.
fuz 8/09/16
1
@FUZxxl: Quais foram as quarta e quinta palavras da minha resposta?
supercat
1
@supercat Sua resposta é muito enganadora, pois considera apenas o caso raro atualmente de um único núcleo e dá ao OP uma falsa sensação de segurança. É por isso que comentei a considerar o caso com vários núcleos também.
fuz 8/09/16
1
@FUZxxl: Fiz uma edição para esclarecer possíveis confusões para os leitores que não perceberam que isso não está falando de CPUs multicore modernas modernas. (E também seja mais específico sobre algumas coisas que o supercat não tinha certeza). BTW, tudo nesta resposta já está na minha, exceto a última frase sobre como são raras as plataformas nas quais a leitura, modificação e gravação é atômica "de graça".
Peter Cordes
7

Naquela época em que os computadores x86 tinham uma CPU, o uso de uma única instrução garantia que as interrupções não dividissem a leitura / modificação / gravação e, se a memória também não fosse usada como um buffer DMA, era atômica (e O C ++ não mencionou threads no padrão, portanto isso não foi abordado).

Quando era raro ter um processador duplo (por exemplo, Pentium Pro de dois soquetes) em uma área de trabalho do cliente, eu efetivamente usava isso para evitar o prefixo LOCK em uma máquina de núcleo único e melhorar o desempenho.

Hoje, isso ajudaria apenas contra vários encadeamentos configurados com a mesma afinidade de CPU; portanto, os encadeamentos com os quais você está preocupado só entrariam em jogo com o intervalo de tempo expirando e executando o outro encadeamento na mesma CPU (núcleo). Isso não é realista.

Com os modernos processadores x86 / x64, a instrução única é dividida em várias micro ops e, além disso, a leitura e gravação de memória são armazenadas em buffer. Portanto, threads diferentes executados em CPUs diferentes não apenas verão isso como não atômico, mas também poderão obter resultados inconsistentes com relação ao que ele lê da memória e ao que ele supõe que outros threads tenham lido até aquele momento: você precisa adicionar cercas de memória para restaurar a integridade comportamento.

JDługosz
fonte
1
Interrupções Ainda não operações RMW divididos, para que eles não ainda sincronizar um único segmento com manipuladores de sinais que são executados no mesmo segmento. Obviamente, isso só funciona se o asm usar uma única instrução, não separar carregar / modificar / armazenar. O C ++ 11 pode expor essa funcionalidade de hardware, mas não o faz (provavelmente porque só foi realmente útil nos kernels do Uniprocessador para sincronizar com manipuladores de interrupção, não no espaço do usuário com manipuladores de sinal). As arquiteturas também não têm instruções de destino da memória de leitura-modificação-gravação. Ainda assim, ele poderia apenas compilar como um RMW atômica relaxado sobre a não-x86
Peter Cordes
Embora, se bem me lembro, o uso do prefixo Lock não fosse absurdamente caro até que os superscalers aparecessem. Portanto, não havia razão para notá-lo como retardando o código importante em um 486, mesmo que não fosse necessário por esse programa.
JDługosz 9/09/16
Sim, desculpe! Na verdade, não li atentamente. Eu vi o começo do parágrafo com o arenque vermelho sobre decodificação para uops e não terminei de ler para ver o que você realmente disse. re: 486: Acho que li que o SMP mais antigo era algum tipo de Compaq 386, mas sua semântica de ordenação de memória não era a mesma que o x86 ISA atualmente diz. Os manuais x86 atuais podem até mencionar o SMP 486. Eles certamente não eram comuns mesmo nos HPC (clusters Beowulf) até os dias do PPro / Athlon XP, no entanto, eu acho.
Peter Cordes
1
@PeterCordes Ok. Claro, assumindo também que não há observadores de DMA / dispositivo - não se encaixavam na área de comentários para incluir esse também. Obrigado JDługosz pela excelente adição (resposta e comentários). Realmente completou a discussão.
Leo Heinsaar 9/09/16
3
@ Leo: Um ponto-chave que não foi mencionado: as CPUs fora de ordem reorganizam as coisas internamente, mas a regra de ouro é que, para um único núcleo , elas preservam a ilusão de instruções executadas uma de cada vez, em ordem. (E isso inclui interrupções que acionam opções de contexto). Os valores podem ser armazenados eletricamente na memória fora de ordem, mas o único núcleo em que tudo está sendo executado controla todas as reordenações que faz, para preservar a ilusão. É por isso que você não precisa de uma barreira de memória para que o equivalente asm a = 1; b = a;carregue corretamente o 1 que você acabou de armazenar.
Peter Cordes
4

Não. Https://www.youtube.com/watch?v=31g0YE61PLQ (esse é apenas um link para a cena "Não" de "The Office")

Você concorda que isso seria uma saída possível para o programa:

saída de amostra:

100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100
100

Nesse caso, o compilador é livre para tornar essa a única saída possível para o programa, da maneira que o compilador desejar. ou seja, um main () que apenas coloca 100s.

Esta é a regra "como se".

E, independentemente da saída, você pode pensar na sincronização de encadeamentos da mesma maneira - se o encadeamento A faz num++; num--;e o encadeamento B lê numrepetidamente, uma possível intercalação válida é que o encadeamento B nunca lê entre num++e num--. Como essa intercalação é válida, o compilador é livre para tornar essa a única intercalação possível. E basta remover totalmente o incr / decr.

Existem algumas implicações interessantes aqui:

while (working())
    progress++;  // atomic, global

(ou seja, imagine que outro segmento atualize uma interface de usuário da barra de progresso com base progress)

O compilador pode transformar isso em:

int local = 0;
while (working())
    local++;

progress += local;

provavelmente isso é válido. Mas provavelmente não é o que o programador estava esperando :-(

O comitê ainda está trabalhando nessas coisas. Atualmente, "funciona" porque os compiladores não otimizam muito os átomos. Mas isso está mudando.

E mesmo se progresstambém fosse volátil, isso ainda seria válido:

int local = 0;
while (working())
    local++;

while (local--)
    progress++;

: - /

Tony
fonte
Essa resposta parece estar apenas respondendo à pergunta secundária que Richard e eu estávamos pensando. Nós finalmente resolvido isso: Acontece que sim, padrão do C ++ não permitir a fusão das operações em não- volatileobjetos atômicos, quando ele não quebrar quaisquer outras regras. Dois documentos de discussão de padrões discutem exatamente isso (links no comentário de Richard ), um usando o mesmo exemplo de contador de progresso. Portanto, é um problema de qualidade de implementação até que o C ++ padronize maneiras de evitá-lo.
Peter Cordes
Sim, o meu "Não" é realmente uma resposta a toda a linha de raciocínio. Se a pergunta for "num ++ pode ser atômica em algum compilador / implementação", a resposta é certa. Por exemplo, um compilador pode decidir adicionar locka todas as operações. Ou alguma combinação de compilador + uniprocessador em que nem a reordenação (ou seja, "os bons e velhos tempos") tudo é atômica. Mas qual é o sentido disso? Você não pode realmente confiar nisso. A menos que você saiba que é o sistema para o qual está escrevendo. (Mesmo assim, melhor seria que atômica <int> não acrescenta ops extras nesse sistema Então você ainda deve escrever código padrão ....)
tony
1
Note que isso And just remove the incr/decr entirely.não está certo. Ainda é uma operação de aquisição e lançamento num. No x86, num++;num--poderia compilar apenas o MFENCE, mas definitivamente não é nada. (A menos que a análise do programa inteiro do compilador possa provar que nada é sincronizado com a modificação de num e que não importa se alguns armazenamentos anteriores são atrasados ​​até depois dos carregamentos posteriores a isso.) Por exemplo, se este foi um desbloqueio e re -caso de uso -lock-imediatamente, você ainda tem duas seções críticas separadas (talvez usando mo_relaxed), não uma grande.
Peter Cordes
@ PeterCordes ah sim, concordou.
Tony
2

Sim mas...

Atômica não é o que você queria dizer. Você provavelmente está perguntando a coisa errada.

O incremento é certamente atômico . A menos que o armazenamento esteja desalinhado (e como você deixou o alinhamento com o compilador, não está), ele está necessariamente alinhado em uma única linha de cache. Com poucas instruções especiais de streaming sem armazenamento em cache, toda e qualquer gravação passa pelo cache. Linhas de cache completas estão sendo lidas e gravadas atomicamente, nunca algo diferente.
Os dados menores que o cache são, é claro, também gravados atomicamente (já que a linha de cache ao redor é).

É thread-safe?

Essa é uma pergunta diferente e há pelo menos duas boas razões para responder com um "Não!" .

Primeiro, existe a possibilidade de que outro núcleo possa ter uma cópia dessa linha de cache em L1 (L2 e superior geralmente é compartilhada, mas L1 é normalmente por núcleo!) E modifica esse valor simultaneamente. É claro que isso também acontece atomicamente, mas agora você tem dois valores "corretos" (corretamente, atomicamente modificados) - qual é o verdadeiramente correto agora?
A CPU resolverá de alguma forma, é claro. Mas o resultado pode não ser o que você espera.

Segundo, há pedidos de memória, ou palavras diferentes acontecem antes das garantias. A coisa mais importante sobre as instruções atômicas não é tanto que elas são atômicas . Está ordenando.

Você tem a possibilidade de impor uma garantia de que tudo o que acontece em termos de memória é realizado em alguma ordem garantida e bem definida, na qual você tem uma garantia "aconteceu antes". Essa ordem pode ser tão "relaxada" (leia-se: absolutamente nenhuma) ou tão rigorosa quanto você precisa.

Por exemplo, você pode definir um ponteiro para algum bloco de dados (por exemplo, os resultados de algum cálculo) e liberar atomicamente o sinalizador "os dados estão prontos". Agora, quem adquirir essa bandeira será levado a pensar que o ponteiro é válido. E, de fato, sempre será um ponteiro válido, nunca algo diferente. Isso ocorre porque a gravação no ponteiro aconteceu antes da operação atômica.

Damon
fonte
2
A carga e o armazenamento são atômicos separadamente, mas toda a operação de leitura-modificação-gravação como um todo definitivamente não é atômica. Os caches são coerentes, portanto, nunca podem conter cópias conflitantes da mesma linha ( en.wikipedia.org/wiki/MESI_protocol ). Outro núcleo não pode sequer ter uma cópia somente leitura enquanto este núcleo o possui no estado Modificado. O que o torna não atômico é que o núcleo que faz o RMW pode perder a propriedade da linha de cache entre a carga e a loja.
Peter Cordes
2
Além disso, não, linhas de cache inteiras nem sempre são transferidas atomicamente. Veja esta resposta , onde é demonstrado experimentalmente que um multi-socket Opteron faz lojas 16B SSE não atômicos através da transferência de linhas de cache em blocos 8B com HyperTransport, mesmo que eles estão atômico para CPUs com um único soquete do mesmo tipo (por causa da carga / hardware de loja possui um caminho 16B para o cache L1). O x86 garante apenas atomicidade para cargas separadas ou armazena até 8B.
Peter Cordes
Deixar o alinhamento no compilador não significa que a memória será alinhada no limite de 4 bytes. Os compiladores podem ter opções ou pragmas para alterar o limite do alinhamento. Isso é útil, por exemplo, para operar com dados compactados em fluxos de rede.
Dmitry Rubanovich 9/09/16
2
Sofisticações, nada mais. Um número inteiro com armazenamento automático que não faz parte de uma estrutura, como mostrado no exemplo, será absolutamente positivamente alinhado corretamente. Reivindicar algo diferente é simplesmente bobo. As linhas de cache e todos os PODs são do tamanho de PoT (poder de dois) e alinhados - em qualquer arquitetura não ilusória do mundo. A matemática diz que qualquer PoT alinhado corretamente se encaixa em exatamente um (nunca mais) de qualquer outro PoT do mesmo tamanho ou maior. Minha afirmação está, portanto, correta.
Damon
1
@ Damon, o exemplo dado na pergunta não menciona uma estrutura, mas não restringe a questão apenas às situações em que números inteiros não fazem parte de estruturas. Definitivamente, os PODs podem ter tamanho de PoT e não ser alinhados a PoT. Dê uma olhada nesta resposta para obter exemplos de sintaxe: stackoverflow.com/a/11772340/1219722 . Portanto, dificilmente é um "sofisma", porque os PODs declarados dessa maneira são usados ​​no código de rede bastante no código da vida real.
Dmitry Rubanovich
2

O fato de a saída de um único compilador, em uma arquitetura específica da CPU, com as otimizações desativadas (já que o gcc nem compila ++ao addotimizar em um exemplo rápido e sujo ), parece implicar que o incremento dessa maneira é atômico, não significa que seja compatível com o padrão ( você causaria um comportamento indefinido ao tentar acessar numem um encadeamento) e está errado de qualquer maneira, porque nãoadd é atômico no x86.

Observe que atomics (usando o lockprefixo da instrução) é relativamente pesado no x86 ( consulte esta resposta relevante ), mas ainda notavelmente menor que um mutex, o que não é muito apropriado nesse caso de uso.

Os resultados a seguir são obtidos do clang ++ 3.8 ao compilar com -Os.

Incrementando um int por referência, a maneira "regular":

void inc(int& x)
{
    ++x;
}

Isso compila em:

inc(int&):
    incl    (%rdi)
    retq

Incrementando um int passado por referência, da maneira atômica:

#include <atomic>

void inc(std::atomic<int>& x)
{
    ++x;
}

Este exemplo, que não é muito mais complexo do que o normal, apenas lockadiciona o prefixo à inclinstrução - mas cuidado, como afirmado anteriormente, isso não é barato. Só porque a montagem parece curta não significa que é rápida.

inc(std::atomic<int>&):
    lock            incl    (%rdi)
    retq
Asu
fonte
-2

Quando seu compilador usa apenas uma única instrução para o incremento e sua máquina é de thread único, seu código está seguro. ^^

Bonita Montero
fonte
-3

Tente compilar o mesmo código em uma máquina que não seja x86 e você verá rapidamente resultados de montagem muito diferentes.

O motivo num++ parece ser atômico porque, em máquinas x86, o incremento de um número inteiro de 32 bits é, de fato, atômico (supondo que nenhuma recuperação de memória ocorra). Mas isso não é garantido pelo padrão c ++, nem é provável que seja o caso de uma máquina que não usa o conjunto de instruções x86. Portanto, esse código não é seguro para várias plataformas contra as condições da corrida.

Você também não tem uma garantia forte de que esse código esteja protegido das Condições de Corrida, mesmo em uma arquitetura x86, porque o x86 não configura cargas e armazena na memória, a menos que seja especificamente instruído a fazê-lo. Portanto, se vários encadeamentos tentaram atualizar essa variável simultaneamente, eles podem acabar incrementando valores em cache (desatualizados)

O motivo, então, que temos std::atomic<int>e assim por diante é que, quando você estiver trabalhando com uma arquitetura em que a atomicidade dos cálculos básicos não é garantida, você terá um mecanismo que forçará o compilador a gerar código atômico.

Xirema
fonte
"é porque em máquinas x86, incrementar um número inteiro de 32 bits é, de fato, atômico". você pode fornecer um link para a documentação que a prova?
Slava
8
Também não é atômico no x86. É seguro para um único núcleo, mas se houver vários núcleos (e existem), não será atômico.
Harold
O x86 é addrealmente garantido atômico? Eu não ficaria surpreso se os incrementos de registro fossem atômicos, mas isso não é útil; para tornar o incremento do registro visível para outro encadeamento, ele precisa estar na memória, o que exigiria instruções adicionais para carregá-lo e armazená-lo, removendo a atomicidade. Meu entendimento é que é por isso que o lockprefixo existe para instruções; o único atômico útil addse aplica à memória não referenciada e usa o lockprefixo para garantir que a linha de cache fique bloqueada durante a operação .
ShadowRanger 8/16 '14
@Slava @Harold @ShadowRanger Atualizei a resposta. addé atômico, mas deixei claro que isso não implica que o código seja seguro para as condições de corrida, porque as mudanças não se tornam visíveis globalmente imediatamente.
Xirema 8/09/16
3
@Xirema que o torna "não atômica", por definição, embora
Harold