问题标签 [compare-and-swap]

while 与 do-while

当块为空时， while 和 do-while 在功能上是等效的，尽管 while 看起来更自然：

带有空块的 while/do-while 的一个典型用例是使用 compareAndSet (CAS) 强制更新原子对象。例如，下面的代码将以a线程安全的方式递增：

语境

java.util.concurrent 的几个部分使用do {} while (...)CAS 操作的习语和解释的 javadoc ForkJoinPool：

有几次出现异常do {} while (!cas...)，这是强制更新 CAS 变量的最简单方法。

既然他们承认这很不寻常，我想他们的意思是best而不是simple。

问题

do {} while (!cas)有没有比这更有效的情况while (!cas) {}？出于什么原因？

我正在阅读一篇关于非阻塞 CAS 的文章并遇到了这段代码：

如果使用同步，这个 CAS 操作如何非阻塞？

如果我们的意思是这个客户端SimulatedCAS不需要实现它自己的同步，那么我们不是只是移动了阻塞而不是消除它吗？

谁能给我总结一下比较和交换编程的优缺点？（例如多核 CPU 性能）

这是Java中的示例：

=== 编辑===

请在单核/核心 CPU 中专门讨论这个问题。

为什么在英特尔架构中我们需要在 CMPXCHG 之前锁定前缀。请参阅 http://courses.engr.illinois.edu/ece390/archive/spr2002/books/labmanual/inst-ref-cmpxchg.html以供参考

我不确定如果不使用锁会有什么后果。因为在将值加载到 eax 和执行 LOCK CMPXCHG 之间，无论锁定前缀如何，值都可以更改，因为将值加载到 eax 和 LOCK CMPXCHG 是两条指令。

意思是说，如果我不使用 CMPXCHG，最糟糕的可能是我必须再次旋转。

InterlockedCompareExchange在 Windows 中，以及__sync_val_compare_and_swap在 gcc 中获取指针，因此我可以将任何地址（例如指向共享内存块的地址）传递给这些函数。

对于非 x86 架构，我可能必须确保内存对齐以确保正确性，而对于 x86（可能还有其他），我可能希望确保缓存行对齐以提高性能，尽管正确性不应该成为问题（-> x86LOCK前缀） .

试图摆脱我的代码中一些依赖于平台的东西（Windows VC++ 与 GCC），我看了一下 C++11atomic_compare_exchange_weak和朋友。但它们都适用于 type 的变量std::atomic<T>*。

有没有办法在 C++11 的原子函数中使用任意指针？它看起来不像是对 std::atomic的简单转换可以解决这个问题。

下面是一个简化的 C 程序，它演示了我在使用 GNU 内置比较和交换在英特尔 cpu 上实现的并发堆栈时遇到的问题。我花了一段时间才明白发生了什么，但现在我明白了，它完全在原子比较和交换提供的保证范围内。

当一个节点从堆栈中弹出，修改，然后放回堆栈时，修改后的值可能成为堆栈的新头部，从而破坏它。test_get 中的注释描述了导致这种情况的事件顺序。

有没有办法多次可靠地使用具有相同堆栈的相同节点？这是一个夸张的例子，但即使将未修改的节点返回给 gHead 也可能泄漏其他节点。这种数据结构的初衷是重复使用相同的节点。

我正在使用 8 个逻辑核心运行此测试。当我只使用 4 个线程时，问题很少发生，但使用 8 个线程很容易重现。我有一台配备 Intel Core i7 的 MacBook。

我对使用一些解决了这个问题的库或框架不感兴趣，我想知道它是如何解决的。谢谢你。

编辑：

这里有两个在我的情况下不起作用的解决方案。

一些体系结构提供了 ll/sc 指令对，它们对地址而不是值执行原子测试。对该地址的任何写入，即使是相同的值，也会阻止成功。

