Wie erreicht man eine StoreLoad-Barriere in C ++ 11?

Ich möchte tragbaren Code (Intel, ARM, PowerPC ...) schreiben, der eine Variante eines klassischen Problems löst:

Initially: X=Y=0

Thread A:
  X=1
  if(!Y){ do something }
Thread B:
  Y=1
  if(!X){ do something }

in dem das Ziel ist, eine Situation zu vermeiden, in der beide Threads arbeitensomething . (Es ist in Ordnung, wenn keines der beiden Elemente ausgeführt wird. Dies ist kein Mechanismus, der genau einmal ausgeführt wird.) Bitte korrigieren Sie mich, wenn Sie einige Fehler in meiner Argumentation unten sehen.

Mir ist bewusst, dass ich das Ziel mit memory_order_seq_cstatomaren stores und loads wie folgt erreichen kann:

std::atomic<int> x{0},y{0};
void thread_a(){
  x.store(1);
  if(!y.load()) foo();
}
void thread_b(){
  y.store(1);
  if(!x.load()) bar();
}

Dies erreicht das Ziel, da es eine einzige Gesamtreihenfolge für die
{x.store(1), y.store(1), y.load(), x.load()}Ereignisse geben muss, die mit den "Kanten" der Programmreihenfolge übereinstimmen muss:

• x.store(1) "in TO ist vor" y.load()
• y.store(1) "in TO ist vor" x.load()

und wenn foo()aufgerufen wurde, dann haben wir zusätzliche Kante:

• y.load() "liest Wert vor" y.store(1)

und wenn bar()aufgerufen wurde, dann haben wir zusätzliche Kante:

• x.load() "liest Wert vor" x.store(1)

und alle diese Kanten zusammen würden einen Zyklus bilden:

x.store(1)"in TO ist vor" y.load()"liest Wert vor" y.store(1)"in TO ist vor" x.load()"liest Wert vor" "x.store(true)

Dies verstößt gegen die Tatsache, dass Bestellungen keine Zyklen haben.

Ich verwende absichtlich nicht standardmäßige Begriffe "in TO ist vor" und "liest Wert vor" im Gegensatz zu Standardbegriffen wie happens-before, weil ich Feedback über die Richtigkeit meiner Annahme einholen möchte, dass diese Kanten tatsächlich eine happens-beforeBeziehung implizieren , die in einer einzigen kombiniert werden können Diagramm, und der Zyklus in einem solchen kombinierten Diagramm ist verboten. Ich bin mir darüber nicht sicher. Was ich weiß ist, dass dieser Code korrekte Barrieren auf Intel gcc & clang und auf ARM gcc erzeugt

Jetzt ist mein eigentliches Problem etwas komplizierter, weil ich keine Kontrolle über "X" habe - es ist hinter einigen Makros, Vorlagen usw. versteckt und möglicherweise schwächer als seq_cst

Ich weiß nicht einmal, ob "X" eine einzelne Variable oder ein anderes Konzept ist (z. B. ein leichtes Semaphor oder ein Mutex). Alles was ich weiß ist , dass ich zwei Makros set()und check()so dass check()Renditen true„nach“ einem anderen Thread aufgerufen hat set(). (Es ist auch bekannt, dass setund checksind threadsicher und können keine Datenrassen-UB erstellen.)

Konzeptionell set()ist es also etwas wie "X = 1" und check()ist wie "X", aber ich habe keinen direkten Zugang zu Atomics, wenn überhaupt.

void thread_a(){
  set();
  if(!y.load()) foo();
}
void thread_b(){
  y.store(1);
  if(!check()) bar();
}

Ich mache mir Sorgen, dass set()dies intern implementiert werden könnte x.store(1,std::memory_order_release)und / oder sein check()könnte x.load(std::memory_order_acquire). Oder hypothetisch ein, std::mutexdass ein Thread entsperrt und ein anderer try_locking; In der ISO-Norm std::mutexwird nur garantiert, dass die Bestellung erworben und freigegeben wird, nicht seq_cst.

