Grundlegendes zu std :: atomic :: compare_exchange_weak () in C ++ 11

bool compare_exchange_weak (T& expected, T val, ..);

compare_exchange_weak()ist eines der in C ++ 11 bereitgestellten Vergleichsaustausch-Grundelemente. Es ist schwach in dem Sinne, dass es false zurückgibt, selbst wenn der Wert des Objekts gleich ist expected. Dies ist auf einen falschen Fehler auf einigen Plattformen zurückzuführen, auf denen eine Folge von Anweisungen (anstelle einer wie bei x86) zur Implementierung verwendet wird. Auf solchen Plattformen kann ein Kontextwechsel, ein erneutes Laden derselben Adresse (oder Cache-Zeile) durch einen anderen Thread usw. das Grundelement verfehlen. Es ist spuriousso, dass es nicht der Wert des Objekts (ungleich expected) ist, der die Operation fehlschlägt. Stattdessen gibt es zeitliche Probleme.

Was mich jedoch verwundert, ist das, was in C ++ 11 Standard (ISO / IEC 14882) gesagt wird.

29.6.5 .. Eine Folge eines falschen Versagens ist, dass fast alle Verwendungen von schwachem Vergleichen und Austauschen in einer Schleife stattfinden.

Warum muss es bei fast allen Anwendungen in einer Schleife sein ? Bedeutet das, dass wir eine Schleife ausführen, wenn dies aufgrund von falschen Fehlern fehlschlägt? Wenn dies der Fall ist, warum verwenden compare_exchange_weak()und schreiben wir die Schleife dann selbst? Wir können nur verwenden, compare_exchange_strong()was meiner Meinung nach falsche Fehler für uns beseitigen sollte. Was sind die häufigsten Anwendungsfälle compare_exchange_weak()?

Eine andere Frage bezog sich. In seinem Buch "C ++ Concurrency In Action" sagt Anthony:

//Because compare_exchange_weak() can fail spuriously, it must typically
//be used in a loop:

bool expected=false;
extern atomic<bool> b; // set somewhere else
while(!b.compare_exchange_weak(expected,true) && !expected);

//In this case, you keep looping as long as expected is still false,
//indicating that the compare_exchange_weak() call failed spuriously.

Warum gibt !expectedes in der Schleife Bedingung? Ist es dort, um zu verhindern, dass alle Threads verhungern und für einige Zeit keine Fortschritte machen?

Edit: (eine letzte Frage)

Auf Plattformen, auf denen kein einziger Hardware-CAS-Befehl vorhanden ist, werden sowohl die schwache als auch die starke Version mit LL / SC implementiert (wie ARM, PowerPC usw.). Gibt es also einen Unterschied zwischen den folgenden zwei Schleifen? Warum, wenn überhaupt? (Für mich sollten sie eine ähnliche Leistung haben.)

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_weak(..))
{ .. }

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_strong(..)) 
{ .. }

Ich komme mit dieser letzten Frage, die ihr alle erwähnt, dass es vielleicht einen Leistungsunterschied innerhalb einer Schleife gibt. Es wird auch in der C ++ 11-Norm (ISO / IEC 14882) erwähnt:

Wenn sich ein Vergleich und Austausch in einer Schleife befindet, bietet die schwache Version auf einigen Plattformen eine bessere Leistung.

Wie oben analysiert, sollten zwei Versionen in einer Schleife die gleiche / ähnliche Leistung bieten. Was vermisse ich?

Warum in einer Schleife austauschen?

Normalerweise möchten Sie, dass Ihre Arbeit erledigt wird, bevor Sie fortfahren. Daher setzen Sie sie compare_exchange_weakin eine Schleife, damit sie versucht, sich auszutauschen, bis sie erfolgreich ist (dh zurückkehrt true).

Beachten Sie, dass dies auch compare_exchange_stronghäufig in einer Schleife verwendet wird. Es schlägt nicht aufgrund eines falschen Fehlers fehl, aber es schlägt aufgrund gleichzeitiger Schreibvorgänge fehl.

