c# - 尝试编写无锁单链表，删除麻烦

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

是的，添加是一个简单的两步循环，在前一个 .Next 指针上使用 CAS；但是移除很难!

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

Harris 通过添加一个标记位创建了这个问题的解决方案，该标记位一旦设置就不允许任何人修改该节点。删除分为两步:首先(CAS)标记已删除的节点以防止任何人更改它(尤其是其 .Next 指针)；第二个 CAS 前一个节点。下一个指针，现在是安全的，因为另一个节点已被标记。

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

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

我没有对这些想法进行冗长的解释，而是在 Internet 上找到了一些引用资料，它们将详细介绍您需要的所有细节，请参阅:

Lock-free Linked List (Part 1)解释问题；

Lock-free Linked List (Part 2)讲解C方案+自旋锁方案；

Lock-free Linked List (Part 3)解释不可变状态引用；

如果您真的对这个话题很好奇，可以找到包含各种解决方案及其性能分析的学术论文，例如这个:Lock-free linked lists and skip lists