// Adding a lock prefix to an instruction on MP machine // VC++ doesn't like the lock prefix to be on a single line // so we can't insert a label after the lock prefix. // By emitting a lock prefix, we can define a label after it. #define LOCK_IF_MP(mp) __asm cmp mp, 0 \ __asm je L0 \ __asm _emit 0xF0 \ __asm L0:
在某个时刻,线程1 试图将栈顶换成 B,但它获取栈顶的 oldValue(为A)后,被 线程2 中断了。线程2 依次将A、B 弹出,然后压入 C、D、A。然后换 线程1 继续运行,线程1 执行 compareAndSet 发现 head 指向的元素确实与 oldValue 一致,都是 A,所以就将 head 指向 B 了。但是,注意第 19 行代码,线程2 在弹出 B 的时候,将 B 的 next 置为 null 了,因此在 线程1 将 head 指向 B 后,栈中只剩了一个孤零零的元素 B。但按预期来说,栈中应该放的是 B → A → D → C
GC 对 ABA 的影响
ConcurrentLinkedQueue 是一个基于 CAS 实现无锁、线程安全的队列,内部使用 CAS 来管理队列的头和尾指针。在 ConcurrentLinkedQueue 中大神道格·李注释到:
1 2 3 4 5 6
Note that like most non-blocking algorithms in this package, this implementation relies on the fact that in garbage collected systems, there is no possibility of ABA problems due to recycled nodes, so there is no need to use "counted pointers" or related techniques seen in versions used in non-GC'ed settings.
ConcurrentLinkedQueue 的实现很大程度上依赖于 Java 的垃圾收集(GC)系统来防止 ABA 问题
在没有垃圾收集的环境中(例如 C 或 C++),当删除节点时(例如调用free()或delete ),可以 回收 该内存位置以供将来分配。因此,相同的内存地址可以重复用于不同的节点或对象,这可能会导致 ABA 问题
publicvoidpush(T value) { // 每 push 一个元素都会 new 一个 Node 对象,即使 value 相同,也不会出现结构紊乱 Node<T> newNode = newNode<>(value); Node<T> oldHead; do { oldHead = head.get(); newNode.next = oldHead; } while (!head.compareAndSet(oldHead, newNode)); size.incrementAndGet(); }
public T pop() { Node<T> oldHead; Node<T> newHead; do { oldHead = head.get(); if (oldHead == null) returnnull; newHead = oldHead.next; } while (!head.compareAndSet(oldHead, newHead)); size.decrementAndGet(); return oldHead.value; }
publicintsize() { return size.get(); }
privatestaticclassNode<T> { final T value; Node<T> next;
Node(T value) { this.value = value; }
@Override public String toString() { return value == null ? "null" : value.toString(); } } }
较通用的方式是引入一个版本号,每更新一次就更新新的版本号,如此一来 A -> B -> A 就变为了 A1 -> B2 -> A3,这样就解决了 ABA 的问题。JDK 中的 AtomicStampedReference 提供了解决 ABA 问题的方法,它的 compareAndSet 方法首先会检查当前引用是否等于预期引用,并且检查当前标志是否等于预期标志,如果全部相等,则以 CAS 更新