过度使用Interlocked.exchange？

Question

我正在尝试理解Interlocked.Exchange的正确用法，所以我实现了一个具有添加和删除功能的简单排序LinkedList。

如果这不是一个threadsafe列表，显然是为了找到插入点，你应该有类似下面这样的东西来找到正确的插入点，然后插入新节点。

    public void Insert(int newValue)
    {
        var prev = _header;
        Node curr = _header.Next;

        while(curr != null && curr.value > newValue )
        {
            prev = curr;
            curr = curr.Next;
        }
        var newNode = new Node(newValue, curr);
        prev.Next = newNode;
    }

下面是我对并发列表必须这样做的看法。是不是有太多的内部锁定。交换正在进行？没有这个，插件还会是threadsafe吗？成百上千的互锁操作会导致糟糕的性能吗？

    public void InsertAsync(int newValue)
    {
        var prev = _header;
        Node curr = new Node(0, null);
        Interlocked.Exchange(ref curr, _header.Next);

        while (curr != null && curr.value > newValue)
        {
            prev = Interlocked.Exchange(ref curr, curr.Next);
        }
        //need some locking around prev.next first, ensure not modified/deleted, etc..
        //not in the scope of this question.
        var newNode = new Node(newValue, prev.Next);
        prev.Next = newNode;
    }

例如，我知道curr = curr.next是原子读取，但是我能确定某个特定的线程将读取curr.next的最新值，而不会发生互锁吗？

Answer 1

使用Interlocked方法可以做两件事：

，

1. ，它执行一系列通常不是原子的操作，并使它们有效地原子。在Exchange的情况下，你做的等同于：var temp = first; first=second; return temp;，但在你这样做的时候，没有任何一个变量被另一个线程修改的风险。
2. ，它引入了一个内存屏障。编译器、运行时和/或硬件优化可能会导致不同的线程拥有一个本地“副本”，该值在技术上位于共享内存中(通常是缓存变量的结果)。这可能导致一个线程需要很长时间才能“看到”另一个线程的写入结果。内存屏障本质上同步了同一变量的所有这些不同版本。

所以，具体到你的代码上。你的第二个解决方案实际上不是线程安全的。每个单独的Interlocked操作都是原子的，但是对各种Interlocked调用的任意数量的调用都不是原子的。考虑到您的方法所做的一切，您的临界区实际上要大得多；您需要使用lock或另一个类似的机制(即信号量或监视器)来限制对代码段的访问仅限于单个线程。在您的特定情况下，我会认为整个方法都是一个关键部分。如果你真的非常小心，你可能会有几个较小的临界块，但很难确保没有可能的竞争条件的结果。

至于性能，嗯，因为代码不能工作，所以性能无关紧要。

Answer 2

只需使用普通的老式显示器即可。如果这仅仅是出于兴趣，那么您需要对无锁算法进行一些研究。

为了更直接地回答您的问题，互锁操作的成本取决于变量争用的数量。在无争用的情况下(例如，单线程)，开销非常小。随着并发访问数量的增加，成本也会增加。原因是互锁操作并不是真正的无锁操作。它只是简单地使用硬件锁而不是软件锁。出于这个原因，无锁算法通常不会像您直观地期望的那样执行得很好。

Answer 3

您只是在保护赋值，但它们无论如何都是原子的。你应该检查交换是否真的成功了。

但这仍然不会使列表成为线程安全的，并发线程可能会在插入点之前插入一个比newValue大的新值。我认为这份清单甚至可能最终被打破。