C++26: Ein einfacher Garbage Collector für den Lock-freien Stack

Nach den Grundlagen zum Lock-freien Stack in den letzten Beiträgen ist es nun Zeit, ihn um einen einfachen Garbage Collector zu erweitern.

5

(Bild: SerbioVas/Shutterstock)

24.02.2025, 11:34 Uhr

Lesezeit: 4 Min.

Developer

Von

Rainer Grimm

In den letzten drei Beiträgen habe ich mich mit dem Thema Lock-freier Stack beschäftigt:

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++.

Für diesen Beitrag erweitere ich ihn um einen einfachen Garbage Collector.

Ich habe besprochen, dass die gleichzeitige Ausführung von mehr als einem topAndPush-Aufruf eine Race Condition ist. Ich kann einen Knoten sicher löschen, wenn nicht mehr als ein topAndPush-Aufruf gleichzeitig ausgeführt wird. Diese Beobachtung ist entscheidend für die Lösung des Speicherleckproblems: Ich speichere entfernte Knoten in einer zu löschenden Liste und lösche die Knoten in dieser Liste, wenn nicht mehr als ein topAndPush-Aufruf aktiv ist. Es gibt nur noch eine Herausforderung: Wie kann ich sicher sein, dass nicht mehr als ein topAndPush-Aufruf aktiv ist? Ich verwende einen atomaren Zähler, der zu Beginn von topAndPush inkrementiert und an dessen Ende dekrementiert wird. Der Zähler ist Null oder Eins, wenn kein oder ein topAndPush-Aufruf aktiv ist.

Das folgende Programm implementiert die vorgestellte Strategie. Ich verwende die Datei lockFreeStackWithLeaks.cpp aus dem Artikel "C++26: Vollständige Implementierung eines Lock-freien Stacks" als Ausgangspunkt.

// lockFreeStackWithGarbageCollection.cpp

#include <atomic>
#include <future>
#include <iostream>
#include <stdexcept>
#include <thread>

template<typename T>
class LockFreeStack {
 private:
    struct Node {
        T data;
        Node* next;
        Node(T d): data(d), next(nullptr){ }
    };

    std::atomic<Node*> head{nullptr};
    std::atomic<int> topAndPopCounter{};                                            // 1
    std::atomic<Node*> toBeDeletedNodes{nullptr};                                   // 2

    void tryToDelete(Node* oldHead) {                                              // 3
        if (topAndPopCounter  == 1) {                                              // 6
            Node* copyOfToBeDeletedNodes = toBeDeletedNodes.exchange(nullptr);     // 8
            if (topAndPopCounter == 1) deleteAllNodes(copyOfToBeDeletedNodes);     // 9
            else addNodeToBeDeletedNodes(copyOfToBeDeletedNodes); 
            delete oldHead;
        }
        else addNodeToBeDeletedNodes(oldHead);                                     // 7
    }

    void addNodeToBeDeletedNodes(Node* oldHead) { 
        oldHead->next = toBeDeletedNodes;
        while( !toBeDeletedNodes.compare_exchange_strong(oldHead->next, oldHead) ); // 10
    }

    void deleteAllNodes(Node* currentNode) {                                      // 4
        while (currentNode) {
            Node* nextNode = currentNode->next;
            delete currentNode;
            currentNode = nextNode;
        }
     }

 public:
    LockFreeStack() = default;
    LockFreeStack(const LockFreeStack&) = delete;
    LockFreeStack& operator= (const LockFreeStack&) = delete;
   
    void push(T val) {
        Node* const newNode = new Node(val); 
        newNode->next = head.load();
        while( !head.compare_exchange_strong(newNode->next, newNode) );
    }

    T topAndPop() {
        ++topAndPopCounter;
        Node* oldHead = head.load();
        while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) {
            if ( !oldHead ) throw std::out_of_range("The stack is empty!");
        }
        auto topElement = oldHead->data;
        tryToDelete(oldHead);                                                   // 5
        --topAndPopCounter;
        return topElement;
    }
};
   
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';

}

Der Lock-freie Stack hat zwei neue Attribute und drei neue Mitgliedsfunktionen. Der atomare Zähler topAndPopCounter zählt (1) die Anzahl der aktiven topAndPop-Aufrufe, und der atomare Zeiger toBeDeletedNodes (2) ist ein Zeiger auf die Liste der zu löschenden Knoten. Außerdem versucht die Mitgliedsfunktion tryToDelete (3), entfernte Knoten zu löschen. Die Mitgliedsfunktion addNodeToBeDeletedNodes fügt einen Knoten zur Liste der zu löschenden Knoten hinzu, und die Mitgliedsfunktion deleteAllNodes (4) löscht alle Knoten.

Analysieren wir nun die Mitgliedsfunktion topAndPop. Zu Beginn und am Ende von topAndPop wird topAndPopCounter inkrementiert und dekrementiert. oldHead wird vom Stack entfernt und kann daher schließlich mit dem Aufruf tryToDelete (5) gelöscht werden. Die Memberfunktion tryToDelete prüft zunächst, ob ein oder mehrere topAndPop-Aufrufe aktiv sind. Wenn ein topAndPop-Aufruf aktiv ist (6), wird oldHead gelöscht. Wenn nicht, wird oldHead zur Liste der zu löschenden Einträge hinzugefügt (7). Ich gehe davon aus, dass nur ein topAndPop-Aufruf aktiv ist. In diesem Fall erstelle ich einen lokalen Zeiger copyOfToBeDeletedNodes auf die zu löschenden Knoten und setze den toBeDeletedNodes-Zeiger auf einen nullptr (8). Bevor ich die Knoten lösche, prüfe ich, ob in der Zwischenzeit kein weiterer topAndPop-Aufruf aktiv ist. Wenn die aktuelle topAndPop noch die einzige Ausführung ist, verwende ich den lokalen Zeiger copyOfToBeDeletedNodes, um die Liste aller zu löschenden Knoten zu löschen (9). Wenn ein weiterer topAndPop-Aufruf dazwischengeschoben wird, verwende ich den lokalen Zeiger copyOfToBeDeletedNodes, um den toBeDeletedNodes-Zeiger zu aktualisieren.

Die beiden Hilfsfunktionen addNodeToBeDeletedNodes und deleteAllNodes iterieren durch die Liste. deleteAllNodes wird nur aufgerufen, wenn ein topAndPop-Aufruf aktiv ist. Folglich ist keine Synchronisierung erforderlich. Diese Feststellung gilt nicht für die Mitgliedsfunktion addNodeToBeDeletedNodes (9) und (7). Sie muss synchronisiert werden, da mehr als ein topAndPop-Aufruf aktiv sein kann. Die while-Schleife macht den oldHead zum ersten Knoten in den zu löschenden Knoten und verwendet ein compare_exchange_strong, um der Tatsache Rechnung zu tragen, dass sich topAndPop-Aufrufe überlagern können. Sich überschneidende topAndPop-Aufrufe führen dazu, dass oldHead->next != toBeDeletedNodes (Zeile 10) und oldHead->next auf die toBeDeletedNodes aktualisiert werden muss.

Bisher funktioniert diese Lock-freie Stack-Implementierung wie erwartet, hat aber ein paar Schwächen. Wenn viele topAndPop-Aufrufe ineinandergreifen, kann es passieren, dass der Zähler topAndPopCounter nie eins wird. Das bedeutet, dass die Knoten in den Listen der zu löschenden Knoten nicht gelöscht werden, und wir haben ein Speicherleck. Außerdem wird die Anzahl der zu löschenden Knoten eventuell zu einem Ressourcenproblem.