CAS（Compare-and-Swap）是一种乐观锁的实现方式，全称为“比较并交换”，是一种无锁的原子操作。

一、乐观锁与悲观锁

悲观锁

对于悲观锁来说，它总是认为每次访问共享资源时会发生冲突，所以必须对每次数据操作加上锁，以保证临界区的程序同一时间只能有一个线程在执行。比如synchronized

乐观锁

乐观锁，顾名思义，它是乐观派。乐观锁总是假设对共享资源的访问没有冲突，线程可以不停地执行，无需加锁也无需等待。一旦多个线程发生冲突，乐观锁通常使用一种称为 CAS 的技术来保证线程执行的安全性。

由于乐观锁假想操作中没有锁的存在，因此不太可能出现死锁的情况，换句话说，乐观锁天生免疫死锁。

乐观锁多用于“读多写少“的环境，避免频繁加锁影响性能；
悲观锁多用于”写多读少“的环境，避免频繁失败和重试影响性能。

二、什么是 CAS

在 CAS 中，有这样三个值：

V：要更新的变量(var)
E：预期值(expected)
N：新值(new)

比较并交换的过程如下：

判断 V 是否等于 E，如果等于，将 V 的值设置为 N；如果不等，说明已经有其它线程更新了 V，于是当前线程放弃更新，什么都不做。

这里的预期值 E 本质上指的是“旧值”。

当多个线程同时使用 CAS 操作一个变量时，只有一个会胜出，并成功更新，其余均会失败，但失败的线程并不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作。

三、CAS 的原理

在 Java 中，如果一个方法是 native 的，那 Java 就不负责具体实现它，而是交给底层的 JVM 使用 C 语言或者 C++ 去实现。

在 Java 中，有一个Unsafe类，它在sun.misc包中。它里面都是一些native方法，其中就有几个是关于 CAS 的：

boolean compareAndSwapObject(Object o, long offset,Object expected, Object x);
boolean compareAndSwapInt(Object o, long offset,int expected,int x);
boolean compareAndSwapLong(Object o, long offset,long expected,long x);

Unsafe 对 CAS 的实现是通过 C++ 实现的，它的具体实现和操作系统、CPU 都有关系。

Linux 的 X86 下主要是通过cmpxchgl这个指令在 CPU 上完成 CAS 操作的，但在多处理器情况下，必须使用lock指令加锁来完成。当然，不同的操作系统和处理器在实现方式上肯定会有所不同。

CMPXCHG是“Compare and Exchange”的缩写，它是一种原子指令，用于在多核/多线程环境中安全地修改共享数据。CMPXCHG在很多现代微处理器体系结构中都有，例如Intel x86/x64体系。对于32位操作数，这个指令通常写作CMPXCHG，而在64位操作数中，它被称为CMPXCHG8B或CMPXCHG16B。

Unsafe 里面还有其它的方法。比如支持线程挂起和恢复的park和unpark 方法， LockSupport 类底层就调用了这两个方法。还有支持反射操作的allocateInstance()方法。

四、CAS 的三大问题

ABA 问题

所谓的 ABA 问题，就是一个值原来是 A，变成了 B，又变回了 A。这个时候使用 CAS 是检查不出变化的，但实际上却被更新了两次。

ABA 问题的解决思路是在变量前面追加上版本号或者时间戳。从 JDK 1.5 开始，JDK 的 atomic 包里提供了一个类AtomicStampedReference类来解决 ABA 问题。

这个类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果二者都相等，才使用 CAS 设置为新的值和标志。

自旋开销大怎么解决？

CAS 失败时会不断自旋重试，如果一直不成功，会给 CPU 带来非常大的执行开销。

可以加一个自旋次数的限制，超过一定次数，就切换到 synchronized 挂起线程。

int MAX_RETRIES = 10;
int retries = 0;
while (!atomicInt.compareAndSet(expect, update)) {
    retries++;
    if (retries > MAX_RETRIES) {
        synchronized (this) { // 超过次数，使用 synchronized 处理
            if (atomicInt.get() == expect) {
                atomicInt.set(update);
            }
        }
        break;
    }
}

涉及到多个变量同时更新怎么办？

可以将多个变量封装为一个对象，使用 AtomicReference 进行 CAS 更新。

class Account {
    static class Balance {
        final int money;
        final int points;

        Balance(int money, int points) {
            this.money = money;
            this.points = points;
        }
    }

    private AtomicReference<Balance> balance = new AtomicReference<>(new Balance(100, 10));

    public void update(int newMoney, int newPoints) {
        Balance oldBalance, newBalance;
        do {
            oldBalance = balance.get();
            newBalance = new Balance(newMoney, newPoints);
        } while (!balance.compareAndSet(oldBalance, newBalance));
    }
}

目录CONTENT

Java中CAS