使用风险指针遍历链表

Question

我正在使用Hazard指针来实现C语言中的无锁链表。除了非常基本的队列和栈之外，我没有找到任何其他示例代码。 问题是我需要遍历链表，所以我的问题是：一旦分配了危险指针，我是否可以更改其值。 例如：

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?
}

- ees_cu

---

http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf 可能会对你有所帮助。 - Alexander Oh

Answer 1

最终，我按照原论文的方法实现了自己的Hazard Pointers（HP）版本。我的问题的答案是否定的，t不再安全使用。原因是，HP机制保护了声明为危险指针时被指向的节点的*hp，因此当t移动到下一个节点时，HP机制仍然保护前一个节点。在安全使用之前，我必须重新分配新值给*hp。

此外，在论文的示例中，虽然没有明确说明，但当你完成使用危险指针时，必须释放它。也就是说，将*hp返回到其原始状态（NULL）。这样，如果另一个线程想要删除（退役）这个节点，它不会被视为正在使用。

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

- ees_cu

Answer 2

当您仅遍历列表时，无需使用危险指针。危险情况发生在不同的线程从同一资源读取和写入时（特别是，危险指针用于克服ABA问题，即资源的值更改为某些值，然后再次更改回其原始值，这使得注意到更改变得困难）。遍历时，您只是读取，因此不需要危险指针。

顺便说一下，我认为您必须将if Top=t更改为if Top!=t，以便在没有危险情况的情况下继续执行代码。请注意，continue返回循环的开头。此外，您的整个代码应该在一个while(true)循环中。

您可以在此处http://www.drdobbs.com/lock-free-data-structures-with-hazard-po/184401890阅读有关危险指针的更多信息，或者通过谷歌搜索！

编辑 你需要提供插入和删除函数的代码。简而言之，你提到的代码部分在执行t←(t→next)后会变成一个无限循环，因为Top！=t之后仍然成立。 你需要做的是，不要将t与Top进行比较，而是将其与先前捕获的值进行比较。同样，这取决于您实现其他方法的方式，但您可能希望实现类似于Tim Harris算法的东西，它使用两个阶段的删除（1-标记和2-释放节点）。然后，在遍历列表时，您需要检查标记节点。还有一个双向链表的实现，其中包含一个查找方法，您可以将其用作实现的基础，在http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf的第9图中。希望这可以帮助到你。

- Ali Alavi

---

谢谢@Lazarus。显然这只是问题的一小部分。这可能是数据结构中的contain()函数，其中我们还有一个insert()和一个remove()可能会同时执行。你对循环的看法是正确的，我会在问题中包含它。 - ees_cu