如果在悬空指针上调用“compare_exchange_weak”会发生什么？我教科书上的代码安全吗？

Question

我觉得在C++：动作中的并发中无锁堆栈的示例实现中可能存在悬空指针。作者 Anthony Williams 为无锁堆栈类提供了一个开端：

class LockFreeStack {
  private:
    struct Node {
        T data;
        Node* next;

        Node(T const& data_) : data(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));
    }
};

Williams 然后讨论如何实施

pop

。他说，“一旦节点被添加到堆栈中，push() 就不会触及该节点，因此调用 pop() 的线程必须是唯一可以触及该节点的线程，并且可以安全地删除它。”要删除的节点最初添加到

std::atomic<Node*> pending_deletion_head

上，变量

std::atomic<unsigned> threads_in_pop

存储正在访问

pop

的线程数。当

pending_deletion_head

为零时，从

threads_in_pop

延伸的整条链最终被删除。

这对我来说总体来说是有意义的，但我对

push

如何安全感到困惑。具体来说，

new_node->next

行中的

while(!head.compare_exchange_weak(new_node->next, new_node));

不能是具有给定的

pop

实现的悬空指针吗？

Answer 1

push

的实现是安全的，因为您只访问

new_node->next

。

new_node

始终是用

new Node

在本地创建的，因此它不能是悬空指针。声明：

while (!head.compare_exchange_weak(new_node->next, new_node)) {}

...正在有效地做：

while(true) {
    // syntax from transactional memory TS
    atomic_noexcept {
        // using -> is safe here because up to this point,
        // new_node is always a not-null pointer
        if (head == new_node->next) {
            // new_node->next may be dangling after this, but we don't care
            // and return from the function
            head = new_node;
            break;
        }
        else {
            new_node->next = head;
            continue;
        }
    }
}

访问

new_node->next

始终是安全的，因为

new_node

是您之前创建的新节点。

new_node->next

可能会在循环期间被

head

替换，这使其成为无效指针，但

new_node

本身永远不会悬空，这使得这没问题。