C++ ConcurrencyInAction：7.2.2 阻止那些讨厌的泄漏：管理无锁数据结构中的内存

Question

我想了解如何在 pop() 中有多个线程保持头指针，如果两个线程在“节点 *old_head = head.load();”处保持头指针然后第一个线程将通过更新头部来完成循环，最后假设我们删除了 old_head 并且 Thread1 完成了它的工作，现在 Thread2 仍然保持 deleted old_head 并且它将进入 while 循环并且old_head和当前的head不一样，所以如果条件和设置“old_head = head;”就会转到else并再次循环并更新头部并退出循环并删除 old_head.

在上面的过程中，Thread2 永远不会取消引用已删除的节点，因为如果 head 和 old_head 的条件不相同，它将进入 else。

但是根据 C++ ConcurrencyInAction Book 的作者，我们真的需要检查持有 old_head 的其他线程吗？

From C++ ConcurrencyInAction Book: The basic problem is that you want to free a node, but you can’t do so until you’re sure there are no other threads that still hold pointers to it.

#include <memory>
#include <atomic>
using namespace std;

template <typename T>
class lock_free_stack
{
private:
    struct node
    {
        std::shared_ptr<T> data;
        node *next;
        node(T const &data_) : data(std::make_shared<T>(data_))
        {
        }
    };
    std::atomic<node *> head;

public:
    void push(T const &data)
    {
        node *const new_node = new node(data);
        new_node->next = head.load();
        while (!head.compare_exchange_weak(new_node->next, new_node));
    } 
    std::shared_ptr<T> pop()
    {
        node *old_head = head.load();
        while (old_head && !head.compare_exchange_weak(old_head, old_head->next)); 
        // background steps of compare_exchange_weak
        /*      if ((old_head != nullptr) && (head == old_head))
                {
                    try 
                    {
                        head = old_head->next;
                        return true; // loop ends
                    }
                    catch(exception &e)
                    {
                        return false; // loop forever, at the end if we are deleting old_head then we are deleting head, it makes Stack without head
                    }
                }
                else if ((old_head != nullptr) && (head != old_head))
                {
                    old_head = head;
                    return false;
                }
                else
                {
                    return false; // loop forever
                } */          
        return old_head ? old_head->data : std::shared_ptr<T>();
    } 
};

int main()
{
    return 0;
}

Answer 1

In the above process Thread2 never dereference the deleted node because it will come to else if condition if head and old_head are not same.

这不是真的。考虑这一行：

head.compare_exchange_weak(old_head, old_head->next)

这将在 compare_exchange_weak 运行之前访问 old_head->next 的值。这意味着如果 old_head 是一个悬空指针，你会得到 Undefined Behavoir.

（请注意，在这种情况下，head 将不等于 old_head，因此 old_head->next 的值将 不被使用 ，而只是在我们知道我们不会使用它之前访问它已经导致了问题）。

此外，在 cew 的伪代码中，您似乎认为访问 old_head->next 会引发异常？在 c++ 中并非如此。访问错误的指针将立即导致 Undefined Behavoir，这意味着所有赌注都已关闭。

C++ ConcurrencyInAction：7.2.2 阻止那些讨厌的泄漏：管理无锁数据结构中的内存

C++ ConcurrencyInAction: 7.2.2 Stopping those pesky leaks: managing memory in lock-free data structures

c++

stack

multithreading

memory-management

atomic