问题标签 [compare-and-swap]

在一些论坛和书籍（即C++ Concurrency in Action）中，有一个很好的多生产者/多消费者堆栈示例，在pop实现中，它们通常执行以下操作：

• old_head->next在线程被抢占之前得到解决（就在compare_exchange_weak之前）
• 然后 BA 场景发生
• 线程恢复后head == old_head有效；在这种情况下old_head->next不会再被解析，指向一个无效的内存位置
• compare_exchange_weak将被执行，将通过，但值old_head->next仍将是旧值

然后会发生与ABA相关的问题。

我相信我错过了一些东西。我在这里想念什么？

干杯

为什么std::atomic_compare_exchange及其所有兄弟姐妹更新传递的期望值？

我想知道除了给定的循环简单性之外是否还有其他原因，例如：是否有一个内在函数可以在一个操作中做到这一点以提高性能？

For high-performance multi-threading system, is there a deterministic way/methodology to determine what concurrency logic can be done using only compare-and-swap a.k.a. atomic operations, what must use locks, semophones and/or barriers?

My systems always involve a lot of concurrency and multi-threading issue. Some are simple as one can work out if a simple lock is needed quickly; but for some complicated problems, or trials to push performance to extreme, I found that I don't have a consistent deterministic methodology to tell if a problem can be resolved using only CAS. As an example:

1. Typical producer/consumer model. Concurrent queue can resolve the problem using CAS only.

2. Producer/consumer model with a lot of updates but conflated consumption. In this case if double-buffering is used, read/write lock must apply; however, if we use triple-buffering, then using CAS is essentially possible.

Roughly speaking, we could say if a piece of logic can be separated into several inter-dependent states, each need only CAS, then such logic can be resolved by only CAS. But applying this in real problems seems much more complicated, and I do feel lack of a good methodology to divided and determine if such logic division is possible.

Please kindly share me your experiences or any methodologies I am not aware of.

如何从地址中窃取 2 个 MSB 来执行原子操作？我正在尝试做一个单词 CAS

一个例子

AtomicReference如果我只需要一个额外的标志，可以使用。 AtomicStampedReference可以使用，但效率不高，因为它创建了一个包含时间戳和参考的额外框。

C 语言中的一个类似问题在 从指针中窃取位时进行了讨论

Martin Thompson 断言，依赖于 CAS 的 ref 的 STM 最终将受到 Amdahl 定律的限制。阿姆达尔定律是并行程序的最大性能受到程序的顺序（非并行）部分的限制。Martin Thompson 是否说 CAS 本质上是非平行的？

作为多线程和互斥锁的新手，我正在浏览维基百科作为初学者。我遇到了这部分：

CAS 可用于通过创建一个链表来实现任何共享数据结构的无等待互斥，其中每个节点代表要执行的所需操作。然后在插入新节点期间使用 CAS 更改链表中的指针。只有一个进程可以在其 CAS 中成功；同时尝试添加节点的所有其他进程都必须重试。然后每个进程可以保留数据结构的本地副本，并且在遍历链表时，可以在其本地副本上执行链表中的每个操作。

现在我了解了 CAS 的基本概念，我们基本上使用原子操作将值与预定值进行比较，如果匹配，我们交换它们。但我无法理解这里的“所需操作的链接列表”是什么意思？为什么所有进程都遵循相同的操作链表？

以下两个引用似乎相互矛盾：

https://www.kernel.org/doc/Documentation/atomic_ops.txt

int atomic_cmpxchg(atomic_t *v, int old, int new);

这将对原子值 v 与给定的旧值和新值执行原子比较交换操作。与所有 atomic_xxx 操作一样，只要 *v 的所有其他访问都通过 atomic_xxx 操作执行，atomic_cmpxchg 只会满足其原子性语义。

atomic_cmpxchg 需要操作周围的显式内存屏障。

对比

https://www.kernel.org/doc/Documentation/memory-barriers.txt

任何修改内存中的某些状态并返回有关状态（旧的或新的）信息的原子操作都意味着在实际操作的每一侧都有一个 SMP 条件通用内存屏障 (smp_mb())（显式锁定操作除外，描述之后）。这些包括：

这些用于实现 LOCK 类和 UNLOCK 类操作以及调整引用计数器以实现对象破坏等事情，因此隐式内存屏障效果是必要的。

那么是否应该atomic_xchg()手动设置内存屏障？

我正在尝试实现一个屏障函数，这样当一个线程调用waitBarrier()它时，它将等到所有其他n线程都调用了该函数，之后一切都会继续进行，即一种同步构造。

我有以下代码：

如果这被n线程访问，这个函数会起作用吗？原子函数返回值的赋值是原子的吗？或者可能会出现竞争条件？

我读过很多帖子说比较和交换保证原子性，但是我仍然无法理解它是如何做到的。这是比较和交换的一般伪代码：

这如何保证原子性？例如，如果我使用它来实现互斥锁，

这如何防止 2 个线程同时获取互斥锁？任何指针将不胜感激。

在 Intel x86 处理器上，是否可以在特定内存位置将一个值与另一个值进行比较，如果比较成功则重置内存而不用担心多线程/处理器问题？我看到了 CMPXCHG 指令——这行得通吗？还是有比较和设置用例的东西？