Werden zwei atomare Schreibvorgänge an verschiedenen Orten in verschiedenen Threads immer in derselben Reihenfolge von anderen Threads gesehen?

Lesezeit: 11 Minuten

Werden zwei atomare Schreibvorgange an verschiedenen Orten in verschiedenen Threads
Toby Brüll

Betrachten Sie ähnlich wie bei meiner vorherigen Frage diesen Code

-- Initially --
std::atomic<int> x{0};
std::atomic<int> y{0};

-- Thread 1 --
x.store(1, std::memory_order_release);

-- Thread 2 --
y.store(2, std::memory_order_release);

-- Thread 3 --
int r1 = x.load(std::memory_order_acquire);   // x first
int r2 = y.load(std::memory_order_acquire);

-- Thread 4 --
int r3 = y.load(std::memory_order_acquire);   // y first
int r4 = x.load(std::memory_order_acquire);

Ist der seltsames Ergebnis r1==1, r2==0 und r3==2, r4==0 in diesem Fall unter dem C++11-Speichermodell möglich? Was wäre, wenn ich alle ersetzen würde std::memory_order_acq_rel durch std::memory_order_relaxed?

Auf x86 scheint ein solches Ergebnis verboten zu sein, siehe diese SO-Frage, aber ich frage nach dem C++ 11-Speichermodell im Allgemeinen.

Bonus-Frage:

Wir sind uns alle einig, dass mit std::memory_order_seq_cst der seltsames Ergebnis wäre in C++11 nicht erlaubt. Nun, sagte Herb Sutter in seinem berühmten atomic<>-Waffen sprechen @ 42:30 das std::memory_order_seq_cst ist genauso wie std::memory_order_acq_rel aber std::memory_order_acquire– Lasten dürfen sich vorher nicht bewegen std::memory_order_release-schreibt. Ich kann nicht sehen, wie diese zusätzliche Einschränkung im obigen Beispiel das verhindern würde seltsames Ergebnis. Kann jemand erklären?

  • Alles ändern std::memory_order_acq_rel macht keinen Unterschied, wenn Sie keine haben std::memory_order_acq_rel in deinem Code. Haben Sie etwas Relevantes aus Ihrer Frage ausgelassen?

    Benutzer743382

    6. Januar 2015 um 21:05 Uhr


  • @hv meine ich std::memory_order_acq_rel sowohl die zu vertreten std::memory_order_acquire‘s und die std::memory_order_release‘S. Vielleicht ändere ich das…

    – Toby Brull

    6. Januar 2015 um 21:10 Uhr

  • Das Ergebnis ist nach dem C++-Speichermodell sicherlich zulässig. Es gibt keine Reihenfolge zwischen den Threads 1 und 2. Sie können sich vorstellen, dass sich die Speicheränderungen unterschiedlich schnell auf verschiedene Kerne ausbreiten. Bei der Synchronisierung geht es nur darum, was passiert wenn Sie den neuen Wert lesen. Es gibt keine Garantie, dass Sie Wille Lesen Sie den neuen Wert.

    – Kerrek SB

    6. Januar 2015 um 21:10 Uhr


  • @TobiasBrüll Das hängt sicherlich davon ab, welche Assembly generiert wird, was sicherlich durch keinen Standard garantiert wird.

    – David Schwartz

    6. Januar 2015 um 21:29 Uhr

  • Ich habe die Lesereihenfolge in Thread 4 vertauscht, da Ihre ursprüngliche Frage nicht viel Sinn machte: Beide Threads lasen die x und y in der gleichen Reihenfolge, sodass sie keine Schreibvorgänge in der entgegengesetzten Reihenfolge erkennen konnten: Sie müssen die Lesereihenfolge tauschen, um dies zu tun. Wie die akzeptierte Antwort zeigt, gibt es trivialerweise eine seq cst-Reihenfolge, die die Werte zulässt, die Sie mit der ursprünglichen Form der Frage angeben.

    – BeeOnRope

    4. Juni 2018 um 2:07 Uhr

1647085816 35 Werden zwei atomare Schreibvorgange an verschiedenen Orten in verschiedenen Threads
Peter Kordes

Diese Art von Neuordnungstest heißt IRIW (Independent Readers, Independent Writers), bei dem wir prüfen, ob zwei Leser sehen können, dass dasselbe Paar von Geschäften in unterschiedlichen Reihenfolgen erscheint. Verwandt, vielleicht ein Duplikat: Acquire/Release-Semantik mit 4 Threads


Das sehr schwache C ++ 11-Speichermodell erfordert nicht, dass sich alle Threads auf eine globale Reihenfolge für Speicher einigen, wie die Antwort von @MWid sagt.