Warum weakstatt verwenden strong?

Ganz einfach: Falsches Versagen kommt nicht oft vor, daher ist es kein großer Leistungseinbruch. Im Gegensatz dazu ermöglicht das Tolerieren eines solchen Fehlers eine wesentlich effizientere Implementierung der weakVersion (im Vergleich zu strong) auf einigen Plattformen: Sie strongmüssen immer nach falschen Fehlern suchen und diese maskieren. Das ist teuer.

Daher weakwird verwendet, weil es viel schneller ist als strongauf einigen Plattformen

Wann weakund wann sollten Sie verwenden strong?

Die Referenzzustände geben Hinweise, wann weakund wann zu verwenden strong:

Wenn sich ein Vergleich und Austausch in einer Schleife befindet, bietet die schwache Version auf einigen Plattformen eine bessere Leistung. Wenn ein schwacher Vergleich und Austausch eine Schleife erfordern würde und eine starke nicht, ist die starke vorzuziehen.

Die Antwort scheint also recht einfach zu sein: Wenn Sie eine Schleife nur wegen eines falschen Fehlers einführen müssten, tun Sie es nicht. verwenden strong. Wenn Sie trotzdem eine Schleife haben, verwenden Sie weak.

Warum ist !expectedim Beispiel

Dies hängt von der Situation und der gewünschten Semantik ab, wird jedoch normalerweise nicht für die Richtigkeit benötigt. Das Weglassen würde eine sehr ähnliche Semantik ergeben. Nur in einem Fall, in dem ein anderer Thread den Wert auf zurücksetzen könnte false, könnte sich die Semantik geringfügig ändern (ich kann jedoch kein aussagekräftiges Beispiel finden, in dem Sie dies wünschen würden). Siehe Tony Ds Kommentar für eine detaillierte Erklärung.

Es ist einfach eine Überholspur, wenn ein anderer Thread schreibt true: Dann brechen wir ab, anstatt trueerneut zu schreiben .

Über deine letzte Frage

Wie oben analysiert, sollten zwei Versionen in einer Schleife die gleiche / ähnliche Leistung bieten. Was vermisse ich?

Aus Wikipedia :

Reale Implementierungen von LL / SC sind nicht immer erfolgreich, wenn der betreffende Speicherort nicht gleichzeitig aktualisiert wird. Alle außergewöhnlichen Ereignisse zwischen den beiden Vorgängen, wie z. B. ein Kontextwechsel, eine andere Ladeverbindung oder sogar (auf vielen Plattformen) eine andere Lade- oder Speicheroperation, führen dazu, dass die Speicherbedingung fälschlicherweise fehlschlägt. Ältere Implementierungen schlagen fehl, wenn Aktualisierungen über den Speicherbus gesendet werden.

So schlägt LL / SC beispielsweise beim Kontextwechsel fälschlicherweise fehl. Jetzt würde die starke Version ihre "eigene kleine Schleife" bringen, um diesen falschen Fehler zu erkennen und ihn durch erneuten Versuch zu maskieren. Beachten Sie, dass diese eigene Schleife auch komplizierter ist als eine übliche CAS-Schleife, da sie zwischen Störfehlern (und Maskieren) und Fehlern aufgrund gleichzeitigen Zugriffs (was zu einer Rückgabe mit Wert führt false) unterscheiden muss. Die schwache Version hat keine solche eigene Schleife.

Da Sie in beiden Beispielen eine explizite Schleife angeben, ist es für die starke Version einfach nicht erforderlich, eine kleine Schleife zu haben. Folglich wird im Beispiel mit der strongVersion die Fehlerprüfung zweimal durchgeführt. einmal durch compare_exchange_strong(was komplizierter ist, da es zwischen fehlerhaften Fehlern und gleichzeitigem Zugriff unterscheiden muss) und einmal durch Ihre Schleife. Diese teure Prüfung ist unnötig und der Grund dafür weakwird hier schneller sein.

