如何在C#中原子性地交换两个整数？

Question

在 C# 中，有没有类似于 x86 汇编中 xchg 指令的等价物呢？

使用这个指令，我可以原子地交换两个整数（不像 Interlocked.Exchange），这正是我想要做的。

更新：

基于我的建议，以下是示例代码。带有 "_V" 后缀的变量被标记为易失性：

// PART 3 - process links
// prepare the new Producer
address.ProducerNew.WorkMask_V = 0;
// copy the current LinkMask
address.ProducerNew.LinkMask_V = address.Producer.LinkMask_V;
// has another (any) thread indicated it dropped its message link from this thread?
if (this.routerEmptyMask[address.ID] != 0)
{
  // allow all other bits to remain on (i.e. turn off now defunct links)
  address.ProducerNew.LinkMask_V &= ~this.routerEmptyMask[address.ID];
  // reset
  this.routerEmptyMask[address.ID] = 0;
}
// PART 4 - swap
address.ProducerNew = Interlocked.Exchange<IPC.Producer>(ref address.Producer, address.ProducerNew);
// PART 5 - lazily include the new links, make a working copy
workMask = address.Producer.LinkMask_V |= address.ProducerNew.WorkMask_V;

请注意惰性更新。

- IamIC

---

请在您的问题中更新评论中提供的其他细节，以便回答者了解所有限制条件。这将有助于其他人回答您的问题。https://dev59.com/YW865IYBdhLWcg3wW9RE#3855700 - Jeff Yates

由于没有XCHG [mem1],[mem2]操作码，所以XCHG指令不是您要寻找的原子操作。您需要使用三条指令：mov reg,[mem1] XCHG reg,[mem2] mov [mem1],reg。 - Skizz

@Skizz 我又看了一遍汇编手册 - 你是对的。哇。即使在汇编语言中，我也无法做到我想要的事情。 - IamIC

实际上，在任何语言中，甚至是汇编语言中，原子交换两个变量是不可能的。只能以原子方式交换a和b，并以非原子方式将a作为结果返回。 - IamIC

@IanC 我相信一些早期的RISC处理器允许内存到内存的原子操作。最近，IBM Cyclops 64也有这个功能。在普通PC上，可以通过直接与总线控制器芯片通信并让它为您启动DMA来实现类似的效果。现在，GPU计算变得流行起来，它们也提供各种形式的DMA。虽然这些方法显然是不切实际的，但我认为“不可能”可能只是有点过了... - Glenn Slayden

@m68k 有/曾经拥有过双字比较和交换（用两个非连续内存中的字与两个寄存器进行比较）。https://en.wikipedia.org/wiki/Double_compare-and-swap. 在现代英特尔上，您可以使用TSX（事务性内存）来完成此操作。 - Peter Cordes

Answer 1

以下是从SSCLI20源代码中复制的Interlocked.Exchange()在CLR中的可能实现：

请注意，函数名称中的UP表示UniProcessor。在SMP /多核系统上不具有原子性。此实现仅适用于单核系统上的CLR。

FASTCALL_FUNC ExchangeUP,8
        _ASSERT_ALIGNED_4_X86 ecx
        mov     eax, [ecx]      ; attempted comparand
retry:
        cmpxchg [ecx], edx
        jne     retry1          ; predicted NOT taken
        retn
retry1:
        jmp     retry
FASTCALL_ENDFUNC ExchangeUP

使用这段代码比使用XCHG更好，因为它可以在不锁定总线的情况下工作。 xchg 带有隐式的 lock 前缀，因此与 xadd 或 cmpxchg 不同，它不能在单核系统中省略执行操作的指令以使其对中断（以及因此对于单处理器上的其他线程）具有原子性。

这个看起来奇怪的跳转代码是一种优化，用于处理分支预测数据不可用的情况。或许无需多言，但尝试比众多优秀软件工程师和芯片制造商经过多年探讨得出的结果更好是一项艰巨的任务。

- Hans Passant

---

确实。毫无疑问。非常。加一（表示同意或赞同）。 - Jeff Yates

如果没有该信息，处理器就得猜测。它总是猜测"跳不执行"。对于这段代码来说，这很有可能是正确的。如果使用je指令，那么很可能是错误的。由于流水线，猜错代价非常高昂。 - Hans Passant

@HansPassant 最终，我能够编写一个阻塞的线程间消息传递系统，其运行速度比内置的 .Net 4.0 类型快9.1倍。代码还实现了更多功能（路由），因此从技术上讲，它比原来快了一个数量级。因此有时候不仅可以击败经过多年由非常出色的软件工程师和芯片制造商慎重考虑的东西，而且可以将其彻底打败 :) - IamIC

@IanC：你能描述一下当谈到“9.1倍”改进时，你实际上正在比较哪两件事吗？特别是因为你接受的答案实际上使用了Interlocked？ - vgru

