Premiere

Atomare Operationen

Eine einzelne Anweisung kann wie eine unteilbare Aktion aussehen und doch alles andere als das sein. Nimm an, du willst fünf zu einem Wert im Speicher addieren:

add qword [rel counter], 5

Im Hintergrund kann der Prozessor nicht direkt in den Speicher addieren. Er zerlegt diese eine Anweisung in drei kleinere Schritte, die Mikrooperationen heißen:

1. Lies den aktuellen Wert aus dem Speicher;
2. ändere diesen Wert in einem Register, indem du fünf addierst;
3. schreibe das Ergebnis zurück.

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

Das ist ein gängiges Muster, das Read-Modify-Write (RMW) genannt wird.

Beachte, dass das Lesen (oder Laden) und das Schreiben (oder Speichern) getrennte Ereignisse sind, zwischen denen ein Zeitfenster liegt. Normalerweise fällt uns das nicht auf, weil auf einem einzelnen Kern garantiert ist, dass jede Anweisung ihre Wirkung vollständig entfaltet, bevor die nächste an der Reihe ist. Dieses Fenster bleibt deshalb unsichtbar, und add verhält sich wie eine einzige Einheit.

Moderne CPUs haben jedoch selten nur einen Kern, und Anwendungen laufen oft gleichzeitig auf vielen Kernen, ohne feste Reihenfolge zwischen ihnen. Wenn mehrere Kerne im selben Augenblick laufen, kann ein anderer Kern counter innerhalb dieses Fensters lesen oder schreiben, also nach dem Laden dieses Kerns und vor dem Speichern. Zwei Threads laden beide denselben alten Wert, addieren beide fünf und speichern beide ihr Ergebnis. Es fanden zwei Additionen statt, aber der Wert hat sich nur um fünf verändert. Ein Update ging stillschweigend verloren.

Das ist ein Data Race, und es ist ein häufiges Problem in Multithread-Code.

Nicht jeder Wert ist dieser Gefahr ausgesetzt. Jeder Thread hat seine eigenen Register und seinen eigenen Stack, daher ist ein Wert in einem Register oder eine lokale Variable auf dem Stack eines Threads exklusiv für diesen Thread und kann nicht von einem Race betroffen sein. Nur der Speicher, den sich die Threads teilen, wie das obige counter, muss geschützt werden.

x86-64 bietet eine Reihe von Anweisungen, um dieses Problem zu lösen, indem sie eine Anweisung unteilbar machen. Sie verhält sich nicht nur für den Kern, der sie ausführt, wie eine einzige Einheit, sondern auch für jeden anderen Kern. Eine Operation, die zusammenhält und die kein anderer Kern aufspalten kann, heißt atomar.

Atomarer Austausch

Die Anweisung xchg vertauscht zwei Operanden. Der Zieloperand nimmt den vorherigen Wert des Quelloperanden an, während der Quelloperand den vorherigen Wert des Zieloperanden annimmt. Konzeptionell kann man sie sich als zwei mov-Anweisungen vorstellen, die gleichzeitig ablaufen.

Wie üblich kann sie mit zwei Registeroperanden oder mit einem Speicheroperanden und einem Registeroperanden verwendet werden:

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

Wenn ein Speicheroperand beteiligt ist, ist xchg immer atomar.

Das lock-Präfix

Die gebräuchlichste Methode, eine Anweisung in x86-64 atomar zu machen, ist das Präfix lock. Es verschmilzt das Lesen, das Ändern und das Schreiben zu einem unteilbaren Schritt. Das bedeutet, dass der Kern den Speicher während des gesamten Vorgangs exklusiv hält, sodass kein anderer Kern diese Adresse dazwischen lesen oder schreiben kann.

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock funktioniert nur, wenn das Ziel im Speicher liegt, und nur bei Anweisungen, die diesen Speicher im Read-Modify-Write-Verfahren bearbeiten:

1. arithmetische Operationen wie add, sub, inc, dec, neg;
2. bitweise Operationen wie and, or, xor, not;
3. die Bitoperationen bts, btr, btc;
4. einige weitere spezielle Anweisungen wie xadd und cmpxchg, die weiter unten beschrieben werden.

Austauschen und Addieren

Ein einfaches lock add aktualisiert den Speicher, verwirft aber den alten Wert. Oft ist der alte Wert genau das, was man möchte, zum Beispiel um jedem Thread eine eigene Ticketnummer zu geben.

Die Anweisung xadd (x steht für exchange) gibt den vorherigen Wert zurück, während sie addiert. Sie schreibt die Summe in das Ziel und lässt den ursprünglichen Wert des Ziels im Quellregister stehen.

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

Mit dem lock-Präfix ist das ein atomares Fetch-and-Add. Wenn viele Threads es auf demselben Zähler ausführen, liefert jeder Aufruf einen anderen alten Wert.

Wie bei lock add steht der Zähler am Ende genau auf der Anzahl der Aufrufe. Anders als bei lock add wird hier jedoch jeder Zwischenwert zurückgegeben, einer an jeden Aufrufer.

Vergleichen und Austauschen

