为什么在这个无锁栈类中'删除'节点会导致竞争状态？

在题为“C++并发在行动”，由安东尼·威廉姆斯，在7.2.1节的书，无锁堆栈实现上市：为什么在这个无锁栈类中'删除'节点会导致竞争状态？

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（）中，我们选择泄漏节点，以避免一个线程删除一个节点时的竞争状态，而另一个线程仍然持有一个指向它的指针，它正要解除引用。

1）我不明白为什么这样的情况会发生，为什么弹出以下（）函数将导致竞争条件：

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）如何来，对于调用弹出多个线程（）同时，'old_head'变量可以在第（3）行之后指向同一个节点对象？

来源

2016-09-16 Benji Mizrahi

线程1进入（2）。它开始评估head_->next。它将head_加载到一个寄存器中，然后放弃优先级。

线程2从函数的开始到结束进行。从存在删除head_删除它并返回head_的内容。

线程1醒来。它遵循head_在获得->next字段的注册表中。但是线程2已经删除了head_指向的数据，我们只是跟着一个悬挂指针。

来源

2016-09-16 19:01:54 Yakk

对不起，我还不清楚。是的，线程1将遵循不存在的指针并在“next”中读取可能已经分配给另一个变量的值。因此，compare_exchange_weak（）的第二个参数将无效。但它不会被使用，因为当执行compare_exchange_weak（）时，它会检测到“head_！= old_head”。所以，是的，我们将读取compare_exchange_weak（）的无效参数，但它将永远不会被使用。问题是什么？你能澄清一下吗？ – Alex

@alex你为什么会认为它们不相等？你跟着一个悬挂指针，值可以是*任何*。它在哪里检查'head _！= old_head_'？我错过了吗？ – Yakk

很可能我错过了一些东西，但我仍然不明白究竟是什么。检查“head _！= old_head_”位于compare_exchange_weak（）内部。如果这些值不相等，则不会使用compare_exchange_weak（）的第二个参数。在我的理解compare_exchange_weak（）从内存原子读取头的当前值。在第一个线程唤醒后的讨论场景中，寄存器中的头值不会等于内存中头的当前值。因此，compare_exchange_weak（）将会看到它，并且不会使用第二个参数（垃圾，我们在注册表头中的无效值之后读取）。 – Alex

为什么在这个无锁栈类中'删除'节点会导致竞争状态？

回答

相关问题