CAS 原理分析

1、了解java中锁的类型

1.1 悲观锁(Pessimistic Lock)

顾名思义，就是很悲观，假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁。

1.2 乐观锁(Optimistic Lock)

顾名思义，就是很乐观，假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。乐观锁不能解决脏读的问题。每次拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号等机制。乐观锁适用于多读的应用类型，这样可以提高吞吐量。

从上面的描述我们可以看出，悲观锁适合写操作非常多的场景，乐观锁适合读操作非常多的场景。

悲观锁在Java中的使用，就是利用各种锁。如synchronized
乐观锁在Java中的使用，是无锁编程，常常采用的是CAS算法，典型的例子就是原子类，通过CAS自旋实现原子操作的更新。

独占锁是一种悲观锁，synchronized就是一种独占锁，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。而另一个更加有效的锁就是乐观锁。所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。*乐观锁用到的机制就是CAS，Compare and Swap。*

2、乐观锁的一种实现：CAS

我们都知道，在java语言之前，并发就已经广泛存在并在服务器领域得到了大量的应用。所以硬件厂商老早就在芯片中加入了大量支持并发操作的原语，从而在硬件层面提升效率。在intel的CPU中，使用cmpxchg指令。

在Java发展初期，java语言是不能够利用硬件提供的这些便利来提升系统的性能的。而随着java不断的发展,Java本地方法(JNI)的出现，使得java程序越过JVM直接调用本地方法提供了一种便捷的方式，因而java在并发的手段上也多了起来。而在Doug Lea提供的cucurenct包中，CAS理论是它实现整个java并发包的基石。

2.1 cas概述

CAS的全称是Compare And Swap 即比较和交换，其算法核心思想如下

执行函数：CAS(V,E,N)其包含3个参数V表示需要读写的内存位置E表示进行比较的预期原值N表示打算写入的新值

**CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。**否则，处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该位置的值。（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前值）CAS 有效地说明了“我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可

由于CAS操作属于乐观派，它总认为自己可以成功完成操作，当多个线程同时使用CAS操作一个变量时，只有一个会胜出，并成功更新，其余均会失败，但失败的线程并不会被挂起，仅是被告知失败，并且允许再次尝试，当然也允许失败的线程放弃操作，基于这样的原理，CAS操作即使没有锁，同样知道其他线程对共享资源操作影响，并执行相应的处理措施。同时从这点也可以看出，由于无锁操作中没有锁的存在，因此不可能出现死锁的情况，也就是说无锁操作天生免疫死锁。

2.2 CPU指令对CAS的支持

或许我们可能会有这样的疑问，假设存在多个线程执行CAS操作并且CAS的步骤很多，有没有可能在判断V和E相同后，正要赋值时，切换了线程，更改了值。造成了数据不一致呢？答案是否定的，因为CAS是一种系统原语，原语属于操作系统用语范畴，是由若干条指令组成的，用于完成某个功能的一个过程，并且原语的执行必须是连续的，在执行过程中不允许被中断，也就是说CAS是一条CPU的原子指令，不会造成所谓的数据不一致问题。所以利用CPU的CAS指令，同时借助JNI来完成Java的非阻塞算法。

Linux的X86下主要是通过cmpxchgl这个指令在CPU级完成CAS操作的，但在多处理器情况下必须使用lock指令加锁来完成。

cas在Java中无锁操作CAS基于以下3个方法实现，在稍后讲解Atomic系列内部方法是基于下述方法的实现的。

//第一个参数o为给定对象，offset为对象内存的偏移量，通过这个偏移量迅速定位字段并设置或获取该字段的值，
//expected表示期望值，x表示要设置的值，下面3个方法都通过CAS原子指令执行操作。
public final native boolean compareAndSwapObject(Object o, long offset,Object expected, Object x); 
public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);
public final native boolean compareAndSwapLong(Object o, long offset,long expected,long x);

挂起与恢复

将一个线程进行挂起是通过park方法实现的，调用 park后，线程将一直阻塞直到超时或者中断等条件出现。unpark可以终止一个挂起的线程，使其恢复正常。Java对线程的挂起操作被封装在 LockSupport类中，LockSupport类中有各种版本pack方法，其底层实现最终还是使用Unsafe.park()方法和Unsafe.unpark()方法。

//线程调用该方法，线程将一直阻塞直到超时，或者是中断条件出现。  
public native void park(boolean isAbsolute, long time);  //终止挂起的线程，恢复正常.java.util.concurrent包中挂起操作都是在LockSupport类实现的，其底层正是使用这两个方法，  
public native void unpark(Object thread);

2.3 并发包中的原子操作类(Atomic系列)

