冒险指针 在多线程环境中 冒险指针是一种解决由无锁 数据结构中的节点动态内存管理引起的问题的方法 这些问题通常仅在没有自动垃圾收集的环境中出现 使用比较和交换原语的任何无锁数据结构都必须处理ABA问题 例如在使用链表实现的无锁堆栈中一个线程可能正在尝试从堆栈的前面弹出项目ABC 它会记住自栈顶而下的第二个值B然后执行 compareandswaptargethead newvalueB expectedA 不幸的是在此操作正在执行时另一个线程可能执行了两次弹出操作然后将A推回顶部从而导致堆栈AC 比较并交换成功将 head与 B交换结果是堆栈现在包含垃圾数据指向已经被释放的元素 B的指针 此外任何包含以下形式代码的无锁算法 Node currentNode  thishead  assume the load from thishead is atomic Node nextNode  currentNodenext  assume this load is also atomic 在没有自动垃圾收集的情况下它还面临另一个主要问题 在这两行之间另一个线程可能会弹出thishead指向的节点并对其进行内存分配这意味着通过第二行上的currentNode进行的内存访问读取了已释放的内存实际上可能已经被另外一部分程序用在了不同的地方 冒险指针可用于同时解决这两个问题 在使用冒险指针的系统中每个线程都保留一个冒险指针的列表 这些指针指示该线程当前正在访问的节点 在许多系统中此列表可能只限于一个 或两个元素 冒险指针列表上的节点不得被任何其他线程修改或释放 Each reader thread owns a singlewritermultireader 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 dont change its contents and certainly keep your deleteing hands off it Andrei Alexandrescu and Maged MichaelLockFree Data Structures with Hazard Pointers 当线程希望删除一个节点时它将其放置在稍后释放的节点列表上但实际上直到其他线程的危险列表中没有包含指针时才真正释放该节点的内存 可以通过专用的垃圾回收线程来完成此手动垃圾回收如果所有线程共享稍后释放的列表或者可以由每个工作线程自行清除待释放列表作为诸如 pop之类的操作的一部分在这种情况下每个工作线程可以负责其自己的待释放列表 在年 IBM的 Maged Michael提出了关于冒险指针技术的美国专利申请 但该申请在年被放弃 冒险指针的替代方法包括引用计数