Diese Antwort erklärt einen möglichen Hardwaremechanismus, der dazu führen kann, dass Threads über die globale Reihenfolge der Geschäfte uneins sind. was beim Einrichten von Tests für sperrlosen Code relevant sein kann. Und nur weil es interessant ist, wenn Sie CPU-Architektur mögen1.

Sehen Eine Tutorial-Einführung in die entspannten Speichermodelle von ARM und POWER für ein abstraktes Modell dessen, was diese ISAs sind: Weder ARM noch POWER garantieren eine konsistente globale Speicherreihenfolge, die von allen Threads gesehen wird. Dies tatsächlich zu beobachten, ist in der Praxis auf POWER-Chips möglich und möglicherweise theoretisch auf ARM möglich, aber möglicherweise nicht auf tatsächlichen Implementierungen.

(Andere schwach geordnete ISAs wie Alpha ermöglichen diese Neuordnung ebenfalls, Ich denke. ARM erlaubte es früher auf dem Papier, aber wahrscheinlich haben keine echten Implementierungen diese Neuordnung vorgenommen. ARMv8 hat sogar sein On-Paper-Modell gestärkt, um dies sogar für zukünftige Hardware zu verbieten.)

In der Informatik ist der Begriff für eine Maschine, bei der Stores gleichzeitig für alle anderen Threads sichtbar werden (und somit eine einzige globale Reihenfolge von Stores besteht) „Mehrfachkopie atomar” oder “multi-copy atomic”. x86 und SPARCs TSO-Speichermodelle haben diese Eigenschaft, aber ARM und POWER benötigen sie nicht.


Verwendung aktueller SMP-Maschinen MESI um eine einzige kohärente Cache-Domäne beizubehalten, sodass alle Kerne die gleiche Ansicht des Speichers haben. Speicher werden global sichtbar, wenn sie aus dem Speicherpuffer in den L1d-Cache übertragen werden. An dieser Stelle eine Belastung ab irgendein Ein anderer Kern wird diesen Laden sehen. Dort ist eine einzige Bestellung aller Speicher, die sich zum Cache verpflichten, da MESI eine einzige Kohärenzdomäne unterhält. Mit ausreichend Barrieren zum Stoppen der lokalen Neuordnung kann die sequentielle Konsistenz wiederhergestellt werden.

Ein Geschäft kann für einige, aber nicht für alle anderen Kerne sichtbar werden Vor es wird global sichtbar.

POWER-CPUs verwenden Gleichzeitiges Multithreading (SMT) (der Oberbegriff für Hyperthreading), um mehrere logische Kerne auf einem physischen Kern auszuführen. Die Speicherordnungsregeln, die uns wichtig sind, sind für logisch Kerne, auf denen Threads laufen, nicht körperlich Kerne.

Wir denken normalerweise, dass Lasten ihren Wert von L1d nehmen, aber das ist nicht der Fall, wenn ein neuer Speicher vom selben Kern neu geladen wird und Daten direkt aus dem Speicherpuffer weitergeleitet werden. (Store-to-Load-Weiterleitung oder SLF). Es ist sogar möglich, dass eine Last einen Wert erhält, der in L1d nie vorhanden war und niemals vorhanden sein wird, selbst auf stark geordnetem x86 mit partiellem SLF. (Siehe meine Antwort auf global unsichtbare Ladeanweisungen).

Der Speicherpuffer verfolgt spekulative Speicherungen, bevor die Speicheranweisung zurückgezogen wurde, puffert aber auch nicht spekulative Speicherungen, nachdem sie aus dem Out-of-Order-Execution-Teil des Kerns (dem ROB/ReOrder-Puffer) zurückgezogen wurden.

Die logischen Kerne auf demselben physischen Kern teilen sich einen Speicherpuffer. Spekulative (noch nicht stillgelegte) Speicher müssen für jeden logischen Kern privat bleiben. (Andernfalls würde dies ihre Spekulationen miteinander verbinden und erfordern, dass beide zurücksetzen, wenn eine Fehlspekulation erkannt wird. Das würde einen Teil des Zwecks von SMT zunichte machen, den Kern beschäftigt zu halten, während ein Thread ins Stocken gerät oder sich von einer Fehlvorhersage eines Zweigs erholt.) .

Aber wir kann Lassen Sie andere logische Kerne den Speicherpuffer nach nicht spekulativen Speichern durchsuchen, die sich letztendlich definitiv in den L1d-Cache einschreiben. Bis sie dies tun, können Threads auf anderen physischen Kernen sie nicht sehen, aber logische Kerne, die denselben physischen Kern teilen, können sie sehen.

