C++26: Ein Lock-freier Stack mit Atomic Smart Pointer
Der einfachste Weg, das in einem frĂĽheren Beitrag beschriebene Speicherleck zu beheben, ist die Verwendung eines std::shared_ptr.
(Bild: SerbioVas/Shutterstock)
- Rainer Grimm
In meinem vorherigen Blogbeitrag habe ich die vollständige Implementierung eines Lock-freien Stacks gezeigt, der aber noch ein Speicherleck hatte. Diesmal zeige ich den Ansatz, um es zu beseitigen.
Atomic Smart Pointer
Es gibt zwei Möglichkeiten, atomare Operationen auf einen std::shared_ptr anzuwenden: In C++11 können die freien Atomic-Funktionen auf std::shared_ptr verwendet werden. Mit C++20 können Atomic Smart Pointers verwendet werden.
C++11
Die Verwendung von Atomic-Operationen auf std::shared_ptr ist mühsam und fehleranfällig. Man kann die Atomic-Operationen leicht vergessen, und alles ist möglich. Das folgende Beispiel zeigt einen Lock-freien Stack, der auf std::shared_ptr basiert.
// lockFreeStackWithSharedPtr.cpp
#include <atomic>
#include <future>
#include <iostream>
#include <stdexcept>
#include <memory>
template<typename T>
class LockFreeStack {
public:
struct Node {
T data;
std::shared_ptr<Node> next;
};
std::shared_ptr<Node> head;
public:
LockFreeStack() = default;
LockFreeStack(const LockFreeStack&) = delete;
LockFreeStack& operator= (const LockFreeStack&) = delete;
void push(T val) {
auto newNode = std::make_shared<Node>();
newNode->data = val;
newNode->next = std::atomic_load(&head); // 1
while( !std::atomic_compare_exchange_strong(&head, &newNode->next, newNode) ); // 2
}
T topAndPop() {
auto oldHead = std::atomic_load(&head); // 3
while( oldHead && !std::atomic_compare_exchange_strong(&head, &oldHead, std::atomic_load(&oldHead->next)) ) { // 4
if ( !oldHead ) throw std::out_of_range("The stack is empty!");
}
return oldHead->data;
}
};
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';
}Diese Implementierung eines Lock-freien Stacks ähnelt der vorherigen Implementierung ohne Speicherrückgewinnung. Der Hauptunterschied besteht darin, dass die Knoten vom Datentyp std::shared_ptr sind. Alle Operationen std::shared_ptr werden atomar unter Verwendung der freien atomaren Operationen std::load (1) und (4) und std::atomic_compare_exchange_strong (2) und (3) durchgeführt. Die atomaren Operationen erfordern einen Zeiger. Ich möchte ausdrücklich betonen, dass die Leseoperation des nächsten Knotens in oldHead->next (4) atomar sein muss, da oldHead->next von anderen Threads verwendet werden kann.
AbschlieĂźend folgt hier die Ausgabe des Programms.
Springen wir neun Jahre in die Zukunft und verwenden C++20.
C++20
C++20 unterstĂĽtzt partielle Spezialisierungen von std::atomic fĂĽr std::shared_ptr und std::weak_ptr. Die folgende Implementierung fĂĽgt die Knoten des Lock-freien Stacks in ein std::atomic<std::shared_ptr<Node>> ein.
// lockFreeStackWithAtomicSharedPtr.cpp
#include <atomic>
#include <future>
#include <iostream>
#include <stdexcept>
#include <memory>
template<typename T>
class LockFreeStack {
private:
struct Node {
T data;
std::shared_ptr<Node> next;
};
std::atomic<std::shared_ptr<Node>> head; // 1
public:
LockFreeStack() = default;
LockFreeStack(const LockFreeStack&) = delete;
LockFreeStack& operator= (const LockFreeStack&) = delete;
void push(T val) { // 2
auto newNode = std::make_shared<Node>();
newNode->data = val;
newNode->next = head;
while( !head.compare_exchange_strong(newNode->next, newNode) );
}
T topAndPop() {
auto oldHead = head.load();
while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) {
if ( !oldHead ) throw std::out_of_range("The stack is empty!");
}
return oldHead->data;
}
};
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 Hauptunterschied zwischen der vorherigen und dieser Implementierung besteht darin, dass der Knoten in einen std::atomic<std::shared_ptr<Node>> eingebettet ist (1). Folglich erstellt die Memberfunktion push (2) einen std::shared_ptr<Node> und der Aufruf head.load() in der Memberfunktion topAndPop gibt einen std::atomic<std::shared_ptr<Node>> zurĂĽck.
Hier ist die Ausgabe des Programms:
std::atomic<std::shared_ptr> ist nicht Lock-frei
Offen gestanden habe ich in den vorherigen Programmen mit atomaren Operationen auf einem std::shared_ptr und einem std::atomic geschummelt. Diese atomaren Operationen auf einem std::shared_ptr sind derzeit nicht Lock-frei. Darüber hinaus kann eine Implementierung von std::atomic einen Lockmechanismus verwenden, um alle teilweisen und vollständigen Spezialisierungen von std::atomic zu unterstützen.
Die Funktion atom.lock_free() fĂĽr ein std::atomic<std::shared_ptr<Node>> gibt false zurĂĽck.
// atomicSmartPointer.cpp
#include <atomic>
#include <iostream>
#include <memory>
template <typename T>
struct Node {
T data;
std::shared_ptr<Node> next;
};
int main() {
std::cout << '\n';
std::cout << std::boolalpha;
std::atomic<std::shared_ptr<Node<int>>> node;
std::cout << "node.is_lock_free(): " << node.is_lock_free() << '\n';
std::cout << '\n';
}Wie geht es weiter?
Wir sind also wieder am Anfang und müssen uns in meinem nächsten Artikel um das Speichermanagement kümmern.
(rme)
