Deferred Reclamation in C++26: Read-Copy Update und Hazard Pointers

Ein häufiges Problem bei Concurrency ist das sogenannte ABA-Problem. Das bedeutet, dass man eine Variable zweimal liest, die jedes Mal den gleichen Wert A zurückgibt. Daher kommt man zu dem Schluss, dass sich dazwischen nichts geändert hat. Aber man hat das B vergessen.

Modernes C++ – Rainer Grimm

Rainer Grimm ist seit vielen Jahren als Softwarearchitekt, Team- und Schulungsleiter tätig. Er schreibt gerne Artikel zu den Programmiersprachen C++, Python und Haskell, spricht aber auch gerne und häufig auf Fachkonferenzen. Auf seinem Blog Modernes C++ beschäftigt er sich intensiv mit seiner Leidenschaft C++.

Folgendes Szenario stellt das Problem vor.

Eine Analogie

Das Szenario sieht so aus, dass man in seinem Auto sitzt und darauf wartet, dass die Ampel grün wird. In unserem Fall steht Grün für B und Rot für A. Wie geht es weiter?

1. Man schaut auf die Ampel und sie ist rot (A).
2. Weil es langweilig ist, schaut man auf dem Smartphone die Nachrichten an und vergisst die Zeit.
3. Man schaut noch einmal auf die Ampel. Verdammt, sie ist immer noch rot (A).

Dabei ist die Ampel zwischen den beiden Überprüfungen grün geworden (B). Daher waren es zwei Rotphasen, obwohl es nur eine zu sein schien.

Wie sieht das nun bei Threads (Prozessen) aus? Jetzt noch einmal ganz formal.

1. Thread 1 liest eine Variable var mit dem Wert A.
2. Thread 1 wird unterbrochen und Thread 2 wird ausgeführt.
3. Thread 2 ändert die Variable var von A zu B zu A.
4. Thread 1 beginnt mit der Ausführung und überprüft den Wert der Variablen var; da der Wert der Variablen var gleich bleibt, setzt Thread 1 seine Arbeit fort,

Oft kann man ABA ignorieren.

Atomare Multiplikation

Im folgenden Code multipliziert die Funktion fetch_mult (1) ein std::atomic<T>&, das von mult gemeinsam genutzt wird.

// fetch_mult.cpp

#include <atomic>
#include <iostream>

template <typename T>
T fetch_mult(std::atomic<T>& shared, T mult){                          // 1
  T oldValue = shared.load();                                          // 2
  while (!shared.compare_exchange_strong(oldValue, oldValue * mult));  // 3
  return oldValue;
}

int main(){
  std::atomic<int> myInt{5};
  std::cout << myInt << '\n';          
  fetch_mult(myInt,5);
  std::cout << myInt << '\n';         
}

shared.compare_exchange_strong(expected, desired)(3) hat das folgende Verhalten:

• Wenn der Vergleich false ergibt, wird expected auf shared gesetzt.
• Wenn der atomare Vergleich true ergibt, wird shared in derselben atomaren Operation auf expected gesetzt.

Die wichtigste Beobachtung ist, dass es ein kleines Zeitfenster zwischen dem Lesen des alten Werts T oldValue = shared.load (2) und dem Vergleich mit dem neuen Wert (3) gibt. Daher kann ein anderer Thread einspringen und oldValue von oldValue zu anotherValue und wieder zurück zu oldValue ändern. anotherValue ist das B in ABA.

Ich möchte ABA anhand einer Lock-freien Datenstruktur veranschaulichen.

Ein Lock-freier Stack

Ich verwende einen Lock-freien Stack, der als verkettete Liste implementiert ist. Der Stack unterstützt nur zwei Operationen.

1. Pop das oberste Objekt und gibt einen Zeiger darauf zurück.
2. Push das angegebene Objekt auf den Stack.

Ich möchte die Pop-Operation in Pseudocode beschreiben, um dir eine Vorstellung vom ABA-Problem zu geben. Die Pop-Operation führt die folgenden Schritte in einer Schleife aus, bis sie erfolgreich ist.

