问题标签 [compare-and-swap]

有没有办法让比较和交换风格的机制成为修改某些资源的唯一方法，同时遵循 HTTP 标准？

有一个If-Match实现正确行为的标头，但是这个标头是可选的：据我所知，如果If-Match没有提供，服务器应该尊重PUT. （也就是说，由客户端决定是否要进行比较和交换，或者只是交换。）412 Precondition Failed如果客户端尝试提供PUT或POST不提供If-Match标头，是否可以接受响应？

假设一些“N”个线程正在尝试对一个 AtomicInteger 变量进行 CAS 处理，是否保证 CAS 必须为一个线程成功？

是否有可能所有“N”个线程都尝试失败？

我正在寻找一些在多线程代码中引起问题的ABA 问题的真实示例。

在执行原子比较和交换指令时，并发代码中会出现 ABA 问题。如果线程在执行比较和交换之前立即中断，则第二个线程可能会将比较和交换的目标从其初始值 A 更改为不同的值 B。如果然后将值更改回 A在第一个线程恢复之前，尽管目标值发生了变化，比较和交换仍将成功。

在许多情况下，ABA 不是问题。以共享引用计数为例：即使 refcount 并发改变我们也没有问题，只要我们从不从已经下降到 0 的 refcount 增加。所以我们显然只关心目标是否匹配交换时的期望值，而不是过去是否发生变化。

维基百科页面有一个受 ABA 影响的无锁堆栈实现示例，但到目前为止，我个人还没有在生产代码中遇到过这个问题。我只是好奇是否有人有一些关于 ABA 的好战争故事要分享。

我正在用 C 语言编写一个程序。为了简单起见：有几个变量可供许多线程读写。每次写入其中一个时，它都会通过原子交换（GCC 原子操作、同步和交换）写入。每次读取其中一个变量时是否需要使用原子负载，或者原子写入是否足以避免在写入过程中读取数据？

请注意，任何需要使用这些变量之一的数据的地方首先复制该值：

我的问题不是关于数据竞赛，我不担心我可能会丢失数据。我担心 shared_x 的值可能会在我阅读的过程中发生变化。假设它是一个 8 字节整数，这是否是一个潜在的问题：假设 shared_x 是一个 64 位整数，8 字节。我的 x = shared_x 是否有可能复制前 4 个字节，然后以原子方式写入 shared_x，然后该语句完成读取第二个 4 个字节。这将导致 x 包含 shared_x 的旧值的前 4 个字节，以及新 shared_x 的最后 4 个字节。我怀疑原子交换中的内存屏障（http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html - 使用__sync_bool_compare_and_swap）足以防止这种情况......但我我不确定。

我需要实现（伪代码）一种新类型的 compare&swap(a,b) (CAS) 对象（我们称之为新类型 CAS2）。

CAS 和 CAS2 对象都支持返回对象值的读取操作。

它们都支持 compare&swap(a,b) 操作，但是在 CAS 上，此操作返回 true/false，如果它等于 a，则将对象值更改为 b，在 CAS2 上，此操作具有相同的效果，但不是返回 true /false，它应该总是在操作之前返回对象值。

例如：

如果 CAS 对象的值为 4，compare&swap(4,5) 将返回 true 并将值更改为 5，但在 CAS2 对象上，compare&swap(4,5) 将返回 4 并将值更改为 5。如果 CAS 对象值为 4，那么 compare&swap (5,6) 将返回 false 并且什么都不做，但在 CAS2 上 compare&swap (5,6) 将返回 4 并且什么也不做。CAS2 对象应该只使用一个 CAS 对象来实现，并且实现应该是无等待和可线性化的。

提前致谢！

我最近使用三重缓冲区的 std::atomic 移植到 C++11，用作并发同步机制。这种线程同步方法背后的想法是，对于生产者-消费者的情况，你有一个运行得更快的生产者消费者，三重缓冲可以带来一些好处，因为生产者线程不会因为不得不等待消费者而“减慢”速度。在我的例子中，我有一个以~120fps 更新的物理线程和一个以~60fps 运行的渲染线程。显然，我希望渲染线程总是尽可能获得最新的状态，但我也知道我会从物理线程中跳过很多帧，因为速率不同。另一方面，我希望我的物理线程保持其恒定的更新率，并且不受锁定数据的较慢渲染线程的限制。

原始的 C 代码是由 remis-thoughts 编写的，完整的解释在他的博客中。我鼓励任何有兴趣阅读它以进一步了解原始实现的人。

我的实现可以在这里找到。

基本思想是拥有一个具有 3 个位置（缓冲区）和一个原子标志的数组，该标志通过比较和交换来定义在任何给定时间哪些数组元素对应于什么状态。这样，只有一个原子变量用于对数组的所有 3 个索引和三重缓冲背后的逻辑进行建模。缓冲区的 3 个位置被命名为 Dirty、Clean 和 Snap。Producer总是写入 Dirty 索引，并且可以翻转 writer 以将 Dirty 与当前的 Clean 索引交换。消费者可以请求一个新的Snap，它将当前的 Snap 索引与 Clean 索引交换以获得最新的缓冲区。消费者总是在Snap 位置读取缓冲区。

该标志由一个 8 位无符号整数组成，这些位对应于：

（未使用）（新写入）（2x 脏）（2x 干净）（2x 快照）

newWrite 额外位标志由写入器设置并由读取器清除。读者可以使用它来检查自上次快照以来是否有任何写入，如果没有，则不会再进行一次快照。可以使用简单的按位运算获得标志和索引。

