Load-Link/Store-Conditional - Load-link/store-conditional
In der Informatik sind Load-Linked/Store-Conditional ( LL/SC ), manchmal auch als Load-Reserved/Store-Conditional ( LR/SC ) bekannt, ein Befehlspaar, das beim Multithreading verwendet wird , um eine Synchronisation zu erreichen . Load-Link gibt den aktuellen Wert einer Speicherstelle zurück, während eine nachfolgende Speicherbedingung an derselben Speicherstelle einen neuen Wert nur dann speichert, wenn seit der Load-Link an dieser Stelle keine Aktualisierungen aufgetreten sind. Zusammen implementiert dies eine blockierungsfreie atomare Read-Modify-Write- Operation.
"Load-linked" wird auch als Load-Link , Load-Reserved und Load-Locked bezeichnet .
LL/SC wurde ursprünglich von Jensen, Hagensen und Broughton für den S-1 AAP Multiprozessor am Lawrence Livermore National Laboratory vorgeschlagen .
Vergleich von LL/SC und Compare-and-Swap
Wenn Aktualisierungen aufgetreten sind, schlägt die Speicherbedingung garantiert fehl, selbst wenn der von der Ladeverbindung gelesene Wert inzwischen wiederhergestellt wurde. Daher ist ein LL/SC-Paar stärker als ein Read gefolgt von einem Compare-and-Swap (CAS), der keine Aktualisierungen erkennt, wenn der alte Wert wiederhergestellt wurde (siehe ABA-Problem ).
Echte Implementierungen von LL/SC sind nicht immer erfolgreich, selbst wenn es keine gleichzeitigen Aktualisierungen an der fraglichen Speicherstelle gibt. Alle außergewöhnlichen Ereignisse zwischen den beiden Operationen, wie 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 wird fehlschlagen , wenn es irgendwelche Updates den Speicherbus ausgestrahlt. Dies wird von Forschern als schwaches LL/SC bezeichnet, da es viele theoretische LL/SC-Algorithmen bricht. Schwäche ist relativ, und einige schwache Implementierungen können für einige Algorithmen verwendet werden.
LL/SC ist schwieriger zu emulieren als CAS. Darüber hinaus kann das Stoppen der Ausführung von Code zwischen gepaarten LL/SC-Befehlen, z.
Nichtsdestotrotz ist LL/SC in dem Sinne äquivalent zu CAS, dass jedes Primitiv in Bezug auf das andere, in O(1) und wartefrei implementiert werden kann.
Implementierungen
LL/SC-Anweisungen werden unterstützt von:
- Alpha : ldl_l/stl_c und ldq_l/stq_c
- PowerPC / Power ISA : lwarx/stwcx und ldarx/stdcx
- MIPS : ll/sc
- ARM : ldrex/strex (ARMv6 und v7) und ldxr/stxr (ARM-Version 8)
- RISC-V : lr/sc
- ARC : LLOCK / Scond
Einige CPUs erfordern, dass die Adresse, auf die ausschließlich zugegriffen wird, im Write-Through-Modus konfiguriert wird.
Typischerweise verfolgen CPUs die Load-Linked-Adresse in einer Cache-Zeile oder einer anderen Granularität, so dass jede Änderung an irgendeinem Teil der Cache-Zeile (sei es über die Speicherbedingung eines anderen Kerns oder nur durch eine normale Speicherung) ausreicht, um den Speichervorgang zu veranlassen -bedingt zu scheitern.
Alle diese Plattformen bieten schwaches LL/SC. Die PowerPC-Implementierung ermöglicht es einem LL/SC-Paar, Ladevorgänge zu umschließen und sogar in andere Cache-Lines zu speichern (obwohl dieser Ansatz anfällig für falsche Cache-Line-Sharing ist). Dies ermöglicht es, zum Beispiel sperrfreies Referenzzählen angesichts sich ändernder Objektgraphen mit beliebiger Zählerwiederverwendung zu implementieren (was ansonsten doppeltes Vergleichen und Austauschen , DCAS erfordert). RISC-V bietet eine architektonische Garantie für den eventuellen Fortschritt für LL/SC-Sequenzen begrenzter Länge.
Einige ARM-Implementierungen definieren plattformabhängige Blöcke, die von 8 Byte bis 2048 Byte reichen, und ein LL/SC-Versuch in einem bestimmten Block schlägt fehl, wenn zwischen LL und SC ein normaler Speicherzugriff innerhalb desselben Blocks stattfindet. Andere ARM-Implementierungen schlagen fehl, wenn irgendwo im gesamten Adressraum eine Änderung erfolgt. Die erstgenannte Implementierung ist die stärkere und praktischste.
LL/SC hat gegenüber CAS zwei Vorteile beim Entwerfen einer Load-Store-Architektur : Lese- und Schreibvorgänge sind getrennte Befehle, wie es die Designphilosophie (und die Pipeline-Architektur ) erfordert ; und beide Befehle können unter Verwendung von nur zwei Registern (Adresse und Wert) ausgeführt werden, was natürlich in gemeinsame 2-Operanden-ISAs passt . CAS hingegen benötigt drei Register (Adresse, alter Wert, neuer Wert) und eine Abhängigkeit zwischen gelesenem und geschriebenem Wert. x86 hat , da es sich um eine CISC- Architektur handelt, diese Einschränkung nicht; obwohl moderne Chips einen CAS-Befehl intern in separate LL/SC - Mikrooperationen übersetzen können.
Erweiterungen
Hardware-LL/SC-Implementierungen erlauben typischerweise keine Verschachtelung von LL/SC-Paaren. Ein Verschachtelungs-LL/SC-Mechanismus kann verwendet werden, um ein MCAS-Grundelement (Mehrwort-CAS, bei dem die Wörter verstreut sein können) bereitzustellen. Im Jahr 2013 implementierten Trevor Brown, Faith Ellen und Eric Ruppert in Software eine Multi-Adress-LL/SC-Erweiterung (die sie LLX/SCX nennen), die auf automatisierter Codegenerierung beruht; sie haben es verwendet , um eine des leistungsfähigsten gleichzeitig zu implementieren binären Suchbaumes (eigentlich ein chromatischer Baum ), leicht die Spiel gegen JDK CAS-basierte Sprungliste Implementierung.
Siehe auch
Verweise
- Jensen, Eric H.; Hagensen, Gary W.; Broughton, Jeffrey M. (November 1987). Ein neuer Ansatz für den exklusiven Datenzugriff in Shared-Memory-Multiprozessoren (PDF) (Technischer Bericht). Lawrence Livermore National Laboratory. UCRL-97663. Archiviert vom Original (PDF) am 02.02.2017 . Abgerufen 2012-02-22 .
- Bruner, John D.; Hagensen, Gary W.; Jensen, Eric H.; Pattin, Jay C.; Broughton, Jeffrey M. (11. November 1987). Cache-Kohärenz auf dem S-1 AAP (PDF) (Technischer Bericht). Lawrence Livermore National Laboratory. UCRL-97646. Archiviert vom Original (PDF) am 2. Februar 2017 . Abgerufen am 10. November 2013 .
- Detlefs, D.; Martin, P.; Moir, M.; Steele, Jr., Guy L. (2001). "Sperrfreies Referenzzählen". PODC '01 Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing . ACM. S. 190–9. CiteSeerX 10.1.1.92.8221 . doi : 10.1145/383962.384016 . ISBN 1-58113-383-9.
- Reinholtz, Kirk (Dezember 2004). "Atomreferenzzählzeiger" . C/C++-Benutzerjournal .
- Sites, RL (Februar 1993). "Alpha AXP-Architektur". Komm. ACM . 36 (2): 33–44. doi : 10.1145/151220.151226 .