>In meinem letzten Beitrag habe ich eine Implementierung von Hazard Pointers vorgestellt: Ein Lock-freier Stack mit Hazard-Pointers-Implementierung. Heute werde ich die Implementierung erläutern.MyNode ist ein Klassen-Template, das durch den Datentyp parametrisiert wird, den es enthält: data. MyNode modelliert das Concept Node.

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){ }
};

Concepts sind Prädikate zur Compile-Zeit. Sie legen semantische Einschränkungen für Template-Parameter fest. Das Concept Node erfordert data-Member und einen Zeiger next, der einen Node zurückgibt.

Die Datentypen des Programms lockFreeStackHazardPointers.cpp sind im Wesentlichen auf das data-Member und das Concept Node parametrisiert. MyNode modelliert das Concept Node. Hier ist beispielsweise die Deklaration des LockFreeStack:

template<typename T, Node MyNode = MyNode<T>>

class LockFreeStack;

So sieht das Programm mit dem Lock-freien Stack aus:

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;
}
};

Der Aufruf push ist aus Concurrency-Sicht nicht kritisch, da head in einem atomaren Schritt aktualisiert wird. Darüber hinaus garantiert der Aufruf compare_exchange_strong, dass head immer der aktuelle Kopf des Stacks ist.

Wegen der Hazard Pointers wird der Aufruf topAndPop komplizierter. Zunächst verweist die Funktion getHazardPointer auf den Hazard Pointer für den aktuellen Thread. Der Aufruf hazardPointer.store(oldHead) macht den aktuellen Thread zum Besitzer des Hazard Pointer, und der Aufruf hazardPointer.store(nullptr) gibt seinen Besitz frei.

Zunächst analysiere ich die inneren und äußeren do-while-Schleifen. Die innere Schleife setzt den Hazard Pointer auf den Kopf des Stacks. Die do-while-Schleife endet, wenn Folgendes gilt: oldHead == tempNode.

Beide Knoten sind gleich, wenn oldHead immer noch der aktuelle Kopf des Lock-freien Stacks ist. oldHead wurde gesetzt und konnte nicht mehr der aktuelle Kopf sein, da möglicherweise ein anderer Thread dazwischenkam und oldHead bereits verwaltete.

Die äußere do-while-Schleife ist dieselbe wie in den vorherigen Implementierungen des Lock-freien Stacks. Ich iteriere in der while-Schleife mit compare_exchange_strong und setze den Head auf oldHead->next. Am Ende ist Head der Head des Stacks. Die Memberfunktion topAndPop sollten den Wert des Head zurückgeben und ihn entfernen. Bevor ich oldHead verwende, muss ich überprüfen, ob oldHead kein Null-Zeiger ist. Ist das der Fall, werfe ich eine Exception.

Der Rest von topAndPop ist unkompliziert. Der Aufruf retireList.isInUse(oldHead) überprüft, ob oldHead noch verwendet wird. Je nach Ergebnis dieser Überprüfung wird oldHead der Ausmusterungsliste retireList.addNode hinzugefügt, wenn es noch nicht auf der Liste steht oder gelöscht wurde. Der letzte Aufruf retireList.deleteUnusedNodes ist der arbeitsintensivste Aufruf in der Memberfunktion topAndPop. Die Memberfunktion retireListe.deleteUnusedNodes durchläuft die gesamte Retire-Liste und löscht alle nicht mehr verwendeten Knoten.

Aus Gründen der Performanz sollte der Aufruf retireList.deleteUnusedNodes nicht bei jedem Aufruf von topAndPop ausgeführt werden Eine bessere Strategie ist es, die Memberfunktion deleteUnusedNodes aufzurufen, wenn die Länge der Retire-Liste einen bestimmten Schwellenwert überschreitet. Wenn die Länge der Retire-Liste beispielsweise doppelt so lang ist wie der Stack, kann mindestens die Hälfte der Knoten gelöscht werden. Dieser Schwellenwert ist ein Kompromiss zwischen den Anforderungen an die Performanz und dem Speicherverbrauch.

Hier ist die Funktion getHazardPointer:

template <typename T, Node MyNode = MyNode<T>>
sttd::atomic<MyNode*>& getHazardPointer() {
thread_local static HazardPointerOwner<T> hazard;
return hazard.getPointer();
}

Die Funktion verweist auf einen Hazard Pointer mithilfe des Besitzers hazard, einer Thread-lokalen und statischen Variable. Daher erhält jeder Thread seine Kopie des Hazard Pointer-Besitzers und seine Lebensdauer ist an die Lebensdauer des besitzenden Threads gebunden. Die gebundene Lebensdauer des Besitzers des Hazard Pointer ist von entscheidender Bedeutung, da sie garantiert, dass der Hazard Pointer gelöscht wird, wenn der Thread-lokale Besitzer des Hazard Pointer zerstört wird. Ich schreibe mehr über dieses RAII-Objekt in meiner Analyse des Datentyps HazardPointerOwner.

Wie geht es weiter?

In meinem nächsten Artikel werde ich die verbleibende Implementierung erläutern.