(Ich bin mir nicht sicher, ob dies genau der HW-Mechanismus ist, der diese Verrücktheit bei POWER ermöglicht, aber es ist plausibel).

Dieser Mechanismus macht Geschäfte für gleichgeordnete SMT-Kerne sichtbar, bevor sie es sind global sichtbar für alle Kerne. Aber es ist immer noch lokal innerhalb des Kerns, so dass diese Neuordnung billig mit Barrieren vermieden werden kann, die nur den Speicherpuffer betreffen, ohne tatsächlich Cache-Interaktionen zwischen Kernen zu erzwingen.

(Das im ARM/POWER-Papier vorgeschlagene abstrakte Speichermodell modelliert dies so, dass jeder Kern seine eigene zwischengespeicherte Ansicht des Speichers hat, mit Links zwischen Caches, die sie synchronisieren lassen. Aber bei typischer physischer moderner Hardware besteht der einzige Mechanismus meiner Meinung nach zwischen SMT-Geschwistern , nicht zwischen getrennten Kernen.)


Beachten Sie, dass x86 nicht zulassen kann, dass andere logische Kerne den Speicherpuffer überhaupt ausspionieren, da dies das TSO-Speichermodell von x86 verletzen würde (indem diese seltsame Neuordnung zugelassen wird). Als meine Antwort auf Was wird für den Datenaustausch zwischen Threads verwendet, die auf einem Kern mit HT ausgeführt werden? erklärt, partitionieren Intel-CPUs mit SMT (von Intel als Hyperthreading bezeichnet) den Speicherpuffer statisch zwischen logischen Kernen.


Fußnote 1: Ein abstraktes Modell für C++ oder für asm auf einem bestimmten ISA ist alles, was Sie wirklich wissen müssen, um über die Speicherordnung nachzudenken.

Das Verständnis der Hardwaredetails ist nicht erforderlich (und kann Sie in die Falle führen, etwas für unmöglich zu halten, nur weil Sie sich keinen Mechanismus dafür vorstellen können).

  • ARM hat sich entschieden zu gehen Mehrfachkopie atomar in ARMv8 und vermutlich auch “in der Praxis” vor v8-Architekturen, da ich nicht glaube, dass atomares Verhalten ohne Mehrfachkopie jemals aufgetreten ist. Sehen Vereinfachung der ARM-Parallelität: Multicopy-AtomicAxiomatic- und Betriebsmodelle für ARMv8. Ich weiß nicht, ob es so ist offiziell noch, aber es scheint, als würde es passieren.

    – BeeOnRope

    1. Juli 2019 um 3:21 Uhr


  • Gute Antwort! Ich war neugierig, warum ARM keine globale Speicherbestellung hat, da es einen kohärenten Cache hat. Nun, diese Antwort gab eine vernünftige Erklärung.

    – Zanmato

    30. November 2021 um 6:05 Uhr

  • @zanmato: Ja, manchmal hinterlassen ISAs Garantien, die auf dem Papier schwächer sind als echte Hardware, um Raum für zukünftige Designs zu lassen, um interessante Dinge zu tun. (Vergessen Sie nicht, zu stimmen, wenn Sie Ihr tägliches Stimmenlimit noch nicht aufgebraucht haben. Auf diese Weise können Sie zukünftige Leser wissen lassen, dass es hier etwas Lesenswertes gibt, wenn sie bei einer fragenübergreifenden Suche nach Stimmen sortieren.)

    – Peter Cordes

    30. November 2021 um 6:31 Uhr

  • Ich habe vor einigen Tagen meine positive Bewertung abgegeben, als ich diese Antwort zum ersten Mal getroffen habe. Und diese Antwort ist es sicherlich wert!

    – Zanmato

    30. November 2021 um 8:18 Uhr

1647085817 448 Werden zwei atomare Schreibvorgange an verschiedenen Orten in verschiedenen Threads
MWid

Die aktualisiert1 Code in der Frage (mit vielen x und y swapped in Thread 4) testet tatsächlich, ob sich alle Threads auf eine globale Speicherreihenfolge einigen.

Unter dem C++11-Speichermodell ist das Ergebnis r1==1, r2==0, r3==2, r4==0 ist auf POWER erlaubt und tatsächlich beobachtbar.

Auf x86 ist dieses Ergebnis nicht möglich, da dort “Speicher von anderen Prozessoren in einer konsistenten Reihenfolge gesehen werden”. Dieses Ergebnis ist auch in einer sequentiellen konsistenten Ausführung nicht zulässig.


