Por que o código que altera uma variável compartilhada entre threads aparentemente NÃO sofre de uma condição de corrida?

107

Estou usando Cygwin GCC e executo este código:

#include <iostream>
#include <thread>
#include <vector>
using namespace std;

unsigned u = 0;

void foo()
{
    u++;
}

int main()
{
    vector<thread> threads;
    for(int i = 0; i < 1000; i++) {
        threads.push_back (thread (foo));
    }
    for (auto& t : threads) t.join();

    cout << u << endl;
    return 0;
}

Compilado com a linha: g++ -Wall -fexceptions -g -std=c++14 -c main.cpp -o main.o.

Ele imprime 1000, o que é correto. No entanto, eu esperava um número menor devido a threads substituindo um valor incrementado anteriormente. Por que este código não sofre de acesso mútuo?

Minha máquina de teste tem 4 núcleos e não coloquei restrições no programa que conheço.

O problema persiste ao substituir o conteúdo do compartilhado foopor algo mais complexo, por exemplo

if (u % 3 == 0) {
    u += 4;
} else {
    u -= 1;
}
mafu
fonte
66
As CPUs da Intel possuem uma incrível lógica interna de "abate" para preservar a compatibilidade com as primeiras CPUs x86 usadas em sistemas SMP (como máquinas Pentium Pro duplas). Muitas condições de falha que aprendemos são possíveis quase nunca acontecem de fato em máquinas x86. Então, digamos que um núcleo vá gravar de uvolta na memória. A CPU realmente fará coisas incríveis como notar que a linha de memória unão está no cache da CPU e reiniciará a operação de incremento. É por isso que ir de x86 para outras arquiteturas pode ser uma experiência reveladora!
David Schwartz
1
Talvez ainda muito rápido. Você precisa adicionar código para garantir que o encadeamento ceda antes de fazer qualquer coisa para garantir que outros encadeamentos sejam iniciados antes de ser concluído.
Rob K
1
Como foi observado em outro lugar, o código do thread é tão curto que pode muito bem ser executado antes que o próximo thread seja colocado na fila. Que tal cerca de 10 threads que colocam u ++ em um loop de 100 contagens. E um pequeno atraso para antes do início do loop (ou um sinalizador "go" global para iniciá-los todos ao mesmo tempo)
RufusVS
5
Na verdade, gerar o programa repetidamente em um loop eventualmente mostra que ele quebra: algo como while true; do res=$(./a.out); if [[ $res != 1000 ]]; then echo $res; break; fi; done;imprime 999 ou 998 em meu sistema.
Daniel Kamil Kozar

Respostas:

266

foo()é tão curto que cada thread provavelmente termina antes mesmo de o próximo ser gerado. Se você adicionar um sleep por um tempo aleatório foo()antes de u++, poderá começar a ver o que espera.

