比较交换（Compare And Swap）有什么用处？

Question

比较交换（Compare And Swap）有什么用处？

c#cassemblythread-safetycompare-and-swap

13

我最近阅读了比较并交换原子操作（CMPXCHG，.NET的Interlocked.CompareExchange等）的内容。

我理解它的内部工作原理以及客户端如何使用它。

我不太确定的是，什么情况下会使用CAS？

维基百科说：

CAS 用于实现同步原语，例如信号量和互斥锁，同样还有更复杂的无锁和无等待算法。

因此，是否有人可以给我提供一个更通用的真实世界的用例，并附上CAS使用的代码和描述？

此问题意在与编程语言无关，因此任何语言都可以（C-based或x86汇编优先）。

谢谢！

- Stanislav Nedelchev

3个回答

6

您可以使用CAS在一个线程或进程中原子地设置一个值（位或字），同时测试另一个线程/进程是否已经这样做。因此，它被用于在多线程环境下获取标志或计数器。

补充说明（2023年2月）：

例如，多个线程可以各自使用CAS指令将其进程ID交换到共享内存的一个共享字中（该字最初保持为零）。将其进程ID存储到该字中的第一个线程可以接管该共享字所保护的任何资源。

当进程完成对资源的使用时，它会将零存储到该字中，释放对资源的所有权，并允许其他线程获得资源的使用权。

- David R Tribble

那是当我们只有一个内核的时候。现在线程可以跨越多个内核，那么这如何应用？（我可能漏掉了什么） - kubal5003

5

@kubal5003 - 这种方法在多核心处理器上尤其有效，因为它保证对一个数据单元的原子性（只被单个CPU/线程/核心访问）。 - David R Tribble

对于单个布尔标志，xchg（Interlocked.Exchange）在包含字节上的效果大致相同。要获取锁定，请交换1并查看旧值是否为0。（类似于这个x86-64汇编自旋锁玩具示例）。这不是CAS真正证明其价值比简单事物更好的用例。它对于计数锁/信号量有更多价值，其中您不希望仅使用fetch_add（x86 lock xadd）与-1，因为这可能会使计数器低于0。 - Peter Cordes

-1

那么，有人能给我一个更通用的真实世界用例，包括CAS使用的代码和描述吗？这篇论文使用CAS实现了一个无锁线程安全队列。

其中有一些伪代码示例。

- anon

2

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Hamed Hajiloo

1

欢迎来到 Stack Overflow！请通过详细说明或解释链接内容来改进您的答案。它应该能够独立存在，仅将外部文档或资源用作进一步阅读的补充。 - spicy.dll

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- usr · Accepted Answer

这很容易通过示例理解。假设我们想要在共享变量上原子并发地设置一个位：

int shared = 0;

void Set(int index) {
 while (true) {
  if (Interlocked.CompareExchange<int>(ref shared, shared | (1 << index), shared) == shared)
   break; //success
 }
}

我们检测失败的方法是查看“旧值”（即返回值）是否在此期间发生了更改。

如果这种情况没有发生，那么我们就没有进行并发修改，因此我们自己的修改已经成功通过。

您可以利用这种技术实现非常复杂的东西。但是，复杂度越高，在旋转过程中会有更多的性能损失。

我想强调CAS的一个关键属性是它可以失败，并且可以可靠地检测到故障。