CAS自旋锁到底是什么？为什么能实现线程安全？

CAS自旋锁到底是什么？为什么能实现线程安全？ 介绍

CAS（Compare and swap），即比较并交换。我们平时所说的自旋锁或乐观锁，其中的核心 *** 作实现就是CAS。

保证原子 *** 作

CAS 适用于保证原子 *** 作不被干扰。原子 *** 作即最小不可拆分的 *** 作，也就是说 *** 作一旦开始，就不能被打断，直到 *** 作完成。
在多线程环境下，原子 *** 作是保证线程安全的重要手段。
比如说，假设有两个线程在工作，都想对某个值做修改，就拿自增 *** 作来说吧，要对整数 i 进行自增 *** 作，需要做三个步骤：

1. 从内存读取 i 的当前值
2. 对 i 值进行加 1 *** 作
3. 将 i 值写回内存

假设两个进程都读取了 i 的当前值，当前值为 0。
这时候 A 线程对 i 加 1 了，B 线程也加 1，最后 i 的是 1 ，而不是 2。

这是因为自增 *** 作不是原子 *** 作，分成的这三个步骤可以被干扰。

再如下面这个例子，10个线程，每个线程都执行 10000次 i++ *** 作，我们期望的值是 100000，但是很遗憾，结果总是小于 100000 的。

public class Main {

    static int i = 0;

    private synchronized static void add() {
        i++;
    }

    private static class plus implements Runnable {
        @Override
        public void run() {
            for (int k = 0; k < 10000; k++) {
                add();
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Thread[] threads = new Thread[10];
        for (int i = 0; i < 10; i++) {
            threads[i] = new Thread(new plus());
            threads[i].start();
        }

        for (int i = 0; i < 10; i++) {
            threads[i].join();
        }
        System.out.println(i);
    }
}

可以加锁或者利用 synchronized 实现：

public synchronized static void add(){
        i++;
    }

或者，加锁 *** 作，如使用 ReentrantLock （可重入锁）实现。

private static Lock lock = new ReentrantLock();
    public static void add(){
        lock.lock();
        i++;
        lock.unlock();
    }

CAS 实现自旋锁

既然用锁或 synchronized 关键字可以实现原子 *** 作，那么为什么还要用 CAS 呢，因为加锁或使用 synchronized 关键字带来的性能损耗较大，而用 CAS 可以实现乐观锁，它实际上是直接利用了 CPU 层面的指令，所以性能很高。

上面也说了，CAS 是实现自旋锁的基础，CAS 利用 CPU 指令保证了 *** 作的原子性，以达到锁的效果。自旋就是循环，一般是用无限循环实现。这样一来，一个无限循环中，执行一个 CAS *** 作，当 *** 作成功，返回 true 时，循环结束；当返回 false 时，接着执行循环，继续尝试 CAS *** 作，直到返回 true。

其实 JDK 中有好多地方用到了 CAS ，上篇博文中说到ConcurrentHashMap中元素添加是线程安全的，就是利用CAS自旋锁实现的。

	//...其他代码省略
        // CAS 自旋，保证线程安全
        while ((tab = table) == null || tab.length == 0) {
        	// sizeCtl 小于0，表示正在初始化 或 正在扩容
            if ((sc = sizeCtl) < 0)
            	// 让出线程
                Thread.yield(); // lost initialization race; just spin
            // CAS（自旋锁） 修改sizeCtl的值为-1.成功则继续初始化，失败则继续自旋
            // compareAndSwapInt 读取传入当前内存中偏移量为SIZECTL位置的值与期望值sc作比较。相等就把-1赋值给SIZECTL位置的值，再返回true。不相等则返回false。
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                    	// sizeCtl为0，取默认长度DEFAULT_CAPACITY=16，否则用sizeCtl的值（回顾：sizeCtl为正数且未初始化表示数组初始容量）
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        // 构建数组对象
                        Node[] nt = (Node[])new Node[n];
                        table = tab = nt;
                        // 计算扩容阈值=数组初始容量*0.75（回顾：sizeCtl为正数且已初始化表示数组的扩容阈值）
                        sc = n - (n >>> 2);
                    }
                } finally {
                	// 扩容阈值赋值给sizeCtl
                    sizeCtl = sc;
                }
                break;
            }
        }
      //...其他代码省略

其中用到了 compareAndSwapInt方法，这就是实现 CAS 的核心方法了。
unsafe.compareAndSwapInt(this, valueOffset, e, u) 方法，它是个 native 方法，是用 c++ 实现的。作用在于利用了 CPU 的 cmpxchg 指令完成比较并替换。这也是CAS（比较并交换）的思想，用于保证并发时的无锁并发的安全性。

使用场景

• CAS 适合简单对象的 *** 作，比如布尔值、整型值等
• CAS 适合冲突较少的情况，如果太多线程在同时自旋，那么长时间循环会导致 CPU 开销很大

ABA问题

CAS 存在一个问题，就是一个值从 A 变为 B ，又从 B 变回了 A，这种情况下，CAS 会认为值没有发生过变化，但实际上是有变化的。对此，并发包下倒是有 AtomicStampedReference 提供了根据版本号判断的实现，可以解决一部分问题。