Vergleichen und tauschen - Compare-and-swap

In der Informatik ist Compare-and-Swap ( CAS ) eine atomare Anweisung, die beim Multithreading verwendet wird , um eine Synchronisation zu erreichen . Es vergleicht den Inhalt einer Speicherstelle mit einem gegebenen Wert und ändert den Inhalt dieser Speicherstelle nur dann, wenn sie gleich sind, auf einen neuen gegebenen Wert. Dies wird als eine einzelne atomare Operation durchgeführt. Die Atomizität garantiert, dass der neue Wert auf Basis aktueller Informationen berechnet wird; Wäre der Wert zwischenzeitlich von einem anderen Thread aktualisiert worden, würde der Schreibvorgang fehlschlagen. Das Ergebnis der Operation muss angeben, ob die Substitution durchgeführt wurde; Dies kann entweder mit einer einfachen booleschen Antwort erfolgen (diese Variante wird oft als Compare-and-Set bezeichnet ) oder durch Rückgabe des aus dem Speicherplatz gelesenen Werts ( nicht des darauf geschriebenen Werts).

Überblick

Eine Vergleichs-und-Swap-Operation ist eine atomare Version des folgenden Pseudocodes , wobei * den Zugriff über einen Zeiger bezeichnet : 

function cas(p: pointer to int, old: int, new: int) is
    if *p ≠ old
        return false

    *p ← new

    return true

Diese Operation wird verwendet, um Synchronisationsprimitive wie Semaphoren und Mutexes sowie ausgefeiltere sperr- und wartefreie Algorithmen zu implementieren . Maurice Herlihy (1991) bewies, dass CAS mehr dieser Algorithmen implementieren kann als atomares Lesen, Schreiben oder Abrufen und Hinzufügen , und unter der Annahme einer ziemlich großen Speichermenge, dass es alle implementieren kann. CAS entspricht Last-Link / Speicher-bedingter , in dem Sinne , dass eine konstante Anzahl von Anrufungen der beiden primitiven verwendet werden kann , die andere in einer implementieren Wartefreie Art und Weise.

Algorithmen, die um CAS herum aufgebaut sind, lesen normalerweise einen Schlüsselspeicherplatz und merken sich den alten Wert. Basierend auf diesem alten Wert berechnen sie einen neuen Wert. Dann versuchen sie, den neuen Wert mit CAS einzutauschen, wobei der Vergleich prüft, ob der Standort noch dem alten Wert entspricht. Wenn CAS anzeigt, dass der Versuch fehlgeschlagen ist, muss er von Anfang an wiederholt werden: Die Stelle wird neu gelesen, ein neuer Wert wird neu berechnet und der CAS wird erneut versucht. Anstatt es sofort nach einem fehlgeschlagenen CAS-Vorgang erneut zu versuchen, haben Forscher herausgefunden, dass die Gesamtsystemleistung in Mehrprozessorsystemen verbessert werden kann – in denen viele Threads ständig eine bestimmte gemeinsam genutzte Variable aktualisieren – wenn Threads, bei denen ihr CAS fehlschlägt, einen exponentiellen Backoff verwenden – mit anderen Worten: Warten Sie ein wenig, bevor Sie den CAS erneut versuchen.

Anwendungsbeispiel: atomarer Addierer

Als Beispiel für den Anwendungsfall von Compare-and-Swap ist hier ein Algorithmus zum atomaren Inkrementieren oder Dekrementieren einer Ganzzahl . Dies ist in einer Vielzahl von Anwendungen nützlich, die Zähler verwenden. Die Funktion add führt die Aktion *p ← *p + a atomar aus (wiederum die Zeigerindirektion mit * bezeichnet , wie in C) und gibt den im Zähler gespeicherten Endwert zurück. Anders als im obigen Pseudocode cas ist es nicht erforderlich, dass eine Folge von Operationen außer cas atomar ist . 

function add(p: pointer to int, a: int) returns int
    done ← false

    while not done
        value ← *p  // Even this operation doesn't need to be atomic.
        done ← cas(p, value, value + a)

    return value + a

