14 - CAS 无锁工具类的典范

CAS 无锁工具类的典范

- - 1. CAS 介绍
  - 2. CAS 解决原子性问题
  - 3. CAS 原理
  - 4. CAS 问题
  - - 4.1 ABA 问题
    - 4.2 自旋时间过长
    - 4.3 只能保证一个共享变量的原子操作
  - 5. Java 中的原子操作类
  - - 5.1 基本数据类型的原子操作类
    - 5.2 数组类型的原子操作类
    - 5.3 引用类型的原子操作类
    - 5.4 字段类型的原子操作类
    - 5.5 原子化的累加器
  - 6 总结

并发编程，为了保证数据的安全，需要满足三个特性：原子性、可见性、有序性。Java 中可以通过锁和 CAS 的方式来实现原子操作。

在《13 - synchronized 同步互斥锁》文章中介绍过，synchronized 是一个重量级操作，性能较差，CAS 在保证原子性中有较好的性能。此外，synchronized 的优化中，偏向锁、轻量级锁也都用的到了 CAS，那么，CAS 到底是什么？今天就来揭秘一下。

1. CAS 介绍

CAS，Compare And Swap，即比较并交换。整个 AQS 同步组件、Atomic 原子类操作等等都是以 CAS 实现的。可以说 CAS 是整个 J.U.C 的基石。

CAS 比较交换的过程 CAS(V,A,B)：V - 一个内存地址存放的实际值、A - 旧的预期值、B - 即将更新的值，当且仅当预期值 A 和内存值 V 相同时，将内存值修改为 B 并返回 true，否则什么都不做，并返回 false。

CAS VS synchronized

synchronized 是线程获取锁是一种悲观锁策略，即假设每一次执行临界区代码都会产生冲突，所以当前线程获取到锁的之后会阻塞其他线程获取该锁。

CAS（无锁操作）是一种乐观锁策略，它假设所有线程访问共享资源的时候不会出现冲突，所以出现冲突时就不会阻塞其他线程的操作，而是重试当前操作直到没有冲突为止。

2. CAS 解决原子性问题

前面我们多次提到一个累加器的例子，示例代码如下。在这个例子中，add10K() 这个方法不是线程安全的，问题就出在变量 count 的可见性和 count+=1 的原子性上。可见性问题可以用 volatile 来解决，而原子性问题我们前面一直都是采用的互斥锁方案，这里我们也可以使用 CAS 。

public class Test {
  	private int count = 0;

    private void add() {
        int idx = 0;
        while (idx ++ < 10000) {
            count += 1;
        }
    }

    private synchronized void add1() {
        int idx = 0;
        while (idx ++ < 10000) {
            count += 1;
        }
    }

    private AtomicInteger atomicCount = new AtomicInteger(0);
    private void add2() {
        int idx = 0;
        while (idx ++ < 10000) {
            atomicCount.getAndIncrement();
        }
    }

	public static void main(String[] args) throws Exception {
        TestCAS testCAS = new TestCAS();

        Thread t1 = new Thread(() -> {
            testCAS.add1();
        });
        Thread t2 = new Thread(() -> {
            testCAS.add1();
        });
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println(testCAS.count);

        Thread t3 = new Thread(() -> {
            testCAS.add1();
        });
        Thread t4 = new Thread(() -> {
            testCAS.add1();
        });
        t3.start();
        t4.start();

        t3.join();
        t4.join();
        System.out.println(testCAS.atomicCount);
	}
}

通过 synchronized 加锁之后，每次只能有一个线程访问 add1() 方法，能够保证最终得到 20000。但是 synchronized 加锁是个重量级操作，程序执行效率很低。利用 CAS，保证 atomicCount = atomicCount + 1 是原子性操作，最终得到结果 20000。

3. CAS 原理

探究 CAS 原理，其实就是探究上个例子中 atomicCount.getAndIncrement() 如何保证 atomicCount=atomicCount+1 是原子性操作，先通过源码看下。