Beachten Sie auch, dass Ihr Argument (LL / SC) nur eine Möglichkeit ist, dies zu implementieren. Es gibt mehr Plattformen mit sogar unterschiedlichen Befehlssätzen. Beachten Sie außerdem (und was noch wichtiger ist), dass std::atomicalle Vorgänge für alle möglichen Datentypen unterstützt werden müssen. Selbst wenn Sie eine Struktur mit zehn Millionen Bytes deklarieren, können Sie compare_exchangediese verwenden. Selbst auf einer CPU mit CAS können Sie keine zehn Millionen Bytes CAS erstellen, sodass der Compiler andere Anweisungen generiert (wahrscheinlich Sperrenerfassung, gefolgt von einem nichtatomaren Vergleichen und Austauschen, gefolgt von einer Sperrenfreigabe). Überlegen Sie nun, wie viele Dinge passieren können, wenn Sie zehn Millionen Bytes austauschen. Während ein Störfehler bei 8-Byte-Austauschen sehr selten sein kann, kann er in diesem Fall häufiger auftreten.

Kurz gesagt, C ++ bietet Ihnen zwei Semantiken, eine "Best Effort" -Einheit ( weak) und eine "Ich werde es mit Sicherheit tun, egal wie viele schlimme Dinge dazwischen passieren können", eine ( strong). Wie diese auf verschiedenen Datentypen und Plattformen implementiert werden, ist ein völlig anderes Thema. Binden Sie Ihr mentales Modell nicht an die Implementierung auf Ihrer spezifischen Plattform. Die Standardbibliothek ist so konzipiert, dass sie mit mehr Architekturen arbeitet, als Sie vielleicht wissen. Die einzige allgemeine Schlussfolgerung, die wir ziehen können, ist, dass die Gewährleistung des Erfolgs normalerweise schwieriger ist (und daher möglicherweise zusätzliche Arbeit erfordert), als nur zu versuchen und Raum für einen möglichen Misserfolg zu lassen.

Warum muss es bei fast allen Anwendungen in einer Schleife sein ?

Denn wenn Sie keine Schleife ausführen und es fälschlicherweise fehlschlägt, hat Ihr Programm nichts Nützliches getan - Sie haben das Atomobjekt nicht aktualisiert und wissen nicht, wie hoch sein aktueller Wert ist (Korrektur: siehe Kommentar unten von Cameron). Wenn der Anruf nichts Nützliches bewirkt, wozu dann?

Bedeutet das, dass wir eine Schleife ausführen, wenn dies aufgrund von falschen Fehlern fehlschlägt?

Ja.

Wenn dies der Fall ist, warum verwenden compare_exchange_weak()und schreiben wir die Schleife dann selbst? Wir können einfach compare_exchange_strong () verwenden, das meiner Meinung nach falsche Fehler für uns beseitigen sollte. Was sind die häufigsten Anwendungsfälle von compare_exchange_weak ()?

Bei einigen Architekturen compare_exchange_weakist dies effizienter, und falsche Fehler sollten eher selten auftreten, sodass möglicherweise effizientere Algorithmen unter Verwendung der schwachen Form und einer Schleife geschrieben werden können.

Im Allgemeinen ist es wahrscheinlich besser, stattdessen die starke Version zu verwenden, wenn Ihr Algorithmus keine Schleife ausführen muss, da Sie sich keine Gedanken über falsche Fehler machen müssen. Wenn es auch für die starke Version ohnehin eine Schleife geben muss (und viele Algorithmen ohnehin eine Schleife benötigen), ist die Verwendung der schwachen Form auf einigen Plattformen möglicherweise effizienter.

Warum gibt !expectedes in der Schleife Bedingung?

Der Wert könnte truevon einem anderen Thread festgelegt worden sein, sodass Sie nicht ständig versuchen möchten, ihn in einer Schleife festzulegen.