9.1倍是指我编写的代码传递消息时使用了同步传递消息而非使用内置的锁{...}方法。 - IamIC

Answer 2

这里有一个有点奇怪的想法。我不知道你的数据结构具体是如何设置的。但如果可能的话，你可以将两个 int 值存储在一个 long 中，然后我认为你可以原子地交换它们。

例如，假设你以以下方式封装了两个值：

class SwappablePair
{
    long m_pair;

    public SwappablePair(int x, int y)
    {
        m_pair = ((long)x << 32) | (uint)y;
    }

    /// <summary>
    /// Reads the values of X and Y atomically.
    /// </summary>
    public void GetValues(out int x, out int y)
    {
        long current = Interlocked.Read(ref m_pair);

        x = (int)(current >> 32);
        y = (int)(current & 0xffffffff);
    }

    /// <summary>
    /// Sets the values of X and Y atomically.
    /// </summary>
    public void SetValues(int x, int y)
    {
        // If you wanted, you could also take the return value here
        // and set two out int parameters to indicate what the previous
        // values were.
        Interlocked.Exchange(ref m_pair, ((long)x << 32) | (uint)y);
    }
}

那么似乎你可以添加以下Swap方法以实现"原子地"交换一对值（实际上，我不知道是否公平地说下面的操作是原子操作；更确切地说，它产生了与原子交换相同的结果）。

/// <summary>
/// Swaps the values of X and Y atomically.
/// </summary>
public void Swap()
{
    long orig, swapped;
    do
    {
        orig = Interlocked.Read(ref m_pair);
        swapped = orig << 32 | (uint)(orig >> 32);
    } while (Interlocked.CompareExchange(ref m_pair, swapped, orig) != orig);
}

当然，我很可能实现得不正确，而且这个想法可能存在缺陷。它只是一个想法。

- Dan Tao

---

这种技术是通过解决ABA问题而被人们所知，其中您在高32位中保持一个递增的“版本”计数器，并在低32位中存储数据，以检测ABA故障。请参阅Duffy的《Windows并发编程》第536页。我基于64位原子操作编写了一个托管无锁字典，完全使用像这样的成对32位邻居实现。 - Glenn Slayden

@dantao 这个想法是可行的。实际上，我成功地将三个数字放入一个长整型变量中，并使用移位运算控制它们。这是完美的解决方案。 - IamIC

@IanC：太棒了！通常我会回顾两年前在SO上发布的答案并感到尴尬；但很高兴知道这个想法最终对你有用（尽管我相信你必须做出重大改变才能将其应用于你的情况）。 - Dan Tao

除非SetValues需要顺序一致性，否则它只需要一个8字节的存储，而不是xchg。因此，您可能不需要使用Interlocked.Exchange。（即使在32位模式下，x86也可以使用x87 fild/fistp或使用SSE进行8字节原子存储）。我不知道您如何在C#中请求它，但我假设使用未使用的结果的Interlocked.Exchange仍然是一个完整的内存屏障，您不需要这个。 - Peter Cordes

顺便说一下，使用CAS重试循环实现原子操作对于硬件不提供的操作是完全有效和正常的。你绝对可以称之为原子交换（atomic swap）。（或者是一个long的原子旋转（atomic rotate）。顺便说一下，x86-64不能使用lock rol qword ptr [mem], 32，因为内存目标旋转不支持lock前缀：如果你尝试，它们会#UD（非法指令）。 - Peter Cordes

Answer 3

为什么对你来说 Interlocked.Exchange 不合适？

如果你需要精确交换内存位置，那么你选择的编程语言和平台可能不合适。.NET将内存管理抽象出来，因此你不需要考虑它。

如果你必须在没有使用 Interlocked.Exchange 的情况下完成类似的操作，则可以编写一些标记为unsafe 的代码，并像在C或C++中一样使用基于指针的传统交换，但你需要将其封装在适当的同步上下文中，以使其成为原子操作。

更新
你无需使用unsafe代码即可完成原子交换。 可以将代码包装在同步上下文中，使其具有原子性。

lock (myLockObject)
{
  var x = Interlocked.Exchange(a, b);
  Interlocked.Exchange(b, x);
}

更新2
如果同步不是一个选项（如在评论中指出），那么我认为你就没有办法了。如果你在追求一些未被衡量的效率，那么你可能需要将精力集中在其他方面。如果交换两个整数值是一个很大的性能负担，那么你可能正在使用错误的平台。

- Jeff Yates

---

@IanC：为什么锁不合适？也许如果你提供所有细节，你就可以得到答案。随着我们的进展逐渐增加限制并不是有帮助的。 - Jeff Yates

