C++26: Vereinfachte Implementierung eines Lock-freien Stacks

Nach der Theorie zur Lock-freien Programmierung in meinem letzten Beitrag geht es nun um die praktische Umsetzung.

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

Allgemeine Überlegungen

Von außen betrachtet ist der Aufrufende (die Anwendung) dafür verantwortlich, die Daten zu schützen. Von innen betrachtet ist die Datenstruktur dafür verantwortlich, sich selbst zu schützen. Eine Datenstruktur, die sich selbst schützt, sodass kein Data Race auftreten kann, wird als Thread-sicher bezeichnet.

Zunächst stellt sich die Frage, wie man beim Entwurf einer Concurrency-Datenstruktur vorgehen sollte.

• Locking-Strategie: Sollte die Datenstruktur grob- oder feinkörniges Locking unterstützen oder Lock-frei sein? Grobkörniges Locking ist zwar einfacher zu implementieren, führt aber zu Konflikten. Eine feinkörnige oder Lock-freie Implementierung ist viel anspruchsvoller. Zunächst einmal: Wie ist grobkörniges Locking zu verstehen? Grobkörniges Locking bedeutet, dass die Datenstruktur zu einem bestimmten Zeitpunkt nur von einem Thread verwendet wird.
• Die Granularität der Schnittstelle: Je mächtiger die Schnittstelle der Thread-sicheren Datenstruktur ist, desto schwieriger wird es, über ihre gleichzeitige Nutzung nachzudenken.
• Typisches Nutzungsmuster: Wenn Leser deine Datenstruktur hauptsächlich verwenden, sollten du sie nicht für Schreiber optimieren.
• Vermeiden von Schlupflöchern: Gib die Interna deiner Datenstruktur nicht an Kunden weiter.
• Konkurrenz: Kommen gleichzeitige Clientanfragen in deiner Datenstruktur häufig vor?
• Skalierbarkeit: Wie ist die Performanz deiner Datenstruktur, wenn die Anzahl der gleichzeitigen Clients zunimmt oder die Datenstruktur begrenzt ist?
• Invarianten: Welche Invariante muss für deine Datenstruktur bei der Verwendung gelten?
• Ausnahmen: Was soll passieren, wenn eine Ausnahme auftritt?

Natürlich sind diese Überlegungen voneinander abhängig. So kann beispielsweise die Verwendung einer grobkörnigen Lock-Strategie die Konkurrenz um die Datenstruktur erhöhen und die Skalierbarkeit beeinträchtigen.

Zunächst einmal: Wie sieht ein Stack aus?

Ein Stack

std::stack folgt dem LIFO-Prinzip (Last In – First Out). Ein Stack sta, der den Header <stack> benötigt, hat drei Memberfunktionen: Mit sta.push(e)kann man ein neues Element e oben auf den Stack einfügen, es mit sta.pop() von oben entfernen und mit sta.top() darauf verweisen. Der Stack unterstützt die Vergleichsoperatoren und kennt seine Größe.

#include <stack>
...
std::stack<int> myStack;

std::cout << myStack.empty() << '\n'; // true
std::cout << myStack.size() << '\n'; // 0

myStack.push(1);
myStack.push(2);
myStack.push(3);

std::cout << myStack.top() << '\n'; // 3
while (!myStack.empty()){
    std::cout << myStack.top() << " ";
    myStack.pop();
} // 3 2 1

std::cout << myStack.empty() << '\n'; // true
std::cout << myStack.size() << '\n'; // 0

Beginnen wir nun mit der Implementierung eines Lock-freien Stacks.

Eine vereinfachte Implementierung

In meiner vereinfachten Implementierung beginne ich mit der push-Member-Funktion. Zunächst möchte ich veranschaulichen, wie ein neuer Knoten zu einer einfach verketteten Liste hinzugefügt wird. head ist der Zeiger auf den ersten Knoten in der einfach verketteten Liste.

Jeder Knoten in der einfach verketteten Liste hat zwei Attribute: Seinen Wert T und den Zeiger next. next verweist auf das nächste Element in der einfach verketteten Liste. Nur der Knoten verweist auf den nullptr. Das Hinzufügen eines neuen Knotens zu den Daten ist unkompliziert. Erstelle einen neuen Knoten und lasse den next-Zeiger auf den vorherigen Kopf verweisen. Bisher ist der neue Knoten nicht zugänglich. Schließlich wird der neue Knoten zum neuen Kopf und schließt den push-Vorgang ab.

Das folgende Beispiel zeigt die Lock-freie Implementierung eines Concurrent Stacks:

// lockFreeStackPush.cpp

#include <atomic>
#include <iostream>

template<typename T>
class LockFreeStackPush {
 private:
    struct Node {
        T data;
        Node* next;
        Node(T d): data(d), next(nullptr) {}
    };
    std::atomic<Node*> head;
 public:
    LockFreeStackPush() = default;
    LockFreeStackPush(const LockFreeStackPush&) = delete;
    LockFreeStackPush& operator= (const LockFreeStackPush&)
      = delete;
   
    void push(T val) {
        Node* const newNode = new Node(val);                // 1
        newNode->next = head.load();                        // 2
        while( !head.compare_exchange_strong(newNode->next,
                                            newNode) );     // 3
    }
};
   
int main(){

    LockFreeStackPush<int> lockFreeStack;
    lockFreeStack.push(5);
    
    LockFreeStackPush<double> lockFreeStack2;
    lockFreeStack2.push(5.5);
    
    LockFreeStackPush<std::string> lockFreeStack3;
    lockFreeStack3.push("hello");

}

Ich möchte die entscheidende Memberfunktion push analysieren. Sie erstellt den neuen Knoten (1), passt seinen nächsten Zeiger an den alten Kopf an und macht den neuen Knoten in einer sogenannten CAS-Operation zum neuen Kopf (3). Eine CAS-Operation bietet in einem atomaren Schritt eine Vergleichs- und Tauschoperation.

Der Aufruf newNode->next = head.load() lädt den alten Wert von head. Wenn der geladene Wert newNode->next immer noch derselbe ist wie head in (3), wird head auf newNode aktualisiert und der Aufruf head.compare_exchange_strong gibt true zurück. Wenn nicht, gibt der Aufruf false zurück und die while-Schleife wird ausgeführt, bis der Aufruf true zurückgibt. head.compare_exchange_strong gibt false zurück, wenn ein anderer Thread inzwischen einen neuen Knoten zum Stack hinzugefügt hat.

Die Zeilen (2) und (3) im Codebeispiel bilden eine Art atomare Transaktion. Zuerst wird eine Momentaufnahme der Datenstruktur erstellt (2), dann wird versucht, die Transaktion zu veröffentlichen (3). Wenn die Momentaufnahme nicht mehr gültig ist, wird ein Rollback durchgeführt und es wird erneut versucht.

Wie geht es weiter?

Die heutige vereinfachte Stack-Implementierung dient mir als Grundlage für zukünftige Stacks.

(rme)