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

Question

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

我认为add项是正确的(循环和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被调用没有下一个或之前被另一个线程之间删除)?

我可以用ReaderWriterLockSlim代替，但我发现这个问题很有趣，因为我知道存在无锁链表。

我的担忧:

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

• prev本身可能已被另一个线程删除。
• node可能已经被其他线程删除了。
• Node.Next可能已被删除

Answer 1

是的，添加一个简单的两步循环，CAS在前一个。next指针上;但是移除是很难的!

实际上，如果不使用额外的信息和逻辑，你就无法做到这一点。

Harris通过添加一个标记位来解决这个问题，一旦设置，任何人都不允许修改节点。删除分为两步:首先(CAS)标记被删除的节点，以防止任何人更改它(特别是它的.Next指针);第二个CAS前一个节点。next指针，现在是安全的，因为另一个节点已被标记。

现在的问题是，在C中，哈里斯使用。next指针的两个最低有效位作为标记。这很聪明，因为对于4字节对齐的指针，它们总是未使用(即00)，并且因为它们适合32位指针，它们可以与指针本身自动地CAS，这是该算法的关键。当然，这在c#中是不可能的，至少在不使用不安全代码的情况下。

解决方案变得有点复杂，并且涉及到对包含两个字段的不可变类的额外引用。下一个+标记)

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

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

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

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

如果你真的对这个话题很好奇，有学术论文提供了各种解决方案和性能分析，例如:无锁链表和跳跃表