Warum leidet Code, der eine gemeinsam genutzte Variable über Threads hinweg mutiert, anscheinend NICHT unter einer Race-Bedingung?

107

Ich verwende Cygwin GCC und führe diesen Code aus:

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

Zusammengestellt mit der Zeile : g++ -Wall -fexceptions -g -std=c++14 -c main.cpp -o main.o.

Es werden 1000 gedruckt, was korrekt ist. Ich habe jedoch eine geringere Anzahl erwartet, da Threads einen zuvor inkrementierten Wert überschreiben. Warum leidet dieser Code nicht unter gegenseitigem Zugriff?

Mein Testgerät hat 4 Kerne und ich habe dem mir bekannten Programm keine Einschränkungen auferlegt.

Das Problem besteht weiterhin, wenn der Inhalt des freigegebenen foodurch etwas Komplexeres ersetzt wird, z

if (u % 3 == 0) {
    u += 4;
} else {
    u -= 1;
}
Mafu
quelle
66
Intel-CPUs verfügen über eine erstaunliche interne "Shoot-Down" -Logik, um die Kompatibilität mit sehr frühen x86-CPUs zu gewährleisten, die in SMP-Systemen (wie zwei Pentium Pro-Computern) verwendet werden. Viele Fehlerbedingungen, die uns beigebracht werden, sind möglich und treten auf x86-Computern so gut wie nie auf. Angenommen, ein Kern wird uin den Speicher zurückgeschrieben. Die CPU wird tatsächlich erstaunliche Dinge tun, z. B. feststellen, dass sich die Speicherzeile für unicht im Cache der CPU befindet, und den Inkrementierungsvorgang neu starten. Aus diesem Grund kann der Wechsel von x86 zu anderen Architekturen eine Erfahrung sein, die die Augen öffnet!
David Schwartz
1
Vielleicht immer noch zu schnell. Sie müssen Code hinzufügen, um sicherzustellen, dass der Thread nachgibt, bevor er etwas unternimmt, um sicherzustellen, dass andere Threads gestartet werden, bevor er abgeschlossen ist.
Rob K
1
Wie bereits an anderer Stelle erwähnt, ist der Thread-Code so kurz, dass er möglicherweise ausgeführt wird, bevor der nächste Thread in die Warteschlange gestellt wird. Wie wäre es mit 10 Threads, die u ++ in einer 100-Count-Schleife platzieren. Und eine kurze Verzögerung innerhalb von vor dem Start der Schleife (oder ein globales "go"
-Flag
5
Tatsächlich zeigt das wiederholte Laichen des Programms in einer Schleife, dass es kaputt geht: So etwas wie while true; do res=$(./a.out); if [[ $res != 1000 ]]; then echo $res; break; fi; done;999 oder 998 auf meinem System drucken.
Daniel Kamil Kozar

Antworten:

266

foo()ist so kurz, dass jeder Thread wahrscheinlich beendet wird, bevor der nächste überhaupt erzeugt wird. Wenn Sie einen zufälligen Schlaf foo()vor dem hinzufügen u++, sehen Sie möglicherweise, was Sie erwarten.

Rob K.
quelle
51
Dies hat in der Tat die Ausgabe in der erwarteten Weise verändert.
Mafu
49
Ich würde bemerken, dass dies im Allgemeinen eine ziemlich gute Strategie ist, um Rennbedingungen zu zeigen. Sie sollten in der Lage sein, eine Pause zwischen zwei beliebigen Vorgängen einzufügen. Wenn nicht, gibt es eine Rennbedingung.
Matthieu M.
Wir hatten kürzlich genau dieses Problem mit C #. Code schlug normalerweise fast nie fehl, aber das kürzlich hinzugefügte Hinzufügen eines API-Aufrufs führte zu einer ausreichenden Verzögerung, um ihn konsistent zu ändern.
Obsidian Phoenix
@MatthieuM. Verfügt Microsoft nicht über ein automatisiertes Tool, das genau das tut, um Rennbedingungen zu erkennen und zuverlässig reproduzierbar zu machen?
Mason Wheeler
1
@ MasonWheeler: Ich arbeite fast ausschließlich unter Linux, also ... keine Ahnung :(
Matthieu M.
59

Es ist wichtig zu verstehen, dass eine Rennbedingung nicht garantiert, dass der Code falsch ausgeführt wird, sondern lediglich, dass er alles kann, da es sich um ein undefiniertes Verhalten handelt. Einschließlich Laufen wie erwartet.

Insbesondere auf X86- und AMD64-Maschinen verursachen die Rennbedingungen in einigen Fällen selten Probleme, da viele der Anweisungen atomar sind und die Kohärenzgarantien sehr hoch sind. Diese Garantien sind bei Multiprozessorsystemen etwas reduziert, bei denen das Sperrpräfix benötigt wird, damit viele Anweisungen atomar sind.

Wenn es sich bei Ihrem Inkrement auf Ihrem Computer um eine atomare Operation handelt, wird diese wahrscheinlich korrekt ausgeführt, obwohl es sich laut Sprachstandard um undefiniertes Verhalten handelt.

Insbesondere erwarte ich in diesem Fall, dass der Code möglicherweise zu einem atomaren Fetch and Add- Befehl (ADD oder XADD in X86-Assembly) kompiliert wird, der in Einzelprozessorsystemen tatsächlich atomar ist. Auf Multiprozessorsystemen ist dies jedoch nicht garantiert atomar und eine Sperre wäre erforderlich, um es so zu machen. Wenn Sie auf einem Multiprozessorsystem arbeiten, wird ein Fenster angezeigt, in dem Threads stören und falsche Ergebnisse erzielen können.

Insbesondere habe ich Ihren Code mithilfe von https://godbolt.org/ zur Assembly foo()kompiliert und Folgendes kompiliert:

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

Dies bedeutet, dass ausschließlich eine Additionsanweisung ausgeführt wird, die für einen einzelnen Prozessor atomar ist (obwohl dies, wie oben erwähnt, für ein Multiprozessorsystem nicht der Fall ist).

Vality
quelle
41
Es ist wichtig, sich daran zu erinnern, dass "wie beabsichtigt laufen" ein zulässiges Ergebnis undefinierten Verhaltens ist.
Mark
3
Wie Sie angegeben haben, ist diese Anweisung auf einem SMP-Computer (wie es alle modernen Systeme sind) nicht atomar . Auch inc [u]ist nicht atomar. Das LOCKPräfix ist erforderlich, um eine Anweisung wirklich atomar zu machen. Das OP hat einfach Glück. Denken Sie daran, dass die CPU, obwohl Sie der CPU sagen, dass sie dem Wort an dieser Adresse 1 hinzufügen soll, diesen Wert abrufen, inkrementieren, speichern muss und eine andere CPU dasselbe gleichzeitig tun kann, was dazu führt, dass das Ergebnis falsch ist.
Jonathon Reinhart
2
Ich habe abgelehnt, aber dann habe ich Ihre Frage erneut gelesen und festgestellt, dass Ihre Atomizitätsaussagen von einer einzelnen CPU ausgehen. Wenn Sie Ihre Frage bearbeiten, um dies klarer zu machen (wenn Sie "atomar" sagen, stellen Sie klar, dass dies nur bei einer einzelnen CPU der Fall ist), kann ich meine Abwahl entfernen.
Jonathon Reinhart
3
Abgestuft finde ich diese Behauptung ein bisschen meh "Besonders auf X86- und AMD64-Maschinen verursachen Rennbedingungen in einigen Fällen selten Probleme, da viele der Anweisungen atomar sind und die Kohärenzgarantien sehr hoch sind." Der Absatz sollte explizit davon ausgehen, dass Sie sich auf einen einzelnen Kern konzentrieren. Trotzdem sind Multi-Core-Architekturen heutzutage De-facto-Standard bei Consumer-Geräten, und ich würde dies als einen Eckfall betrachten, um den letzten und nicht den ersten zu erklären.
Patrick Trentin
3
Oh, auf jeden Fall. x86 bietet jede Menge Abwärtskompatibilität, um sicherzustellen, dass falsch geschriebener Code so weit wie möglich funktioniert. Es war eine wirklich große Sache, als der Pentium Pro eine Ausführung außerhalb der Reihenfolge einführte. Intel wollte sicherstellen, dass die installierte Codebasis funktioniert, ohne dass sie speziell für den neuen Chip neu kompiliert werden muss. x86 begann als CISC-Kern, hat sich jedoch intern zu einem RISC-Kern entwickelt, obwohl es sich aus Sicht eines Programmierers immer noch in vielerlei Hinsicht als CISC darstellt und verhält. Weitere Informationen finden Sie hier in der Antwort von Peter Cordes .
Cody Gray
20

Ich denke, es ist nicht so sehr die Sache, wenn Sie vor oder nach dem schlafen u++. Es ist vielmehr so, dass die Operation u++in Code übersetzt wird, der - verglichen mit dem Overhead der aufrufenden Spawning-Threads foo- sehr schnell ausgeführt wird, so dass es unwahrscheinlich ist, dass er abgefangen wird. Wenn Sie jedoch die Operation "verlängern" u++, wird die Rennbedingung viel wahrscheinlicher:

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

Ergebnis: 694


Übrigens: Ich habe es auch versucht

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

und es gab mir meistens 1997, aber manchmal 1995.

Stephan Lechner
quelle
1
Ich würde von jedem vage vernünftigen Compiler erwarten, dass die gesamte Funktion auf dasselbe optimiert wird. Ich bin überrascht, dass es nicht so war. Vielen Dank für das interessante Ergebnis.
Vality
Das ist genau richtig. Viele tausend Anweisungen müssen ausgeführt werden, bevor der nächste Thread die betreffende winzige Funktion ausführt. Wenn Sie die Ausführungszeit in der Funktion näher an den Aufwand für die Thread-Erstellung heranführen, sehen Sie die Auswirkungen der Race-Bedingung.
Jonathon Reinhart
@Vality: Ich habe auch erwartet, dass die falsche for-Schleife unter O3-Optimierung gelöscht wird. Es nicht?
user21820
Wie könnte else u -= 1jemals ausgeführt werden? Selbst in einer parallelen Umgebung sollte der Wert niemals nicht passen %2, nicht wahr?
Mafu
2
Von der Ausgabe sieht es so aus, als würde sie else u -= 1einmal ausgeführt, wenn foo () zum ersten Mal aufgerufen wird, wenn u == 0. Die verbleibenden 999 mal u ist ungerade undu += 2 werden ausgeführt, was zu u = -1 + 999 * 2 = 1997 führt. dh die richtige Ausgabe. Eine Rennbedingung führt manchmal dazu, dass eines der + = 2 durch einen parallelen Thread überschrieben wird und Sie 1995 erhalten.
Luke
7

Es leidet unter einer Rennbedingung. Setzen Sie usleep(1000);vorher u++;ein foound ich sehe jedes Mal eine andere Ausgabe (<1000).

juf
quelle
6
  1. Die wahrscheinliche Antwort darauf, warum sich die Racebedingung für Sie nicht manifestiert hat, obwohl sie existiert, ist, dass sie im Vergleich zu der Zeit, die zum Starten eines Threads benötigt wird, foo()so schnell ist, dass jeder Thread beendet wird, bevor der nächste überhaupt starten kann. Aber...

  2. Selbst mit Ihrer Originalversion variiert das Ergebnis je nach System: Ich habe es auf einem (Quad-Core-) Macbook versucht und in zehn Durchläufen dreimal 1000, sechsmal sechsmal und einmal 998 Mal. Das Rennen ist also etwas selten, aber deutlich präsent.

  3. Sie haben mit kompiliert '-g', wodurch Fehler verschwinden können. Ich habe Ihren Code neu kompiliert, immer noch unverändert, aber ohne '-g', und das Rennen wurde viel ausgeprägter: Ich habe 1000 einmal, 999 dreimal, 998 zweimal, 997 zweimal, 996 einmal und 992 einmal.

  4. Re. Der Vorschlag, einen Schlaf hinzuzufügen - das hilft, aber (a) eine feste Schlafzeit lässt die Threads immer noch durch die Startzeit verzerrt (abhängig von der Timer-Auflösung), und (b) ein zufälliger Schlaf verteilt sie, wenn wir wollen ziehe sie näher zusammen. Stattdessen würde ich sie codieren, um auf ein Startsignal zu warten, damit ich sie alle erstellen kann, bevor ich sie zur Arbeit bringen kann. Mit dieser Version (mit oder ohne '-g') erhalte ich überall Ergebnisse, so niedrig wie 974 und nicht höher als 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
quelle
Nur eine Notiz. Die -gFlagge lässt in keiner Weise "Fehler verschwinden". Das -gFlag auf GNU- und Clang-Compilern fügt der kompilierten Binärdatei einfach Debug-Symbole hinzu. Auf diese Weise können Sie Diagnosetools wie GDB und Memcheck in Ihren Programmen mit einer von Menschen lesbaren Ausgabe ausführen. Wenn Memcheck beispielsweise über ein Programm mit einem Speicherverlust ausgeführt wird, wird die Zeilennummer nur angezeigt, wenn das Programm mit dem -gFlag erstellt wurde.
MS-DDOS
Zugegeben, Fehler, die sich vor dem Debugger verstecken, sind normalerweise eher eine Frage der Compileroptimierung. Ich habe versucht haben, und sagte, „unter Verwendung -O2 anstelle von -g“. Aber das heißt, wenn Sie noch nie die Freude hatten, einen Fehler zu jagen, der sich nur manifestieren würde, wenn Sie ihn ohne kompilieren würden -g, sollten Sie sich glücklich schätzen. Es kann passieren, mit einigen der schlimmsten subtilen Aliasing-Fehler. Ich habe es gesehen, wenn auch nicht in letzter Zeit, und ich konnte glauben, dass es vielleicht eine Eigenart eines alten proprietären Compilers war, also werde ich Ihnen vorläufig über moderne Versionen von GNU und Clang glauben.
Dgould
-ghindert Sie nicht daran, Optimierungen zu verwenden. zB gcc -O3 -gmacht das gleiche asm wie gcc -O3, aber mit Debug-Metadaten. gdb sagt jedoch "optimiert", wenn Sie versuchen, einige Variablen zu drucken. -gkönnte möglicherweise die relativen Positionen einiger Dinge im Speicher ändern, wenn eines der hinzugefügten Dinge Teil des .textAbschnitts ist. Es nimmt definitiv Platz in der Objektdatei ein, aber ich denke, nach dem Verknüpfen endet alles an einem Ende des Textsegments (nicht im Abschnitt) oder überhaupt nicht Teil eines Segments. Könnte sich möglicherweise darauf auswirken, wo Dinge für dynamische Bibliotheken zugeordnet sind.
Peter Cordes