并发编程-CAS原理与JUC原子类-02

1-CAS

什么是CAS：JDK 5所增加的JUC（java.util.concurrent）并发包对操作系统的底层CAS原子操作进行了封装，为上层Java程序提供了CAS操作的API。

1.1 使用CAS进行无锁编程

CAS是一种无锁算法，该算法关键依赖两个值——期望值（旧值）和新值，底层CPU利用原子操作判断内存原值与期望值是否相等，如果相等就给内存地址赋新值，否则不做任何操作。

使用CAS进行无锁编程的步骤大致如下：
（1）获得字段的期望值（oldValue）。
（2）计算出需要替换的新值（newValue）。
（3）通过CAS将新值（newValue）放在字段的内存地址上，如果CAS失败就重复第（1）步到第（2）步，一直到CAS成功，这种重复俗称CAS自旋。

2-JUC原子类

在多线程并发执行时，诸如“++”或“--”类的运算不具备原子性，不是线程安全的操作。通常情况下，大家会使用synchronized将这些线程不安全的操作变成同步操作，但是这样会降低并发程序的性能。所以，JDK为这些类型不安全的操作提供了一些原子类，与synchronized同步机制相比，JDK原子类是基于CAS轻量级原子操作的实现，使得程序运行效率变得更高。

2.1 JUC中的Atomic原子操作包

Atomic操作翻译成中文是指一个不可中断的操作，即使在多个线程一起执行Atomic类型操作的时候，一个操作一旦开始，就不会被其他线程中断。所谓Atomic类，指的是具有原子操作特征的类。

根据操作的目标数据类型，可以将JUC包中的原子类分为4类：基本原子类、数组原子类、原子引用类和字段更新原子类。

CAS用于保障变量操作的原子性，volatile关键字用于保障变量的可见性，二者常常结合使用。

基本原子类的功能是通过原子方式更新Java基础类型变量的值。基本原子类主要包括以下三个：

·AtomicInteger：整型原子类。
·AtomicLong：长整型原子类。
·AtomicBoolean：布尔型原子类。

（2）数组原子类

数组原子类的功能是通过原子方式更数组中的某个元素的值。数组原子类主要包括以下三个：

·AtomicIntegerArray：整型数组原子类。
·AtomicLongArray：长整型数组原子类。
·AtomicReferenceArray：引用类型数组原子类。

2.2 对象操作的原子性

基础的原子类型只能保证一个变量的原子操作，当需要对多个变量进行操作时，CAS无法保证原子性操作，这时可以用AtomicReference（原子引用类型）保证对象引用的原子性。

简单来说，如果需要同时保障对多个变量操作的原子性，就可以把多个变量放在一个对象中进行操作。

与对象操作的原子性有关的原子类型，除了引用类型原子类之外，还包括属性更新原子类。

引用类型原子类包括以下种：

·AtomicReference：基础的引用原子类。
·AtomicStampedReference：带印戳的引用原子类。
·AtomicMarkableReference：带修改标志的引用原子类。

2.3 属性更新原子性

如果需要保障对象某个字段（或者属性）更新操作的原子性，就需要用到属性更新原子类。属性更新原子类有以下三个：

·AtomicIntegerFieldUpdater：保障整型字段的更新操作的原子性。
·AtomicLongFieldUpdater：保障长整型字段的更新操作的原子性。
·AtomicReferenceFieldUpdater：保障引用字段的更新操作的原子性。

使用属性更新原子类保障属性安全更新的流程大致需要两步：
·第一步，更新的对象属性必须使用public volatile修饰符。
·第二步，因为对象的属性修改类型原子类都是抽象类，所以每次使用都必须调用静态方法newUpdater()创建一个更新器，并且需要设置想要更新的类和属性。

2.3 ABA问题

