介绍#

ABA问题是并发编程中，在使用无锁（lock-free）算法，特别是基于比较并交换（Compare-And-Swap, CAS）操作时可能出现的一种逻辑错误。

它之所以被称为”ABA”问题，是因为一个变量的值从 A 变成了 B，然后又变回了 A。对于一个只检查当前值是否等于期望值的CAS操作来说，它会认为值没有发生变化，从而成功执行操作，但实际上变量在期间已经被修改过了。

ABA问题发生的场景及危害#

想象一个无锁的栈（Stack），其 pop() 操作需要原子地更新栈顶元素。

假设初始状态： 栈顶 top 指向元素 A。

正常 pop 操作流程：

线程1读取当前栈顶元素 A。
线程1准备将栈顶更新为 A.next (假设是 null)。
线程1执行 top.compareAndSet(A, A.next)，如果成功，A 被弹出。

ABA问题发生过程：

线程1 读取当前栈顶元素，发现是 A。它记下 A，并准备执行 CAS(A, C)。
```
1
top -> A -> B -> D
2
Thread 1 reads top: A
```

线程2 此时突然执行，它将 A 弹出。

1
top -> B -> D  (A is now removed)
2
Thread 2 pops A

线程2 又将一个**新的元素 A （或者一个值和 A 相同但实际上是不同对象的元素）**压入栈。 注意：这里的“新的元素A”指的是一个与最开始的A值相同，但内存地址可能不同，或者即便内存地址相同，其内部状态已经发生过变化的对象。
```
1
top -> A -> B -> D  (This A is NOT the original A, it's a new one!)
2
Thread 2 pushes A back
```
线程1 恢复执行 CAS(A, C)。它检查当前栈顶是否是它之前读取的 A。由于栈顶现在又指向了 A（尽管是新的 A），compareAndSet 操作会认为当前值等于期望值 A，并成功将栈顶更新为 C。
```
1
top -> C       (Thread 1's CAS(A, C) succeeds!)
```

危害： 尽管线程1的CAS操作成功了，但它操作的实际上是一个新的 A，而不是它最初读取的那个 A。如果 A 的内部状态（比如它的 next 指针）在这期间被改变了，那么线程1的后续操作可能会导致：

数据结构损坏：例如，在链表中，节点指针可能指向错误的位置。
逻辑错误：程序基于过时的或不正确的状态信息做出决策。
内存泄漏：旧的 A （或其他被弹出又压入的元素）可能永远无法被垃圾回收。

1
package org.example.aba;
2

3
import java.util.concurrent.atomic.AtomicReference;
4

5
class Node {
6
    public final String item; // 节点内容
7
    public Node next; // 下一个节点的引用
8

9
    public Node(String item) {
10
        this.item = item;
11
    }
12

13
    @Override
14
    public String toString() {
15
        return item;
16
    }
17
}
18

19
class LockFreeStackABA {
20
    private AtomicReference<Node> top = new AtomicReference<>();
21

22
    // 压入栈顶
23
    public void push(String item) {
24
        Node newHead = new Node(item);
25
        Node oldHead;
26
        do {
27
            oldHead = top.get();
28
            newHead.next = oldHead;
29
        } while (!top.compareAndSet(oldHead, newHead));
30
        System.out.println(Thread.currentThread().getName() + " 压入: " + item + " (当前栈顶: " + top.get() + ")");
31
    }
32

33
    // 弹出栈顶
34
    public Node pop() {
35
        Node oldHead;
36
        Node newHead;
37
        do {
38
            oldHead = top.get();
39
            if (oldHead == null) {
40
                System.out.println(Thread.currentThread().getName() + " 尝试弹出，但栈为空！");
41
                return null;
42
            }
43
            newHead = oldHead.next;
44
            System.out.println(Thread.currentThread().getName() + " 尝试弹出 " + oldHead.item +
45
                    " (期望栈顶: " + oldHead + ", 更新栈顶至: " + newHead + ")");
46
        } while (!top.compareAndSet(oldHead, newHead)); // CAS操作：如果当前栈顶仍是oldHead，则更新为newHead
47
        System.out.println(Thread.currentThread().getName() + " 成功弹出: " + oldHead.item + " (当前栈顶: " + top.get() + ")");
48
        return oldHead;
49
    }
50

51
    // 打印栈内容
52
    public void printStack() {
53
        System.out.print("当前栈: ");
54
        Node current = top.get();
55
        if (current == null) {
56
            System.out.println("空");
57
            return;
58
        }
59
        StringBuilder sb = new StringBuilder();
60
        while (current != null) {
61
            sb.append(current.item).append(" -> ");
62
            current = current.next;
63
        }
64
        sb.setLength(sb.length() - 4); // 移除最后的 " -> "
65
        System.out.println(sb.toString());
66
    }
67

68
    // 获取栈顶节点
69
    public Node getTop() {
70
        return top.get();
71
    }
72
}
73

