问题标签 [aba]

我正在实现一个基于这个算法的无锁队列，它使用一个计数器来解决 ABA 问题。但我不知道如何用 c++11 CAS 实现这个计数器。例如，从算法：

这是一个原子操作，意思是 iftail.ptr->next等于next， lettail.ptr->next指向node并同时（原子地） make next.count+1。但是，使用 C++11 CAS，我只能实现：

这不能next.count+1同时发生。

我在维基百科的实践书中调查了并发中的 ABA 问题，并且我已经阅读了以下帖子

据我了解 ABA 问题的根本原因是，在算法中我们检查该状态与以前相同，但算法暗示该状态未被触及。

具有堆栈数据结构的示例：

要将元素添加到堆栈，我们使用以下算法：

导致 ABA 问题的步骤：
初始状态

1. Thread_1 尝试向d堆栈添加值并且操作系统在操作之前暂停线程compareAndSet（point_1）

2. Thread_2 然后执行 pop（Thread_1 仍然挂起）

   /li>

3. Thread_3 然后执行 pop（Thread_1 仍然挂起）

   /li>

4. Thread_4 然后执行 push a（Thread_1 仍然挂起）

   /li>

5. Thread_1 唤醒并且 cas 操作成功执行，尽管在某些情况下它可能是不可取的。

虽然这个答案被接受了，但我不明白为什么自动垃圾收集会消除这个问题。

虽然我不是 CI 专家，但我知道在 C 中你不能为两个不同的对象分配一个内存范围。

你能更清楚地澄清它吗？

我想知道 Clojure 是否有针对 ABA 问题的内置解决方案。我正在创建一个显示此问题的示例，但 Clojure 以某种方式检测到更改。这是因为 Clojure 的事务比较的是引用而不是值吗？

我的例子：

Try 计数始终为 2，因此事务 t3 一定注意到了 t1 和 t2 的 ref 变化。有人知道这种行为的原因吗？

在 CppCon 2014 上，Herb Sutter 描述了使用原子共享 ptr的ABA 问题的简洁解决方案。此解决方案的摘要可在本文底部找到。然而，atomicon的部分特化shared_ptr是传入 C++20 的一个特性（参见此处）。有没有办法使用 C++14 优雅地解决问题？

在C++ Concurrency in Action一书中，作者给出了一个使用危险指针实现无锁堆栈数据结构的例子。部分代码如下：

描述说

您必须在while循环中执行此操作，以确保在读取旧指针和设置危险指针node之间没有删除。head在此窗口期间，没有其他线程知道您正在访问此特定节点。head幸运的是，如果要删除旧 节点，head它本身肯定已经改变，因此您可以检查这一点并继续循环，直到您知道head 指针仍然具有您设置危险指针的相同值。

我认为代码有缺陷，因为head节点受ABA 问题的影响。即使 的值head保持不变，它最初指向的节点也可能已被删除。分配了一个新head节点，该节点恰好与前一个节点具有相同的地址值。

我想出了一个想法，我正在尝试实现一个不依赖引用计数来解决 ABA 问题的无锁堆栈，并且还可以正确处理内存回收。它在概念上类似于 RCU，并且依赖于两个功能：将列表条目标记为已删除，以及跟踪遍历列表的读者。前者很简单，它只是使用指针的 LSB。后者是我在实现无限制无锁堆栈的方法上的“聪明”尝试。

基本上，当任何线程尝试遍历列表时，一个原子计数器 (list.entries) 会递增。当遍历完成时，第二个计数器 (list.exits) 会增加。

节点分配由 push 处理，释放由 pop 处理。

push 和 pop 操作与朴素的无锁堆栈实现非常相似，但必须遍历标记为要删除的节点才能到达未标记的条目。因此，推送基本上很像链表插入。

pop 操作类似地遍历列表，但它使用 atomic_fetch_or 在遍历时将节点标记为已删除，直到到达未标记的节点。

在遍历 0 个或多个标记节点的列表后，正在弹出的线程将尝试对堆栈的头部进行 CAS。至少有一个线程并发弹出会成功，在此之后所有进入堆栈的读取器将不再看到以前标记的节点。

成功更新列表的线程然后加载原子 list.entries，并且基本上自旋加载 atomic.exits，直到该计数器最终超过 list.entries。这应该意味着列表的“旧”版本的所有读者都已完成。然后线程简单地释放它从列表顶部交换的标记节点列表。

所以 pop 操作的含义应该是（我认为）不存在 ABA 问题，因为在所有使用它们的并发读者完成之前，被释放的节点不会返回到可用的指针池中，显然内存回收问题出于同样的原因，也会被处理。

所以无论如何，这是理论上的，但我仍然对实现摸不着头脑，因为它目前不起作用（在多线程情况下）。似乎我在免费问题之后得到了一些写作，但我在发现问题时遇到了麻烦，或者我的假设可能有缺陷并且它不起作用。

任何关于概念和调试代码方法的见解都将不胜感激。

这是我当前的（损坏的）代码（使用 gcc -D_GNU_SOURCE -std=c11 -Wall -O0 -g -pthread -o list list.c 编译）：

我正在学习无锁结构，我注意到一个 ABA 问题。

我认为JavaAtomicStampedReference可以解决这个问题。

那么，C++ 中有什么类似的东西可以解决这个问题吗？

我担心嵌套指针和访问，特别是在处理基于无锁节点的树结构时是否有办法避免这个 ABA 问题。

我的担忧如下：

标准是否对此做出保证并且 funcB 是否等同于 funcA？

如果这里存在 ABA 问题，是否有解决无锁编程嵌套成员访问的方法？

上面的汇编输出是：

以下伪代码摘自http://15418.courses.cs.cmu.edu/spring2013/article/46

这是push使用比较和交换习惯用法的无锁堆栈的操作，但它是原子的。在这里似乎与 ABA 问题无关，我想知道推送和插入操作是否通常是这种情况？