c - 使用危险指针遍历列表

Question

我正在使用 Hazard pointer 来实现 C 中的无锁链表。 除了 vary basics queues 和 stacks 之外，我找不到任何示例代码。 问题是我需要遍历列表，所以我的问题是我是否可以在分配后更改风险指针的值。 例如:

t←Top
while(true) {
    if t=null then
        return null
    *hp←t
    if Top!=t then
        continue
    ...
    t←(t→next) //after this instruction pointer t will be still protected?
}

Answer 1

最后，我根据 the original paper 结束了自己版本的危险指示器 (HP) 的实现.我的问题的答案是否定的，t 不再可以安全使用。原因是，根据 HP 的工作方式，*hp 正在保护 t 指向的节点，当您将它声明为危险指针时，所以当 t 移动到下一个节点，HP机制一直保护前一个节点。在我可以安全地使用它之前，我必须将新值重新分配给 *hp。

另外，在论文的例子中，它不是显式的，但是当你用完一个危险指针时，你必须释放它。这意味着，将 *hp 返回到其原始状态 (NULL)。这样，如果另一个线程想要删除(退出)这个节点，它就不会被视为正在使用。

在我上面的示例中，我必须在离开方法之前释放 *hp。在循环中没有必要，因为我正在覆盖相同的 *hp 位置 (*hp ← t)，因此前一个节点不再受到保护。