C ++ 26: Tehlike riski altında uygulanan blokları olmayan bir yığın
Son gönderilerde yığını bloklar olmadan tartıştım. Tehlikeli epizodlar, basit çöp toplayıcısıyla önceki katkılarda gösterilen uygulamanın tüm sorunlarını çözer.
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.
Bir hafta ila iki haftaya
Her şeyden önce, kendi başıma bir not: 2023'ün sonunda bana bir tanı, ciddi bir progresif sinir bozukluğu teşhisi kondu. Bu nedenle, blogumu gelecekte bir ila iki hafta yayınlama sıklığını değiştireceğim. The Voice'da yazmak yerine bir makale yazmak son derece yorucu ve tüketici zamanıdır.
Tehlikelerin Tehlikeleri
Tehlikeli işaretçi terimi Maged M. Michael'a kadar uzanır. Tehlikeli epizodlar, B. Bloklar olmadan klasik veri yapılarının klasik problemini çözer. Blokları olmayan bir yığın: Bir iş parçacığı bir veri yapısının bir düğümünü güvenli bir şekilde ortadan kaldırabilirken, diğer iş parçacıkları bu düğümü aynı anda kullanabilir?
(Resim: Rainer Grimm)
Bir tehlike işaretçisi, bloklar olmadan veri yapılarında sık sık depolama onayı sorunu için genel bir çözüm sunsa da, yığınımızın bloklar olmadan bakış açısından göstermek istiyorum.
(Resim: Rainer Grimm)
Tehlike işaretçisi, yazma ve okumaya farklı erişim ile bir işaretçidir. Tüm tehlikeli epizodlar bağlı bir liste oluşturur ve sıfır işaretçi ile başlatılır. Bir iş parçacığı bir yığın düğümü kullandığında, düğüm adresi bir tehlike işaretçisine eklenir, bu da bu iş parçacığının bu düğümü kullandığını ve kullanılan tehlike işaretçisinin tek sahibi olduğunu gösterir. İpliğin artık düğüme ihtiyaç duymadığı takdirde, tehlike işaretçisini sıfır bir işaretçiye koyar ve bu nedenle mülkünden vazgeçer.
Bir iş parçacığı, iş parçacığı tarafından kullanılan düğümleri temsil eden ve ortadan kaldırılamayan tehlikeli bölümlerin bir listesini yönlendirir. Bir iş parçacığı bir düğümü silmek istiyorsa, tüm tehlikeli bölümlerin listesini arayın ve düğümün kullanılıp kullanılmadığını kontrol edin. Düğüm kullanılmazsa, silinir. Düğüm kullanıldığında, nihayet silinecek düğümlerin deaktivasyon listesine eklenir. Sonuçta, düğüm deaktivasyon listesine yalnızca listede değilse eklenir.
Blokları olmayan yığınımızın durumunda. Üye işlevi topAndPop Arşivin kurtarılmasıyla ilgili iki görevi vardır. Her şeyden önce, düğümün ortadan kaldırılmasını başarır; İkincisi, düğümün deaktivasyon listesini geçer ve artık kullanılmadıklarında bunları siler.
Yeni bir uygulamada aşağıdaki üye işlevine ihtiyacım var topAndPopÖnceki açıklamaya dayanarak: getHazardPointerBir tehlike işaretçisine referans almak için, retireList.addNode VE retireList.deleteUnusedNodesbir düğüm için retireList eklemek. Üstelik retireList.deleteUnusedNodesSeçim listesi tarafından artık kullanılmayan tüm düğümleri silmek için. Ayrıca, üye işlevi kullanır retireList.deleteUnusedNode Yardımcı işlev retireList.isInUseBir düğümün şu anda kullanımda olup olmadığına karar vermek için. Üye işlevi isInUse Ayrıca içinde topAndPop Geçerli düğümün seçim listesine eklenip eklenmeyeceğine veya doğrudan silinmesi gerekip gerekmediğine karar vermek için kullanışlıdır.
Bu önceki uygulamamı nasıl etkiler? Görüyoruz. Aşağıdaki program, tehlikeli bölümlere dayanan bloklar olmayan bir yığın uygulanmasını göstermektedir:
// lockFreeStackHazardPointers.cpp
#include <atomic>
#include <cstddef>
#include <future>
#include <iostream>
#include <stdexcept>
#include <thread>
template <typename T>
concept Node = requires(T a) {
{T::data};
{ *a.next } -> std::same_as<T&>;
};
template <typename T>
struct MyNode {
T data;
MyNode* next;
MyNode(T d): data(d), next(nullptr){ }
};
constexpr std::size_t MaxHazardPointers = 50;
template <typename T, Node MyNode = MyNode<T>>
struct HazardPointer {
std::atomic<std:
:id> id;std::atomic<MyNode*> pointer;
};
template <typename T>
HazardPointer<T> HazardPointers[MaxHazardPointers];
template <typename T, Node MyNode = MyNode<T>>
class HazardPointerOwner {
HazardPointer<T>* hazardPointer;
public:
HazardPointerOwner(HazardPointerOwner const &) = delete;
HazardPointerOwner operator=(HazardPointerOwner const &) = delete;
HazardPointerOwner() : hazardPointer(nullptr) {
for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
std:
:id old_id;if (HazardPointers<T>.id.compare_exchange_strong(
old_id, std::this_thread::get_id())) {
hazardPointer = &HazardPointers<T>;
break;
}
}
if (!hazardPointer) {
throw std:
ut_of_range(„No hazard pointers available!“);}
}
std::atomic<MyNode*>& getPointer() {
return hazardPointer->pointer;
}
~HazardPointerOwner() {
hazardPointer->pointer.store(nullptr);
hazardPointer->id.store(std:
:id());}
};
Template <typename T, Node MyNode = MyNode<T>>
std::atomic<MyNode*>& getHazardPointer() {
thread_local static HazardPointerOwner<T> hazard;
return hazard.getPointer();
}
template <typename T, Node MyNode = MyNode<T>>
class RetireList {
struct RetiredNode {
MyNode* node;
RetiredNode* next;
RetiredNode(MyNode* p) : node(p), next(nullptr) { }
~RetiredNode() {
delete node;
}
};
std::atomic<RetiredNode*> RetiredNodes;
void addToRetiredNodes(RetiredNode* retiredNode) {
retiredNode->next = RetiredNodes.load();
while (!RetiredNodes.compare_exchange_strong(retiredNode->next, retiredNode));
}
public:
bool isInUse(MyNode* node) {
for (std::size_t i = 0; i < MaxHazardPointers; ++i) {
if (HazardPointers<T>.pointer.load() == node) return true;
}
return false;
}
void addNode(MyNode* node) {
addToRetiredNodes(new RetiredNode(node));
}
void deleteUnusedNodes() {
RetiredNode* current = RetiredNodes.exchange(nullptr);
while (current) {
RetiredNode* const next = current->next;
if (!isInUse(current->node)) delete current;
else addToRetiredNodes(current);
current = next;
}
}
};
template<typename T, Node MyNode = MyNode<T>>
class LockFreeStack {
std::atomic<MyNode*> head;
RetireList<T> retireList;
public:
LockFreeStack() = default;
LockFreeStack(const LockFreeStack&) = delete;
LockFreeStack& operator= (const LockFreeStack&) = delete;
void push(T val) {
MyNode* const newMyNode = new MyNode(val);
newMyNode->next = head.load();
while( !head.compare_exchange_strong(newMyNode->next, newMyNode) );
}
T topAndPop() {
std::atomic<MyNode*>& hazardPointer = getHazardPointer<T>();
MyNode* oldHead = head.load();
do {
MyNode* tempMyNode;
do {
tempMyNode = oldHead;
hazardPointer.store(oldHead);
oldHead = head.load();
} while( oldHead != tempMyNode );
} while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) ;
if ( !oldHead ) throw std:
ut_of_range(„The stack is empty!“);hazardPointer.store(nullptr);
auto res = oldHead->data;
if ( retireList.isInUse(oldHead) ) retireList.addNode(oldHead);
else delete oldHead;
retireList.deleteUnusedNodes();
return res;
}
};
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';
Program beklendiği gibi çalışıyor:
(Resim: Ekran görüntüsü (Rainer Grimm))
Sırada ne var?
Bir sonraki yazımda programı adım adım analiz edeceğim.
(RME)