Wenn dies der Fall ist, check()kann der Körper vorher "neu angeordnet" werden y.store(true)( siehe Alex 'Antwort, in der gezeigt wird, dass dies auf PowerPC geschieht ).
Das wäre wirklich schlimm, da jetzt diese Abfolge von Ereignissen möglich ist:

• thread_b()lädt zuerst den alten Wert von x( 0)
• thread_a() führt alles aus einschließlich foo()
• thread_b() führt alles aus einschließlich bar()

Also beide foo()und bar()wurden angerufen, was ich vermeiden musste. Welche Möglichkeiten habe ich, dies zu verhindern?

Option A.

Versuchen Sie, die Store-Load-Barriere zu erzwingen. Dies kann in der Praxis erreicht werden, indem std::atomic_thread_fence(std::memory_order_seq_cst);- wie von Alex in einer anderen Antwort erklärt - alle getesteten Compiler einen vollständigen Zaun emittierten:

• x86_64: MFENCE
• PowerPC: hwsync
• Itanuim: mf
• ARMv7 / ARMv8: dmb ish
• MIPS64: Synchronisieren

Das Problem bei diesem Ansatz ist, dass ich in C ++ - Regeln keine Garantie finden konnte, die std::atomic_thread_fence(std::memory_order_seq_cst)zu einer vollständigen Speicherbarriere führen muss. Tatsächlich atomic_thread_fencescheint sich das Konzept von s in C ++ auf einer anderen Abstraktionsebene zu befinden als das Assemblierungskonzept von Speicherbarrieren und befasst sich eher mit Dingen wie "Welche atomare Operation synchronisiert sich mit was?". Gibt es einen theoretischen Beweis dafür, dass die unten stehende Implementierung das Ziel erreicht?

void thread_a(){
  set();
  std::atomic_thread_fence(std::memory_order_seq_cst)
  if(!y.load()) foo();
}
void thread_b(){
  y.store(true);
  std::atomic_thread_fence(std::memory_order_seq_cst)
  if(!check()) bar();
}

Option B.

Verwenden Sie die Kontrolle über Y, um eine Synchronisation zu erreichen, indem Sie die Operationen read_ modify-write memory_order_acq_rel für Y verwenden:

void thread_a(){
  set();
  if(!y.fetch_add(0,std::memory_order_acq_rel)) foo();
}
void thread_b(){
  y.exchange(1,std::memory_order_acq_rel);
  if(!check()) bar();
}

Die Idee dabei ist, dass der Zugriff auf ein einzelnes Atom ( y) eine einzige Reihenfolge bilden muss, in der sich alle Beobachter einig sind, also entweder fetch_addvorher exchangeoder umgekehrt.

Wenn dies fetch_addvorher exchangeder Fall ist, fetch_addsynchronisiert sich der "Release" -Teil von mit dem "Erwerb" -Teil von exchangeund daher müssen alle Nebenwirkungen von set()für die Ausführung des Codes sichtbar sein check(), bar()wird also nicht aufgerufen.

Ansonsten exchangeist vorher fetch_add, dann fetch_addwird der sehen 1und nicht anrufen foo(). Es ist also unmöglich, beide foo()und anzurufen bar(). Ist diese Argumentation richtig?

Option C.

Verwenden Sie Dummy-Atomics, um "Kanten" einzuführen, die eine Katastrophe verhindern. Betrachten Sie folgenden Ansatz:

void thread_a(){
  std::atomic<int> dummy1{};
  set();
  dummy1.store(13);
  if(!y.load()) foo();
}
void thread_b(){
  std::atomic<int> dummy2{};
  y.store(1);
  dummy2.load();
  if(!check()) bar();
}

Wenn Sie der Meinung atomicsind, dass das Problem hier s lokal ist, stellen Sie sich vor, Sie verschieben sie in den globalen Bereich. In der folgenden Argumentation scheint es mir nicht wichtig zu sein, und ich habe den Code absichtlich so geschrieben, dass deutlich wird, wie lustig dieser Dummy1 ist und Dummy2 sind völlig getrennt.

Warum um alles in der Welt könnte das funktionieren? Nun, es muss eine einzelne Gesamtreihenfolge geben, {dummy1.store(13), y.load(), y.store(1), dummy2.load()}die mit den "Kanten" der Programmreihenfolge übereinstimmen muss:

• dummy1.store(13) "in TO ist vor" y.load()
• y.store(1) "in TO ist vor" dummy2.load()

(Ein seq_cst store + load bildet hoffentlich das C ++ - Äquivalent einer vollständigen Speicherbarriere einschließlich StoreLoad, wie dies bei echten ISAs einschließlich AArch64 der Fall ist, bei denen keine separaten Barriereanweisungen erforderlich sind.)

Nun müssen wir zwei Fälle berücksichtigen: entweder y.store(1)vor y.load()oder nach in der Gesamtreihenfolge.

Wenn y.store(1)vorher y.load()ist, foo()wird nicht angerufen und wir sind in Sicherheit.

Wenn y.load()es vorher ist y.store(1), dann kombinieren wir es mit den beiden Kanten, die wir bereits in der Programmreihenfolge haben, daraus:

• dummy1.store(13) "in TO ist vor" dummy2.load()

Nun, das dummy1.store(13)ist eine Freigabeoperation, die die Effekte von freigibt set()und dummy2.load()eine Erfassungsoperation ist, check()sollte also die Auswirkungen von sehen set()und bar()wird daher nicht aufgerufen und wir sind sicher.

Ist es hier richtig zu denken, dass check()die Ergebnisse von sehen werden set()? Kann ich die "Kanten" verschiedener Arten ("Programmreihenfolge", auch bekannt als "Sequenced Before", "Total Order", "Before Release", "After Acquisition")) so kombinieren? Ich habe ernsthafte Zweifel: C ++ - Regeln scheinen von "Synchronisierungen mit" Beziehungen zwischen Speichern und Laden am selben Ort zu sprechen - hier gibt es keine solche Situation.

