由于ABA问题,这个危险指针示例是否有缺陷？

Question

在" 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分配了一个新节点,该节点恰好具有与前一个节点相同的地址值.

Answer 1

默认memory_order的load()操作是std::memory_order_seq_cst,确保所有操作(占全球总量排序)的顺序一致性:

从原子变量加载的每个memory_order_seq_cst操作B都会 M观察到以下情况之一:

• A修改的最后一个操作的结果M,它出现B在单个总订单之前
• 或者,如果有这样的A,B可能会观察到一些修改的结果就M不是memory_order_seq_cst,不发生,前A
• 或者,如果不是这样的A,B可能会观察到的一些无关修改的结果M,是不是memory_order_seq_cst.

因此,如果节点被修改(删除)并且这发生在全局总顺序中的第二次读取之前,则可以保证看到该更改,因此循环将继续执行.如果在此之后订购此修改,则由于已经设置了危险指针,因此没有任何危害.

你有这个保证,因为存储危险指针也完成了std::memory_order_seq_cst.此内存顺序为您提供了对存储的加载和释放操作的获取操作,从而防止在同一线程内重新排序.因此,"成功"read()可确保保存正确的数据.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(),而是因为您需要更强的访问限制以确保确实从堆栈中删除了最后一个已检查的元素.