为什么将变量声明为 volatile 并同时对其使用 Interlocked？

Question

我正在阅读 Joe Duffy 的 Concurrent Programming on Windows。在“Memory Models and Lock Freedom”一章的最后，他给出了一个无锁栈的例子。我浏览了代码，但有一件事我不明白，那就是需要将 m_next 字段标记为 volatile。因为 Interlocked.CompareExchange 有一个完整的内存屏障，对吗？有人有想法吗？

我已经在下面粘贴了示例代码。

class LockFreeStack<T>
{
    class Node
    {
        internal T m_value;
        internal volatile Node m_next;
    }

    volatile Node m_head;

    void Push(T value)
    {
        Node n = new Node();
        n.m_value = value;

        Node h;
        do
        {
            h = m_head;
            n.m_next = h;
        }
        while (Interlocked.CompareExchange(ref m_head, n, h) != h);
    }

    T Pop()
    {
        Node n;
        do
        {
            n = m_head;
            if (n == null) throw new Exception('stack empty');

        }
        while (Interlocked.CompareExchange(ref m_head, n.m_next, n) != n);

        return n.m_value;
    }
}

Answer 1

我会给我两分钱，但不能 100% 确定我要说的是正确的。 Joe Duffy 是世界级的class 多线程专家，但我认为在这个实现中他对 LockFreeStack<T> [=46] 的内部状态的跨线程可见性过于谨慎=]. Node.m_next 字段的波动性在我看来是多余的。 Node 个实例是可变的，但它们仅在在链接到内部链表之前发生了变化。在那个阶段之后，它们实际上是不可变的。该可变阶段由单个线程执行，因此另一个线程不可能看到 Node 实例的陈旧版本。

这只剩下指令重新排序的可能性，作为将 Node.m_next 声明为 volatile 的原因。由于 n.m_next = h; 赋值夹在读取另一个可变字段 (m_head) 和一个 Interlocked.CompareExchange 操作之间，我会假设可能重新已经阻止了会损害实现正确性的指令排序，但正如我所说，我不是 100% 确定。

我很确定 LockFreeStack<T> class 的实现可以在性能方面得到改进，但代价是通过使 Node 变得不可变class。现在（C# 9）这可以简单地通过从类型 class 切换到类型 record 来实现。这是这样一个实现的样子：

class LockFreeStack<T>
{
    record Node(T Value, Node Next) { }

    Node _head;

    void Push(T value)
    {
        Node h = Volatile.Read(ref _head);
        while (true)
        {
            Node n = new Node(value, h);
            var original = Interlocked.CompareExchange(ref _head, n, h);
            if (original == h) break;
            h = original;
        }
    }

    T Pop()
    {
        Node h = Volatile.Read(ref _head);
        while (true)
        {
            if (h == null) throw new Exception("Stack empty");
            var original = Interlocked.CompareExchange(ref _head, h.Next, h);
            if (original == h) break;
            h = original;
        }
        return h.Value;
    }
}

请注意，每次 Push 或 Pop 操作只会产生一次波动成本。人们甚至可以争辩说 Volatile.Read of the _head field could be omitted altogether, since a possible stale _head value would be corrected anyway by the first Interlocked.CompareExchange 操作只花费了 while (true) 循环的额外迭代。

为什么将变量声明为 volatile 并同时对其使用 Interlocked？

Why declare a variable as volatile and use Interlocked on it at the same time?

c#

concurrency

multithreading

volatile

interlocked