茶年 · 中文维基百科

冒险指针

Wikipedia · 2020-12-20 维基百科 👁 1 阅读

在多线程环境中， 冒险指针是一种解决由无锁 数据结构中的节点动态内存管理引起的问题的方法。 这些问题通常仅在没有自动垃圾收集的环境中出现。

使用比较和交换原语的任何无锁数据结构都必须处理ABA问题。 例如，在使用链表实现的无锁堆栈中，一个线程可能正在尝试从堆栈的前面弹出项目（A→B→C）。 它会记住自栈顶而下的第二个值“B”，然后执行
compare_and_swap(target=&head, newvalue=B, expected=A) 不幸的是，在此操作正在执行时，另一个线程可能执行了两次弹出操作，然后将A推回顶部，从而导致堆栈（A→C）。 比较并交换成功将“ head”与“ B”交换，结果是堆栈现在包含垃圾数据（指向已经被释放的元素“ B”的指针）。

此外，任何包含以下形式代码的无锁算法
Node* currentNode = this->head; // assume the load from "this->head" is atomic
Node* nextNode = currentNode->next; // assume this load is also atomic
在没有自动垃圾收集的情况下，它还面临另一个主要问题。 在这两行之间，另一个线程可能会弹出this->head指向的节点并对其进行内存分配，这意味着通过第二行上的currentNode进行的内存访问读取了已释放的内存（实际上可能已经被另外一部分程序用在了不同的地方）。

冒险指针可用于同时解决这两个问题。 在使用冒险指针的系统中，每个线程都保留一个冒险指针的列表 ，这些指针指示该线程当前正在访问的节点。 （在许多系统中，此“列表”可能只限于一个或两个元素。 ）冒险指针列表上的节点不得被任何其他线程修改或释放。 {{Quote|Each reader thread owns a single-writer/multi-reader shared pointer called "hazard pointer." When a reader thread assigns the address of a map to its hazard pointer, it is basically announcing to other threads (writers), "I am reading this map. You can replace it if you want, but don't change its contents and certainly keep your deleteing hands off it."|Andrei Alexandrescu and Maged Michael|Lock-Free Data Structures with Hazard Pointers但该申请在2010年被放弃。

冒险指针的替代方法包括引用计数 。

参见

  • 并发数据结构
  • 冒险(计算机体系结构)

参考文献
*

外部链接

#程序架構

评论 (0)

  • 还没有评论，来抢沙发吧。