基于CAS分析对ABA问题的一点思考

什么是CAS？

背景

synchronized加锁消耗太大
volatile只保证可见性,不保证原子性

基础

用CPU提供的特殊指令，可以:

1. 自动更新共享数据;
2. 能检测到是否有其他线程的干扰;

CAS(Compare and Swap)

不加锁而是尝试去完成替换(写)操作，如果失败就重试，直到成功;

分析

// AtomicInteger
public class AtomicInteger extends Number implements java.io.Serializable {
    private static final Unsafe unsafe = Unsafe.getUnsafe(); // 直接操作内存的底层类
    private static final long valueOffset; // value属性的内存位置
    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value; // 用volatile保证可见性

    public final int addAndGet(int delta) { // 更新操作入口
        return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
    }

    ...

}

// Unsafe
public final class Unsafe {
    // 添加操作
    public final int getAndAddInt(Object obj, long valueOffset, int delta) {
        int value;
        do {
            value = this.getIntVolatile(obj, valueOffset); // 取出最新值
            // 一直尝试替换操作,直到成功替换
        } while(!this.compareAndSwapInt(obj, valueOffset, value, value + delta));
        return value;
    }

    // 本地的比较方法
    public final native boolean compareAndSwapInt(Object obj, long valueOffset, int expect, int update);

}

总结

比之于悲观的加锁阻塞,乐观的CAS算法是非阻塞的. J.U.C(java.util.concurrent)是建立在CAS之上的,所以在性能上有很大的优势;

什么是ABA问题

*对ABA的说明很形象,大意是:
你提着很多现金的包去机场,这时来了个辣妹挑逗你,并趁你不注意时用一个一模一样的空包换了你的现金包,然后她就走了,此时你发现你的包还在,于是就是拿着包去赶飞机了.

注意几个关键字眼: 现金包, 辣妹, 空包, 一模一样, 发现包还在;

翻译成代码

有链表： A->B->NULL;
此时线程1想移除A把表头替换成B: list.compareAndSet(A,B);

但是还没执行,线程2抢占了时间片,它把B移除了并添加了节点C。
链表: A->C->null, 此时B游离: B->null;

这时又轮到线程1执行了,检查发现list表头还是A,所以进行替换操作。这样做就导致了C节点数据丢失。

分析

这里不论是皮包还是节点,都有一个特点: 非基本数据类型, 即壳的内部还有数据;
辣妹就是抢占了时间片的线程, "一模一样"和"发现包还在"都是只检查了壳而并没有检查内部数据,所以导致ABA问题,丢了C节点;

// Node
public static class Node {
    char value;
    Node next;

    public Node(char value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object obj) {
        System.out.println("equals"); // compareAndSet是native的并没有走equals
        return super.equals(obj);
    }
}

// test
public static void main(String... arg) throws InterruptedException {
    Node a = new Node('A');
    Node b = new Node('B');
    Node c = new Node('C');

    a.next = b;
    AtomicReference<Node> stack = new AtomicReference<>(a);

    a.next = c; // 改变了内部数据,但是比较时任然认为A还是原来的A
    boolean x = stack.compareAndSet(a, b);

    System.out.println(x); // x == true
}

个人感觉解决了equals的问题上层就可控制ABA问题了。

这就和比较两个文件一样: 可以根据内容逐行扫描(equals),也可以摘要比较(如文件MD5);
而这里只要一个比较结果,采用标记或摘要的方式明显效率上有优势;
想必AtomicMarkableReference和AtomicStampedReference应该就是出于这样的一种想法设计吧;