@IanC：你怎么知道它会更有效率？我认为你是在瞎猜。请发表证据。 - Jeff Yates

@Jeff，你说得对。.Net平台不是最适合这个需求的。但它非常适合项目的其他部分。现在，我只能坚持使用当前的代码，看看效果如何。 - IamIC

@Matt：Interlocked.Exchange是原子操作，但对b的赋值不是。 - Jeff Yates

嗯，我在这里的锁有问题 - 它并不会使代码块内部的语句自身成为原子操作 - 它的原子性只能来自其他地方有相同的锁 - 在没有它的情况下访问变量将会破坏那个原子性... - Daniel Mošmondor

Answer 4

Interlocked.Exchange 真的是你唯一能做的事情：

  var x = Interlocked.Exchange(a, b);
  Interlocked.Exchange(b, x);

你说得对，这不会是原子性的，但是使用本地变量，只要两行代码都执行，你就可以保证值是一致的。其他选项包括使用不安全代码（使用指针），使用p/invoke调用本地库，或重新设计使其不再需要。

- Philip Rieck

---

必须是原子性的。你能告诉我如何使用不安全的代码完成这个吗？ - IamIC

Interlocked.Exchange是一个原子操作，但是连续执行两次并不是没有同步的。正如MSDN文档所示 - http://msdn.microsoft.com/en-us/library/system.threading.interlocked.exchange.aspx - Jeff Yates

@IanC 不安全的 C# 并不会使其比这更原子化。如果你真的、真的需要 XCHG，你将不得不自己用 C 写它。不确定过渡是否会比瘦锁带来巨大的性能优势。可以参考这样的文章：http://www.codeproject.com/KB/cs/unmanage.aspx - Philip Rieck

@Jeff Yates 确实连续两次并不是原子操作 - 这就是我在这里的观点。他想要实际交换两个值，而不仅仅是改变一个值，我认为这是在纯C#中最接近实现它的方法。 - Philip Rieck

Answer 5

根据MSDN，Interlocked.Exchange是原子操作。

如果不适合您，您可以使用C/C++在unsafe部分实现XCHG。

- Rob Vermeulen

---

那似乎是唯一的解决方案。谢谢。 - IamIC

没有锁，我不认为不安全的代码能够正常工作。如果没有某种形式的同步，就无法使其原子化。 - Jeff Yates

@Jeff Yates，你在原子部分是正确的。我想说的是，在不安全的部分中，您可以使用内联汇编来执行XCHG。 - Rob Vermeulen

Answer 6

在C#中，Interlocked.Exchange是以线程安全的方式交换两个int值的最佳方法。

即使您拥有多处理器计算机，并且您不知道您的线程将在哪个处理器上运行，请使用此类。

- TalentTuner

Answer 7

除了Interlocked.Exchange之外，我认为XCHG命令可能是XOR Swap的实现，因此您可以编写自己的代码。

C语法：（来自维基百科链接）

 void xorSwap (int *x, int *y) {
     if (x != y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

编辑 这不是原子操作，你需要自己同步

- Kenny Cason

---

根据原帖作者的要求，这将不是原子操作。 - Jeff Yates

XCHG 是 x86 CPU 指令，它是原子性的，意味着它不能被另一个指令中断。如果没有在参数上先添加额外的锁定，XOR 交换则不是原子性的。 - Rup

@Rup，我之前不知道需要原子性。 - Kenny Cason

Answer 8

我认为我刚刚找到了最好的解决方案。它是：

Interlocked.Exchange() 方法 (ref T, T)

所有的“新”变量都可以在一个类（T 的）中设置，并与当前变量交换。这使得原子快照可以进行，同时有效地交换任意数量的变量。

- IamIC

---

是的，我认为这种方法唯一的问题在于你必须将数据放入不可变的引用类型中，这可能有些过度，具体取决于你执行交换操作的频率。 - Dan Tao

@Dan 我只需要创建2个对象，然后简单地交换它们的指针。一旦交换完成并读取了数据，对象就可以被清零，然后准备好进行交换。你明白我的意思吗？ - IamIC

我已经测试了我提出的想法，目前它正在工作。将进行更多的测试。 - IamIC

@IanC：实际上，我越想这个想法，就越不信服。如果没有原子读取，如何确保交换的原子性呢？换句话说，假设您要交换的数据都在对象X中，您需要在交换X和Y之前将对象Y填充为该数据的“交换”版本。我在这里看不到任何关于如何以原子方式完成所有这些操作的提示——只有如何交换X和Y本身的引用，这只是谜题的一小部分。但当然，您是正确的，我可能只是不够熟悉您的确切情况，无法评估这个想法。 - Dan Tao

@Dan 我有两个引用，分别指向我想要交换的两个对象的实例。这些引用都被标记为volatile。让我将代码作为更新发布。 - IamIC