6

在C++ Concurrency in Action一书中，作者给出了一个使用危险指针实现无锁堆栈数据结构的例子。部分代码如下：

std::shared_ptr<T> pop()
{
    std::atomic<void*>& hp=get_hazard_pointer_for_current_thread();
    node* old_head=head.load();
    node* temp;
    do
    {
        temp=old_head;
        hp.store(old_head);
        old_head=head.load();
    } while(old_head!=temp);
    // ...
}

描述说

您必须在while循环中执行此操作，以确保在读取旧指针和设置危险指针node之间没有删除。head在此窗口期间，没有其他线程知道您正在访问此特定节点。head幸运的是，如果要删除旧 节点，head它本身肯定已经改变，因此您可以检查这一点并继续循环，直到您知道head 指针仍然具有您设置危险指针的相同值。

我认为代码有缺陷，因为head节点受ABA 问题的影响。即使 的值head保持不变，它最初指向的节点也可能已被删除。分配了一个新head节点，该节点恰好与前一个节点具有相同的地址值。

4

1 回答 1

5

操作的默认memory_order值为，它确保所有操作的顺序一致性（全局全局排序）：load()std::memory_order_seq_cst

从 atomic variable 加载的 每个memory_order_seq_cst操作都遵循以下条件之一：BM

  • 上次A修改的操作的结果M，它出现B在单个总订单的前面
  • 或者，如果有这样的A，B可能会观察到一些修改的结果，M即不是memory_order_seq_cst也不会发生 - 之前A
  • 或者，如果没有这样的A，B则可能会观察到一些不相关的修改的M结果 is not memory_order_seq_cst。

因此，如果节点被修改（删除）并且这发生在全局顺序中的第二次读取之前，则可以保证看到该更改，因此循环将继续执行。如果在此之后进行修改，则不会有任何危害，因为已经设置了危险指针。

你有这个保证，因为存储到危险指针也是用std::memory_order_seq_cst. 此内存顺序为您提供了用于加载的获取操作和用于存储的释放操作，从而防止在同一线程中重新排序。因此，“成功”的读取 ( old_head==temp) 保证了正确的数据被保存。

将这两个负载视为同步点 - 因为它们执行获取操作，所以它们与修改这些值的相应释放操作同步，导致所有写入变得可见。

您描述的问题不会以任何方式破坏该示例。pop()函数旨在删除顶部元素，它会做到这一点。如果同时添加/删除元素，它将弹出它，无论它的地址是什么（它甚至可能与之前获取的相同）。这是一个完全不同的问题。考虑：

concurrent_stack<int> p;
if (!p.empty() && (p.top() == 5))
{
  auto t = p.pop();
  assert( t ); // May fail
  assert( *t == 5 ); // May fail
}

两个断言都可能失败，如果许多线程非常密集地使用堆栈，很可能会经常失败。但这不是由于 的错误实现pop()，而是您需要更强的访问限制以确保确实从堆栈中删除最后一个检查的元素。

于 2018-02-14T09:48:40.640 回答