Fußnote 1: Die Frage hatten ursprünglich beide Leser gelesen x dann y. EIN fortlaufend konsistent Ausführung davon ist:

-- Initially --
std::atomic<int> x{0};
std::atomic<int> y{0};

-- Thread 4 --
int r3 = x.load(std::memory_order_acquire);

-- Thread 1 --
x.store(1, std::memory_order_release);

-- Thread 3 --
int r1 = x.load(std::memory_order_acquire);
int r2 = y.load(std::memory_order_acquire);

-- Thread 2 --
y.store(2, std::memory_order_release);

-- Thread 4 --
int r4 = y.load(std::memory_order_acquire);

Das führt zu r1==1, r2==0, r3==0, r4==2. Daher ist dies nicht überhaupt ein seltsames Ergebnis.

Um sagen zu können, dass jeder Leser eine andere Filialreihenfolge gesehen hat, müssen sie in entgegengesetzter Reihenfolge lesen, um auszuschließen, dass sich die letzte Filiale einfach verzögert.

  • Beeindruckend. Das war super hilfreich für mich. Danke vielmals. Denn ich kann jetzt den Schluss ziehen, dass die in der Bonusfrage erwähnte zusätzliche Einschränkung für sich genommen tatsächlich nicht ausreicht, um sequentielle Konsistenz zu erzwingen. Mit den Worten von @yohjp: „[it is] ein Aspekt der Beschränkungen der sequentiellen Konsistenz”.

    – Toby Brull

    9. Januar 2015 um 18:38 Uhr

  • Wie wäre es, es zu ändern std::memory_order_seq_cst? Wäre es noch erlaubt?

    – Ari

    16. Juli 2020 um 2:56 Uhr

  • @Ari Nein, das konnte nicht passieren std::memory_order_seq_cst. Die Antwort sagt es auch.

    – Toby Brull

    18. Juli 2020 um 1:07 Uhr

Die kurze Antwort ist nein. Der Standard sagt nicht, dass sie es sein müssen, und deshalb müssen sie es auch nicht sein. Dabei spielt es keine Rolle, ob Sie sich einen konkreten Weg dafür vorstellen können oder nicht.

1647085817 417 Werden zwei atomare Schreibvorgange an verschiedenen Orten in verschiedenen Threads
yohjp

Ist der seltsames Ergebnis r1==1, r2==0 und r3==0, r4==2 in diesem Fall unter dem C++11-Speichermodell möglich?

Jawohl. Das C++-Speichermodell ermöglicht so etwas seltsames Ergebnis.

Was wäre, wenn ich alle ersetzen würde std::memory_order_acq_rel durch std::memory_order_relaxed?

Wenn Sie alle ersetzen memory_order_acquire und memory_order_release durch memory_order_relaxedan Ihrem Code hat sich nichts geändert.

std::memory_order_seq_cst ist genauso wie std::memory_order_acq_rel aber std::memory_order_acquire– Lasten dürfen sich vorher nicht bewegen std::memory_order_release-schreibt. Ich kann nicht sehen, wie diese zusätzliche Einschränkung im obigen Beispiel das verhindern würde seltsames Ergebnis.

acquire– Lasten dürfen sich vorher nicht bewegen release-writes.” zeigt einen Aspekt von Einschränkungen der sequentiellen Konsistenz (memory_order_seq_cst).

Im C++-Speichermodell wird dies nur garantiert seq_cst hat acq_rel Semantik u alle seq_cst Der atomare Zugriff hat eine “totale Ordnung”, nicht mehr und nicht weniger. Wenn eine solche “totale Ordnung” existiert, können wir sie nicht bekommen seltsames Ergebnis denn alle seq_cst Der atomare Zugriff wird wie in einer beliebigen verschachtelten Reihenfolge auf einem einzelnen Thread ausgeführt.

Deine vorherige Frage behandelt “Kohärenz” von Einzel atomare Variable, und diese Frage fragt nach “Konsistenz”. alle atomare Variablen. Garantien des C++-Speichermodells intuitiv Kohärenz für einzelne atomare Variable sogar schwächste Ordnung (relaxed) und “sequentielle Konsistenz” für verschiedene atomare Variablen, solange die Standardreihenfolge (seq_cst). Wenn Sie ausdrücklich nichtseq_cst Wenn Sie den atomaren Zugriff bestellen, kann dies ein seltsames Ergebnis sein, wie Sie darauf hingewiesen haben.

993540cookie-checkWerden zwei atomare Schreibvorgänge an verschiedenen Orten in verschiedenen Threads immer in derselben Reihenfolge von anderen Threads gesehen?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy