多线程 – 具有危险指针的无锁存储器回收

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年所指出的那样,删除是一个两阶段的操作：首先你必须“取消发布”节点,从数据结构中删除它,使其不能再从公共接口访问.

在这一点上,迈克尔的术语可能会删除节点.并发线程访问它是不再安全的(除非他们已经持有一个危险指针).

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

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

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之后发生抢占,则访问线程访问节点甚至是安全的(因为存在指向节点的危险指针),但由于访问线程不可能区分这种情况下,它必须虚假地失败.

重要的一点是,如果一个节点没有被删除,那么它只会被访问.