Wenn sich bei diesem Algorithmus der Wert von *p ändert, nachdem (oder während!) er abgerufen wurde und bevor der CAS das Speichern durchführt, wird CAS dies bemerken und melden, wodurch der Algorithmus einen erneuten Versuch veranlasst.

ABA-Problem

Hauptartikel: ABA-Problem

Einige CAS-basierte Algorithmen sind betroffen und müssen das Problem einer falsch positiven Übereinstimmung oder das ABA-Problem behandeln . Es ist möglich, dass zwischen dem Zeitpunkt, an dem der alte Wert gelesen wird, und dem Zeitpunkt, an dem CAS versucht wird, einige andere Prozessoren oder Threads den Speicherplatz zwei- oder mehrmals ändern, so dass er ein Bitmuster erhält, das dem alten Wert entspricht. Das Problem tritt auf, wenn dieses neue Bitmuster, das genauso aussieht wie der alte Wert, eine andere Bedeutung hat: es könnte beispielsweise eine recycelte Adresse oder ein umschlossener Versionszähler sein.

Eine allgemeine Lösung hierfür ist die Verwendung eines Doppellängen-CAS (DCAS). Auf einem 32-Bit-System kann zB ein 64-Bit-CAS verwendet werden. Die zweite Hälfte wird verwendet, um einen Zähler zu halten. Der Vergleichsteil der Operation vergleicht den zuvor gelesenen Wert des Zeigers und des Zählers mit dem aktuellen Zeiger und Zähler. Wenn sie übereinstimmen, erfolgt der Tausch – der neue Wert wird geschrieben – aber der neue Wert hat einen inkrementierten Zähler. Dies bedeutet, dass wenn ABA aufgetreten ist, obwohl der Zeigerwert derselbe ist, es äußerst unwahrscheinlich ist, dass der Zähler gleich ist (für einen 32-Bit-Wert müsste ein Vielfaches von 2 32 Operationen aufgetreten sein, wodurch der Zähler Wrap und in diesem Moment müsste der Zeigerwert auch zufällig gleich sein).

Eine alternative Form davon (nützlich bei CPUs ohne DCAS) ist die Verwendung eines Index in eine Freelist anstelle eines vollständigen Zeigers, zB bei einem 32-Bit-CAS einen 16-Bit-Index und einen 16-Bit-Zähler verwenden. Die reduzierten Zählerlängen beginnen jedoch, ABA bei modernen CPU-Geschwindigkeiten zu ermöglichen.

Eine einfache Technik, die hilft, dieses Problem zu mildern, besteht darin, einen ABA-Zähler in jedem Datenstrukturelement zu speichern, anstatt einen einzelnen ABA-Zähler für die gesamte Datenstruktur zu verwenden.

Eine kompliziertere, aber effektivere Lösung ist die Implementierung einer sicheren Speicherrückgewinnung (SMR). Dies ist im Grunde eine sperrungsfreie Garbage Collection. Der Vorteil der Verwendung von SMR ist die Gewissheit, dass ein gegebener Zeiger zu jedem Zeitpunkt nur einmal in der Datenstruktur vorhanden ist, wodurch das ABA-Problem vollständig gelöst ist. (Ohne SMR wird so etwas wie eine Freelist verwendet, um sicherzustellen, dass auf alle Datenelemente sicher zugegriffen werden kann (keine Speicherzugriffsverletzungen), auch wenn sie nicht mehr in der Datenstruktur vorhanden sind auf die Datenstruktur zugegriffen wird).

Kosten und Nutzen

CAS und andere atomare Befehle werden in Einprozessorsystemen manchmal als unnötig angesehen, da die Atomarität jeder Befehlsfolge durch Deaktivieren von Interrupts während der Ausführung erreicht werden kann. Das Deaktivieren von Interrupts hat jedoch zahlreiche Nachteile. Beispielsweise muss darauf vertraut werden, dass Code, der dies erlaubt, nicht bösartig ist und die CPU monopolisiert, korrekt ist und die Maschine nicht versehentlich in einer Endlosschleife oder einem Seitenfehler hängt. Außerdem wird das Deaktivieren von Interrupts oft als zu teuer erachtet, um praktikabel zu sein. So profitieren selbst Programme, die nur auf Einprozessormaschinen laufen sollen, von atomaren Anweisungen, wie im Fall der Linux- Futexe .

