锁定空闲列表删除操作

Question

我有以下问题定义：

设计一个无锁简单链表，操作如下：

Add(item): 将节点添加到列表的开头（头部）
Remove(item): 从列表中删除给定的项目

下面显示了到目前为止实现的代码：

public class List<T>
{
    private readonly T _sentinel;
    private readonly Node<T> _head;

    public List()
    {
        _head = new Node<T>();
        _sentinel = default(T);
    }

    public List(T item)
    {
        _head = new Node<T>(item);
        _sentinel = item;
    }

    public void Add(T item)
    {
        Node<T> node = new Node<T>(item);

        do
        {
            node.Next = _head.Next;
        }
        while (!Atomic.CAS(ref _head.Next, node.Next, node));
    }

    public void Remove(Node<T> item)
    {
        Node<T> next;
        Node<T> oldItem = item;  

        if (item.Value.Equals(_sentinel))
            return;

        item.Value = _sentinel;

        do
        {
            next = item.Next;

            if (next == null)
            {
                Atomic.CAS(ref item.Next, null, null);
                return;
            }

        } while (!Atomic.CAS(ref item.Next, next, next.Next));

        item.Value = next.Value;
    }
}

头部实际上是为了便于使用而保留的虚拟（哨兵）节点。实用头其实是_head.Next。问题出在尝试删除列表的最后一个元素时的删除操作上：

remove部分有两种情况：

该节点有一个非空的next指针：然后进行CAS操作并窃取下一项的值数据实际上删除了下一项
有问题的情况是要删除的元素是列表中的最后一个元素：
- 以原子方式执行：If (item == oldItem and item.Next == null) then item = null where oldItem is a pointer to the item to remove;

所以我想做的是在去掉C节点的情况下：

if(C==old-C-reference and C.Next == null) then C = null => all原子地

问题是我只有一个对象有 CAS。我怎样才能原子地解决这个问题？或者有没有更好的方法来执行我在这里遗漏的删除操作？

Answer 1

when removing B we do a trick by copying C's contents to B and removing C: B.Next = C.Next (in the loop) and B.Value = C.Value after the move succeeded

所以你需要原子地修改两个内存位置。 .NET 中的 CAS 不支持。但是，您可以将这两个值包装在另一个可以自动换出的对象中：

class ValuePlusNext<T> {
 T Value;
 Node<T> Next;
}

class Node<T> {
 ValuePlusNext<T> Value;
}

现在您可以在一个原子操作中写入两个值。 CAS(ref Value, new ValuePlusNext<T>(next.Value, next.Value.Next)。诸如此类。

奇怪的是，ValuePlusNext 与您的旧节点 class 具有相同的结构。从某种意义上说，您现在正在为每个逻辑节点管理两个物理链表节点。

while (true) {
 var old = item.Value;
 var new = new ValuePlusNext(...);
 if (CAS(ref Value, old, new)) break;
}

锁定空闲列表删除操作

Lock free list remove operation

concurrency

multithreading

synchronization

locking

lock-free