Bearbeiten:

Wie oben analysiert, sollten zwei Versionen in einer Schleife die gleiche / ähnliche Leistung bieten. Was vermisse ich?

Sicherlich ist es offensichtlich, dass auf Plattformen, auf denen ein fehlerhafter Fehler möglich ist, die Implementierung compare_exchange_strongkomplizierter sein muss, um auf fehlerhaften Fehler zu prüfen und es erneut zu versuchen.

Die schwache Form kehrt nur bei einem falschen Fehler zurück und versucht es nicht erneut.

Ich versuche, dies selbst zu beantworten, nachdem ich verschiedene Online-Ressourcen (z. B. diese und diese ), den C ++ 11-Standard sowie die hier gegebenen Antworten durchgesehen habe.

Die zugehörigen Fragen werden zusammengeführt (z. B. " Warum! Erwartet? " Wird mit "Warum vergleiche_exchange_weak () in eine Schleife setzen? " Zusammengeführt) und die Antworten werden entsprechend angegeben.

Warum muss compare_exchange_weak () in fast allen Anwendungen in einer Schleife sein?

Typisches Muster A.

Sie müssen eine atomare Aktualisierung basierend auf dem Wert in der atomaren Variablen durchführen. Ein Fehler zeigt an, dass die Variable nicht mit unserem gewünschten Wert aktualisiert wurde und wir es erneut versuchen möchten. Beachten Sie, dass es uns egal ist, ob es aufgrund eines gleichzeitigen Schreibvorgangs oder eines falschen Fehlers fehlschlägt. Aber es ist uns wichtig, dass wir diese Änderung vornehmen.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

Ein Beispiel aus der Praxis besteht darin, dass mehrere Threads gleichzeitig ein Element zu einer einzeln verknüpften Liste hinzufügen. Jeder Thread lädt zuerst den Kopfzeiger, weist einen neuen Knoten zu und hängt den Kopf an diesen neuen Knoten an. Schließlich wird versucht, den neuen Knoten mit dem Kopf zu tauschen.

Ein weiteres Beispiel ist die Implementierung von Mutex mit std::atomic<bool>. Allenfalls kann ein Thread den kritischen Abschnitt zu einer Zeit ein, je nachdem , welcher Thread zuerst eingestellt currentauf trueund um die Schleife zu beenden.

Typisches Muster B.

Dies ist eigentlich das Muster, das in Anthonys Buch erwähnt wird. Im Gegensatz zu Muster A möchten Sie, dass die atomare Variable einmal aktualisiert wird, aber es ist Ihnen egal, wer dies tut. Solange es nicht aktualisiert wird, versuchen Sie es erneut. Dies wird normalerweise mit booleschen Variablen verwendet. Sie müssen beispielsweise einen Trigger implementieren, damit eine Zustandsmaschine weitergeht. Welcher Thread den Abzug drückt, ist unabhängig.

expected = false;
// !expected: if expected is set to true by another thread, it's done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Beachten Sie, dass wir dieses Muster im Allgemeinen nicht zum Implementieren eines Mutex verwenden können. Andernfalls können sich mehrere Threads gleichzeitig im kritischen Bereich befinden.

Das heißt, es sollte selten sein, compare_exchange_weak()außerhalb einer Schleife zu verwenden. Im Gegenteil, es gibt Fälle, in denen die starke Version verwendet wird. Z.B,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak ist hier nicht richtig, denn wenn es aufgrund eines falschen Fehlers zurückkehrt, ist es wahrscheinlich, dass noch niemand den kritischen Abschnitt belegt.

Hungernder Faden?

Ein erwähnenswerter Punkt ist, was passiert, wenn weiterhin falsche Fehler auftreten und der Faden aushungert? Theoretisch könnte es auf Plattformen passieren, wenn compare_exchange_XXX()es als eine Folge von Anweisungen implementiert wird (z. B. LL / SC). Häufiger Zugriff auf dieselbe Cache-Zeile zwischen LL und SC führt zu kontinuierlichen Störfehlern. Ein realistischeres Beispiel ist eine dumme Planung, bei der alle gleichzeitigen Threads auf folgende Weise verschachtelt werden.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

