C++26: Vollständige Implementierung eines Lock-freien Stacks

Nach der Theorie zur Lock-freien Programmierung im vorletzten Beitrag und einer unvollständigen Implementierung im vorherigen Artikel folgt nun die vollständige Implementierung eines Lock-freien Stacks.

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

Sequenzielle Konsistenz

Dieser Absatz ist optional. In meinen Beispielen verwende ich die Standard-Speicherordnung: sequenzielle Konsistenz. Der Grund dafür ist einfach. Die sequenzielle Konsistenz bietet die stärksten Garantien aller Speicherordnungen und ist daher einfacher zu verwenden als die anderen Speicherordnungen. Die sequenzielle Konsistenz ist ein idealer Ausgangspunkt für die Gestaltung von Lock-freien Datenstrukturen. In weiteren Optimierungsschritten kann die Speicherordnung abgeschwächt und eine Acquire-Release-Semantik oder Relaxed Semantik angewendet werden.

Je nach Architektur kann es sein, dass sich eine Schwächung der Speicheranordnung nicht auszahlt. Das x86-Speichermodell ist beispielsweise eines der stärksten Speichermodelle aller moderneren Architekturen. Daher bringt eine Aufhebung der sequenziellen Konsistenz und die Anwendung einer schwächeren Speicherordnung möglicherweise nicht die gewünschten Leistungsverbesserungen. Im Gegensatz dazu kann es sich bei ARMv8, PowerPC, Itanium und insbesondere DEC Alpha auszahlen, wenn die sequenzielle Konsistenz aufgehoben wird.

Die vereinfachte Stack-Version aus dem letzten Artikel weist zwei Probleme auf: Erstens verfügt sie nicht über eine Pull-Operation und zweitens gibt sie keinen Speicher frei.

Eine vollständige Implementierung

Normalerweise unterstützt ein Stack die Memberfunktionen push, pop und top. Die Implementierung der Memberfunktionen pop und top in einer threadsicheren Weise garantiert nicht, dass der Aufruf von top, gefolgt von pop, threadsicher ist. Es kann vorkommen, dass ein Thread t1 stack.top() aufruft und von einem anderen Thread t2 überlagert wird, der stack.top() und dann stack.pop() aufruft. Nun basiert der letzte Aufruf von pop auf der falschen Stackgröße.

Keine Speicherrückgabe

Folglich werden in der folgenden Implementierung die beiden Elementfunktionen top und pop in einer einzigen Funktion zusammengefasst: topAndPop.

// lockFreeStackWithLeaks.cpp

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

template<typename T>
class LockFreeStack {
 private:
    struct Node {
        T data;
        Node* next;
        Node(T d): data(d), next(nullptr){ }
    };
    std::atomic<Node*> head;
 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() {
        Node* oldHead = head.load();                                                 // 1
        while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) {  // 2
            if ( !oldHead ) throw std::out_of_range("The stack is empty!");          // 3
        }
        return oldHead->data;                                                        // 4
    }
};
   
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();                            // 5  
    
    std::cout << fut3.get() << '\n';
    std::cout << fut4.get() << '\n';
    std::cout << fut5.get() << '\n';

}

Die Memberfunktion topAndPop gibt das oberste Element des Stack zurück. Sie liest das Kopfelement des Stacks (Zeile 1) und macht den nächsten Knoten zum neuen Kopf, wenn oldHead kein nullptr ist (Zeile 2). oldhead ist ein nullptr, wenn der Stack leer ist. Ich werfe eine Exception, wenn der Stack leer ist (Zeile 3). Die Rückgabe eines speziellen Nicht-Werts oder die Rückgabe eines std::optional ist ebenfalls eine gültige Option. Das Kopieren des Werts hat einen Nachteil: Wenn der Kopierkonstruktor eine Ausnahme wie std::bad_alloc auslöst, geht der Wert verloren. Schließlich gibt die Memberfunktion das Kopfelement zurück (Zeile 4).

Die Aufrufe fut.get(), fut1.get(), fut2.get() (Zeile 5) stellen sicher, dass der zugehörige Promise ausgeführt wird. Wenn man die Launch Policy nicht angibt, wird der Promise möglicherweise im Thread des Aufrufers verzögert ausgeführt. Lazy bedeutet, dass der Promise nur dann ausgeführt wird, wenn der Future mit get oder wait nach seinem Ergebnis fragt. Der Promise kann auch in einem separaten Thread starten:

auto fut = std::async(std::launch::asnyc, [&conStack]{ conStack.push(2011); });
auto fut1 = std::async(std::launch::asnyc, [&conStack]{ conStack.push(2014); });
auto fut2 = std::async(std::launch::asnyc, [&conStack]{ conStack.push(2017); });

Die Ausgabe des Programms liefert schließlich:

Obwohl der vorgestellte Lock-freie Stack push und topAndPop unterstützt, hat er ein schwerwiegendes Problem: Er verliert Speicher. Warum kann oldHead nicht einfach nach dem Aufruf head.compare_exchange_strong(oldHead, oldHead->next) (2) in der Memberfunktion topAndPop entfernt werden? Die Antwort ist, dass ein anderer Thread oldHead verwenden könnte. Analysieren wir die Memberfunktionen push und topAndPop. Die gleichzeitige Ausführung von push ist kein Problem, da der Aufruf !head.compare_exchange_strong(newNode->next, newNode) newNode->next atomar auf den neuen Kopf aktualisiert. Dies gilt auch, wenn nur ein Aufruf von topAndPop erfolgt. Das Problem tritt auf, wenn mehrere Aufrufe von topAndPop mit oder ohne einen Aufruf von push verschachtelt sind. Das Löschen von oldHead, während ein anderer Thread es verwendet, wäre katastrophal, da das Löschen von oldHead immer vor oder nach seiner Aktualisierung auf den neuen Kopf erfolgen muss: oldHead->next (2).

Was kommt als Nächstes?

Dank RCU und Hazard Pointers kann ich die Speicherverluste in meinem nächsten Artikel beseitigen. (rme)