C ++ 26: Atomik Akıllı İşaretçi ile Bloklar Olmayan Bir Yığın

[Saberie]

Önceki blog yazımda, hala hafıza kaybı olan bloksız bir yığın uygulamasını gösterdim. Bu sefer onu kaldırma yaklaşımını gösteriyorum.


Duyuru

Rainer Grimm yıllardır yazılım mimarı, ekip ve eğitim müdürü olarak çalıştı. C ++ programlama dilleri, Python ve Haskell hakkında makaleler yazmayı seviyor, ancak uzman konferanslarla konuşmayı da seviyor. Modern C ++ blogunda, C ++ tutkusuyla yoğun bir şekilde ilgileniyor.







Atomik akıllı işaretçi

Birinde nükleer operasyon elde etmenin iki yolu vardır std::shared_ptr Uygulama: C ++ 11'de, ücretsiz atom işlevleri std::shared_ptr kullanılabilir. C ++ 20 ile atomik akıllı bölümler kullanabilirsiniz.

C ++ 11

Atom operasyonlarının kullanımı std::shared_ptr Sıkıcı ve hatalara eğilimlidir. Atom operasyonlarını kolayca unutabilirsiniz ve her şey mümkündür. Aşağıdaki örnekte blokları olmayan bir yığın std::shared_ptr temelli.


// 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:ut_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';

}


Blok olmayan bir bloğun uygulanması, depolama kurtarma olmadan önceki uygulamaya benzer. Temel fark, veri türünden düğümlerin std::shared_ptr Ben. Tüm Operasyonlar std::shared_ptr Ücretsiz atom operasyonları kullanarak atomik olun std::load (1) ve (4) e std::atomic_compare_exchange_strong (2) ve (3). Atom işlemleri bir işaretçi gerektirir. Bir sonraki düğümün okunduğunu vurgulamak istiyorum oldHead->next (4) Atomik olmalı, orada oldHead->next Diğer iş parçacıkları tarafından kullanılabilir.

Son olarak, program burada takip ediyor.

Dokuz yıl boyunca geleceğe atlıyoruz ve C ++ 20 kullanıyoruz.

C ++ 20

C ++ 20, kısmi uzmanlıklarını destekler std::atomic İçin std::shared_ptr VE std::weak_ptr. Aşağıdaki uygulama, bir tane blok olmadan yığın düğümlerini ekler std::atomic<std::shared_ptr<Node>> A.


// 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:ut_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';

}


Bir öncekiyle bu uygulama arasındaki temel fark, düğümün bir std::atomic<std::shared_ptr<Node>> Dahil edilmiştir (1). Sonuç olarak, üye işlevi oluşturur push (2) Bir std::shared_ptr<Node> Ve çağrı head.load() Üye işlevinde topAndPop Bir tane verir std::atomic<std::shared_ptr<Node>> Geriye doğru.

İşte programın baskısı:

std::atomic<std::shared_ptr> Bloklar olmadan değil

Birinde nükleer operasyonlarla önceki programlarda açıkça bulundum std::shared_ptr ve bir std::atomic aldattı. Bu atom operasyonları std::shared_ptr Şu anda bloksuz değiller. Ayrıca, std::atomic Tüm kısmi ve eksiksiz uzmanlıkları kullanmak için kavisli bir mekanizma kullanın. std::atomic Desteklemek için.

İşlev atom.lock_free() için std::atomic<std::shared_ptr<Node>> itibaren false Geriye doğru.


// 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';

}


Sırada ne var?


Bu yüzden başlangıca geri döndük ve bir sonraki makalemde depolama yönetimi ile uğraşmalıyız.


(RME)