AtomicInteger 类结构：

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 6214790243416807050L;

    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;
}

Unsafe 是 CAS 的核心类，由于 Java 方法无法直接访问底层系统，需要通过本地（native）方法来访问，Unsafe 相当于一个后门，基于该类可以直接操作特定内存的数据；
变量 valueOffset 表示该变量值在内存中的偏移地址，因为 Unsafe 就是根据内存偏移地址获取数据的原值；
变量 value 用 volatile 修饰，保证了多线程之间的内存可见性。

atomicCount.getAndIncrement()的实现如下：

public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);
}

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
    	// 根据对象 var1 和对象中该变量地址 var2，获取变量的值 var5
        var5 = this.getIntVolatile(var1, var2);
        
        // 比较并交换，返回是否交换成功
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

this.compareAndSwapInt(var1, var2, var5, var5 + var4)：

根据对象 var1 和对象中该变量地址 var2 获取变量当前的值 value；
比较 value 跟 var5，如果 value==var5，则 value=var5+var4 并返回 true。这步操作就是比较和替换操作，是原子性的；
如果 value!=var5，则返回 false，再去自旋循环到下一次调用 compareAndSwapInt 方法。

可见，getAndIncrement()的原子性是通过 compareAndSwapInt()中的第二步比较和替换保证的，那么 compareAndSwapInt()又是怎么保证原子性的呢？

compareAndSwapInt 方法是 JNI（Java Native InterfaceJAVA 本地调用），java 通过 C 来调用 CPU 底层指令实现的。

compareAndSwapInt 方法中的比较替换操作之前插入一个 lock 前缀指令，这个指令能过确保后续操作的原子性。

lock 前缀指令确保后续指令执行的原子性：

在Pentium及之前的处理器中，带有lock前缀的指令在执行期间会锁住总线，使得其它处理器暂时无法通过总线访问内存，很显然，这个开销很大；

在新的处理器中，Intel使用缓存锁定来保证指令执行的原子性，缓存锁定将大大降低lock前缀指令的执行开销。

CPU 提供了两种方法来实现多处理器的原子操作：总线加锁和缓存加锁。

总线加锁：总线加锁就是就是使用处理器提供的一个 LOCK#信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占使用共享内存。但是这种处理方式显得有点儿霸道，不厚道，他把 CPU 和内存之间的通信锁住了，在锁定期间，其他处理器都不能其他内存地址的数据，其开销有点儿大。所以就有了缓存加锁。
缓存加锁：其实针对于上面那种情况我们只需要保证在同一时刻对某个内存地址的操作是原子性的即可。缓存加锁就是缓存在内存区域的数据如果在加锁期间，当它执行锁操作写回内存时，处理器不在输出 LOCK#信号，而是修改内部的内存地址，利用缓存一致性协议来保证原子性。缓存一致性机制可以保证同一个内存区域的数据仅能被一个处理器修改，也就是说当 CPU1 修改缓存行中的 i 时使用缓存锁定，那么 CPU2 就不能同时缓存了 i 的缓存行。

比较替换操作过程分析

假设线程 A 和线程 B 同时调用 a.getAndIncrement()–>getAndIncrement()–>getAndAddInt()，AtomicInteger 里面的 value 原始值为 3，即主内存中 AtomicInteger 的 value 为 3，且线程 A 和线程 B 各自持有一份 value 的副本，值为 3；
线程 A 通过 getIntVolatile(var1, var2)拿到 value 值 3，线程 B 也通过 getIntVolatile(var1, var2)拿到 value 值 3，线程 A 和线程 B 同时调用 compareAndSwapInt()；
线程 A 执行 compareAndSwapInt()方法比较和替换时，其他 CPU 无法访问该变量的内存，所以线程 B 不能进行比较替换。线程 A 成功修改内存值为 4，返回 true，执行结束；
线程 B 恢复，执行 compareAndSwapInt()方法比较和替换，发现内存的实际值 4 跟自己期望值 3 不一致，说明该值已经被其它线程提前修改过了，返回 false，自旋进入 while 循环，再通过 getIntVolatile(var1, var2)方法获取 value 值 4，执行 compareAndSwapInt()比较替换，直到成功。