In Mehrprozessorsystemen ist es normalerweise unmöglich, Interrupts auf allen Prozessoren gleichzeitig zu deaktivieren. Selbst wenn es möglich wäre, könnten zwei oder mehr Prozessoren gleichzeitig versuchen, auf den Speicher des gleichen Semaphors zuzugreifen, und somit würde keine Atomarität erreicht. Der Vergleichs-und-Swap-Befehl ermöglicht es jedem Prozessor, einen Speicherort atomar zu testen und zu modifizieren, wodurch solche Kollisionen mit mehreren Prozessoren verhindert werden.

Auf Server-Grade-Multiprozessorarchitekturen der 2010er Jahre ist Compare-and-Swap im Vergleich zu einer einfachen Last, die nicht aus dem Cache bereitgestellt wird, günstig. Ein Papier aus dem Jahr 2013 weist darauf hin, dass ein CAS nur 1,15-mal teurer ist als eine nicht zwischengespeicherte Last auf Intel Xeon ( Westmere-EX ) und 1,35-mal auf AMD Opteron (Magny-Cours).

Implementierungen

Compare-and-Swap (und Compare-and-Swap-double) ist seit 1970 ein integraler Bestandteil der Architekturen von IBM 370 (und allen Nachfolgern). (dh System- und Benutzertasks) und Prozessor- (dh Zentralprozessoren) Parallelität, während die "deaktivierten Spinlocks ", die in früheren IBM-Betriebssystemen verwendet wurden, im größtmöglichen Maße beseitigt werden. Ebenso wurde die Verwendung von Test-and-Set eliminiert. In diesen Betriebssystemen können neue Arbeitseinheiten "global" in die globale Dienstprioritätsliste oder "lokal" in die lokale Dienstprioritätsliste durch die Ausführung eines einzelnen Vergleichs-und-Austausch-Befehls instanziiert werden. Dadurch wurde die Reaktionsfähigkeit dieser Betriebssysteme erheblich verbessert.

In den x86- (seit 80486 ) und Itanium- Architekturen wird dies als Vergleichs- und Austauschbefehl ( CMPXCHG ) implementiert (bei einem Multiprozessor muss das LOCK- Präfix verwendet werden).

Seit 2013 unterstützen die meisten Multiprozessorarchitekturen CAS in Hardware, und der Vergleichs- und Swap-Vorgang ist das beliebteste Synchronisierungsprimitiv für die Implementierung von sowohl sperrenbasierten als auch nicht blockierenden gleichzeitigen Datenstrukturen .

Die atomaren Zähler- und atomaren Bitmasken-Operationen im Linux-Kernel verwenden bei ihrer Implementierung typischerweise einen Vergleichs-und-Swap-Befehl. Die SPARC-V8- und PA-RISC- Architekturen sind zwei der wenigen neueren Architekturen, die CAS in Hardware nicht unterstützen; die Linux-Portierung auf diese Architekturen verwendet einen Spinlock .

Implementierung in C

Viele C-Compiler unterstützen die Verwendung von Compare-and-Swap entweder mit den C11- <stdatomic.h> Funktionen oder einer nicht standardmäßigen C-Erweiterung dieses bestimmten C-Compilers oder durch Aufrufen einer direkt in Assembler geschriebenen Funktion mit der Compare-and-Swap-Anweisung.

Die folgende C-Funktion zeigt das grundlegende Verhalten einer Compare-and-Swap-Variante, die den alten Wert des angegebenen Speicherplatzes zurückgibt; Diese Version bietet jedoch nicht die entscheidenden Garantien für die Atomarität, die ein echter Vergleichs-und-Swap-Vorgang hätte: 

