Dlaczego kod mutujący zmienną współdzieloną w wątkach najwyraźniej NIE cierpi z powodu wyścigu?

107

Używam Cygwin GCC i uruchamiam ten kod:

#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;
}

Zestawione z linii: g++ -Wall -fexceptions -g -std=c++14 -c main.cpp -o main.o.

Drukuje 1000, co jest poprawne. Spodziewałem się jednak mniejszej liczby z powodu wątków nadpisujących poprzednio zwiększoną wartość. Dlaczego ten kod nie podlega wzajemnemu dostępowi?

Moja maszyna testowa ma 4 rdzenie i nie stawiam żadnych ograniczeń programowi, który znam.

Problem utrzymuje się przy zamianie treści udostępnionej na foocoś bardziej złożonego np

if (u % 3 == 0) {
    u += 4;
} else {
    u -= 1;
}
mafu
źródło
66
Procesory Intela mają niesamowitą wewnętrzną logikę "strzelania", aby zachować kompatybilność z bardzo wczesnymi procesorami x86 używanymi w systemach SMP (jak podwójne maszyny Pentium Pro). Wiele warunków awarii, o których się nas uczono, prawie nigdy się nie zdarza na maszynach x86. Powiedzmy, że rdzeń uwraca do pamięci. Procesor faktycznie zrobi niesamowite rzeczy, na przykład zauważy, że linia pamięci unie znajduje się w pamięci podręcznej procesora i ponownie uruchomi operację inkrementacji. Dlatego przejście z x86 na inną architekturę może otworzyć oczy!
David Schwartz
1
Może wciąż za szybko. Musisz dodać kod, aby upewnić się, że wątek daje wynik, zanim cokolwiek zrobi, aby upewnić się, że inne wątki zostaną uruchomione przed zakończeniem.
Rob K,
1
Jak zauważono w innym miejscu, kod wątku jest tak krótki, że można go wykonać przed umieszczeniem w kolejce następnego wątku. Co powiesz na 10 wątków, które umieszczają u ++ w pętli liczącej 100. I krótkie opóźnienie przed rozpoczęciem pętli (lub globalna flaga „start”, aby uruchomić je wszystkie w tym samym czasie)
RufusVS
5
Właściwie, powtarzanie programu w pętli w końcu pokazuje, że się psuje: coś w rodzaju wyświetla while true; do res=$(./a.out); if [[ $res != 1000 ]]; then echo $res; break; fi; done;999 lub 998 w moim systemie.
Daniel Kamil Kozar

Odpowiedzi:

266

foo()jest tak krótka, że ​​każdy wątek prawdopodobnie kończy się, zanim następny w ogóle się pojawi. Jeśli dodasz sen na losowy czas foo()przed u++, możesz zacząć widzieć, czego się spodziewasz.