Kann es passieren?

Zum Glück wird es nicht für immer passieren, dank der Anforderungen von C ++ 11:

Implementierungen sollten sicherstellen, dass schwache Vergleichs- und Austauschoperationen nicht konsistent false zurückgeben, es sei denn, das atomare Objekt hat einen anderen als den erwarteten Wert oder es werden gleichzeitig Änderungen am atomaren Objekt vorgenommen.

Warum verwenden wir compare_exchange_weak () und schreiben die Schleife selbst? Wir können einfach compare_exchange_strong () verwenden.

Es hängt davon ab, ob.

Fall 1: Wenn beide innerhalb einer Schleife verwendet werden müssen. C ++ 11 sagt:

Wenn sich ein Vergleich und Austausch in einer Schleife befindet, bietet die schwache Version auf einigen Plattformen eine bessere Leistung.

Auf x86 (zumindest derzeit. Vielleicht wird eines Tages auf ein ähnliches Schema wie LL / SC zurückgegriffen, um die Leistung zu verbessern, wenn mehr Kerne eingeführt werden) sind die schwache und die starke Version im Wesentlichen gleich, da beide auf die einzelne Anweisung hinauslaufen cmpxchg. Auf einigen anderen Plattformen, auf denen compare_exchange_XXX()keine atomare Implementierung erfolgt (hier bedeutet dies, dass kein einzelnes Hardware-Grundelement vorhanden ist), kann die schwache Version innerhalb der Schleife den Kampf gewinnen, da die starke Version die falschen Fehler behandeln und es erneut versuchen muss.

Aber,

selten, so können wir es vorziehen , compare_exchange_strong()über compare_exchange_weak()selbst in einer Schleife. Wenn beispielsweise viel zu tun ist, wird eine atomare Variable geladen und ein berechneter neuer Wert ausgetauscht (siehe function()oben). Wenn sich die atomare Variable selbst nicht häufig ändert, müssen wir die kostspielige Berechnung nicht für jeden falschen Fehler wiederholen. Stattdessen können wir hoffen, dass compare_exchange_strong()solche Fehler "absorbiert" werden, und wir wiederholen die Berechnung nur, wenn sie aufgrund einer tatsächlichen Wertänderung fehlschlägt.

Fall 2: Wenn nur compare_exchange_weak() innerhalb einer Schleife verwendet werden muss. C ++ 11 sagt auch:

Wenn ein schwacher Vergleich und Austausch eine Schleife erfordern würde und eine starke nicht, ist die starke vorzuziehen.

Dies ist normalerweise der Fall, wenn Sie eine Schleife ausführen, um falsche Fehler in der schwachen Version zu beseitigen. Sie versuchen es erneut, bis der Austausch entweder erfolgreich ist oder aufgrund des gleichzeitigen Schreibens fehlgeschlagen ist.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Bestenfalls erfindet es die Räder neu und funktioniert genauso wie compare_exchange_strong(). Schlechter? Dieser Ansatz nutzt Maschinen, die einen nicht störenden Vergleich und Austausch von Hardware ermöglichen, nicht vollständig aus .

Wenn Sie für andere Dinge eine Schleife durchführen (siehe z. B. "Typisches Muster A" oben), besteht eine gute Chance, dass diese compare_exchange_strong()auch in eine Schleife eingefügt wird, die uns zum vorherigen Fall zurückführt.

Also gut, ich brauche eine Funktion, die atomare Linksverschiebung ausführt. Mein Prozessor hat hierfür keine native Operation, und die Standardbibliothek hat keine Funktion dafür. Es sieht also so aus, als würde ich meine eigene schreiben. Hier geht:

