使用Load-link/store-conditional避免ABA问题的无锁C++11示例？

Question

使用比较交换（CAS）技术编写无锁代码时，存在一个称为ABA问题的问题：

http://en.wikipedia.org/wiki/ABA_problem

因此，仅仅比较值"A"是有问题的，因为在两次观察之间可能会发生写操作。我继续阅读并找到了这个解决方案：

http://en.wikipedia.org/wiki/LL/SC

在计算机科学中，load-link 和 store-conditional（LL/SC）是一对指令，用于多线程同步。Load-link 返回内存位置的当前值，而后续的 store-conditional 只有在自从 load-link 以来该位置没有更新时才会存储新值。这样可以实现无锁原子读取-修改-写入操作。一个典型的 C++ 无锁 CAS 技术如何使用上述解决方案进行修改？有人能展示一个小例子吗？我不介意它是 C++11/x86，x86-64 Linux 特定（最好不要 Win32 的答案）。

- user997112

Answer 1

LL/SC 是一些架构（例如 SPARC）实现的指令，用于构建更高级别的原子操作。在 x86 中，您可以使用LOCK前缀来实现类似的目标。但是，为了避免在 x86 的 LOCK 中出现ABA问题，您需要提供自己的保护措施来防止干扰存储操作。一种方法是在相关内存旁边存储一个生成编号（即递增整数）。每个更新器都要执行一个原子比较/交换操作，它涵盖数据和序列号。只有在找到正确的数据和编号时更新才会成功。同时，它更新编号，以便其他线程看到变化。值得注意的是，x86 似乎一直都有一个双倍于机器字长的CMPXCHG指令（请参见CMPXCHG8B和后来的CMPXCGH16B），可用于此目的。

- Ben Jackson

---

你是说CMPXCHG实现了CAS2/Double CAS吗？ - user997112

在32位系统上，CMPXCGH8B 或在64位系统上的CMPXCHG16B 更像是“双倍宽度 CAS”。通用CAS2将适用于非连续内存。 - Ben Jackson

假设您正在使用指针上的CAS，请记住，在Windows 64位上，地址对齐为8字节，有23个未使用的位。我只是使用联合封装了一个64位数字和一个具有我的ptr / aba成员的结构体。在Linux中，除非您想要访问完整的64位范围，否则可以使用相同的技巧。我的经验是128位CAS比64位CAS慢，因此我总是尝试将其压缩到64位中。 - johnnycrash

如果您在指针中有ABA问题，那么您也会有寿命管理问题。至少我不知道有任何方法可以在指针中出现ABA问题，而不必在某个时候持有悬挂指针。Herb Sutter关于此的演讲，他提出的解决方案已经在MSVC中实现了C++20，希望有一天它能够在其他地方得到实现：https://youtu.be/CmxkPChOcvw - Balthazar