Beachten Sie, dass wir nur über den Fall besorgt , wo dumm1.storeist bekannt (über andere Argumentation) , bevor zu sein dummy2.loadin dem seq_cst Gesamtauftrag. Wenn sie also auf dieselbe Variable zugegriffen hätten, hätte die Last den gespeicherten Wert gesehen und mit ihm synchronisiert.

(Die Begründung für die Speicherbarriere / Neuordnung bei Implementierungen, bei denen atomare Lasten und Speicher zu mindestens 1-Wege-Speicherbarrieren kompiliert werden (und seq_cst-Operationen können nicht neu anordnen: z. B. kann ein seq_cst-Speicher eine seq_cst-Last nicht passieren), ist, dass alle Lasten / speichert nach dummy2.loaddefinitiv sichtbar für andere Threads nach y.store . Und ähnlich für den anderen Thread, ... vorher y.load.)

Sie können mit meiner Implementierung der Optionen A, B, C unter https://godbolt.org/z/u3dTa8 spielen

Die Optionen A und B sind gültige Lösungen.

• Option A: Es spielt keine Rolle, was ein zweiter Zaun bedeutet. Der C ++ - Standard definiert klar, welche Garantien er bietet. Ich habe sie in diesem Beitrag angelegt: Wann ist ein Zaun memory_order_seq_cst nützlich?
• Option B: Ja, Ihre Argumentation ist richtig. Alle Änderungen an einem Objekt haben eine einzige Gesamtreihenfolge (die Änderungsreihenfolge), sodass Sie diese verwenden können, um die Threads zu synchronisieren und die Sichtbarkeit aller Nebenwirkungen sicherzustellen.