void atomicLeftShift(std::atomic<int>* var, int shiftBy)
{
    do {
        int oldVal = std::atomic_load(var);
        int newVal = oldVal << shiftBy;
    } while(!std::compare_exchange_weak(oldVal, newVal));
}

Es gibt zwei Gründe, warum die Schleife möglicherweise mehrmals ausgeführt wird.

1. Jemand anderes hat die Variable geändert, während ich meine Linksschicht gemacht habe. Die Ergebnisse meiner Berechnung sollten nicht auf die atomare Variable angewendet werden, da dadurch das Schreiben eines anderen effektiv gelöscht wird.
2. Meine CPU rülpste und das schwache CAS fiel fälschlicherweise aus.

Es ist mir ehrlich gesagt egal welches. Das Schalten nach links ist schnell genug, dass ich es genauso gut noch einmal machen kann, selbst wenn der Fehler falsch war.

Was jedoch weniger schnell ist, ist der zusätzliche Code, den starkes CAS benötigt, um schwaches CAS zu umschließen, um stark zu sein. Dieser Code macht nicht viel, wenn das schwache CAS erfolgreich ist ... aber wenn er fehlschlägt, muss das starke CAS Detektivarbeit leisten, um festzustellen, ob es sich um Fall 1 oder Fall 2 handelt. Diese Detektivarbeit hat die Form einer zweiten Schleife. effektiv in meiner eigenen Schleife. Zwei verschachtelte Schleifen. Stellen Sie sich vor, Ihr Algorithmuslehrer starrt Sie gerade an.

Und wie ich bereits erwähnt habe, ist mir das Ergebnis dieser Detektivarbeit egal! In jedem Fall werde ich das CAS wiederholen. Die Verwendung von starkem CAS bringt mir also genau nichts und verliert mir eine kleine, aber messbare Menge an Effizienz.

Mit anderen Worten, schwaches CAS wird verwendet, um atomare Aktualisierungsoperationen zu implementieren. Starkes CAS wird verwendet, wenn Sie sich für das Ergebnis von CAS interessieren.

Ich denke, die meisten der obigen Antworten beziehen sich auf "Störfehler" als eine Art Problem, Kompromiss zwischen Leistung und Korrektheit.

Es kann gesehen werden, dass die schwache Version die meiste Zeit schneller ist, aber im Falle eines falschen Fehlers wird sie langsamer. Und die starke Version ist eine Version, bei der keine Möglichkeit eines falschen Ausfalls besteht, die jedoch fast immer langsamer ist.

Für mich besteht der Hauptunterschied darin, wie diese beiden Versionen das ABA-Problem behandeln:

Eine schwache Version ist nur dann erfolgreich, wenn niemand die Cache-Zeile zwischen Laden und Speichern berührt hat, sodass das ABA-Problem zu 100% erkannt wird.

Eine starke Version schlägt nur fehl, wenn der Vergleich fehlschlägt, sodass ein ABA-Problem ohne zusätzliche Maßnahmen nicht erkannt wird.

Wenn Sie also eine schwache Version für eine Architektur mit schwacher Ordnung verwenden, benötigen Sie theoretisch keinen ABA-Erkennungsmechanismus, und die Implementierung ist viel einfacher und bietet eine bessere Leistung.

Unter x86 (Architektur mit starker Ordnung) sind die schwache und die starke Version identisch, und beide leiden unter ABA-Problemen.

Wenn Sie also einen vollständig plattformübergreifenden Algorithmus schreiben, müssen Sie das ABA-Problem trotzdem beheben. Die Verwendung der schwachen Version bietet also keinen Leistungsvorteil, aber es gibt einen Leistungsnachteil für die Behandlung von falschen Fehlern.

Fazit: Aus Gründen der Portabilität und Leistung ist die starke Version immer eine bessere oder gleichwertige Option.

Eine schwache Version kann nur dann eine bessere Option sein, wenn Sie damit ABA-Gegenmaßnahmen vollständig überspringen können oder Ihr Algorithmus sich nicht um ABA kümmert.