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