CAS在Java中的应用，即并发包中的原子操作类(Atomic系列)，从JDK 1.5开始提供了java.util.concurrent.atomic包，在该包中提供了许多基于CAS实现的原子操作类，用法方便，性能高效，主要分以下4种类型。

原子更新基本类型主要包括3个类：AtomicBoolean：原子更新布尔类型
AtomicInteger：原子更新整型
AtomicLong：原子更新长整型原子更新引用数据类型主要包括：
AtomicReference 原子操作引用对象类型

基本数据类型的原子操作类的实现原理和使用方式几乎是一样的，以AtomicInteger为例进行分析，AtomicInteger主要是针对int类型的数据执行原子操作，它提供了原子自增方法、原子自减方法以及原子赋值方法等，源码如下

public class AtomicInteger extends Number implements java.io.Serializable {private static final long serialVersionUID = 6214790243416807050L;// 获取指针类Unsafeprivate static final Unsafe unsafe = Unsafe.getUnsafe();//下述变量value在AtomicInteger实例对象内的内存偏移量private static final long valueOffset;static {try {//通过unsafe类的objectFieldOffset()方法，获取value变量在对象内存中的偏移//通过该偏移量valueOffset，unsafe类的内部方法可以获取到变量value对其进行取值或赋值操作valueOffset = unsafe.objectFieldOffset(AtomicInteger.class.getDeclaredField("value"));} catch (Exception ex) { throw new Error(ex); }}//当前AtomicInteger封装的int变量valueprivate volatile int value;public AtomicInteger(int initialValue) {value = initialValue;}public AtomicInteger() {}//获取当前最新值，public final int get() {return value;}//设置当前值，具备volatile效果，方法用final修饰是为了更进一步的保证线程安全。public final void set(int newValue) {value = newValue;}//最终会设置成newValue，使用该方法后可能导致其他线程在之后的一小段时间内可以获取到旧值，有点类似于延迟加载public final void lazySet(int newValue) {unsafe.putOrderedInt(this, valueOffset, newValue);}//设置新值并获取旧值，底层调用的是CAS操作即unsafe.compareAndSwapInt()方法public final int getAndSet(int newValue) {return unsafe.getAndSetInt(this, valueOffset, newValue);}//如果当前值为expect，则设置为update(当前值指的是value变量)public final boolean compareAndSet(int expect, int update) {return unsafe.compareAndSwapInt(this, valueOffset, expect, update);}//当前值加1返回旧值，底层CAS操作public final int getAndIncrement() {return unsafe.getAndAddInt(this, valueOffset, 1);}//当前值减1，返回旧值，底层CAS操作public final int getAndDecrement() {return unsafe.getAndAddInt(this, valueOffset, -1);}//当前值增加delta，返回旧值，底层CAS操作public final int getAndAdd(int delta) {return unsafe.getAndAddInt(this, valueOffset, delta);}//当前值加1，返回新值，底层CAS操作public final int incrementAndGet() {return unsafe.getAndAddInt(this, valueOffset, 1) + 1;}//当前值减1，返回新值，底层CAS操作public final int decrementAndGet() {return unsafe.getAndAddInt(this, valueOffset, -1) - 1;}//当前值增加delta，返回新值，底层CAS操作public final int addAndGet(int delta) {return unsafe.getAndAddInt(this, valueOffset, delta) + delta;}//省略一些不常用的方法....
}

AtomicReference****类实现自旋锁：

自旋锁是假设在不久将来，当前的线程可以获得锁，因此虚拟机会让当前想要获取锁的线程做几个空循环(这也是称为自旋的原因)，在经过若干次循环后，如果得到锁，就顺利进入临界区。如果还不能获得锁，那就会将线程在操作系统层面挂起，这种方式确实也是可以提升效率的。但问题是当线程越来越多竞争很激烈时，占用CPU的时间变长会导致性能急剧下降，因此Java虚拟机内部一般对于自旋锁有一定的次数限制，可能是50或者100次循环后就放弃，直接挂起线程，让出CPU资源。

//使用CAS原子操作作为底层实现public class SpinLock {private AtomicReference<Thread> sign =new AtomicReference<>();public void lock(){Thread current = Thread.currentThread();while(!sign .compareAndSet(null, current)){}}public void unlock (){Thread current = Thread.currentThread();sign .compareAndSet(current, null);}
}

2.4 CAS存在的问题

CAS虽然很高效的解决原子操作，但是CAS仍然存在三大问题：

ABA问题。因为CAS需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A 就会变成1A-2B-3A。

从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。
循环时间长开销大。自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。如果JVM能支持处理器提供的pause指令那么效率会有一定的提升，pause指令有两个作用，第一它可以延迟流水线执行指令（de-pipeline）,使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突（memory order violation）而引起CPU流水线被清空（CPU pipeline flush），从而提高CPU的执行效率。
只能保证一个共享变量的原子操作。当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。

