Ich versuche mein Verständnis von Speicherbarrieren zu verbessern. Angenommen, wir haben ein schwaches Speichermodell und passen den Dekker-Algorithmus an. Ist es möglich, dass es durch das Hinzufügen von Speicherbarrieren unter dem Modell des schwachen Speichers funktioniert?
Ich denke, die Antwort ist ein überraschendes Nein. Der Grund (wenn ich richtig bin) ist, dass, obwohl eine Speicherbarriere verwendet werden kann, um sicherzustellen, dass ein Lesen nicht an einem anderen vorbei bewegt wird, es nicht sicherstellen kann, dass ein Lesen keine veralteten Daten (wie die in einem Cache) sieht. So könnte es in der Vergangenheit etwas Zeit sehen, als der kritische Bereich entsperrt wurde (pro Cache der CPU), aber andere Prozessoren sehen ihn zur Zeit möglicherweise als gesperrt. Wenn mein Verständnis korrekt ist, muss man verriegelte Operationen verwenden, wie sie üblicherweise als Test-and-Set oder Compare-and-Swap bezeichnet werden, um eine synchronisierte Übereinstimmung eines Werts an einem Speicherort unter mehreren Prozessoren sicherzustellen.
Können wir also zu Recht erwarten, dass kein System mit einem schwachen Speichermodell nur Speicherbarrieren bietet? Das System muss Operationen wie Test-and-Set oder Compare-and-Swap bereitstellen, um nützlich zu sein.
Ich stelle fest, dass populäre Prozessoren, einschließlich x86, Speichermodelle bereitstellen, die viel stärker sind als ein schwaches Speichermodell. Bitte konzentrieren Sie sich auf schwache Speichermodelle.
(Wenn Dekkers Algorithmus eine schlechte Wahl ist, wählen Sie einen anderen gegenseitigen Ausschlussalgorithmus, bei dem Speicherbarrieren, wenn möglich, erfolgreich eine korrekte Synchronisation erreichen können.)
Sie haben Recht, dass eine Speicherbarriere nicht gewährleisten kann, dass ein Lesevorgang aktuelle Werte anzeigt. Was es tut, ist eine Reihenfolge zwischen Operationen erzwingen, sowohl für einen einzelnen Thread, als auch zwischen Threads.
Wenn zum Beispiel Thread A eine Reihe von Speichern ausführt und dann eine Freigabesperre vor einem letzten Speichern an einer Flagposition ausführt und Thread B von der Flagposition liest und dann eine Erfassungsbarriere ausführt, bevor die anderen Werte gelesen werden, dann Bei anderen Variablen werden die Werte von Thread A gespeichert:
%Vor% Natürlich müssen Sie sicherstellen, dass das Laden und Speichern von flag atomar ist (welche einfachen Lade- und Speicherbefehle auf den meisten gängigen CPUs sind, vorausgesetzt, die Variablen sind entsprechend ausgerichtet). Ohne die while-Schleife in Thread B kann Thread B möglicherweise einen veralteten Wert (0) für flag lesen, und daher können Sie keine der für die anderen Variablen gelesenen Werte garantieren.
Zäune können somit verwendet werden, um die Synchronisation in Dekkers Algorithmus zu erzwingen.
Hier ist eine Beispielimplementierung in C ++ (mit C ++ 0x atomaren Variablen):
%Vor%Eine vollständige Analyse finden Sie in meinem Blog-Eintrag unter Ссылка
Nehmen wir an, Sie legen nach jeder Anweisung eine Lade- und Speicherbarriere an und zusätzlich haben Sie sichergestellt, dass der Compiler Ihre Filialen nicht neu geordnet hat. Wäre dies nicht, auf irgendeiner vernünftigen Architektur, strikte Konsistenz? Dekker arbeitet an sequentiell konsistenten Architekturen. Sequenzielle Konsistenz ist eine schwächere Bedingung als strikte Konsistenz.
Auch bei einer CPU mit einem schwachen Konsistenzmodell würden Sie immer noch mit Cache-Kohärenz rechnen. Ich glaube, dass das Verhalten von Speicherpuffern und spekulativen Lesevorgängen dort, wo Dinge entgleist sind, und welche Operationen verfügbar sind, Flush-Stored-Writes und Invalidate-Speculated-Reads sind. Wenn es keinen Ladezaun gibt, der spekulierte Lesevorgänge ungültig machen kann, oder wenn es keinen Schreibzaun gibt, der einen Speicherpuffer löscht, und Dekker nicht implementiert werden kann, können Sie keinen Mutex! Also hier ist mein Anspruch. Wenn Sie eine Schreibbarriere und eine Lesebarriere haben und der Cache zwischen den CPUs kohärent ist, können Sie den gesamten Code sequentiell konsistent machen, indem Sie nach jeder Anweisung Schreibvorgänge (Zaun speichern) und Spekulationen (Lesezaun) vor jedem leeren Anweisung. Ich behaupte also, dass Sie für das, worüber Sie sprechen, keine Atomik brauchen und dass Sie nur mit Dekkers tun können, was Sie brauchen. Sicher, du würdest es nicht wollen. BTW, Corensic, das Unternehmen, für das ich arbeite, schreibt coole Tools zum Debuggen von Nebenläufigkeitsproblemen. Besuche Ссылка .
Einige Barrieren (z. B. powerpc isync und .acq load on ia64) wirken sich auch auf nachfolgende Lasten aus. dh wenn vor dem isync aufgrund des prefetching ein load verfügbar war, muss dieser verworfen werden. Bei geeigneter Verwendung reicht das vielleicht aus, um den Dekker-Algorithmus an einem schwachen Speichermodell arbeiten zu lassen.
Sie haben auch eine Cache-Invalidierungslogik, die für Sie arbeitet. Wenn Sie wissen, dass Ihre Ladung aufgrund einer Isync aktuell ist und die zwischengespeicherte Version der Daten ungültig wird, wenn eine andere CPU sie berührt, reicht das?
Interessante Fragen beiseite, Dekkers Algorithmus ist für alle praktischen Zwecke dumm. Sie werden atomare Hardwareschnittstellen und Speicherbarrieren für jede reale Anwendung benutzen wollen, so dass es sich nicht lohnt, sich auf die Reparatur von Dekkers mit Atomics zu konzentrieren;)
Tags und Links concurrency lock-free memory-barriers mutex