• Erhalte den Kopfknoten: head
• Erhalte den nachfolgenden Knoten: headNext
• Mache headNext zum neuen Kopf, wenn head immer noch der Kopf des Stacks ist

Hier sind die ersten beiden Knoten des Stacks:

Stack: TOP -> head -> headNext -> ...

ABA in Aktion

Beginnen wir mit dem folgenden Stack:

Stack: TOP -> A -> B -> C

Thread 1 ist aktiv und möchte den Stack-Kopf entfernen.

• Thread 1 speichert
• head = A
• headNext = B

Bevor Thread 1 den Pop-Algorithmus beendet, wird Thread 2 aktiviert.

• Thread 2 entfernt A

Stack: TOP -> B -> C

• Thread 2 entfernt B und löscht B

Stack: TOP -> C

• Thread 2 schiebt A zurück

Stack: TOP -> A -> C

Thread 1 wird neu scheduled, um zu überprüfen, ob A == head. Da A == head, wird headNext, also B, zum neuen Kopf. Aber B wurde bereits gelöscht. Daher hat das Programm ein undefiniertes Verhalten.

Es gibt einige Abhilfen für das ABA-Problem.

Abhilfe für ABA

Das konzeptionelle Problem von ABA ist relativ leicht zu verstehen. Ein Knoten wie B == headNext wurde gelöscht, obwohl ein anderer Knoten, A == head, darauf verwies. Die Lösung für unser Problem besteht darin, das vorzeitige Löschen des Knotens zu verhindern. Hier sind einige Lösungsansätze.

• Referenz auf markierten Zustand

Man kann ein Tag hinzufügen, das angibt, wie oft der Knoten erfolgreich geändert wurde. Die Methode "Vergleichen und Austauschen" schlägt jedoch irgendwann fehl, obwohl die Überprüfung [/code]true[/code] ergibt.

Die nächsten drei Techniken basieren auf der Idee der Deferred Reclamation.

• Garbage Collection

Garbage Collection garantiert, dass die Variablen nur gelöscht werden, wenn sie nicht mehr benötigt werden. Das klingt vielversprechend, hat aber einen großen Nachteil. Die meisten Garbage Collectors sind nicht Lock-frei. Daher haben Sie eine Lock-freie Datenstruktur, aber das Gesamtsystem ist nicht Lock-frei.

• Hazard Pointers

Aus Wikipedia: Hazard Pointers:

In einem Hazard-Pointer-System führt jeder Thread eine Liste von Hazard Pointers, die angeben, auf welche Knoten der Thread zugreift. (Diese "Liste" kann in vielen Systemen auf nur ein oder zwei Elemente beschränkt sein.) Knoten auf der Hazard-Pointer-Liste dürfen von keinem anderen Thread geändert oder freigegeben werden. ... Wenn ein Thread einen Knoten entfernen möchte, setzt er ihn auf eine Liste von Knoten, die "später freigegeben werden sollen", gibt den Speicher des Knotens jedoch erst frei, wenn die Hazard-Liste keines anderen Threads den Zeiger enthält. Ein dedizierter Garbage-Collection-Thread kann diese manuelle Garbage Collection durchführen (wenn die Liste "später freigeben" von allen Threads gemeinsam genutzt wird); alternativ kann die Bereinigung der Liste "freigeben" von jedem Arbeitsthread als Teil einer Operation wie "Pop" durchgeführt werden.

• RCU

RCU steht für Read Copy Update, eine von Paul McKenney entwickelte und seit 2002 im Linux-Kernel verwendete Synchronisierungstechnik für fast schreibgeschützte Datenstrukturen.

Die Idee ist recht einfach und folgt dem Akronym. Um Daten zu ändern, erstellt man eine Kopie der Daten und ändert diese Kopie. Im Gegensatz dazu arbeiten alle Leser mit den Originaldaten. Wenn kein Leser vorhanden ist, kann die Datenstruktur bedenkenlos durch die Kopie ersetzt werden.

Wie geht es weiter?

In meinem nächsten Artikel werde ich einen Lock-freien Stack mit Deferred Reclamation implementieren. (rme)