为什么“删除"此无锁堆栈类中的节点会导致争用情况? [英] Why would 'deleting' nodes in this lock-free stack class would cause race condition?

问题描述

在Anthony Williams题为"C ++ Concurrency in Action"的书的第7.2.1节中，列出了无锁堆栈实现:

In the book titled "C++ Concurrency in Action" by Anthony Williams, in Section 7.2.1, a lock-free stack implementation is listed:

template <typename T>
class lock_free_stack {
    struct node {
        shared_ptr<T> data_;
        node* next_;
        node(const T& data) : data_(make_shared(data)) {}
    };
    atomic<node*> head_;
public:
    void push(const T& data)
    {
        node* new_node = new node(data);
        new_node->next_ = head_.load();
        while(!head.compare_exchange_weak(new_node->next_, new_node));
    }
    shared_ptr<T> pop()
    {
        node* old_head = head_.load();
        while (old_head &&
                !head_.compare_exchange_weak(old_head, head_->next_));
        return old_head ? old_head->data_ : shared_ptr<T>();
    }
};

然后在第7.2.2节中，作者说"...在pop()处，我们选择泄漏节点，以避免争用情况，其中一个线程删除了一个节点，而另一个线程仍然持有指向该节点的指针，它正要取消引用."

Then in Section 7.2.2, the author says "... at pop(), we opted to leak nodes in order to avoid the race condition where one thread deletes a node while another thread still holds a pointer to it that it's just about to dereference."

1)我不明白为什么会发生这种情况，以及为什么以下pop()函数会导致竞争状态:

1) I don't understand why such a scenario might happen and why the following pop() function would cause race condition:

shared_ptr<T> pop()
{
    node* old_head = head_.load(); // (1)
    while (old_head &&
            !head_.compare_exchange_weak(old_head, head_->next_)); // (2)
    shared_ptr<T> res; // (3)
    if (old_head) {
        res.swap(old_head->data);
        delete old_head;
        return res;
    } else {
        return {};
    }
}

2)对于同时调用pop()的多个线程，'old_head'变量如何可以指向第(3)行之后的同一节点对象?

2) How comes that for multiple threads that call pop() at the same time, 'old_head' variable can point to the same node object after line (3)?

推荐答案

线程1前进至(2).它开始评估 head _-> next .它将 head _ 加载到寄存器中，然后放弃优先级.

Thread 1 proceeds to (2). It starts to evaluate head_->next. It loads head_ into a register, then gives up priority.

线程2从函数的开始到结束.通过删除 head _ 使其不存在，并返回 head _ 的内容.

Thread 2 proceeds from the start to the end of the function. It removes head_ from existence by deleting it and returns the contents of head_.

线程1唤醒.它跟随 head _ 在寄存器中，以获取-> next 字段.但是线程2已经删除了 head _ 所指向的数据，而我们只是跟随了一个悬空的指针.

Thread 1 wakes up. It follows head_ in a register getting the ->next field. But thread 2 has already deleted the data pointed to by head_, and we just followed a dangling pointer.

这篇关于为什么“删除"此无锁堆栈类中的节点会导致争用情况?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！