CAS，Compare and set。是Java中实现原子操作的重要手段，在Java并发工具中起着重要作用。

CAS是什么

CAS是一种多线程同步中常用的原子操作。在CAS中，有三个重要的参数：内存值V、旧的预期值A、要更新成为的值B，当且仅当内存值V等于旧的预期值A时，才把内存值V更改成B。基于CAS操作，可以实现乐观锁机制，乐观锁的思想是认为数据一般情况下不会发生冲突，所以在数据提交更新的时候，才会对冲突进行检测。乐观锁是种思想，而CAS是这种思想的一种实现方式。注意，CAS是一种操作，CAS一般配合自旋来实现乐观锁机制。

让我们以AtomicInteger为例来看看CAS的应用。

1
2
3
4
5
6
7

private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe();

private static final long VALUE = U.objectFieldOffset(AtomicInteger.class, "value");

public final int addAndGet(int delta) {
    return U.getAndAddInt(this, VALUE, delta) + delta;
}

其中，VALUE是变量值在内存中的地址，delta是在原值基础上要加的值。

调用unsafe的方法

1
2
3
4
5
6
7
8
9
10
11
12
13

public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);
    } while (!weakCompareAndSetInt(o, offset, v, v + delta));
    return v;
}

public final boolean weakCompareAndSetInt(Object o, long offset,
                                              int expected,
                                              int x) {
        return compareAndSetInt(o, offset, expected, x);
    }

其中，getIntVolatile 和compareAndSetInt都是调用的native方法，从getIntVolatile可以看出利用CAS进行不断重试，注意，CAS只是一次操作，native方法compareAndSetInt的四个参数：对象、对象的地址、预期值和修改值。

CAS缺点

竞争激烈时开销大

在竞争激励时，CAS失败的概率比较大，如果循环CAS，则可能出现CAS长时间不成功会给CPU带来非常大的执行开销。

只能实现一个共享变量的原子操作

可以使用AtomicReference类来保证引用对象的原子性，把多个变量放在一个对象里进行CAS操作。

ABA问题

ABA问题即，如果一个值原来是A，中间变成了B，后来又变成了A。这时候CAS检查时会认为没有发生变化。这就是ABA问题。ABA问题会带来什么隐患呢。

ABA隐患

在Java这种垃圾回收型的语言中，可以避免一种比较典型的ABA问题。以C++为例

A common case of the ABA problem is encountered when implementing a lock-free data structure. If an item is removed from the list, deleted, and then a new item is allocated and added to the list, it is common for the allocated object to be at the same location as the deleted object due to optimization. A pointer to the new item is thus sometimes equal to a pointer to the old item which is an ABA problem.

C++中，对指针进行CAS操作，即使两个指针相同，它们也未必指向同一个对象。有可能是第一个指针所指向的内存被释放后，第二个对象恰好分配在相同地址的内存。

而在GC环境中，两个引用相等，其指向对对象必然相等，因为只要对象存在引用，其对象的内存就不会被回收掉，那么新new出来的对象地址也不可能重复。

当然，Java中也存在ABA问题，在链表结构中容易出现。

如下例子：

线程1准备用CAS将变量的值由A替换为B，在此之前，线程2将变量的值由A替换为C，又由C替换为A，然后线程1执行CAS时发现变量的值仍然为A，所以CAS成功。但实际上这时的现场已经和最初不同了，尽管CAS成功，但可能存在潜藏的问题，例如下面的例子：

现有一个用单向链表实现的堆栈，栈顶为A，这时线程T1已经知道A.next为B，然后希望用CAS将栈顶替换为B：

head.compareAndSet(A,B)

在T1执行上面这条指令之前，线程T2介入，将A、B出栈，再pushD、C、A，此时堆栈结构如下图，而对象B此时处于游离状态：

此时轮到线程T1执行CAS操作，检测发现栈顶仍为A，所以CAS成功，栈顶变为B，但实际上B.next为null，所以此时的情况变为：

其中堆栈中只有B一个元素，C和D组成的链表不再存在于堆栈中，平白无故就把C、D丢掉了。

ABA问题解决

ABA问题可以通过版本号进行解决，利用AtomicStampedReference可以解决 这个问题，AtomicStampedReference主要维护包含一个对象引用以及一个可以自动更新的整数”stamp”的pair对象来解决ABA问题。

利用CAS实现线程安全的单例

不使用synchronized和lock，如何实现一个线程安全的单例？可以利用CAS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class Singleton {
    private static final AtomicReference<Singleton> INSTANCE = new AtomicReference<Singleton>(); 

    private Singleton() {}

    public static Singleton getInstance() {
        for (;;) {
            Singleton singleton = INSTANCE.get();
            if (null != singleton) {
                return singleton;
            }

            singleton = new Singleton();
            if (INSTANCE.compareAndSet(null, singleton)) {
                return singleton;
            }
        }
    }
}