带有危险指针的无锁内存回收

Question

危险指针是一种在没有垃圾收集的情况下以无锁代码安全回收内存的技术.

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

现在,假设我们的删除线程开始迭代危险指针列表,并在i+1元素上被抢占.现在,另一个线程将危险指针设置为i删除线程当前正在尝试删除的对象.然后,删除线程恢复,检查列表的其余部分,并删除对象,即使现在在i指向对象的位置存在危险指针.

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

Answer 1

权威答案

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

该方法需要无锁算法,以保证在可能从对象中移除动态节点时,没有线程可以访问动态节点,除非至少有一个线程的相关危险指针从一个时间开始连续指向该节点当保证节点可以从对象的根目录到达时.该方法防止一个或多个线程的一个或多个危险指针从其移除之前的点连续指向的任何退役节点的释放.

这对删除线程意味着什么

正如Anton的回答所指出的,删除操作是一个两阶段操作:首先,您必须"取消发布"该节点,将其从数据结构中删除,以便无法再从公共接口访问它.

此时,用迈克尔的术语可能删除节点.并发线程访问它不再安全(除非它们已经持有危险指针).

因此,一旦可能删除节点,删除线程就可以安全地迭代危险指针列表.即使删除线程被抢占,并发线程也可能不再访问该节点.在验证没有为节点设置危险指针后,删除线程可以安全地进入第二阶段的删除:实际的解除分配.

总之,删除线程的操作顺序是

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.

真正的算法稍微复杂一些,因为我们需要维护那些无法回收的节点列表,并确保它们最终被删除.这里已经忽略了这一点,因为它与解释问题中提出的问题无关.

对访问线程意味着什么

设置危险指针不足以保证安全访问它.毕竟,在我们设置危险指针时可能会删除节点.

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

由于代码应该是无锁的,因此只有一种方法可以实现:我们乐观地设置我们的危险指针到节点,然后检查该节点是否已被标记为可能被删除(即,它不再可达从公共根)之后.

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

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,访问线程访问节点甚至是安全的(因为危险指针始终指向节点),但由于访问线程无法区分这种情况,它必须虚假地失败.

重要的一点是,如果节点尚未被删除,则只能访问该节点.