multithreading - 使用危险指针的无锁内存回收

Question

Hazard pointers是一种在无垃圾收集的情况下在无锁代码中安全回收内存的技术。

这个想法是，在访问一个可以并发删除的对象之前，一个线程设置它的冒险指针指向那个对象。想要删除对象的线程将首先检查是否设置了任何冒险指针指向该对象。如果是这样，删除将被推迟，这样访问线程就不会以读取已删除的数据而告终。

现在，假设我们的删除线程开始迭代危险指针列表，并在 i+1 元素处被抢占。现在，另一个线程将 i 处的风险指针设置为删除线程当前试图删除的对象。之后，删除线程恢复，检查列表的其余部分，并删除该对象，即使现在在位置 i 处有一个指向该对象的冒险指针。

很明显，仅仅设置危险指针是不够的，因为删除线程可能已经检查了我们的危险指针并决定我们的线程不想访问该对象。我如何确保在设置危险指针后，我尝试访问的对象不会从我手中删除？

Answer 1

权威答案

original paper by Maged M. Michael对使用危险指针的算法施加了这一重要限制:

The methodology requires lock-free algorithms to guarantee that no thread can access a dynamic node at a time when it is possibly removed from the object, unless at least one of the thread’s associated hazard pointers has been pointing to that node continuously, from a time when the node was guaranteed to be reachable from the object’s roots. The methodology prevents the freeing of any retired node continuously pointed to by one or more hazard pointers of one or more threads from a point prior to its removal.

删除线程意味着什么

正如 Anton's answer 中指出的那样, 删除是一个两阶段操作:首先你必须“取消发布”节点，将它从数据结构中删除，这样它就不能再从公共(public)接口(interface)访问。

此时，按照 Michael 的说法，节点可能被移除。并发线程访问它不再安全(除非它们一直持有指向它的危险指针)。

因此，一旦一个节点可能被删除，删除线程迭代风险指针列表是安全的。即使删除线程被抢占，并发线程也可能不再访问该节点。在验证没有风险指针被设置到节点之后，删除线程可以安全地进行到删除的第二阶段:实际的释放。

综上所述，删除线程的操作顺序是

D-1. Remove the node from the data structure.
D-2. Iterate the list of hazard pointers.
D-3. If no hazards were found, delete the node.

真正的算法稍微复杂一些，因为我们需要维护一个无法回收的节点列表，并确保它们最终被删除。这已被跳过，因为它与解释问题中提出的问题无关。

访问线程的意义

设置危险指针不足以保证安全访问它。毕竟，当我们设置风险指针时，该节点可能已被删除。

确保安全访问的唯一方法是，如果我们能够保证我们的风险指针一直指向该节点，从保证可以从对象的根访问该节点。

由于代码应该是无锁的，只有一种方法可以实现这一点:我们乐观地将风险指针设置为节点，然后检查该节点是否已被标记为可能已删除(即，它是不再可以从公共(public)根访问)之后。

因此访问线程的操作顺序是

A-1. Obtain a pointer to the node by traversing the data structure.
A-2. Set the hazard pointer to point to the node.
A-3. Check that the node is still part of the data structure.
     That is, it has not been possibly removed in the meantime.
A-4. If the node is still valid, access it.

影响删除线程的潜在竞争

在一个节点可能被删除后(D-1)，删除线程可能被抢占。因此，并发线程仍然可以乐观地将它们的危险指针设置为它(即使不允许它们访问它)(A-2)。

因此，删除线程可能会检测到虚假危险，从而阻止它立即删除该节点，即使其他线程都不会再访问该节点。这将以与合法危险相同的方式简单地延迟节点的删除。

重点是节点最终还是会被删除

影响访问线程的潜在竞争

在验证节点未被潜在删除之前，访问线程可能会被删除线程抢占 (A-3)。在这种情况下，不再允许访问该对象。

请注意，如果抢占发生在 A-2 之后，访问线程访问该节点甚至是安全的(因为自始至终都有一个指向该节点的风险指针)，但是由于访问线程无法区分这种情况，因此它一定会虚假地失败。

重要的一点是一个节点只有在它没有被删除的情况下才会被访问。