74
public class AbaAppear {
75
    public static void main(String[] args) throws InterruptedException {
76
        LockFreeStackABA stack = new LockFreeStackABA();
77

78
        // 1. 初始状态：栈中逐步压入 A、B、C
79
        stack.push("C"); // 栈顶：C
80
        stack.push("B"); // 栈顶：B → C
81
        stack.push("A"); // 栈顶：A → B → C
82

83
        Node originalNodeA = stack.getTop(); // 获取当前栈顶的 A 节点引用
84

85
        System.out.println("\n--- 初始栈内容 ---");
86
        stack.printStack();
87

88
        // 2. 线程1 启动，读取栈顶元素后等待
89
        Thread thread1 = new Thread(() -> {
90
            Node readNode = stack.getTop(); // 线程1在原栈中看到栈顶元素 A
91
            System.out.println("\n线程-1 读取到栈顶节点: " + readNode);
92
            try {
93
                Thread.sleep(200); // 等待线程2的干扰行为发生
94
            } catch (InterruptedException e) {
95
                e.printStackTrace();
96
            }
97
            System.out.println("\n线程-1 开始尝试弹出栈顶节点...");
98
            Node popNode = stack.pop(); // 线程1尝试弹出栈顶（被线程2修改为新 A）
99
            if (readNode == popNode) {
100
                System.out.println("同一个节点");
101
            }else {
102
                System.out.println("不是同一个节点，ABA问题已重现！");
103
            }
104
        }, "线程-1");
105

106
        // 3. 线程2 启动，执行 ABA 序列
107
        Thread thread2 = new Thread(() -> {
108
            System.out.println("\n--- 线程-2 执行 ABA 序列 ---");
109
            stack.pop(); // 弹出 A，栈顶变为 B
110
            stack.pop(); // 弹出 B，栈顶变为 C
111
            stack.push("X"); // 压入一个新节点 X，栈顶变为 X → C
112
            stack.push("A"); // 再压入一个新的 A，栈顶变为 A → X → C
113
            System.out.println("--- 线程-2 完成 ABA 序列 ---");
114
            stack.printStack();
115
        }, "线程-2");
116

117
        thread1.start(); // 启动线程1
118
        thread2.start(); // 启动线程2
119

120
        thread1.join(); // 等待线程1完成
121
        thread2.join(); // 等待线程2完成
122

123
        System.out.println("\n--- 最终栈内容 ---");
124
        stack.printStack();
125
        System.out.println("当前栈顶节点: " + stack.getTop());
126
        if (stack.getTop() != null) {
127
            System.out.println("栈顶节点的 next: " + stack.getTop().next);
128
        }
129
    }
130
}

如何解决ABA问题#

解决ABA问题的主要方法是引入一个版本号（或时间戳）机制。每次修改变量时，不仅修改值，也同时修改版本号。CAS操作时，需要同时比较值和版本号。

使用AtomicStampedReference解决问题

1
package org.example.aba;
2

3
import lombok.extern.slf4j.Slf4j;
4

5
import java.util.concurrent.TimeUnit;
6
import java.util.concurrent.atomic.AtomicStampedReference;
7

8
@Slf4j
9
public class AbaSolve {
10
    static AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);
11

12
    public static void main(String[] args) {
13
        log.debug("main start ....");
14
        String prev = ref.getReference();
15
        int stamp = ref.getStamp();
16
        log.debug("stamp: {}", stamp);
17

18
        other();
19
        try {
20
            TimeUnit.SECONDS.sleep(1);
21
        } catch (InterruptedException e) {
22
            throw new RuntimeException(e);
23
        }
24
        log.debug("change A -> C {} ", ref.compareAndSet(prev, "C", stamp, stamp + 1));
25
    }
26

27
    private static void other() {
28
        new Thread(() -> {
29
            int stamp = ref.getStamp();
30
            log.debug("{} 's stamp is : {}",Thread.currentThread().getName(),stamp);
31
            log.debug("change A-> B {} ", ref.compareAndSet(ref.getReference(), "B", stamp, stamp + 1));
32
            stamp = ref.getStamp();
33
            log.debug("{} 's changed stamp is : {}",Thread.currentThread().getName(),stamp);
34
        }, "t1").start();
35
        try {
36
            TimeUnit.MILLISECONDS.sleep(500);
37
        } catch (InterruptedException e) {
38
            throw new RuntimeException(e);
39
        }
40
        new Thread(()->{
41
            int stamp = ref.getStamp();
42
            log.debug("{} 's stamp is : {}",Thread.currentThread().getName(),stamp);
43
            log.debug("change B->A {}",ref.compareAndSet(ref.getReference(),"A",stamp,stamp + 1));
44
            stamp = ref.getStamp();
45
            log.debug("{} 's changed stamp is : {}",Thread.currentThread().getName(),stamp);
46
        },"t2").start();
47
    }
48
}