2.5 concurrent包的实现

由于java的CAS同时具有 volatile 读和volatile写的内存语义，因此Java线程之间的通信现在有了下面四种方式：

1. A线程写volatile变量，随后B线程读这个volatile变量。

2. A线程写volatile变量，随后B线程用CAS更新这个volatile变量。

3. A线程用CAS更新一个volatile变量，随后B线程用CAS更新这个volatile变量。

4. A线程用CAS更新一个volatile变量，随后B线程读这个volatile变量。

Java的CAS会使用现代处理器上提供的高效机器级别原子指令，这些原子指令以原子方式对内存执行读-改-写操作，这是在多处理器中实现同步的关键（从本质上来说，能够支持原子性读-改-写指令的计算机器，是顺序计算图灵机的异步等价机器，因此任何现代的多处理器都会去支持某种能对内存执行原子性读-改-写操作的原子指令）。同时，volatile变量的读/写和CAS可以实现线程之间的通信。把这些特性整合在一起，就形成了整个concurrent包得以实现的基石。如果我们仔细分析concurrent包的源代码实现，会发现一个通用化的实现模式：

1. 首先，声明共享变量为volatile；

2. 然后，使用CAS的原子条件更新来实现线程之间的同步；

3. 同时，配合以volatile的读/写和CAS所具有的volatile读和写的内存语义来实现线程之间的通信。

AQS，非阻塞数据结构和原子变量类（java.util.concurrent.atomic包中的类），这些concurrent包中的基础类都是使用这种模式来实现的，而concurrent包中的高层类又是依赖于这些基础类来实现的。从整体来看，concurrent包的实现示意图如下：

在这里插入图片描述

2.6 CAS与自旋：

下面看一下getAndAddInt在底层Unsafe类中的代码（自旋锁），运用到了CAS

//va1为对象，var2为地址值，var4是要增加的值，var5为当前地址中最新的值
public final int getAndAddInt(Object var1, long var2, int var4) {int var5;do {var5 = this.getIntVolatile(var1, var2);} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));return var5;}

首先通过volatile的可见性，取出当前地址中的值，作为期望值。如果期望值与实际值不符，就一直循环获取期望值，直到set成功。

适用场景：

1. CAS 适合简单对象的操作，比如布尔值、整型值等；

2. CAS 适合冲突较少的情况，如果太多线程在同时自旋，那么长时间循环会导致 CPU 开销很大；

2.7 拓展：

AtomicStampedReference类

AtomicStampedReference原子类是一个带有时间戳的对象引用，在每次修改后，AtomicStampedReference不仅会设置新值而且还会记录更改的时间。当AtomicStampedReference设置对象值时，对象值以及时间戳都必须满足期望值才能写入成功，这也就解决了反复读写时，无法预知值是否已被修改的窘境

底层实现为：通过Pair私有内部类存储数据和时间戳, 并构造volatile修饰的私有实例
接着看AtomicStampedReference类的compareAndSet（）方法的实现：

同时对当前数据和当前时间进行比较，只有两者都相等是才会执行casPair()方法，

单从该方法的名称就可知是一个CAS方法，最终调用的还是Unsafe类中的compareAndSwapObject方法

到这我们就很清晰AtomicStampedReference的内部实现思想了，

通过一个键值对Pair存储数据和时间戳，在更新时对数据和时间戳进行比较，

只有两者都符合预期才会调用Unsafe的compareAndSwapObject方法执行数值和时间戳替换，也就避免了ABA的问题。

AtomicMarkableReference类

AtomicMarkableReference与AtomicStampedReference不同的是，

AtomicMarkableReference维护的是一个boolean值的标识，也就是说至于true和false两种切换状态，

经过博主测试，这种方式并不能完全防止ABA问题的发生，只能减少ABA问题发生的概率。

会调用Unsafe的compareAndSwapObject方法执行数值和时间戳替换，也就避免了ABA的问题。

AtomicMarkableReference类

AtomicMarkableReference与AtomicStampedReference不同的是，

AtomicMarkableReference维护的是一个boolean值的标识，也就是说至于true和false两种切换状态，

经过博主测试，这种方式并不能完全防止ABA问题的发生，只能减少ABA问题发生的概率。

AtomicMarkableReference的实现原理与AtomicStampedReference类似，这里不再介绍。到此，我们也明白了如果要完全杜绝ABA问题的发生，我们应该使用AtomicStampedReference原子类更新对象，而对于AtomicMarkableReference来说只能减少ABA问题的发生概率，并不能杜绝。