16

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

我认为我得到了正确的添加项目（循环和Interlocked.CompareExchange）。

但是我不知道如何删除节点（列表中的任何位置），因为我必须获取上一个项目，并且他们将其Next字段设置为当前节点Next字段。

class Node
{
    Node Next;
    object Value;
}

class SinglyLinkedList
{
    Root _root;

    public void Add(object value)
    {}

    public void Remove(object value)
    {}
}

IE

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可能已被删除
4

1 回答 1

24

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

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

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

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

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

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

无锁链表（第 1 部分）解释问题；

无锁链表（二）讲解C方案+自旋锁方案；

无锁链表（第 3 部分）解释不可变状态引用；

如果您真的对该主题感到好奇，这里有各种解决方案及其性能分析的学术论文，例如：无锁链表和跳过列表

于 2013-06-03T17:07:52.433 回答