4. CAS 问题

4.1 ABA 问题

CAS 需要检查操作值有没有发生改变，如果没有发生改变则更新。但是存在这样一种情况：如果一个值原来是 A，变成了 B，然后又变成了 A，那么在 CAS 检查的时候会认为没有改变，但是实质上它已经发生了改变，这就是 ABA 问题。

解决方案可以沿袭数据库中常用的乐观锁方式，添加一个版本号可以解决。原来的变化路径 A->B->A 就变成了 1A->2B->3A。

在 java 1.5 后的 atomic 包中提供了 AtomicStampedReference 来解决 ABA 问题，解决思路就是这样的。

4.2 自旋时间过长

使用 CAS 时非阻塞同步，也就是说不会将线程挂起，会自旋（无非就是一个死循环）进行下一次尝试，如果自旋 CAS 长时间地不成功，则会给 CPU 带来非常大的开销。

优化：限制 CAS 自旋的次数，例如 BlockingQueue 的 SynchronousQueue。

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

当对一个共享变量执行操作时 CAS 能保证其原子性，如果对多个共享变量进行操作，CAS 就不能保证其原子性。解决方案：把多个变量整成一个变量：

利用对象整合多个共享变量，即一个类中的成员变量就是这几个共享变量，然后将这个对象做 CAS 操作就可以保证其原子性。atomic 中提供了 AtomicReference 来保证引用对象之间的原子性；
利用变量的高低位，如 JDK 读写锁 ReentrantReadWriteLock 的 state，高 16 位用于共享模式 ReadLock，低 16 位用于独占模式 WriteLock。

5. Java 中的原子操作类

在 J.U.C 下的 atomic 包提供了一系列原子操作类。

5.1 基本数据类型的原子操作类

AtomicInteger、AtomicLong、AtomicBoolean，以 AtomicInteger 为例总结一下常用的方法：

addAndGet(int delta) ：以原子方式将输入的数值delta与实例中原本的值相加，并返回最后的结果；
incrementAndGet() ：以原子的方式将实例中的原值进行加1操作，并返回最终相加后的结果；
getAndSet(int newValue)：将实例中的值更新为新值newValue，并返回旧值；
getAndIncrement()：以原子的方式将实例中的原值加1，返回的是自增前的旧值；

public static void main(String[] args) {
    AtomicInteger count = new AtomicInteger(1);
    System.out.println(count.getAndIncrement());
    System.out.println(count.getAndSet(5));
    System.out.println(count.get());
}

// 运行结果如下：
1
2 
5

5.2 数组类型的原子操作类

AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray（引用类型数组）。以 AtomicIntegerArray 来总结下常用的方法：

addAndGet(int i, int delta)：以原子更新的方式将数组中索引为i的元素与输入值delta相加；
getAndIncrement(int i)：以原子更新的方式将数组中索引为i的元素自增加1；
compareAndSet(int i, int expect, int update)：将数组中索引为i的位置的元素进行更新。

public static void main(String[] args) {
        int[] count = {1, 3, 5};
        AtomicIntegerArray integerArray = new AtomicIntegerArray(count);
        int result = integerArray.getAndAdd(1, 4);
        System.out.println(result);
        integerArray.incrementAndGet(2);
        System.out.println(integerArray.get(2));
    }
    
// 代码运行结果如下：
3
6

5.3 引用类型的原子操作类

AtomicReference

public class AtomicDemo {

    private static AtomicReference<User> reference = new AtomicReference<>();

    public static void main(String[] args) {
        User user1 = new User("a", 1);
        reference.set(user1);
        User user2 = new User("b",2);
        User user = reference.getAndSet(user2);
        System.out.println(user);
        System.out.println(reference.get());
    }