Option C ist jedoch nicht gültig! Eine Synchronisationsbeziehung kann nur durch Erfassungs- / Freigabeoperationen für dasselbe Objekt hergestellt werden . In Ihrem Fall haben Sie zwei völlig unterschiedliche und unabhängige Objekte dummy1und dummy2. Diese können jedoch nicht verwendet werden, um eine Vor-Ort-Beziehung herzustellen. Da die atomaren Variablen rein lokal sind (dh immer nur von einem Thread berührt werden), kann der Compiler sie basierend auf der Als-ob-Regel entfernen .

Aktualisieren

Option A:
Ich gehe davon aus set()und check()arbeite mit einem Atomwert. Dann haben wir die folgende Situation (-> bezeichnet vorher sequenziert ):

• set()-> fence1(seq_cst)->y.load()
• y.store(true)-> fence2(seq_cst)->check()

Wir können also die folgende Regel anwenden:

Für Atomoperationen A und B an einem Atomobjekt M , bei dem A M modifiziert und B seinen Wert annimmt, wenn es memory_order_seq_cstZäune X und Y gibt, so dass A vor X sequenziert wird , wird Y vor B sequenziert und X steht vor Y in S , dann beobachtet B entweder die Wirkungen von A oder eine spätere Modifikation von M in seiner Modifikationsreihenfolge.

Dh check()sieht entweder diesen Wert gespeichert in setoder y.load()sieht den geschriebenen Wert sein y.store()(die Operationen auf ykönnen sogar verwenden memory_order_relaxed).

Option C:
Die C ++ 17-Standardzustände [32.4.3, S. 1347]:

Für alle Vorgänge muss eine einzige Gesamtbestellung S vorhanden seinmemory_order_seq_cst , die mit der Bestellung "Vorher" und den Änderungsaufträgen für alle betroffenen Standorte [...] übereinstimmt.

Das wichtige Wort hier ist "konsequent". Dies bedeutet, dass, wenn eine Operation A vor einer Operation B stattfindet , A in S vor B stehen muss . Die logische Implikation ist jedoch eine Einbahnstraße, daher können wir nicht auf die Umkehrung schließen: Nur weil eine Operation C einer Operation D in S vorausgeht, bedeutet dies nicht, dass C vor D stattfindet .

Insbesondere können zwei seq-cst-Operationen für zwei separate Objekte nicht verwendet werden, um eine Beziehung vor der Beziehung herzustellen, obwohl die Operationen vollständig in S angeordnet sind. Wenn Sie Operationen für separate Objekte bestellen möchten, müssen Sie sich auf seq-cst beziehen -Zäune (siehe Option A).

Im ersten Beispiel bedeutet das y.load()Lesen von 0 nicht, dass y.load()dies zuvor passiert ist y.store(1).

Dies bedeutet jedoch, dass es in der einzelnen Gesamtreihenfolge früher ist, da ein seq_cst-Ladevorgang entweder den Wert des letzten seq_cst-Speichers in der Gesamtreihenfolge oder den Wert eines Nicht-seq_cst-Speichers zurückgibt, der zuvor nicht aufgetreten ist es (was in diesem Fall nicht existiert). Wenn also y.store(1)früher als y.load()in der Gesamtbestellung gewesen y.load()wäre , hätte 1 zurückgegeben.

Der Beweis ist immer noch korrekt, da die einzelne Gesamtbestellung keinen Zyklus hat.

Wie wäre es mit dieser Lösung?

std::atomic<int> x2{0},y{0};

void thread_a(){
  set();
  x2.store(1);
  if(!y.load()) foo();
}

void thread_b(){
  y.store(1);
  if(!x2.load()) bar();
}

@mpoeter erklärte, warum die Optionen A und B sicher sind.

In der Praxis für reale Implementierungen denke ich, dass Option A nur std::atomic_thread_fence(std::memory_order_seq_cst)in Thread A benötigt wird, nicht in B.

seq-cst-Speicher enthalten in der Praxis eine vollständige Speicherbarriere oder können auf AArch64 zumindest bei späteren Erfassungs- oder seq_cst-Ladevorgängen nicht neu angeordnet werden ( stlrsequentielle Freigabe muss aus dem Speicherpuffer entleert werden, bevor ldarsie aus dem Cache gelesen werden kann).