现在好了，代码：

执行：

如您所见，我决定使用Release-Consume模式进行内存排序。存储的释放(memory_order_release) 确保当前线程中的写入不能在存储之后重新排序。另一方面，Consume确保当前线程中依赖于当前加载的值的读取不会在此加载之前重新排序。这确保了对释放相同原子变量的其他线程中的因变量的写入在当前线程中是可见的。

如果我的理解是正确的，因为我只需要原子设置标志，编译器可以自由地重新排序不直接影响标志的其他变量的操作，从而进行更多优化。通过阅读一些关于新内存模型的文档，我也知道这些宽松的原子只会在 ARM 和 POWER 等平台上产生显着影响（它们主要是因为它们而引入的）。由于我的目标是 ARM，我相信我可以从这些操作中受益，并且能够挤出更多的性能。

现在的问题：

对于这个特定问题，我是否正确使用了 Release-Consume 宽松排序？

谢谢，

安德烈

PS：对不起，很长的帖子，但我认为需要一些体面的上下文才能更好地了解问题。

编辑： 实施@Yakk的建议：

• 修复flags了 read onnewSnap()和flipWriter()使用直接赋值的问题，因此使用 default load(std::memory_order_seq_cst)。
• 为清晰起见，将位摆弄操作移至专用功能。
• 添加bool了返回类型newSnap()，现在在没有新内容时返回 false，否则返回 true。
• 使用习惯用法将类定义为不可= delete复制，因为如果使用了复制构造函数和赋值构造函数，则它们都是不安全的TripleBuffer。

编辑 2： 修复了不正确的描述（感谢@Useless）。是消费者请求一个新的 Snap 并从 Snap 索引中读取数据（而不是“作者”）。抱歉打扰了，感谢无用的指出。

编辑 3：根据@Display Name 的建议 优化了newSnap()and功能，有效地去除了每个循环周期的 2 个冗余 's。flipriter()load()

我在更改 ArrayList 中特定位置的值时遇到问题。更清楚地说，情况如下：

我想在一个列表中添加产品 ID，并在另一个列表中添加它们的计数。但是，如果用户选择了已经在 productList 中的产品，我想在 countList 更新中使用新选择的计数器进行计数。

这是代码：

问题是它没有进入 for 循环，没有进行检查。只需将项目放入列表中。请帮忙。先谢谢了！！！

我在我的多线程代码中使用incrementAndGet方法AtomicLong来测量我们的一些客户端代码的性能。

在上面的代码中，我试图测量多少时间-

client.getAttributes(columnsList);

正在服用。

据我所知，incrementAndGet方法将以原子方式将当前值增加一。这意味着每个线程可能会等待其他线程增加该值。我对吗？意思是会被屏蔽？

这是否会影响我测量任何方法的性能的方式？这意味着它还会为该测量增加一些额外的时间吗？

为什么我问这个是因为我正在尝试对我们的大多数客户端代码和服务器端代码进行基准测试，如果我需要测量每种方法所花费的时间，那么我就是这样做 -

无论我想测量什么代码，我通常将下面的行放在该方法的正上方

long start = System.nanoTime();

这两行采用相同的方法但不同ConcurrentHashMap

因此，如果我正在使用incrementAndGet方法并且如果它为我的性能测量增加了额外的时间，那么我可能没有得到准确的结果？

更新：-

这是下面的方法，我F3在incrementAndGetin上做的时候得到的eclipse。

所以这里有一个同步块。这意味着每个线程都会在这里等待其他线程。这是一个阻塞呼叫。

啊。我刚刚检查了我的 JVM，IBM JVM与SUN JVM. 因为我在一家公司工作，我无法改变这个特殊的事情。

那么有什么方法可以避免这种基于锁的解决方案来衡量任何方法的性能/基准？请记住，我正在运行 IBM JVM。

谢谢您的帮助。

许多 C++11 CAS 操作（例如 , atomic_compare_exchange_weak）atomic_compare_exchange_strong采用两个指针和一个值，即像这样：

相比之下，来自 Microsoft、gcc 和 Intel 的 CAS 操作都采用一个指针和两个值：

为什么 C++11 CAS 函数采用两个指针和一个值，而不是看起来更传统的一个指针和两个值？

在互斥体上使用原子的主要原因是互斥体很昂贵，但是使用默认的内存模型，这atomics不是memory_order_seq_cst一样昂贵吗？

问题：使用锁的并发程序能否与并发无锁程序一样快？

如果是这样，除非我想用于原子，否则可能不值得付出努力memory_order_acq_rel。

编辑：我可能遗漏了一些东西，但基于锁的不能比无锁更快，因为每个锁也必须是一个完整的内存屏障。但是对于无锁，可以使用比内存屏障限制更少的技术。

所以回到我的问题，无锁是否比基于新 C++11 标准的默认锁更快memory_model？

“以性能衡量时，无锁 >= 基于锁”是真的吗？假设有 2 个硬件线程。

编辑2：我的问题不是关于进度保证，也许我在上下文之外使用“无锁”。

基本上，当您有 2 个线程共享内存时，您需要的唯一保证是，如果一个线程正在写入，则另一个线程无法读取或写入，我的假设是简单的原子compare_and_swap操作比锁定互斥锁快得多.

因为如果一个线程甚至从未接触过共享内存，您最终将无缘无故地一遍又一遍地锁定和解锁，但使用原子操作您每次只使用 1 个 CPU 周期。

关于评论，当争用很少时，自旋锁与互斥锁是非常不同的。