一些架构提供大于指针大小的比较和交换。有了这个，单调计数器与指针配对，每次使用时都会以原子方式递增，因此值总是会变化。一些英特尔芯片支持这一点，但没有 GNU 包装器。

这是一个问题。两个线程，A 和 B，到达test_get它们具有相同值的点，result而不是NULL。然后发生以下顺序：

1. 线程 A 通过比较和交换并result从test_get
2. 线程A修改内容result
3. 线程 B 取消引用result，得到任何线程 A 放在那里
4. 线程 A 结束result并调用test_put
5. 线程 A 通过比较和交换test_put将结果放回gHead
6. 线程 B 到达比较并换入test_get并通过
7. 线程 B 现在已经被gHead线程 A 的值破坏了

这是一个类似的场景，其中三个线程不需要线程 A 进行修改result。

1. 线程 A 通过比较和交换并result从test_get
2. 线程A不修改内容result
3. 线程 B 取消引用result，在scratch
4. 线程 C 调用test_put不相关的值并成功
5. 线程A调用test_put并成功result放回gHead
6. 线程 B 到达比较并换入test_get并通过
7. 线程 B 现在已gHead通过泄漏任何线程 C 添加的内容而损坏

在任何一种情况下，问题都是线程 A 通过了比较和交换两次，一次是 get，然后是 put，在线程 B 到达比较和交换以获得 get 之前。线程 B 的任何从头开始的值都应该被丢弃，但这并不是因为 gHead 中的值看起来是正确的。

任何使这种可能性降低而不实际阻止它的解决方案只会使错误更难追踪。

请注意，临时变量只是在原子指令开始之前放置结果的取消引用值的位置的名称。删除名称确实会删除可能被中断的取消引用和比较之间的时间片。

另请注意，原子意味着它作为一个整体成功或失败。指针的任何对齐读取在相关硬件上都是隐式原子的。就其他线程而言，不存在只读取一半指针的可中断点。

在 .NET 框架中，原子操作CompareAndExchange 仅为 、和引用int类型定义。但我需要 CompareAndExchange 的类型。我该如何实施？longdoubleboolCompareAndSwapbool

C++11 对原子变量有一个“比较和交换”操作。

语义是：

原子地比较 所指向的值obj与 所指向的值expected，如果相等，则将前者替换为desired（执行读-修改-写操作）。否则，将指向的实际值加载到objinto *expected（执行加载操作）。

我想做同样的事情，但不是*obj在值相等时设置，而是在一个大于另一个时设置它（假设我们谈论的是有序类型）。

这是否以某种方式支持？也许可以通过一些黑客来实现？

注意： CAS 循环不适合我，因为我比较的两个值可能会在非原子操作之间发生变化。

C++11 中有两个原子 CAS 操作：atomic_compare_exchange_weak和atomic_compare_exchange_strong.

根据cppreference：

函数的弱形式被允许虚假地失败，也就是说，即使它们相等，也可以像 *obj != *expected 一样行事。当比较和交换处于循环中时，弱版本将在某些平台上产生更好的性能。当弱比较和交换需要循环而强循环不需要时，强循环更可取。

以下是使用弱版本的示例，我认为：

有人可以举一个比较和交换不在循环中以便强版本更可取的例子吗？

说有：

我需要的是对中的某些两个相邻位byte（例如第四个和第五个）执行原子 CAS（比较和交换）操作。

当然，没有办法处理比字节短的东西，但是有一个字节的 CAS 函数，所以如下：

byte将与进行原子比较expected，如果它们相等，将分配desired给byte并返回true，否则（即如果byte不等于expected），它将分配byte给expected并返回false。

因此，如果它是对字节的 CAS 操作，其中比较不仅仅是通过检查 EQUALITY 来完成，而是通过一些按位操作，如按位与或按位或，那么就有可能对位进行 CAS。

所以问题变成了是否存在字节的 CAS 操作，在比较时，它不是寻找相等性，而是寻找一些按位运算，如按位与或按位或？