Linux C/C++并发编程实战（8）CAS机制的ABA问题

ABA问题：CAS在操作的时候会检查变量的值是否被更改过，如果没有则更新值，但是带来一个问题，最开始的值是A，接着变成B，最后又变成了A。经过检查这个值确实没有修改过，因为最后的值还是A，但是实际上这个值确实已经被修改过了。

听起来似乎没有什么严重的问题，举几个实际的例子看下。

无锁队列中的ABA问题

/* Naive lock-free stack which suffers from ABA problem.*/
class Stack {
  std::atomic<Obj*> top_ptr;
  //
  // Pops the top object and returns a pointer to it.
  //
  Obj* Pop() {
    while (1) {
      Obj* ret_ptr = top_ptr;
      if (ret_ptr == nullptr) return nullptr;
      // For simplicity, suppose that we can ensure that this dereference is safe
      // (i.e., that no other thread has popped the stack in the meantime).
      Obj* next_ptr = ret_ptr->next;
      // If the top node is still ret, then assume no one has changed the stack.
      // (That statement is not always true because of the ABA problem)
      // Atomically replace top with next.
      if (top_ptr.compare_exchange_weak(ret_ptr, next_ptr)) {
        return ret_ptr;
      }
      // The stack has changed, start over.
    }
  }
  //
  // Pushes the object specified by obj_ptr to stack.
  //
  void Push(Obj* obj_ptr) {
    while (1) {
      Obj* next_ptr = top_ptr;
      obj_ptr->next = next_ptr;
      // If the top node is still next, then assume no one has changed the stack.
      // (That statement is not always true because of the ABA problem)
      // Atomically replace top with obj.
      if (top_ptr.compare_exchange_weak(next_ptr, obj_ptr)) {
        return;
      }
      // The stack has changed, start over.
    }
  }
};

考虑有两个线程并发的访问该队列。

初始时，栈顶元素是 A，A 指向 B，B 指向 C。

top --> A --> B --> C

• Thread 1 执行 pop 操作，将栈顶元素 A 弹出，取出了top_ptr, 和 next_ptr后被中断。

Obj* ret_ptr = top_ptr;
if (ret_ptr == nullptr) return nullptr;
      // For simplicity, suppose that we can ensure that this dereference is safe
      // (i.e., that no other thread has popped the stack in the meantime).
  Obj* next_ptr = ret_ptr->next;

此刻，Thread 1里看到的是top_ptr等于A， next_ptr 等于B，问题其实就在这里了，保证top_ptr等于A时，并不能保证next_ptr等于B。

• Thread 2 执行 pop 操作，将栈顶元素从 A 改为 B。

top --> B --> C

• Thread 2 再次执行 pop 操作，将栈顶元素从 B 改为 C。

top --> C

• Thread 2 执行 push 操作，将元素 A 推回到栈顶。

top --> A --> C

• Thread 1 继续执行，执行 compare_exchange_weak(A, B)，由于 top == ret，操作成功，栈顶元素变为了 B。
  此刻

top --> B(already delete)

• Thread 1 访问栈顶元素，但是 B 已经被删除，这导致了 ABA 问题。

当从列表中删除一个项目并释放其内存后，如果再次分配一个新项目并将其添加到列表中，由于最近最常使用（MRU）的内存分配策略，新分配的对象通常会位于被删除对象的相同位置。
或者是在启用缓存机制时，重新分配的对象也有极大的概率是之前释放的对象。

ABA问题解决方案

在原有的内容上添加额外的“标签”或“戳记”位。例如，使用比较和交换（compare and swap）操作指针的算法可以使用地址的低位来表示指针成功修改的次数。因此，即使地址相同，下一次比较和交换操作也会失败，因为标签位不匹配。这种情况有时被称为ABA?，因为第二个A与第一个略有不同。这种带标签的状态引用也被用于事务内存（transactional memory）中。

在实现中，可以使用带标签的指针来解决ABA问题，其中指针的低位用于存储标签信息。然而，如果支持双宽比较和交换（double-width CAS），更常见的做法是使用单独的标签字段。

通过使用标签位，每次对共享数据进行操作时都会更新标签，即使地址相同，标签的变化也能够反映出对象的修改历史。这样，在进行比较和交换操作时，除了比较地址外，还需要比较标签位，从而更可靠地检测到对象的变化。

如果“标签”字段发生了环绕（wraparound），那么对抗ABA问题的保证就不再有效。然而，根据观察，在当前存在的CPU上，并且使用60位标签，只要程序的生命周期（即在不重新启动程序的情况下）限制在10年内，就不会发生环绕；此外，有人认为，为了实际目的，通常只需拥有40-48位的标签来确保不会发生环绕。由于现代CPU（特别是所有现代x64 CPU）倾向于支持128位的CAS（比较和交换）操作，这可以提供对抗ABA问题的可靠保证。

当使用128位CAS操作时，除了存储指针地址外，还可以存储一个更大的标签值。因为标签位数更多，所以即使在长时间运行的程序中，标签的环绕概率也非常低，几乎可以忽略不计。

通过使用128位CAS操作，并保留足够长度的标签位，可以提供对抗ABA问题的坚实保证。这意味着在多线程或并发环境中，即使对象的地址没有改变，只要标签发生变化，CAS操作也会失败，从而可以正确检测到对象的变化。这种方法在实践中被广泛采用，以确保数据的一致性和并发操作的正确性。

所谓的版本号、标记基本都是采用这个原理。