fbpx
维基百科

冒险指针

行進 15, 2023

在多线程环境中， 冒险指针是一种解决由无锁 数据结构中的节点动态内存管理引起的问题的方法。 这些问题通常仅在没有自动垃圾收集的环境中出现。 [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进行的内存访问读取了已释放的内存（实际上可能已经被另外一部分程序用在了不同的地方）。

冒险指针可用于同时解决这两个问题。 在使用冒险指针的系统中，每个线程都保留一个冒险指针的列表 ，这些指针指示该线程当前正在访问的节点。 （在许多系统中，此“列表”可能只限于一个[1] [2]或两个元素。 ）冒险指针列表上的节点不得被任何其他线程修改或释放。

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[2]

当线程希望删除一个节点时，它将其放置在“稍后释放”的节点列表上，但实际上直到其他线程的危险列表中没有包含指针时才真正释放该节点的内存。 可以通过专用的垃圾回收线程来完成此手动垃圾回收（如果所有线程共享“稍后释放”的列表）；或者，可以由每个工作线程自行清除“待释放”列表，作为诸如“ pop”之类的操作的一部分（在这种情况下，每个工作线程可以负责其自己的“待释放”列表）。

在2002年， IBM的 Maged Michael提出了关于冒险指针技术的美国专利申请， [3]但该申请在2010年被放弃。

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

参见

参考文献

  1. ^ 1.0 1.1 1.2 Anthony Williams. C++ Concurrency in Action: Practical Multithreading. Manning:Shelter Island, 2012. See particularly Chapter 7.2, "Examples of lock-free data structures".
  2. ^ 2.0 2.1 Andrei Alexandrescu and Maged Michael. Lock-Free Data Structures with Hazard Pointers. Dr. Dobb's. 2004 [2020-01-17]. （原始内容于2019-07-19）. 
  3. ^ US application 20040107227  Maged M. Michael, "Method for efficient implementation of dynamic lock-free data structures with safe memory reclamation." Filed on 3 December 2002.
  • Maged Michael. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects (PDF). IEEE Transactions on Parallel and Distributed Systems. 2004, 15 (8): 491–504 [2020-01-17]. Bibcode:10.1.1.130.8984 请检查|bibcode=值 (帮助). doi:10.1109/TPDS.2004.8. （原始内容 (PDF)于2017-05-06）. 

外部链接

  • 并发构建块 （页面存档备份，存于互联网档案馆） -冒险指针（称为“ SMR”）和其他无锁数据结构的C ++实现。 还有Java接口。
  • 并发工具包 （页面存档备份，存于互联网档案馆） -冒险指针和无锁数据结构的C实现
  • Atomic Ptr Plus （页面存档备份，存于互联网档案馆） - 具有冒险指针实现的C / C ++库
  • 并行转换和C++的内存模型 （页面存档备份，存于互联网档案馆） -附录中包含Windows的下的C++实现
  • libcds （页面存档备份，存于互联网档案馆） - 无锁容器和冒险指针实现的C++库

行進 15, 2023
冒险指针, 在多线程环境中, 是一种解决由无锁, 数据结构中的节点动态内存管理引起的问题的方法, 这些问题通常仅在没有自动垃圾收集的环境中出现, 使用比较和交换原语的任何无锁数据结构都必须处理aba问题, 例如, 在使用链表实现的无锁堆栈中, 一个线程可能正在尝试从堆栈的前面弹出项目, 它会记住自栈顶而下的第二个值, 然后执行, span, class, compare, swap, span, span, class, span, span, class, target, span, span, class, s. 在多线程环境中 冒险指针是一种解决由无锁 数据结构中的节点动态内存管理引起的问题的方法 这些问题通常仅在没有自动垃圾收集的环境中出现 1 使用比较和交换原语的任何无锁数据结构都必须处理ABA问题 例如 在使用链表实现的无锁堆栈中 一个线程可能正在尝试从堆栈的前面弹出项目 A B C 它会记住自栈顶而下的第二个值 B 然后执行 span class n compare and swap span span class p span span class n target span span class o amp span span class n head span span class p span span class w span span class n newvalue span span class o span span class n B span span class p span span class w span span class n expected span span class o span span class n A span span class p span span class w span 不幸的是 在此操作正在执行时 另一个线程可能执行了两次弹出操作 然后将A推回顶部 从而导致堆栈 A C 比较并交换成功将 head 与 B 交换 结果是堆栈现在包含垃圾数据 指向已经被释放的元素 B 的指针 此外 任何包含以下形式代码的无锁算法Node currentNode this gt head assume the load from this gt head is atomic Node nextNode currentNode gt next assume this load is also atomic在没有自动垃圾收集的情况下 它还面临另一个主要问题 在这两行之间 另一个线程可能会弹出this gt head指向的节点并对其进行内存分配 这意味着通过第二行上的currentNode进行的内存访问读取了已释放的内存 实际上可能已经被另外一部分程序用在了不同的地方 冒险指针可用于同时解决这两个问题 在使用冒险指针的系统中 每个线程都保留一个冒险指针的列表 这些指针指示该线程当前正在访问的节点 在许多系统中 此 列表 可能只限于一个 1 2 或两个元素 冒险指针列表上的节点不得被任何其他线程修改或释放 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 2 当线程希望删除一个节点时 它将其放置在 稍后释放 的节点列表上 但实际上直到其他线程的危险列表中没有包含指针时才真正释放该节点的内存 可以通过专用的垃圾回收线程来完成此手动垃圾回收 如果所有线程共享 稍后释放 的列表 或者 可以由每个工作线程自行清除 待释放 列表 作为诸如 pop 之类的操作的一部分 在这种情况下 每个工作线程可以负责其自己的 待释放 列表 在2002年 IBM的 Maged Michael提出了关于冒险指针技术的美国专利申请 3 但该申请在2010年被放弃 冒险指针的替代方法包括引用计数 1 参见 编辑并发数据结构 冒险 计算机体系结构 参考文献 编辑 1 0 1 1 1 2 Anthony Williams C Concurrency in Action Practical Multithreading Manning Shelter Island 2012 See particularly Chapter 7 2 Examples of lock free data structures 2 0 2 1 Andrei Alexandrescu and Maged Michael Lock Free Data Structures with Hazard Pointers Dr Dobb s 2004 2020 01 17 原始内容存档于2019 07 19 US application 20040107227 Maged M Michael Method for efficient implementation of dynamic lock free data structures with safe memory reclamation Filed on 3 December 2002 Maged Michael Hazard Pointers Safe Memory Reclamation for Lock Free Objects PDF IEEE Transactions on Parallel and Distributed Systems 2004 15 8 491 504 2020 01 17 Bibcode 10 1 1 130 8984 请检查 bibcode 值 帮助 doi 10 1109 TPDS 2004 8 原始内容存档 PDF 于2017 05 06 外部链接 编辑并发构建块 页面存档备份 存于互联网档案馆 冒险指针 称为 SMR 和其他无锁数据结构的C 实现 还有Java接口 并发工具包 页面存档备份 存于互联网档案馆 冒险指针和无锁数据结构的C实现 Atomic Ptr Plus 页面存档备份 存于互联网档案馆 具有冒险指针实现的C C 库 并行转换和C 的内存模型 页面存档备份 存于互联网档案馆 附录中包含Windows的下的C 实现 libcds 页面存档备份 存于互联网档案馆 无锁容器和冒险指针实现的C 库 取自 https zh wikipedia org w index php title 冒险指针 amp oldid 63338652, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。