Ich habe einen Lock-Free-Code geschrieben, der gut mit Local funktioniert liest, unter den meisten Bedingungen.
Bedeutet lokales Drehen auf einem Speicherlesen notwendigerweise I müssen vor dem Drehen IMMER eine Speicherbarriere einlegen gelesen?
(Um dies zu überprüfen, habe ich einen Leser / Schreiber erstellt Kombination, die dazu führt, dass ein Leser niemals die geschriebener Wert, unter bestimmten sehr spezifischen Bedingungen - dedizierte CPU, Prozess an CPU angeschlossen, der Optimierer hat den ganzen Weg nach oben gedreht, keine andere Arbeit in der Schleife - so zeigen die Pfeile in diese Richtung, aber ich bin nicht völlig sicher über die Kosten des Durchdrehens durch eine Erinnerung Barriere.)
Was kostet es, sich durch eine Speicherbarriere zu drehen, wenn Es gibt nichts, was im Speicherpuffer des Cache geleert werden kann. h. der gesamte Prozess macht (in C) ist
%Vor%Bin ich richtig anzunehmen, dass es kostenlos ist und es nicht belasten wird der Speicherbus mit jedem Verkehr?
Eine andere Möglichkeit, dies zu stellen, ist zu fragen: macht eine Speicherbarriere etwas mehr als: Spülen Sie den Speicherpuffer, wenden Sie die Invalidierungen zu und verhindern den Compiler von Neuordnen von Lese- / Schreibvorgängen an seinem Speicherort?
Disassembling, __sync_synchronize () scheint übersetzt zu werden in:
%Vor%Aus dem Intel-Handbuch (ähnlich nebulös für den Neophyten):
%Vor%Meine Übersetzung: "Wenn du LOCK sagst, wäre das teuer, aber wir sind es mach es nur wo nötig. "
@BlankXavier:
Ich habe getestet, dass, wenn der Schreiber nicht explizit den Schreibvorgang aus dem Speicherpuffer auslöst und es der einzige Prozess ist, der auf dieser CPU läuft, der Leser niemals den Effekt des Schreibers sehen kann ( Ich kann es mit einem Testprogramm reproduzieren, aber wie ich oben erwähnt habe, passiert es nur mit einem spezifischen Test, mit spezifischen Kompilierungsoptionen und dedizierten Kernzuweisungen - mein Algorithmus funktioniert gut, nur wenn ich neugierig wurde, wie das funktioniert und geschrieben hat der explizite Test, dass ich erkannte, dass es möglicherweise ein Problem auf dem Weg haben könnte).
Ich denke standardmäßig sind einfache Schreibvorgänge WB-Schreibvorgänge (Zurückschreiben), was bedeutet, dass sie nicht sofort ausgespült werden, sondern Lesevorgänge ihren jüngsten Wert annehmen (ich denke, sie nennen das "Speichernweiterleitung"). Also verwende ich eine CAS-Anweisung für den Schreiber. Ich habe im Intel-Handbuch alle diese verschiedenen Arten von Schreibimplementierungen (UC, WC, WT, WB, WP), Intel Vol. 3A, Kap. 11-10, entdeckt, die immer noch über sie lernen.
Meine Ungewissheit liegt auf der Seite des Lesers: Ich verstehe aus McKenneys Papier, dass es auch eine Ungültigkeitswarteschlange gibt, eine Warteschlange von eingehenden Ungültigkeitserklärungen vom Bus in den Cache. Ich bin mir nicht sicher, wie dieser Teil funktioniert. Insbesondere scheinen Sie zu implizieren, dass das Durchlaufen eines normalen Lesevorgangs (dh ohne Sperre, ohne Sperre und Verwendung von flüchtig, um sicherzustellen, dass das Optimierungsprogramm den einmal kompilierten Lesevorgang verlässt) jedes Mal in die "Invalidierungswarteschlange" eincheckt (wenn so etwas existiert). Wenn ein einfaches Lesen nicht gut genug ist (dh eine alte Cache-Zeile lesen könnte, die immer noch gültig erscheint, während eine Invalidierung in die Warteschlange geht (das klingt für mich auch etwas inkohärent, aber wie funktionieren Invalidierungswarteschlangen?)), Dann wäre ein atomarer Lesevorgang notwendig sein und meine Frage ist: Wird dies in diesem Fall Auswirkungen auf den Bus haben? (Ich denke wahrscheinlich nicht.)
Ich lese immer noch meinen Weg durch das Intel-Handbuch und während ich eine großartige Diskussion über die Speicherweiterleitung sehe, habe ich keine gute Diskussion über Entwertungswarteschlangen gefunden. Ich habe beschlossen, meinen C-Code in ASM zu konvertieren und zu experimentieren. Ich denke, das ist der beste Weg, um wirklich ein Gefühl dafür zu bekommen, wie das funktioniert.
Die Anweisung "xchg reg, [mem]" signalisiert über den LOCK-Pin des Kerns ihre Sperrabsicht. Dieses Signal bahnt sich seinen Weg an anderen Kernen vorbei und zwischengespeichert zu den Bus-Mastering-Bussen (PCI-Varianten usw.), die beenden, was sie tun, und schließlich wird der LOCKA (Bestätigungs) Pin der CPU signalisieren, dass der xchg abgeschlossen sein kann. Dann wird das LOCK-Signal abgeschaltet. Diese Sequenz kann sehr lange dauern (Hunderte von CPU-Zyklen oder mehr). Danach werden die entsprechenden Cache-Zeilen der anderen Kerne ungültig gemacht und Sie haben einen bekannten Zustand, dh einen, der zwischen den Kernen synchronisiert wurde.
Die xchg-Anweisung ist alles, was zum Implementieren einer atomaren Sperre erforderlich ist. Wenn die Sperre selbst erfolgreich ist, haben Sie Zugriff auf die Ressource, für die Sie die Sperre definiert haben, um den Zugriff zu steuern. Eine solche Ressource könnte ein Speicherbereich, eine Datei, ein Gerät, eine Funktion oder was Sie haben. Dennoch bleibt es dem Programmierer immer überlassen, Code zu schreiben, der diese Ressource verwendet, wenn sie gesperrt wurde, und nicht, wenn dies nicht der Fall ist. In der Regel sollte die Codefolge nach einer erfolgreichen Sperre so kurz wie möglich sein, damit anderer Code so wenig wie möglich vom Zugriff auf die Ressource behindert wird.
Beachten Sie, dass, wenn die Sperre nicht erfolgreich war, Sie es erneut versuchen müssen, indem Sie ein neues xchg ausgeben.
"Lock free" ist ein ansprechendes Konzept, erfordert aber die Eliminierung von gemeinsam genutzten Ressourcen. Wenn Ihre Anwendung über zwei oder mehr Kerne verfügt, die gleichzeitig aus einer gemeinsamen Speicheradresse lesen und sie in eine gemeinsame Speicheradresse schreiben, ist "lock free" keine Option.
Ich habe die Frage vielleicht nicht richtig verstanden, aber ...
Wenn Sie sich drehen, ist ein Problem der Compiler, der Ihren Spin optimiert. Volatile löst das.
Die Speicherschranke, wenn Sie eine haben, wird vom Schreiber an die Spin-Sperre ausgegeben, nicht an den Leser. Der Schreiber hat nicht wirklich , um einen zu verwenden - so wird sichergestellt, dass der Schreibvorgang sofort ausgeführt wird, aber er wird trotzdem ziemlich bald ausgehen.
Die Barriere verhindert, dass ein Thread diesen Code über seinen Standort neu sortiert, was seine anderen Kosten ist.
Denken Sie daran, dass Barrieren normalerweise dazu verwendet werden, Gruppen von Speicherzugriffen zu bestellen, so dass Ihr Code sehr wahrscheinlich auch an anderen Stellen Barrieren benötigt. Zum Beispiel wäre es nicht ungewöhnlich, dass die Barriereanforderung stattdessen so aussieht:
%Vor% Diese Barriere würde verhindern, dass Lasten und Speicher in dem if-Block (dh pShared->something ) ausgeführt werden, bevor die value Last abgeschlossen ist. Ein typisches Beispiel ist, dass Sie einen "Produzenten" haben, der einen Speicher von v != 0 verwendet, um zu kennzeichnen, dass ein anderer Speicher ( pShared->something ) in einem anderen erwarteten Zustand ist, wie in:
In diesem Szenario für typische Produzentenverbraucher werden Sie fast immer gepaarte Barrieren benötigen, eine für den Speicher, der anzeigt, dass der Hilfsspeicher sichtbar ist (so dass die Effekte des Wertspeichers nicht vor dem etwas Speicher sichtbar sind). und eine Barriere für den Verbraucher (damit die Last nicht gestartet wird, bevor der Wert geladen ist).
Diese Barrieren sind auch plattformspezifisch. Auf powerpc (mit dem xlC-Compiler) würden Sie beispielsweise __isync() und __lwsync() für den Consumer bzw. Producer verwenden. Welche Barrieren erforderlich sind, hängt auch von dem Mechanismus ab, den Sie für das Laden und Laden von value verwenden. Wenn Sie eine atomare intrinsische Methode verwendet haben, die zu einer intel LOCK (möglicherweise implizit) führt, führt dies zu einer impliziten Barriere, sodass Sie möglicherweise nichts benötigen. Darüber hinaus müssen Sie wahrscheinlich auch volatilen Gebrauch (oder verwenden Sie vorzugsweise eine atomare Implementierung, die dies unter den Abdeckungen tut), um den Compiler zu tun, was Sie wollen.
Tags und Links lock-free memory-barriers spinlock barrier