C++ 26: Ein Lock-freier Stack mit Hazard-Pointer-Implementierung
Bei der Implementierung des Lock-freien Stacks mit einem Garbage Collector in C++ helfen Hazard Pointers.
(Bild: SerbioVas/Shutterstock)
- Rainer Grimm
In den letzten Beiträgen habe ich den Lock-freien Stack besprochen. Hazard Pointers lösen alle Probleme der im vorherigen Beitrag gezeigten Implementierung mit dem einfachen Garbage Collector.
Von einer Woche auf zwei Wochen
Zunächst eine Anmerkung in eigener Sache: Ende 2023 wurde bei mir ALS diagnostiziert, ein schwerwiegend fortschreitendes Nervenleiden. Daher werde ich die Häufigkeit, mit der ich meinen Blog veröffentliche, in Zukunft von einer auf zwei Wochen ändern. Einen Artikel mit der Stimme zu verfassen, statt zu tippen, ist außergewöhnlich anstrengend und zeitaufwendig.
Hazard Pointers
Der Begriff Hazard Pointer geht auf Maged M. Michael zurück. Hazard Pointer lösen das klassische Problem Lock-freier Datenstrukturen wie z. B. eines Lock-freien Stacks: Wann kann ein Thread einen Knoten einer Datenstruktur sicher löschen, während andere Threads diesen Knoten gleichzeitig verwenden können?
(Bild: Rainer Grimm)
Obwohl ein Hazard Pointer eine allgemeine Lösung für das häufige Problem der sicheren Speicherfreigabe in Lock-freien Datenstrukturen bietet, möchte ich ihn aus der Perspektive unseres Lock-freien Stacks zeigen.
(Bild: Rainer Grimm)
Ein Hazard Pointer ist ein Zeiger mit einem Schreib- und mehreren Lesezugriffen. Alle Hazard Pointer bilden eine verknüpfte Liste und werden mit einem Null-Zeiger initialisiert. Wenn ein Thread einen Stack-Knoten verwendet, wird die Adresse des Knotens in einen Hazard Pointer eingefügt, was anzeigt, dass dieser Thread diesen Knoten verwendet und der alleinige Besitzer des verwendeten Hazard Pointers ist. Wenn der Thread den Knoten nicht mehr benötigt, setzt er den Hazard Pointer auf einen Null-Zeiger und gibt somit seinen Besitzanspruch auf.
Ein Thread führt eine Liste von Hazard Pointers, die für die vom Thread verwendeten Knoten stehen und nicht gelöscht werden können. Wenn ein Thread einen Knoten löschen möchte, durchsucht er die Liste aller Hazard Pointers und prüft, ob der Knoten verwendet wird. Wenn der Knoten nicht verwendet wird, wird er gelöscht. Wenn der Knoten verwendet wird, wird er schließlich auf eine Stilllegungsliste der zu löschenden Knoten gesetzt. Schließlich wird der Knoten nur dann zur Stilllegungsliste hinzugefügt, wenn er noch nicht auf der Liste steht.
Dies ist bei unserem Lock-freien Stack der Fall. Die Member-Funktion topAndPop hat zwei Aufgaben in Bezug auf die Speicherrückgewinnung. Erstens verwaltet sie den zu löschenden Knoten; zweitens durchläuft sie die Stilllegungsliste der Knoten und löscht sie, wenn sie nicht mehr verwendet werden.
Ich benötige die folgende Member-Funktion in einer neuen Implementierung von topAndPop, basierend auf der vorherigen Beschreibung: getHazardPointer, um eine Referenz auf einen Hazard Pointer zu erhalten, retireList.addNode und retireList.deleteUnusedNodes, um einen Knoten zur retireList hinzuzufügen. Zusätzlich retireList.deleteUnusedNodes, um alle nicht mehr verwendeten Knoten aus der Ausmusterungsliste zu löschen. Darüber hinaus verwendet die Member-Funktion retireList.deleteUnusedNode die Hilfsfunktion retireList.isInUse, um zu entscheiden, ob ein Knoten derzeit verwendet wird. Die Member-Funktion isInUse ist auch in topAndPop nützlich, um zu entscheiden, ob der aktuelle Knoten zur Ausmusterungsliste hinzugefügt oder direkt gelöscht werden soll.
Wie wirkt sich dies auf meine vorherige Implementierung aus? Schauen wir mal. Das folgende Programm zeigt die Implementierung eines Lock-freien Stacks auf der Grundlage von Hazard Pointers:
// lockFreeStackHazardPointers.cpp
#include <atomic>
#include <cstddef>
#include <future>
#include <iostream>
#include <stdexcept>
#include <thread>
template <typename T>
concept Node = requires(T a) {
{T::data};
{ *a.next } -> std::same_as<T&>;
};
template <typename T>
struct MyNode {
T data;
MyNode* next;
MyNode(T d): data(d), next(nullptr){ }
};
constexpr std::size_t MaxHazardPointers = 50;
template <typename T, Node MyNode = MyNode<T>>
struct HazardPointer {
std::atomic<std::thread::id> id;
std::atomic<MyNode*> pointer;
};
template <typename T>
HazardPointer<T> HazardPointers[MaxHazardPointers];
template <typename T, Node MyNode = MyNode<T>>
class HazardPointerOwner {
HazardPointer<T>* hazardPointer;
public:
HazardPointerOwner(HazardPointerOwner const &) = delete;
HazardPointerOwner operator=(HazardPointerOwner const &) = delete;
HazardPointerOwner() : hazardPointer(nullptr) {
for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
std::thread::id old_id;
if (HazardPointers<T>[i].id.compare_exchange_strong(
old_id, std::this_thread::get_id())) {
hazardPointer = &HazardPointers<T>[i];
break;
}
}
if (!hazardPointer) {
throw std::out_of_range(„No hazard pointers available!“);
}
}
std::atomic<MyNode*>& getPointer() {
return hazardPointer->pointer;
}
~HazardPointerOwner() {
hazardPointer->pointer.store(nullptr);
hazardPointer->id.store(std::thread::id());
}
};
Template <typename T, Node MyNode = MyNode<T>>
std::atomic<MyNode*>& getHazardPointer() {
thread_local static HazardPointerOwner<T> hazard;
return hazard.getPointer();
}
template <typename T, Node MyNode = MyNode<T>>
class RetireList {
struct RetiredNode {
MyNode* node;
RetiredNode* next;
RetiredNode(MyNode* p) : node(p), next(nullptr) { }
~RetiredNode() {
delete node;
}
};
std::atomic<RetiredNode*> RetiredNodes;
void addToRetiredNodes(RetiredNode* retiredNode) {
retiredNode->next = RetiredNodes.load();
while (!RetiredNodes.compare_exchange_strong(retiredNode->next, retiredNode));
}
public:
bool isInUse(MyNode* node) {
for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
if (HazardPointers<T>[i].pointer.load() == node) return true;
}
return false;
}
void addNode(MyNode* node) {
addToRetiredNodes(new RetiredNode(node));
}
void deleteUnusedNodes() {
RetiredNode* current = RetiredNodes.exchange(nullptr);
while (current) {
RetiredNode* const next = current->next;
if (!isInUse(current->node)) delete current;
else addToRetiredNodes(current);
current = next;
}
}
};
template<typename T, Node MyNode = MyNode<T>>
class LockFreeStack {
std::atomic<MyNode*> head;
RetireList<T> retireList;
public:
LockFreeStack() = default;
LockFreeStack(const LockFreeStack&) = delete;
LockFreeStack& operator= (const LockFreeStack&) = delete;
void push(T val) {
MyNode* const newMyNode = new MyNode(val);
newMyNode->next = head.load();
while( !head.compare_exchange_strong(newMyNode->next, newMyNode) );
}
T topAndPop() {
std::atomic<MyNode*>& hazardPointer = getHazardPointer<T>();
MyNode* oldHead = head.load();
do {
MyNode* tempMyNode;
do {
tempMyNode = oldHead;
hazardPointer.store(oldHead);
oldHead = head.load();
} while( oldHead != tempMyNode );
} while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) ;
if ( !oldHead ) throw std::out_of_range(„The stack is empty!“);
hazardPointer.store(nullptr);
auto res = oldHead->data;
if ( retireList.isInUse(oldHead) ) retireList.addNode(oldHead);
else delete oldHead;
retireList.deleteUnusedNodes();
return res;
}
};
int main(){
LockFreeStack<int> lockFreeStack;
auto fut = std::async([&lockFreeStack]{ lockFreeStack.push(2011); });
auto fut1 = std::async([&lockFreeStack]{ lockFreeStack.push(2014); });
auto fut2 = std::async([&lockFreeStack]{ lockFreeStack.push(2017); });
auto fut3 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
auto fut4 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
auto fut5 = std::async([&lockFreeStack]{ return lockFreeStack.topAndPop(); });
fut.get(), fut1.get(), fut2.get();
std::cout << fut3.get() << '\n';
std::cout << fut4.get() << '\n';
std::cout << fut5.get() << '\n';
Das Programm läuft wie erwartet:
(Bild: Screenshot (Rainer Grimm))
Wie geht es weiter?
Ich werde das Programm in meinem nächsten Beitrag Schritt für Schritt analysieren.
(rme)
