为什么您可以从lock_free_stack中的pop（）中的Atomic Compare_exchange_weak中取出的节点免费？

Question

我正在阅读《行动》第二本书的＆lt; c ++并发。 ed＆gt;由安东尼·威廉姆斯（Anthony Williams） 第7.2.2节停止了那些讨厌的泄漏：在无锁数据中管理内存。

在本节之前，我们

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));
    return old_head ? old_head->data : std::shared_ptr<T>();
  }
};

在第7.2.2节中实施了一个lock_free_stack，安东尼说：

当您第一次查看pop（）时，您选择泄漏节点以避免比赛 一个线程删除节点的条件，而另一个线程仍然容纳指针 对此即将退出。

我不了解，如果两个线程同时调用pop（），则每个线程都会有不同的头，因此每个线程的old_head彼此不同，并且它们可以自由删除old_head。

我认为，无内存的裂变流行音乐（）是：

  std::shared_ptr<T> pop() {
    node *old_head = head.load();
    while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
    std::shared_ptr<T> res = old_head ? old_head->data : std::shared_ptr<T>();
    delete old_head;
    return res;
  }

如何理解安东尼的话？

Answer 1

比赛在这里

  while (old_head && !head.compare_exchange_weak(old_head, old_head->next));
                                                           ^^^^^^^^^^^^^^

可能的一场比赛是：

1. 线程1呼叫head.load（），在地址x
2. call.load.load（）中
3. 2
4. thread 检索节点在old_head
5. thread 2上删除地址x线程的
6. 节点1尝试读取已删除的old_head-＆gt; next，在其自己的调用之前，已删除了compare_exchange_weak_weak

Answer 2

让我们假设2个线程Enter pop同时却被中断了，因此中断了这样的中断：

Thread 1                                 Thread 2
node *old_head = head.load();            node *old_head = head.load();
while (old_head &&
   !head.compare_exchange_weak(old_head,
                       old_head->next));
std::shared_ptr<T> res =
     old_head ? old_head->data
              : std::shared_ptr<T>();
delete old_head;
                                         while (old_head &&
                                            !head.compare_exchange_weak(old_head,
                                                                old_head->next));
                                      

两个线程都以相同的old_head = head.load（）;开始。然后线程1删除对象，然后在该线程2访问old_head--＆gt; Next。这是免费的。