1

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

如果这不是线程安全列表，显然要找到插入点，您将有类似下面的内容来找到插入新节点的正确点。

    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;
    }

以下是我对您必须如何为并发列表执行此操作的看法。是否有太多 Interlocked.Exchange 正在进行？没有这个，插入仍然是线程安全的吗？成百上千的联锁操作会导致性能下降吗？

    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 的最新值，而无需 Interlocked？

4

3 回答 3

5

使用Interlocked方法做两件事：

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

因此，专门针对您的代码。您的第二个解决方案实际上不是线程安全的。每个单独Interlocked的操作都是原子的，但是对各种Interlocked调用的任意数量的调用都不是原子的。鉴于您的方法正在执行的所有操作，您的关键部分实际上要大得多；您需要使用lock或其他类似的机制（即信号量或监视器）来限制对代码段的访问仅限于单个线程。在您的特定情况下，我想整个方法都是关键部分。如果你真的非常小心，你可能会拥有几个更小的关键块，但要确保没有可能的竞态条件将是非常困难的。

至于性能，好吧，因为它是代码不起作用，所以性能是无关紧要的。

于 2012-10-19T17:38:57.283 回答
4

实现无锁链表要比这复杂得多。我强烈建议你不要这样做。只需使用普通的旧显示器即可。如果这只是为了利益，那么您需要对无锁算法进行一些研究。

为了更直接地回答您的问题，联锁操作的成本取决于变量争用的数量。在无争用场景（例如单线程）中，成本极低。随着并发访问数量的增加，成本也会增加。原因是联锁操作并不是真正的无锁操作。它只是使用硬件锁而不是软件锁。出于这个原因，无锁算法的性能通常不如您直观预期的那样好。

于 2012-10-19T17:41:32.003 回答
3

您只是在保护分配，但无论如何它们都是原子的。您应该检查 Exchanged 是否确实成功。

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

于 2012-10-19T17:36:50.713 回答