xadd addiert und xchg überschreibt, aber keines von beiden kann den neuen Wert vom aktuellen abhängig machen und ihn nur dann anwenden, wenn sich darunter nichts geändert hat. Diese bedingte Aktualisierung bietet cmpxchg, compare-and-exchange, und sie ist die allgemeinste dieser Primitive.

cmpxchg dest, src verwendet rax als impliziten Akkumulator und vergleicht ihn mit dest:

• Wenn dest == rax, dann dest = src und ZF = 1.
• Wenn dest != rax, dann rax = dest und ZF = 0.

Beachte, dass dest nur dann aktualisiert wird, wenn es gleich dem erwarteten Wert ist, der zuvor in rax geladen wurde. Diese Gleichheit stellt sicher, dass dest noch den Wert enthält, aus dem der neue berechnet wurde, sodass eine Aktualisierung auf Basis eines veralteten Lesevorgangs niemals angewendet wird. Dadurch ist cmpxchg der Baustein für eine atomare Aktualisierung, auch bekannt als Compare-and-Swap (CAS):

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

Diese Retry-Schleife ist das Herzstück von lock-freien Aktualisierungen. Das Fenster zwischen dem Lesevorgang und dem compare-and-exchange ist genau der Moment, in dem ein anderer Thread eingreifen könnte, und cmpxchg fängt das ab, indem es sich weigert, einen aus einem veralteten Lesevorgang berechneten Wert zu speichern.

Speicherordnung

Jede bisherige Operation hat genau eine Adresse berührt. Wenn Threads über mehr als eine Adresse kommunizieren, taucht eine neue Frage auf: In welcher Reihenfolge werden die Schreibvorgänge eines Threads für einen anderen sichtbar? Die Regeln, die diese Frage beantworten, sind die Speicherordnung des Prozessors.

Das branchless-code-Konzept hat die Idee eingeführt, dass ein moderner Kern nicht die Anweisungen eins nach dem anderen abarbeitet. Er hält viele gleichzeitig in Bearbeitung und läuft voraus, wo er kann. Das bedeutet, dass ein Schreibvorgang für die anderen Kerne später sichtbar werden kann, als das Programm vermuten lässt, während nachfolgende Anweisungen bereits vorausgeeilt sind.

x86-64 hält eine starke Speicherordnung unter gewöhnlichen Lade- und Speicherzugriffen ein, sodass auf jedem Kern gilt:

1. ein Ladevorgang wird nie hinter einen späteren Ladevorgang verschoben;
2. ein Speichervorgang wird nie hinter einen späteren Speichervorgang verschoben;
3. ein Ladevorgang wird nie hinter einen späteren Speichervorgang verschoben.

Die einzige mögliche Umsortierung ist, dass ein Speichervorgang erst nach einem späteren Ladevorgang einer anderen Adresse abgeschlossen zu sein scheint.

Eine Anweisung mit lock-Präfix oder ein xchg mit Speicheroperand ist eine vollständige Barriere: nichts scheint sie in irgendeine Richtung zu überqueren. Deshalb genügen sie in den meisten Situationen, um die vollständige Ordnung sicherzustellen.

Spinning und pause

Anweisungen, die ein Flag setzen und gleichzeitig seinen vorherigen Zustand zurückgeben, heißen Test-and-Set. Sie können als Grundlage für einen Spinlock dienen, mit dem ein Kern exklusiven Zugriff auf einen Teil des Codes erhält.

Der Gesamtablauf sieht so aus, mit der Anweisung xchg und einem binären Flag:

1. Das Flag startet bei 0.
2. Um die Sperre zu erlangen, vertauscht ein Kern den Wert im Flag mit 1.
3. Ist der zurückgegebene Wert 1, bedeutet das, dass die Sperre von einem anderen Kern gehalten wird. Der aktuelle Kern wartet dann und versucht erneut, die Sperre zu erlangen.
4. Ist der zurückgegebene Wert 0, war die Sperre frei. xchg hat sie nun auf 1 gesetzt, und andere Kerne warten, bis dieser Kern sie freigibt.
5. Sobald der aktuelle Kern seine Arbeit beendet hat, gibt er die Sperre frei, indem er das Flag auf 0 setzt.

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

Die Anweisung pause in der Warteschleife ändert nichts daran, was der Code berechnet. Sie gibt dem Prozessor den Hinweis, dass hier aktiv gewartet wird. Die CPU kann dann den Energieverbrauch des wartenden Threads senken und an einen anderen Thread abgeben, der sich denselben Kern teilt. Eine Warteschleife ohne pause ist immer noch korrekt, nur verschwenderisch.

Sobald der Thread seine Arbeit beendet hat, kann er die Sperre mit einem einfachen mov freigeben, das 0 speichert. Mehr als ein mov ist nicht nötig, weil auf x86-64 Lade- und Speichervorgänge nie hinter einen späteren Speichervorgang verschoben werden. Ein Speichervorgang, der die vorhergehenden Zugriffe nie überholt, hat Release-Ordering, und auf x86 bringt jeder einfache Speichervorgang es mit.