什么是ABA问题？举一个例子来说明。比如一个线程A从内存位置M中取出V1，另一个线程B也取出V1。现在假设线程B进行了一些操作之后将M位置的数据V1变成了V2，然后又在一些操作之后将V2变成了V1。之后，线程A进行CAS操作，但是线程A发现M位置的数据仍然是V1，然后线程A操作成功。尽管线程A的CAS操作成功，但是不代表这个过程是没有问题的，线程A操作的数据V1可能已经不是之前的V1，而是被线程B替换过的V1，这就是ABA问题。

ABA问题解决方案
很多乐观锁的实现版本都是使用版本号（Version）方式来解决ABA问题。乐观锁每次在执行数据的修改操作时都会带上一个版本号，版本号和数据的版本号一致就可以执行修改操作并对版本号执行加1操作，否则执行失败。因为每次操作的版本号都会随之增加，所以不会出现ABA问题，因为版本号只会增加，不会减少。

（1）使用AtomicStampedReference解决ABA问题

参考乐观锁的版本号，JDK提供了一个AtomicStampedReference类来解决ABA问题。AtomicStampReference在CAS的基础上增加了一个Stamp（印戳或标记），使用这个印戳可以用来觉察数据是否发生变化，给数据带上了一种实效性的检验。
AtomicStampReference的compareAndSet()方法首先检查当前的对象引用值是否等于预期引用，并且当前印戳（Stamp）标志是否等于预期标志，如果全部相等，就以原子方式将引用值和印戳（Stamp）标志的值更新为给定的更新值。

（2）使用AtomicMarkableReference解决ABA问题

AtomicMarkableReference是AtomicStampedReference的简化版，不关心修改过几次，只关心是否修改过。因此，其标记属性mark是boolean类型，而不是数字类型，标记属性mark仅记录值是否修改过。
AtomicMarkableReference适用于只要知道对象是否被修改过，而不适用于对象被反复修改的场景。

2.4 以空间换时间：LongAdder

Java 8提供了一个新的类LongAdder，以空间换时间的方式提升高并发场景下CAS操作的性能。
LongAdder的核心思想是热点分离，与ConcurrentHashMap的设计思想类似：将value值分离成一个数组，当多线程访问时，通过Hash算法将线程映射到数组的一个元素进行操作；而获取最终的value结果时，则将数组的元素求和。

3-CAS操作的弊端和规避措施

CAS操作的弊端主要有以下三点：

1.ABA问题
使用CAS操作内存数据时，数据发生过变化也能更新成功，如操作序列A==>B==>A时，最后一个CAS的预期数据A实际已经发生过更改，但也能更新成功，这就产生了ABA问题。

ABA问题的解决思路是使用版本号。在变量前面追加上版本号，每次变量更新的时候将版本号加1，那么操作序列A==>B==>A就会变成A1==>B2==>A3，如果将A1当作A3的预期数据，就会操作失败。

JDK提供了两个类AtomicStampedReference和AtomicMarkableReference来解决ABA问题。比较常用的是AtomicStampedReference类，该类的compareAndSet()方法的作用是首先检查当前引用是否等于预期引用，以及当前印戳是否等于预期印戳，如果全部相等，就以原子方式将引用和印戳的值一同设置为新的值。

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

一个比较简单的规避方法为：把多个共享变量合并成一个共享变量来操作。

JDK提供了AtomicReference类来保证引用对象之间的原子性，可以把多个变量放在一个AtomicReference实例后再进行CAS操作。比如有两个共享变量i＝1、j=2，可以将二者合并成一个对象，然后用CAS来操作该合并对象的AtomicReference引用。

3.开销问题
自旋CAS如果长时间不成功（不成功就一直循环执行，直到成功），就会给CPU带来非常大的执行开销。

解决CAS恶性空自旋的有效方式之一是以空间换时间，较为常见的方案为：
（1）分散操作热点，使用LongAdder替代基础原子类AtomicLong，LongAdder将单个CAS热点（value值）分散到一个cells数组中。
（2）使用队列削峰，将发生CAS争用的线程加入一个队列中排队，降低CAS争用的激烈程度。JUC中非常重要的基础类AQS（抽象队列同步器）就是这么做的。