Rob K
źródło
51
To rzeczywiście zmieniło produkcję w oczekiwany sposób.
mafu
49
Chciałbym zauważyć, że jest to ogólnie dość dobra strategia pokazania warunków wyścigu. Powinieneś być w stanie wprowadzić pauzę między dowolnymi dwiema operacjami; jeśli nie, istnieje warunek wyścigu.
Matthieu M.
Niedawno mieliśmy ten problem z C #. Kod prawie nigdy nie zawodził, ale niedawne dodanie wywołania interfejsu API pomiędzy wprowadziło wystarczające opóźnienie, aby konsekwentnie się zmieniać.
Obsidian Phoenix
@MatthieuM. Czy Microsoft nie ma zautomatyzowanego narzędzia, które robi dokładnie to, jako metodę zarówno wykrywania warunków wyścigu, jak i zapewniania ich niezawodnej powtarzalności?
Mason Wheeler
1
@MasonWheeler: Pracuję prawie wyłącznie na Linuksie, więc ... nie wiem :(
Matthieu M.,
59

Ważne jest, aby zrozumieć, że sytuacja wyścigu nie gwarantuje, że kod będzie działał niepoprawnie, a jedynie, że może zrobić cokolwiek, ponieważ jest to niezdefiniowane zachowanie. W tym bieganie zgodnie z oczekiwaniami.

Szczególnie na maszynach X86 i AMD64 warunki wyścigu w niektórych przypadkach rzadko powodują problemy, ponieważ wiele instrukcji jest atomowych, a gwarancje spójności są bardzo wysokie. Gwarancje te są nieco ograniczone w systemach wieloprocesorowych, w których przedrostek blokady jest wymagany, aby wiele instrukcji było atomowych.

Jeśli inkrementacja na twoim komputerze jest atomową operacją, prawdopodobnie będzie działać poprawnie, mimo że zgodnie ze standardem językowym jest to niezdefiniowane zachowanie.

W szczególności spodziewam się, że w tym przypadku kod może być kompilowany do atomowej instrukcji Pobierz i dodaj (ADD lub XADD w zestawie X86), która jest rzeczywiście atomowa w systemach jednoprocesorowych, jednak w systemach wieloprocesorowych nie ma gwarancji, że będzie to atomowa i blokada byłby do tego zobowiązany. Jeśli korzystasz z systemu wieloprocesorowego, pojawi się okno, w którym wątki mogą zakłócać działanie i generować nieprawidłowe wyniki.

W szczególności skompilowałem twój kod do asemblera przy użyciu https://godbolt.org/ i foo()kompiluję do:

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

Oznacza to, że wykonuje wyłącznie instrukcję dodawania, która dla pojedynczego procesora będzie atomowa (chociaż, jak wspomniano powyżej, nie dotyczy to systemu wieloprocesorowego).

Vality
źródło
41
Należy pamiętać, że „działanie zgodnie z przeznaczeniem” jest dopuszczalnym wynikiem niezdefiniowanego zachowania.
Mark
3
Jak wskazałeś, ta instrukcja nie jest atomowa na maszynie SMP (którą są wszystkie nowoczesne systemy). Nawet inc [u]nie jest atomowy. LOCKPrefiks jest wymagane, aby instrukcja prawdziwie atomowy. PO po prostu ma szczęście. Przypomnij sobie, że nawet jeśli mówisz procesorowi „dodaj 1 do słowa pod tym adresem”, procesor nadal musi pobierać, zwiększać i przechowywać tę wartość, a inny procesor może robić to samo jednocześnie, powodując niepoprawny wynik.
Jonathon Reinhart
2
Głosowałem w dół, ale potem ponownie przeczytałem twoje pytanie i zdałem sobie sprawę, że twoje oświadczenia o atomowości zakładały pojedynczy procesor. Jeśli zmodyfikujesz swoje pytanie, aby było bardziej zrozumiałe (kiedy powiesz „atomic”, wyjaśnij, że dotyczy to tylko jednego procesora), będę mógł usunąć mój głos negatywny.
Jonathon Reinhart
3
Zignorowane, uważam to twierdzenie za nieco mylące "Szczególnie na maszynach X86 i AMD64 warunki wyścigu w niektórych przypadkach rzadko powodują problemy, ponieważ wiele instrukcji jest atomowych, a gwarancje spójności są bardzo wysokie." Akapit powinien zacząć od wyraźnego założenia, że ​​skupiasz się na jednym rdzeniu. Mimo to, architektury wielordzeniowe są obecnie de facto standardem w urządzeniach konsumenckich, dlatego uważam to za kwestię narożną, aby wyjaśnić ją na końcu, a nie na początku.
Patrick Trentin
3
Och, zdecydowanie. x86 ma mnóstwo kompatybilności wstecznej… rzeczy, aby upewnić się, że niepoprawnie napisany kod działa w możliwie największym stopniu. To była naprawdę wielka sprawa, kiedy Pentium Pro wprowadził wykonanie poza kolejnością. Intel chciał się upewnić, że zainstalowana baza kodu działa bez konieczności ponownej kompilacji specjalnie dla nowego chipa. x86 zaczynał jako rdzeń CISC, ale wewnętrznie ewoluował do rdzenia RISC, chociaż z perspektywy programisty nadal prezentuje się i zachowuje na wiele sposobów jako CISC. Aby dowiedzieć się więcej, zobacz odpowiedź Petera Cordesa tutaj .
Cody Gray
20

Myślę, że nie chodzi o to, że kładziesz się spać przed lub po u++. Chodzi raczej o to, że operacja u++przekłada się na kod, który jest - w porównaniu z narzutem związanym z tworzeniem się wątków, które wywołują foo- bardzo szybko wykonywany w taki sposób, że jest mało prawdopodobne, aby został przechwycony. Jeśli jednak „przedłużysz” operację u++, stan wyścigu stanie się znacznie bardziej prawdopodobny:

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

wynik: 694


BTW: też próbowałem

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

i dawało mi to większość razy 1997, ale czasami 1995.

Stephan Lechner
źródło
1
Spodziewałbym się, że po jakimś niejasno rozsądnym kompilatorze cała funkcja będzie zoptymalizowana do tego samego. Dziwię się, że tak nie było. Dziękuję za ciekawy wynik.
Vality
To jest dokładnie poprawne. Wiele tysięcy instrukcji musi zostać uruchomionych, zanim następny wątek zacznie wykonywać tę drobną funkcję. Kiedy przybliżasz czas wykonywania funkcji do narzutu tworzenia wątku, zobaczysz wpływ stanu wyścigu.
Jonathon Reinhart
@Vality: Spodziewałem się również, że usunie fałszywą pętlę for w ramach optymalizacji O3. Nieprawda?
user21820
Jak mógł else u -= 1kiedykolwiek zostać stracony? Nawet w równoległym środowisku wartość nigdy nie powinna nie pasować %2, prawda?
mafu
2
z danych wyjściowych wygląda na to, że else u -= 1jest wykonywane raz, przy pierwszym wywołaniu foo (), gdy u == 0. Pozostałe 999 razy u jest nieparzyste i u += 2jest wykonywane, w wyniku czego u = -1 + 999 * 2 = 1997; tj. prawidłowe wyjście. Stan wyścigu czasami powoduje nadpisanie jednego z + = 2 przez równoległy wątek i otrzymujesz 1995.
Luke
7

Cierpi na stan wyścigu. Umieścić usleep(1000);zanim u++;się fooi widzę inny wyjściowy (<1000) za każdym razem.

juf
źródło
6
  1. Przewidywany odpowiedź dlaczego wyścigu nie manifest dla ciebie, choć nie istnieje, jest to, że foo()jest tak szybki, w porównaniu do czasu potrzebnego do rozpoczęcia wątku, że każdy kończy gwint przed następnym mogę nawet zacząć. Ale...

  2. Nawet w przypadku oryginalnej wersji wynik różni się w zależności od systemu: wypróbowałem ją na (czterordzeniowym) Macbooku i po dziesięciu uruchomieniach uzyskałem 1000 trzy razy, 999 sześć razy i 998 raz. Tak więc rasa jest dość rzadka, ale wyraźnie obecna.

  3. Skompilowałeś z '-g', który ma sposób na znikanie błędów. Ponownie skompilowałem Twój kod, wciąż niezmieniony, ale bez znaku '-g', i wyścig stał się znacznie wyraźniejszy: dostałem 1000 raz, 999 trzy razy, 998 dwa razy, 997 dwa razy, 996 raz i 992 raz.

  4. Re. sugestia dodania uśpienia - to pomaga, ale (a) ustalony czas uśpienia sprawia, że ​​wątki są nadal wypaczone przez czas rozpoczęcia (zależnie od rozdzielczości timera), oraz (b) losowy sen rozciąga je, gdy chcemy przyciągnij je bliżej siebie. Zamiast tego zakodowałbym je, aby czekały na sygnał startu, więc mogę je wszystkie utworzyć, zanim pozwolę im zabrać się do pracy. W tej wersji (z lub bez '-g') otrzymuję wyniki we wszystkich miejscach, tak niskie, jak 974, ale nie wyższe niż 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
źródło
Tylko uwaga. -gFlaga nie ma w żaden sposób „make błędy zniknie.” -gFlaga na obu kompilatorów GNU i brzękiem po prostu dodaje się do symboli debugowania skompilowany binarny. Pozwala to na uruchamianie narzędzi diagnostycznych, takich jak GDB i Memcheck, w programach z danymi w postaci czytelnej dla człowieka. Na przykład, gdy Memcheck jest uruchamiany na programie z wyciekiem pamięci, nie poda numeru wiersza, chyba że program został zbudowany przy użyciu -gflagi.
MS-DDOS
To prawda, błędy ukrywane przed debuggerem są zwykle bardziej kwestią optymalizacji kompilatora; Należy Próbowałem, i powiedział: „stosując -O2 zamiast z -g”. Ale to powiedziawszy, jeśli nigdy nie miałeś radości z polowania na błąd, który ujawniłby się tylko wtedy, gdy zostałby skompilowany bez -g , uważaj się za szczęściarza. Może się to zdarzyć w przypadku niektórych z najgorszych z subtelnych błędów aliasingu. Ja nie widziałem, choć nie niedawno i mogłem uwierzyć, może to był kaprys starego własnego kompilatora, więc będę ci wierzyć, tymczasowo, o nowoczesnej wersji GNU i Clang.
dgould
-gnie powstrzymuje Cię przed korzystaniem z optymalizacji. np. gcc -O3 -gtworzy taki sam asm jak gcc -O3, ale z metadanymi debugowania. gdb powie „zoptymalizowane”, jeśli spróbujesz wydrukować niektóre zmienne. -gmoże zmienić względne położenie niektórych rzeczy w pamięci, jeśli którykolwiek z elementów, które dodaje, jest częścią .textsekcji. Zdecydowanie zajmuje miejsce w pliku obiektowym, ale myślę, że po połączeniu to wszystko kończy się na jednym końcu segmentu tekstu (nie w sekcji) lub w ogóle nie jest częścią segmentu. Może może mieć wpływ na to, gdzie rzeczy są mapowane dla bibliotek dynamicznych.
Peter Cordes,