试图写一个无锁的单链表,删除麻烦

Question

我正在尝试编写一个无锁的单链表.最终的一致性不是问题(有人遍历可能包含不正确项目的列表).

我认为我得到了正确的添加项目(循环和Interlocked.CompareExchange).

但我无法弄清楚如何删除节点(列表中的任何位置),因为我必须得到前一个项目并将它们的Next字段设置为当前节点Next字段.

class Node
{
    Node Next;
    object Value;
}

class SinglyLinkedList
{
    Root _root;

    public void Add(object value)
    {}

    public void Remove(object value)
    {}
}

即

a - > b - > c

至

a - > c

伪代码:

Node prev;
Node node = _root;
while (node.Value != nodeValue)
{
  prev = node;
  node = node.Next;
}
prev.Next = node.Next;

我如何使这成为一个原子操作(即确保prev.Next = node.Next调用没有next或prev被另一个线程删除)？

我可以使用ReaderWriterLockSlim,但我发现这个问题很有趣,因为我知道存在无锁链表.

我的担忧:

如果当前线程在循环和赋值之间挂起,则会发生以下情况:

• prev 本身可能已被另一个线程删除.
• node 可能已被另一个线程删除.
• Node.Next 可能已被删除

Answer 1

是的,添加是一个简单的两步循环,CAS在前一个.Next指针上; 但删除很难!

实际上,如果不使用额外的信息和逻辑,你就无法做到.

Harris通过添加一个标记位来创建解决此问题的方法,该标记位曾禁止任何人修改节点.删除变为两步:首先(CAS)标记已删除的节点以防止任何人更改它(尤其是其.Next指针); 第二个CAS是前一个节点.下一个指针,现在是安全的,因为另一个节点已被标记.

问题是现在在C Harris中使用.Next指针的两个最低有效位作为标记.这很聪明,因为对于4字节对齐的指针,它们总是未被使用(即00),并且因为它们适合32位指针,所以它们可以原子地与指针本身一起使用CAS,这是该算法的关键.当然,这在C#中是不可能的,至少在不使用不安全代码的情况下.

解决方案稍微复杂一些,并涉及对包含两个字段(.Next + marker)的不可变类的额外引用.

我没有对这些想法进行冗长的解释,而是在互联网上找到了一些将引用您需要的所有细节的参考资料,请参阅:

无锁链接列表(第1部分)解释了问题;

无锁链接列表(第2部分)解释C解决方案+自旋锁解决方案;

无锁链接列表(第3部分)解释不可变状态引用;

如果您对该主题非常好奇,那么学术论文会提供各种解决方案并对其性能进行分析,例如:无锁链接列表和跳过列表