C ++ -> asm-Zuordnungen haben die Wahl, die Kosten für das Entleeren des Speicherpuffers auf Atomspeicher oder Atomlasten zu setzen. Die vernünftige Wahl für echte Implementierungen besteht darin, atomare Lasten billig zu machen, sodass seq_cst-Speicher eine vollständige Barriere enthalten (einschließlich StoreLoad). Während seq_cst-Lasten mit den meisten Lasten identisch sind.

(Aber nicht POWER; selbst Lasten benötigen eine hohe Synchronisierung = volle Barriere, um die Weiterleitung von Speichern von anderen SMT-Threads auf demselben Kern zu stoppen, was zu einer IRIW-Neuordnung führen kann, da seq_cst erfordert, dass sich alle Threads auf die Reihenfolge von einigen können all seq_cst ops. Werden zwei atomare Schreibvorgänge an verschiedenen Stellen in verschiedenen Threads von anderen Threads immer in derselben Reihenfolge angezeigt? )

(Natürlich brauchen wir für eine formelle Sicherheitsgarantie einen Zaun in beiden, um den Erwerb / die Freigabe von set () -> check () in eine seq_cst-Synchronisation mit zu fördern. Würde auch für ein entspanntes Set funktionieren, denke ich, aber a Ein entspannter Check könnte mit einem Balken aus dem POV anderer Threads neu angeordnet werden.)

Ich denke, das eigentliche Problem mit Option C ist, dass es von einem hypothetischen Beobachter abhängt, der sich mit yden Dummy-Operationen synchronisieren könnte . Daher erwarten wir, dass der Compiler diese Reihenfolge beibehält, wenn er asm für eine barrierebasierte ISA erstellt.

Dies wird in der Praxis bei echten ISAs der Fall sein. Beide Threads enthalten eine vollständige Barriere oder ein gleichwertiges Element, und Compiler optimieren (noch) nicht die Atomics. Aber natürlich ist "Kompilieren auf eine barrierebasierte ISA" nicht Teil des ISO C ++ - Standards. Kohärenter gemeinsam genutzter Cache ist der hypothetische Beobachter, der für das asm-Denken existiert, nicht jedoch für das ISO C ++ - Denken.

Damit Option C funktioniert, benötigen wir eine Reihenfolge wie dummy1.store(13);/ y.load()/ set();(wie in Thread B dargestellt), um gegen eine ISO C ++ - Regel zu verstoßen .

Der Thread, der diese Anweisungen ausführt, muss sich so verhalten, als würde erset() zuerst ausgeführt (aufgrund von Sequenced Before). Das ist in Ordnung, die Reihenfolge des Laufzeitspeichers und / oder die Neuordnung der Kompilierungszeit von Vorgängen könnte dies immer noch tun.

Die beiden seq_cst ops d1=13und ystimmen mit dem Sequenced Before (Programmreihenfolge) überein. set()nimmt nicht an der erforderlichen globalen Reihenfolge für seq_cst-Operationen teil, da es sich nicht um seq_cst handelt.

Thread B wird nicht mit dummy1.store synchronisiert, sodass keine Vor-Ort-Anforderung für setrelativ zu d1=13gilt , obwohl diese Zuweisung eine Freigabeoperation ist.

Ich sehe keine anderen möglichen Regelverstöße. Ich kann hier nichts finden, was mit dem setSequenced-Before übereinstimmen muss d1=13.

Die Argumentation "dummy1.store release set ()" ist der Fehler. Diese Reihenfolge gilt nur für einen echten Beobachter, der mit ihm synchronisiert oder in asm. Wie @mpoeter antwortete, erzeugt oder impliziert das Vorhandensein der Gesamtreihenfolge seq_cst keine Beziehungen, bevor dies erfolgt, und dies ist das einzige, was eine Bestellung außerhalb von seq_cst formal garantiert.