Rob K
fonte
51
Isso realmente mudou a saída da maneira esperada.
mafu
49
Eu observaria que esta é, em geral, uma estratégia bastante boa para exibir condições de corrida. Você deve ser capaz de injetar uma pausa entre quaisquer duas operações; se não, há uma condição de corrida.
Matthieu M.
Recentemente, tivemos esse problema com o C #. Normalmente, o código quase nunca falhava, mas a recente adição de uma chamada de API no meio introduzia um atraso suficiente para que fosse alterado de forma consistente.
Obsidian Phoenix
@MatthieuM. A Microsoft não tem uma ferramenta automatizada que faz exatamente isso, como um método para detectar condições de corrida e torná-las reproduzíveis de maneira confiável?
Mason Wheeler
1
@MasonWheeler: Eu trabalho quase exclusivamente no Linux, então ... não sei :(
Matthieu M.
59

É importante entender que uma condição de corrida não garante que o código será executado incorretamente, apenas que ele pode fazer qualquer coisa, pois é um comportamento indefinido. Incluindo a execução conforme o esperado.

Particularmente em máquinas X86 e AMD64, as condições de corrida em alguns casos raramente causam problemas, já que muitas das instruções são atômicas e as garantias de coerência são muito altas. Essas garantias são um tanto reduzidas em sistemas multiprocessadores onde o prefixo de bloqueio é necessário para que muitas instruções sejam atômicas.

Se em sua máquina o incremento for uma operação atômica, provavelmente será executado corretamente, embora de acordo com o padrão da linguagem seja um comportamento indefinido.

Especificamente, espero que neste caso o código possa estar sendo compilado para uma instrução atômica Fetch and Add (ADD ou XADD no assembly X86) que é de fato atômica em sistemas de processador único, no entanto, em sistemas de multiprocessador não é garantido que seja atômico e um bloqueio seria necessário para torná-lo assim. Se você estiver executando em um sistema multiprocessador, haverá uma janela onde os threads podem interferir e produzir resultados incorretos.

Especificamente, eu compilei seu código para montagem usando https://godbolt.org/ e foo()compilar para:

foo():
        add     DWORD PTR u[rip], 1
        ret

Isso significa que ele está apenas executando uma instrução add que, para um único processador, será atômica (embora, como mencionado acima, não seja para um sistema com vários processadores).

Validade
fonte
41
É importante lembrar que "funcionar como planejado" é um resultado permissível de comportamento indefinido.
Marcos
3
Como você indicou, esta instrução não é atômica em uma máquina SMP (como todos os sistemas modernos são). Even inc [u]não é atômico. O LOCKprefixo é necessário para tornar uma instrução verdadeiramente atômica. O OP está simplesmente dando sorte. Lembre-se de que mesmo que você esteja dizendo à CPU "adicione 1 à palavra neste endereço", a CPU ainda precisa buscar, incrementar, armazenar esse valor e outra CPU pode fazer a mesma coisa simultaneamente, fazendo com que o resultado seja incorreto.
Jonathon Reinhart
2
Eu votei contra, mas então reli sua pergunta e percebi que suas declarações de atomicidade estavam assumindo uma única CPU. Se você editar sua pergunta para deixar isso mais claro (quando você disser "atômico", deixe claro que esse é apenas o caso em uma única CPU), então poderei remover meu voto negativo.
Jonathon Reinhart
3
Na votação negativa, acho esta afirmação um pouco meh "Particularmente em máquinas X86 e AMD64, as condições de corrida, em alguns casos, raramente causam problemas, pois muitas das instruções são atômicas e as garantias de coerência são muito altas." O parágrafo deve começar fazendo a suposição explícita de que você está se concentrando em um único núcleo. Mesmo assim, as arquiteturas multi-core são o padrão de fato hoje em dia em dispositivos de consumo que eu consideraria um caso esquivo para explicar por último, em vez de primeiro.
Patrick Trentin
3
Oh, definitivamente. O x86 tem toneladas de compatibilidade com versões anteriores ... coisas para garantir que o código escrito incorretamente funcione na medida do possível. Foi muito importante quando o Pentium Pro introduziu a execução fora de ordem. A Intel queria ter certeza de que a base de código instalada funcionava sem precisar ser recompilada especificamente para seu novo chip. O x86 começou como um núcleo CISC, mas evoluiu internamente para um núcleo RISC, embora ainda se apresente e se comporte de várias maneiras como CISC da perspectiva do programador. Para mais informações, veja a resposta de Peter Cordes aqui .
Cody Gray
20

Acho que não é tanto a coisa se você colocar um sono antes ou depois do u++. Em vez disso, a operação se u++traduz em código que é - em comparação com a sobrecarga de threads de geração que chamam foo- executado muito rapidamente de modo que é improvável que seja interceptado. No entanto, se você "prolongar" a operação u++, a condição de corrida se tornará muito mais provável:

void foo()
{
    unsigned i = u;
    for (int s=0;s<10000;s++);
    u = i+1;
}

resultado: 694


BTW: eu também tentei

if (u % 2) {
    u += 2;
} else {
    u -= 1;
}

e isso me deu na maioria das vezes 1997, mas às vezes 1995.

Stephan Lechner
fonte
1
Eu esperaria em qualquer compilador vagamente lógico que toda a função seria otimizada para a mesma coisa. Estou surpreso que não tenha sido. Obrigado pelo resultado interessante.
Vality
Isso é exatamente correto. Muitos milhares de instruções precisam ser executadas antes que o próximo thread comece a executar a função minúscula em questão. Quando você torna o tempo de execução na função mais próximo da sobrecarga de criação do encadeamento, você vê o impacto da condição de corrida.
Jonathon Reinhart
@Vality: Eu também esperava que ele excluísse o loop for espúrio na otimização O3. Não é?
user21820
Como poderia else u -= 1ser executado? Mesmo em um ambiente paralelo, o valor nunca deveria não caber %2, não é?
mafu
2
a partir da saída, parece que else u -= 1é executado uma vez, na primeira vez que foo () é chamado, quando u == 0. Os 999 vezes restantes u são ímpares e u += 2são executados resultando em u = -1 + 999 * 2 = 1997; ou seja, a saída correta. Uma condição de corrida às vezes faz com que um dos + = 2 seja sobrescrito por um thread paralelo e você obtém 1995.
Lucas
7

Ele sofre de uma condição de corrida. Coloque usleep(1000);antes u++;em fooe eu ver uma saída diferente (<1000) a cada vez.

juf
fonte
6
  1. A provável resposta de por que a condição de corrida não se manifestou para você, embora não existir, é que foo()é tão rápido, em comparação com o tempo que leva para iniciar uma discussão, que cada segmento termina antes do próximo pode até mesmo começar. Mas...

  2. Mesmo com sua versão original, o resultado varia de acordo com o sistema: tentei do seu jeito em um Macbook (quad-core) e, em dez execuções, consegui 1000 três vezes, 999 seis vezes e 998 uma vez. Portanto, a corrida é um tanto rara, mas claramente presente.

  3. Você compilou com '-g' , que tem uma maneira de fazer os bugs desaparecerem. Recompilei seu código, ainda inalterado, mas sem o '-g', e a corrida ficou muito mais acentuada: consegui 1000 uma vez, 999 três vezes, 998 duas vezes, 997 duas vezes, 996 uma vez e 992 uma vez.

  4. Ré. a sugestão de adicionar um sono - isso ajuda, mas (a) um tempo fixo de sono deixa os fios ainda distorcidos pelo tempo de início (sujeito à resolução do temporizador), e (b) um sono aleatório os espalha quando o que queremos é aproxime-os. Em vez disso, eu os codificaria para aguardar um sinal de início, para que pudesse criá-los todos antes de deixá-los trabalhar. Com esta versão (com ou sem '-g'), obtenho resultados em todos os lugares, tão baixos quanto 974 e não superiores a 998:

    #include <iostream>
    #include <thread>
    #include <vector>
    using namespace std;
    
    unsigned u = 0;
    bool start = false;
    
    void foo()
    {
        while (!start) {
            std::this_thread::yield();
        }
        u++;
    }
    
    int main()
    {
        vector<thread> threads;
        for(int i = 0; i < 1000; i++) {
            threads.push_back (thread (foo));
        }
        start = true;
        for (auto& t : threads) t.join();
    
        cout << u << endl;
        return 0;
    }
dgould
fonte
Apenas uma nota. A -gbandeira não "faz com que os bugs desapareçam" de forma alguma. O -gsinalizador nos compiladores GNU e Clang simplesmente adiciona símbolos de depuração ao binário compilado. Isso permite que você execute ferramentas de diagnóstico como GDB e Memcheck em seus programas com alguma saída legível por humanos. Por exemplo, quando o Memcheck é executado em um programa com vazamento de memória, ele não informa o número da linha, a menos que o programa tenha sido criado com o -gsinalizador.
MS-DDOS
Concedido, bugs ocultos do depurador geralmente são mais uma questão de otimização do compilador; Eu deveria ter tentado e dito "usando em -O2 vez de -g". Mas, dito isso, se você nunca teve a alegria de caçar um bug que se manifestaria quando compilado sem ele -g , considere-se um sortudo. Isso pode acontecer, com alguns dos mais sutil dos bugs de aliasing. Eu vi isso, embora não recentemente, e eu podia acreditar que talvez fosse um capricho de um compilador proprietária de idade, então eu vou acreditar em você, provisoriamente, sobre as versões modernas do GNU e Clang.
dgould
-gnão o impede de usar otimizações. por exemplo, gcc -O3 -gfaz o mesmo que gcc -O3, mas com metadados de depuração. O gdb dirá "otimizado" se você tentar imprimir algumas variáveis. -gpoderia talvez mudar as localizações relativas de algumas coisas na memória, se alguma das coisas que ele adiciona fizer parte da .textseção. Definitivamente, ocupa espaço no arquivo de objeto, mas acho que depois de vincular tudo acaba em uma extremidade do segmento de texto (não na seção), ou não faz parte de um segmento. Talvez possa afetar onde as coisas são mapeadas para bibliotecas dinâmicas.
Peter Cordes