    static class User {
        private String userName;
        private int age;

        public User(String userName, int age) {
            this.userName = userName;
            this.age = age;
        }

        @Override
        public String toString() {
            return "User{" +
                    "userName='" + userName + '\'' +
                    ", age=" + age +
                    '}';
        }
    }
}

// 代码运行结果如下：
User{userName='a', age=1}
User{userName='b', age=2}

5.4 字段类型的原子操作类

如果需要更新对象的某个字段，并在多线程的情况下，能够保证线程安全，atomic 同样也提供了相应的原子操作类：

AtomicIntegeFieldUpdater：原子更新整型字段类；
AtomicLongFieldUpdater：原子更新长整型字段类；
AtomicStampedReference：原子更新引用类型，这种更新方式会带有版本号。解决 CAS 的 ABA 问题。

用法：

通过 AtomicIntegerFieldUpdater 的静态方法 newUpdater 来创建一个更新器，并且需要设置想要更新的类和属性；
更新类的属性必须使用 public volatile 进行修饰；

public class AtomicDemo {

    private static AtomicIntegerFieldUpdater updater = AtomicIntegerFieldUpdater.newUpdater(User.class,"age");
    public static void main(String[] args) {
        User user = new User("a", 1);
        int oldValue = updater.getAndAdd(user, 5);
        System.out.println(oldValue);
        System.out.println(updater.get(user));
    }

    static class User {
        private String userName;
        public volatile int age;

        public User(String userName, int age) {
            this.userName = userName;
            this.age = age;
        }

        @Override
        public String toString() {
            return "User{" +
                    "userName='" + userName + '\'' +
                    ", age=" + age +
                    '}';
        }
    }
}

// 代码运行结果如下：
1
6

5.5 原子化的累加器

DoubleAccumulator、DoubleAdder、LongAccumulator 和 LongAdder，这四个类仅仅用来执行累加操作，相比原子化的基本数据类型，速度更快，但是不支持 compareAndSet() 方法。如果你仅仅需要累加操作，使用原子化的累加器性能会更好。至于为什么它的性能要优与 AmoticInteger 可以参考《原子化的累加器》，这篇文章里进行了详细的说明。

6 总结

CAS 即比较和替换，可以高效的解决原子性问题。

CAS 原子操作原理：使用一个期望值和一个变量的当前值进行比较，如果当前变量的值与我们期望的值相等，就使用一个新值替换当前变量的值。

Java 中的 CAS：atomic 包下原子操作类，如 AtomicInteger 常用于修饰共享变量来保证原子性。

14 - CAS 无锁工具类的典范

14 - CAS 无锁工具类的典范

CAS 无锁工具类的典范

1. CAS 介绍

2. CAS 解决原子性问题

3. CAS 原理

4. CAS 问题

4.1 ABA 问题

4.2 自旋时间过长

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

5. Java 中的原子操作类

5.1 基本数据类型的原子操作类

5.2 数组类型的原子操作类

5.3 引用类型的原子操作类

5.4 字段类型的原子操作类

5.5 原子化的累加器

6 总结

继续阅读

2023爬虫学习笔记 -- 多线程操作

java socket多线程聊天室(一)

This application is modifying the autolayout engine from a background thread, which can lead

Socket实现聊天室（二）

网络编程----TCP实现聊天室项目前言

OO设计的重要原则

【一】深入理解Java高并发 - 并发的设计原则

避免条件竞争的三种方法

线程死锁的触发、修复、避免策略一、什么是死锁二、死锁例子三、死锁的必要条件四、定位死锁五、死锁的修复六、避免死锁的策略七、活锁八、总结

Go 基础之 Goroutine

ThreadLocal线程局部变量-多线程与高并发

python两种方法解决线程冲突问题线程冲突起因解决方案

C++ 多线程用条件变量确定线程的执行顺序而不是使用 sleep(1)

C#多线程——前台线程和后台线程

线程同步，可重入锁，synchronized

并发专题-Volatile关键字实现原理