int compare_and_swap(int* reg, int oldval, int newval)
{
    ATOMIC();
    int old_reg_val = *reg;
    if (old_reg_val == oldval)
        *reg = newval;
    END_ATOMIC();
    return old_reg_val;
}

old_reg_valwird immer zurückgegeben, aber es kann nach der compare_and_swapOperation getestet werden, um zu sehen, ob es übereinstimmt oldval, da es anders sein kann, was bedeutet, dass ein anderer Prozess erfolgreich in einem Wettbewerb compare_and_swapum die Änderung des reg-Werts von erfolgreich war oldval.

Beispielsweise kann ein Wahlprotokoll so implementiert werden, dass jeder Prozess das Ergebnis compare_and_swapgegen seine eigene PID (= newval) prüft. Der Gewinnprozess findet das compare_and_swapZurückgeben des anfänglichen Nicht-PID-Werts (zB Null). Für die Verlierer wird die gewinnende PID zurückgegeben. 

bool compare_and_swap(int *accum, int *dest, int newval)
{
    if (*accum == *dest) {
        *dest = newval;
        return true;
    } else {
        *accum = *dest;
        return false;
    }
}

Dies ist die Logik im Intel Software Manual Vol 2A.

Erweiterungen

Da CAS auf einem einzigen arbeitet Zeiger -sized Speicherplatz, während die meisten Lock-frei und warten freien Algorithmen mehrere Standorte ändern müssen, wurden mehrere Erweiterungen implementiert.

Double Compare-and-Swap (DCAS)
Vergleicht zwei nicht zusammenhängende Speicherorte mit zwei erwarteten Werten und setzt beide Speicherorte auf neue Werte, wenn sie gleich sind. Die Verallgemeinerung von DCAS auf mehrere (nicht benachbarte) Wörter wird MCAS oder CASN genannt. DCAS und MCAS sind für die bequeme (gleichzeitige) Implementierung einiger Datenstrukturen wie Dequeues oder binäre Suchbäume von praktischem Interesse . DCAS und MCAS können jedoch unter Verwendung des ausdrucksstärkeren Hardware- Transaktionsspeichers implementiert werden, der in einigen neueren Prozessoren wie IBM POWER8 oder in Intel-Prozessoren vorhanden ist, die Transactional Synchronization Extensions (TSX) unterstützen.
Vergleichen und austauschen mit doppelter Breite
Funktioniert an zwei benachbarten zeigergroßen Stellen (oder äquivalent an einer Stelle, die doppelt so groß ist wie ein Zeiger). Auf späteren x86-Prozessoren erfüllen die Anweisungen CMPXCHG8B und CMPXCHG16B diese Rolle, obwohl frühe 64-Bit-AMD-CPUs CMPXCHG16B nicht unterstützten (moderne AMD-CPUs tun dies). Auch einige Intel-Mainboards aus der Core-2- Ära erschweren den Einsatz, obwohl die Prozessoren dies unterstützen. Diese Probleme kamen bei der Einführung von Windows 8.1 ins Rampenlicht, da dafür Hardwareunterstützung für CMPXCHG16B erforderlich war.
Einfach vergleichen, doppelt tauschen
Vergleicht einen Zeiger, schreibt aber zwei. Der Befehl cmp8xchg16 des Itanium implementiert dies, wobei die beiden geschriebenen Zeiger benachbart sind.
Vergleichen und Vertauschen von mehreren Wörtern
Ist eine Verallgemeinerung des normalen Vergleichens und Tauschens. Es kann verwendet werden, um eine beliebige Anzahl von willkürlich angeordneten Speicherplätzen atomar auszutauschen. Üblicherweise wird Mehrwort-Vergleichen und Vertauschen in Software unter Verwendung normaler doppelter Vergleichs- und Vertauschungsoperationen implementiert. Der Nachteil dieses Ansatzes ist die fehlende Skalierbarkeit.

Siehe auch

Verweise

Externe Links

Mit CAS . implementierte Grundalgorithmen

Implementierungen von CAS