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