Jede Art von "normaler" CPU mit kohärentem gemeinsam genutzten Cache, bei der diese Neuordnung zur Laufzeit tatsächlich stattfinden könnte, erscheint nicht plausibel. (Aber wenn ein Compiler entfernen könnte dummy1und dummy2dann eindeutig, hätten wir ein Problem, und ich denke, das ist nach dem Standard erlaubt.)

Da das C ++ - Speichermodell jedoch nicht in Form eines Speicherpuffers, eines gemeinsam genutzten kohärenten Caches oder von Lackmustests für die zulässige Neuordnung definiert ist, werden die von der Vernunft geforderten Dinge von den C ++ - Regeln formal nicht verlangt. Dies ist möglicherweise beabsichtigt, um die Optimierung selbst von seq_cst-Variablen zu ermöglichen, die sich als threadprivat herausstellen. (Aktuelle Compiler tun dies natürlich nicht oder machen keine andere Optimierung von atomaren Objekten.)

Eine Implementierung, bei der ein Thread wirklich set()zuletzt sehen konnte, während ein anderer zuerst sehen konnte, set()klingt unplausibel. Nicht einmal POWER konnte das tun; Sowohl seq_cst load als auch store enthalten vollständige Barrieren für POWER. (Ich hatte in Kommentaren vorgeschlagen, dass eine IRIW-Neuordnung hier relevant sein könnte. Die acq / rel-Regeln von C ++ sind schwach genug, um dies zu berücksichtigen, aber das völlige Fehlen von Garantien außerhalb von Synchronisierungen mit oder anderen Situationen, bevor Situationen auftreten, ist viel schwächer als bei jeder HW. )

C ++ nichts für Nicht-seq_cst garantieren , es sei denn es tatsächlich ist ein Beobachter, und dann nur für den Beobachter. Ohne einen sind wir in Schrödingers Katzengebiet. Oder, wenn zwei Bäume in den Wald fallen, ist einer vor dem anderen gefallen? (Wenn es sich um einen großen Wald handelt, sagt die allgemeine Relativitätstheorie, dass dies vom Beobachter abhängt und dass es kein universelles Konzept der Gleichzeitigkeit gibt.)

@mpoeter schlug vor, dass ein Compiler sogar die Dummy-Lade- und Speicheroperationen entfernen könnte, selbst für seq_cst-Objekte.

Ich denke, das mag richtig sein, wenn sie beweisen können, dass nichts mit einer Operation synchronisiert werden kann. dummy2Zum Beispiel kann ein Compiler, der sehen kann, dass er der Funktion nicht entgeht, diese seq_cst-Last wahrscheinlich entfernen.

Dies hat mindestens eine reale Konsequenz: Wenn für AArch64 kompiliert wird, kann ein früherer seq_cst-Speicher in der Praxis mit späteren entspannten Vorgängen neu angeordnet werden, was mit einem seq_cst-Speicher + Laden, der den Speicherpuffer zuvor entleert, nicht möglich gewesen wäre spätere Ladevorgänge könnten ausgeführt werden.

Natürlich optimieren aktuelle Compiler die Atomics überhaupt nicht, obwohl ISO C ++ dies nicht verbietet. Das ist ein ungelöstes Problem für das Normungsgremium.

Dies ist meiner Meinung nach zulässig, da das C ++ - Speichermodell keinen impliziten Beobachter oder eine Anforderung hat, dass alle Threads der Reihenfolge zustimmen. Es bietet einige Garantien, die auf kohärenten Caches basieren, erfordert jedoch nicht, dass alle Threads gleichzeitig sichtbar sind.

In der ISO-Norm wird für std :: mutex nur eine Erfassungs- und Freigabereihenfolge garantiert, nicht für seq_cst.

Es ist jedoch nicht garantiert, dass "seq_cst order" vorhanden ist, da dies seq_cstkeine Eigenschaft einer Operation ist.

seq_cstist eine Garantie für alle Operationen einer bestimmten Implementierung std::atomicoder einer alternativen Atomklasse. Daher ist Ihre Frage nicht stichhaltig.