带危险指针的无锁内存回收 [英] Lock-free memory reclamation with hazard pointers

问题描述

危险指针是一种无需垃圾收集即可安全地释放无锁代码中的内存的技术.

Hazard pointers are a technique for safely reclaiming memory in lock-free code without garbage-collection.

这个想法是，在访问可以同时删除的对象之前，线程将其危险指针设置为指向该对象.想要删除对象的线程将首先检查是否有任何危害指针设置为指向该对象.如果是这样，将推迟删除操作，以使访问线程最终不会读取已删除的数据.

The idea is that before accessing an object that can be deleted concurrently, a thread sets its hazard pointer to point to that object. A thread that wants to delete an object will first check whether any hazard pointers are set to point to that object. If so, deletion will be postponed, so that the accessing thread does not end up reading deleted data.

现在，想象一下我们的删除线程开始迭代危险指针列表，并且在i+1元素处它被抢占.现在，另一个线程在i处将危险指针设置为正在删除的线程正在尝试删除的对象.之后，即使现在位置i上有一个指向该对象的危险指针，删除线程也会继续进行，检查列表的其余部分，然后删除该对象.

Now, imagine our deleting thread starts to iterate the list of hazard pointers and at the i+1 element it gets preempted. Now another thread sets the hazard pointer at i to the object that the deleting thread is currently trying to delete. Afterwards, the deleting thread resumes, checks the rest of the list, and deletes the object, even though there is now a hazard pointer at position i pointing to the object.

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

So clearly just setting the hazard pointer is not enough, as a deleting thread might already have checked our hazard pointer and decided that our thread does not want to access the object. How can I make sure, after setting a hazard pointer, that the object I'm trying to access won't be deleted from under my hands?

推荐答案

权威性答案

Maged M. Michael的原始论文使用危险指针对算法施加了重要限制:

The Authoritative Answer

The original paper by Maged M. Michael places this important restriction on algorithms using hazard pointers:

该方法需要无锁算法，以确保没有 线程可以在可能被删除的时候访问动态节点 从物体上移开，除非至少有一个与线程相关的危险 从 该节点保证可以从对象的根开始访问.这 方法论防止连续释放任何退休的节点 由一个或多个线程的一个或多个危险指针指向 删除之前的一个点.

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的答案中指出，删除操作分为两个阶段:首先，您必须取消发布"节点，请将其从数据结构中删除，以便不再可以从公共接口访问它.

What it means for the deleting thread

As pointed out in Anton's answer, deletion is a two-phase operation: First you have to 'unpublish' the node, remove it from the data structure so that it can no longer be accessed from the public interface.

这时，按照迈克尔的说法，该节点已可能被移除.并发线程访问它不再是安全的(除非它们已经在整个过程中一直持有指向它的危险指针).

At this point, the node is possibly removed, in Michael's terms. It is no longer safe for concurrent threads to access it (unless they already have been holding a hazard pointer to it throughout).

因此，一旦可能删除节点，删除线程就可以遍历危险指针列表.即使删除线程被抢占，并发线程也可能无法再访问该节点.在确认没有为节点设置危害指针之后，删除线程可以安全地进行到删除的第二阶段:实际释放.

Thus, once a node is possibly removed, it is safe for the deleting thread to iterate the list of hazard pointers. Even if the deleting thread gets preempted, a concurrent thread may not access the node anymore. After verifying that no hazard pointers are set to the node, the deleting thread can safely proceed to the second phase of deletion: The actual deallocation.

总而言之，删除线程的操作顺序为

In summary, the order of operations for the deleting thread is

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.

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

The real algorithm is slightly more involved, as we need to maintain a list of those nodes that cannot be reclaimed and ensure that they get deleted eventually. This has been skipped here, as it is not relevant to explain the issue raised in the question.

设置危险指针不足以保证对其进行安全访问.毕竟，当我们设置危险指针时，该节点可能已被删除.

Setting the hazard pointer is not enough to guarantee safe access to it. After all, the node might be possibly removed by the time we set our hazard pointer.

确保安全访问的唯一方法是，从保证从对象的根开始可以到达该节点起，我们就可以确保危害指针一直指向该节点.

The only way to ensure safe access is if we can guarantee that our hazard pointer has been pointing to that node continuously, from a time when the node was guaranteed to be reachable from the object’s roots.

由于该代码应该是无锁的，所以只有一种方法可以实现此目的:我们乐观地将危险指针设置为该节点，然后检查该节点是否已标记为可能已删除(即， 之后.

Since the code is supposed to be lock-free, there is only one way to achieve this: We optimistically set our hazard pointer to the node and then check whether that node has been marked as possibly deleted (that is, it is no longer reachable from the public root) afterwards.

因此，访问线程的操作顺序为

Thus the order of operations for the accessing thread is

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).

Potential Races affecting the deleting thread

After a node has been possibly removed (D-1), the deleting thread could be preempted. Thus it is still possible for concurrent threads to optimistically set their hazard pointer to it (even though they are not allowed to access it) (A-2).

因此，即使其他线程都不再访问该节点，删除线程也可能检测到虚假危害，阻止其立即删除该节点.这只会像合法危险那样简单地延迟节点的删除.

Therefore, the deleting thread might detect a spurious hazard, preventing it from deleting the node right away, even though none of the other threads will access the node anymore. This will simply delay deletion of the node in the same way a legitimate hazard would.

重要的一点是该节点最终仍将被删除.

The important point is that the node will still be deleted eventually.

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

An accessing thread may get preempted by a deleting thread before verifying that the node has not been potentially removed (A-3). In such a case, it is no longer allowed to access the object.

请注意，如果抢占发生在A-2之后，则访问线程甚至可以安全地访问该节点(因为始终有指向该节点的危险指针)，但是由于不可能进行访问线程来区分这种情况，它必须是虚假的失败.

Note that in case the preemption occurs after A-2, it would even be safe for the accessing thread to access the node (since there was a hazard pointer pointing to the node throughout), but since it is impossible for the accessing thread to distinguish this case, it must fail spuriously.

重要的一点是，只有在未删除节点的情况下，该节点才会被访问.

The important point is that a node will only ever be accessed if it has not been deleted.

这篇关于带危险指针的无锁内存回收的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！