【并发编程】 --- Compare And Swap（CAS）原理分析

源码地址：https://github.com/nieandsun/concurrent-study.git

---

1 什么是CAS？

---

1.1 加锁和CAS解决原子性问题的不同原理

首先看如下代码：

package com.nrsc.ch2.cas;

import java.util.ArrayList;
import java.util.List;

public class CasDemo {

    //共享资源
    static int i = 0;

    public static void increase() {
        i++;
    }

    public static void main(String[] args) throws InterruptedException {
        Runnable r = () -> {
            for (int j = 0; j < 1000; j++) {
                increase();
            }
        };

        List<Thread> threads = new ArrayList<>();
        for (int j = 0; j < 10; j++) {
            Thread thread = new Thread(r);
            threads.add(thread);
            thread.start();
        }

        //确保前面10个线程都走完
        for (Thread thread : threads) {
            thread.join();
        }

        System.out.println(i);
    }
}

相信每个人都知道这段代码由于i++不是原子操作,因此会导致这10个线程执行后的最终结果不是10*1,000 = 10,000。
当然也相信几乎所有人都知道通过加锁可以解决这个问题，加锁方式解决该问题的原理基本可以用下图进行概况：

而其实除了加锁之外利用CAS机制也能解决这个问题。既然说它是除了加锁之外的另一种解决方式，那它肯定是无锁的，因此利用CAS机制解决该问题的方式大致可以用下图进行概况：

那到底啥是CAS呢？它又是是如何解决这个问题的呢？

---

1.2 CAS原理分析

先看定义(摘自百度百科)：

compare and swap，解决多线程并行情况下使用锁造成性能损耗的一种机制，CAS操作包含三个操作数——内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。无论哪种情况，它都会在CAS指令之前返回该位置的值。CAS有效地说明了“我认为位置V应该包含值A；如果包含该值，则将B放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。"

再画个图解释一下：

---

2 CAS可能的问题

---

2.1 ABA问题

说实话刚接触CAS的时候，其实我就想到ABA这个问题了。☺☺☺

通过1.2可以知道，CAS需要在操作值的时候，检查值有没有发生变化，如果没有发生变化就更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了 —> 这就是所谓的ABA问题。

举个通俗点的例子，你倒了一杯水放桌子上，干了点别的事，然后同事把你水喝了又给你重新倒了一杯水，你回来看水还在，拿起来就喝，如果你不管水中间被人喝过，只关心水还在，还好 ； 但是假若你是一个比较讲卫生的人，那你肯定就不高兴了。。。

ABA问题的解决思路其实也很简单，就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加1，那么A→B→A就会变成1A→2B→3A了。

---

2.2 循环时间长开销大

自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。

---

2.3只能保证一个共享变量的原子操作

当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁。

还有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如，有两个共享变量i＝2，j=a，合并一下ij=2a，然后用CAS来操作ij。从Java 1.5开始，JDK提供了AtomicReference类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行CAS操作。

---

3 JDK中对CAS的支持 — unsafe类

java中提供了对CAS操作的支持，具体在sun.misc.unsafe类中，声明如下:

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

上面各个参数的含义：

• 参数var1:表示要操作的对象
• 参数var2:表示要操作对象中属性地址的偏移量
• 参数var4:表示需要修改数据的期望的值
• 参数var5/var6:表示雷要修改为的新值

注意:Unsafe类使Java拥有了像C语言的指针一样操作内存空间的能力，同时也带来了指针的问题。过度的使 用Unsafe类会使得出错的几率变大，因此Java官方并不建议使用的，官方文档也几乎没有。Unsafe对 象不能直接调用，只能通过反射获得。

---

4 JDK中的相关原子操作类简介 — 底层CAS机制

---

4.1 AtomicInteger

• int addAndGet（int delta）：以原子方式将输入的数值与实例中的值（AtomicInteger里的value）相加，并返回结果。
• boolean compareAndSet（int expect，int update）：如果输入的数值等于预期值，则以原子方式将该值设置为输入的值。
• int getAndIncrement()：以原子方式将当前值加1，注意，这里返回的是自增前的值。
• int getAndSet（int newValue）：以原子方式设置为newValue的值，并返回旧值。

---

4.2 AtomicIntegerArray

主要是提供原子的方式更新数组里的整型，其常用方法如下。

• int addAndGet（int i，int delta）：以原子方式将输入值与数组中索引i的元素相加。
• boolean compareAndSet（int i，int expect，int update）：如果当前值等于预期值，则以原子方式将数组位置i的元素设置成update值。

需要注意的是，数组value通过构造方法传递进去，然后AtomicIntegerArray会将当前数组复制一份，所以当AtomicIntegerArray对内部的数组元素进行修改时，不会影响传入的数组。

---

4.3更新引用类型

原子更新基本类型的AtomicInteger，只能更新一个变量，如果要原子更新多个变量，就需要使用这个原子更新引用类型提供的类。Atomic包提供了以下3个类。

• AtomicReference
  原子更新引用类型。
• AtomicStampedReference
  利用版本戳的形式记录了每次改变以后的版本号，这样的话就不会存在ABA问题了。这就是AtomicStampedReference的解决方案。AtomicMarkableReference跟AtomicStampedReference差不多， AtomicStampedReference是使用pair的int stamp作为计数器使用，AtomicMarkableReference的pair使用的是boolean mark。 还是那个水的例子，AtomicStampedReference可能关心的是动过几次，AtomicMarkableReference关心的是有没有被人动过，方法都比较简单。
• AtomicMarkableReference：
  原子更新带有标记位的引用类型。可以原子更新一个布尔类型的标记位和引用类型。构造方法是AtomicMarkableReference（V initialRef，booleaninitialMark）。

---

4.4 原子更新字段类

如果需原子地更新某个类里的某个字段时，就需要使用原子更新字段类，Atomic包提供了以下3个类进行原子字段更新。
要想原子地更新字段类需要两步。第一步，因为原子更新字段类都是抽象类，每次使用的时候必须使用静态方法newUpdater()创建一个更新器，并且需要设置想要更新的类和属性。 第二步，更新类的字段（属性）必须使用public volatile修饰符。

• AtomicIntegerFieldUpdater：
  原子更新整型的字段的更新器。
• AtomicLongFieldUpdater：
  原子更新长整型字段的更新器。
• AtomicReferenceFieldUpdater：
  原子更新引用类型里的字段。

---