java多线程编程之volatile和CAS

java多线程里面volatile以及CAS都是比单纯的锁能提供更高性能的一种共享资源访问机制，在这里进行对其原理的探究和解析

在前言这里先介绍一下并发编程的两个概念：

（1）原子性：（这里暂且用数据库的事务的原子性来解释，跟并发编程里面的原子性是同一个意思）

一个事务（transaction）中的所有操作，要么全部完成，要么全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样

（2）可见性：

可见性是指当多个线程访问同一个变量时，一个线程修改了这个变量的值，其他线程能够立即看得到修改的值。

一.volatile

原理：首先我们要了解线程在java内存里面执行的原理，每个线程获取到CPU的时钟区间之后，会从ready状态->running状态，在x86处理器下，每个线程在执行的时候，不会直接读取主内存，而是会在每个CPU的高速缓存里面读取数据，每次CPU在执行线程的时候，会将需要的数据从主内存读取到高速缓存中，而在多核CPU的情况下，如果一个CPU进行了计算，然而其他CPU里面的缓存数据还是旧的，那么就会导致计算出错（脏数据）的情况，为了避免这种情况，保证多个CPU之间的高速缓存是一致的，OS里面会有一个缓存一致性协议，volatile就是通过OS的缓存一致性策略来保持共享变量在多个线程之间的可见性。

缓存一致性：每个CPU会在总线上面有一个嗅探器，当一个CPU将高速缓存的内容写到主内存时候，每个CPU会去查看自己缓存里面的缓存行对应的内存地址的值是否被修改了，如果发现被修改了，会将缓存里面的数据设为无效，当处理器要对自身告诉缓存里面的这个数据进行修改，会强制重新从系统主内存读取数据进来之后再去修改（详细可参考intel的mesi协议：http://blog.csdn.net/muxiqingyang/article/details/6615199）。

局限性：由于volatile只是保持了共享变量的可见性，当多线程并发的时候，多个线程分别分配到CPU中，比如执行x++操作，我们都知道实际上x++ <=> x=x+1，那么x++不是一个原子操作而是一个两步的操作，当对共享变量使用volatile之后，在CPU1里面一个线程进行了+1操作，并将数据写回到主内存时候，根据缓存一致性策略，会将各个其他CPU高速缓存里面的缓存行设为无效，然而当此时另一个线程已经完成了从CPU告诉缓存段读取数据到变量的操作，此时变量的值已经在jvm的栈里面，虽然CPU2里面的缓存段已经失效了，但是在并发情况下，还是可能会出现数据丢失的情况，不能保证并发情况下对共享变量的访问。

使用场景：

(1)对变量的写操作不依赖于当前值。

(2)该变量没有包含在具有其他变量的不变式中。

实际上，这些条件表明，可以被写入 volatile 变量的这些有效值独立于任何程序的状态，包括变量的当前状态。

所以可以看出，实际上volatile作为只保证可见性的并发策略，只适用于独立的不依赖于当前值的变量，一般来说是只能适合于Boolean变量并且是独立的与其他互不相关的Boolean变量，当然自从jdk1.5之后，java引进了CAS机制来保证volatile的原子性，这会从下面CAS的介绍里面一并讲解。

demo：

package com.vip.learn.cocurrent.chapter5;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

/**
 * Created by andrew.huang on 2018/1/4.
 */
public class VolatileMain {

    static volatile Integer x = 0;

    public static void main(String[] args) {
        ExecutorService service = Executors.newCachedThreadPool();
        service.execute(new TestThread1());
        service.execute(new TestThread2());
        service.shutdown();
    }

    static class TestThread1 implements Runnable{

        @Override
        public void run() {
            for(int i = 0;i < 1000;i++){
                x++;
                System.out.println("thread1 is " + "time is " + i + "result is " + x);
            }
        }
    }

    static class TestThread2 implements Runnable{

        @Override
        public void run() {
            for(int i = 0;i < 1000;i++){
                x++;
                System.out.println("thread2 is " + "time is " + i + "result is " + x);
            }
        }
    }

}

计算结果：

可以看到thread2最后的值只有1998，而远不是我们所想象的2000，有两个数值在他们进行计算的时候被吞掉了，而这还只是在两个线程并发的执行情况下，在生产环境里面大量线程并发情况下，volatile造成的值缺失问题会更加严重，所以如果单独使用volatile去作为并发策略，需要在比使用锁(synchronized和lock)要考虑更多的因素和情况。

二.CAS

含义：CAS是指compare and swap，意识是指一个旧的预期值A,主内存的值是B，要修改的值C，当且仅当A==B的时候，A的值才会被修改成C，而且这个操作是原子性的，是一个非阻塞性的 乐观锁

原理：CAS底层是通过JNI去调用，是java通过调用C代码操作OS来获取的一个原子操作，通过看sun.misc.Unsafe类里面的方法，可以看到compareAndSwap()是一个native方法：

因为compareAndSwap的native方法在OS里面实际上就是cmpxchg指令，接来下去到openjdk里面查看这个指令的源码：

可以看到有一个LOCK_IF_MP的指令，mp就是指是否多核CPU的判断，如果当是MP的时候，执行cmpxchg指令之前会先执行LOCK指令,进行锁操作之后，再去执行cmpxchg指令，这样就保证了一个独占锁的作用，就保持了CAS操作的原子性。

那这里衍生出一个问题，既然都会有LOCK，那么为什么CAS会比synchronized更快呢？

有两个原因：

（1）CAS是一个硬件指令，通过硬件层次去保证原子性，比synchronized在jvm层次通过一个监听者作为锁来保证原子性更快

（2）OS里面的LOCK指令分为两种锁：

1.一种是总线锁，当LOCK指令锁住的是总线的时候，那么每一刻只有一个CPU能够访问到总线，那样就保证了原子性的操作，但是由于同一时刻只有一个CPU，就是单线程能访问到总线，但因为是硬件上层次的锁，所以性能还是优于synchronized；

2.另外一种是缓存锁，当cmpxchg指令要操作的内存能完全保存在一个缓存行里面的时候，CPU高速缓存里面也完全缓存了这个缓存行，当要对缓存行进行写操作之前，根据缓存一致性策略会将缓存行修改为MESI里面的E（Exclusive）状态，当缓存行处于这个状态的时候，其他CPU里面不能访问这个缓存行的数据，就是说此时这个缓存行是被锁定独占的，那么CAS就会就直接执行cmpxchg指令而不去发出LOCK指令到总线，因为是独占的占有这个缓存行，所以也是一个原子性的操作。而因为缓存行层次上的锁更具有并发性和锁的时间更短，所以性能上比synchronized要快的多。

但是需要注意的是有两种情况不可以使用缓存锁只能使用总线锁：

1.操所数据无法缓存在CPU内部，或者跨越多个缓存行

解释：
（1）无法缓存在CPU内部那么就没有缓存行的概念，那么也就不存在基于缓存行的缓存锁而是指应该到内存层次的内存锁
（2）跨越多个缓存行时候，可能另外一个缓存行会被另外的CPU锁定，所以无法使用缓存锁智能使用总线锁

2.CPU不支持缓存锁定

局限性：

（1）ABA问题：当CPU1从缓存里面读到了数值A，另一个CPU2这时候也从缓存里面读到了A，然后将他主内存里面的值先修改成B，再将他修改成A，释放缓存锁，此时CPU1获取到缓存锁，去读主内存里面的值，发现还是A，判断相等修改新值，这在CPU1的线程里面看起来是没有任何改变，但实际上主内存里面这块地址的值已经有了一个A->B->A的改变，自从jdk1.5之后，加入了AtomicStampedReference类来防止这个问题，通过将引用和版本号作为一个tuple来防止ABA问题，那么修改结果就会变成1A->1B->2A，就能看到内存里面这个值的改变。

(2)自旋效率问题：因为在AtomicInteger类里面，其实是一个自旋的CAS，就是不断重复通过执行CAS指令，直到成功为止，当长时间进行CAS的自旋的时候，会引起CPU资源的大量消耗。

(3)只能保证一个共享变量的原子操作：当只有一个共享变量进行CAS操作的时候，就可以进行自旋的CAS去进行原子操作，但是对多个共享变量进行CAS操作的时候，循环CAS无法保证原子性（可以在脑海里面想一下如果一个CAS同时保证x++和y++是什么情况），这时候我们可以取巧将这两个变量放在一个对象里面，因为这时候锁定的就直接锁定了一个对象的缓存行（段），那么就可以完整的对这个对象及其引用做一个原子操作。java提供的AtomicReference类可以用来保证对象之间的原子性（大致的原理还不了解，但大概是将所有引用对象的缓存段都进行缓存锁或者总线锁来处理），看看源代码和注释：

demo：

（1）参考java里面的AtomicInteger类源代码：

通过volatile原语对value进行了可见性的判断，当多个线程去并发访问的时候，能够启用缓存一致性原则保证线程之间的可见性

可以看到AtomicInteger类通过自旋cas来保证一个乐观锁的原子操作

（2）AtomicInteger进行++操作：

package javaLearn;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

public class AtomicIntegerMain {

    static AtomicInteger x = new AtomicInteger(0);

    public static void main(String[] args) {
        ExecutorService service = Executors.newCachedThreadPool();
        service.execute(new TestThread1());
        service.execute(new TestThread2());
        service.shutdown();
    }

    static class TestThread1 implements Runnable{

        @Override
        public void run() {
            for(int i = 0;i < 1000;i++){
                x.incrementAndGet();
                System.out.println("thread1 is " + "time is " + i + "result is " + x);
            }
        }
    }

    static class TestThread2 implements Runnable{

        @Override
        public void run() {
            for(int i = 0;i < 1000;i++){
                x.incrementAndGet();
                System.out.println("thread2 is " + "time is " + i + "result is " + x);
            }
        }
    }

}

结果：

（3）java.util.concurrent包里面的工具类基本全部都是使用了CAS+volatile的乐观锁机制，像我们常用的ReentrantReadWriteLock类，实际上内部也是使用了CAS+volatile的机制，并且ReentrantReadWriteLock类能支持在获取锁的时候响应线程的中断，能够设置等待锁的超时时间，还有tryLock等方法，所以在要使用需要耗费长时间同步锁的情况下，使用ReentrantReadWriteLock类会比synchronized更具有可操作性和更好的性能，下面来简单看看ReentrantReadWriteLock的源码：

可以看到ReentrantReadWriteLock会先去获取锁的count，然后在小于MAX_COUNT锁数目的时候，再去用cas设置锁的状态，然后再去获取锁。

三.那什么情况下使用CAS+volatile来保证对共享变量的操作？

我觉得引用stackoverflow上面一个大神说的话最是在理：

所以当同步锁的性能还不是系统性能瓶颈的时候，可以先考虑使用同步锁synchronized和lock，但是当同步锁的性能已经是系统瓶颈，那就要开始考虑使用CAS+volatile的非阻塞乐观锁的方式来降低同步锁带来的阻塞性能的问题，例如现在很火的Disruptor内部就是使用了cas来代替传统的阻塞锁lock，作为一个无阻塞队列在性能上相比传统的阻塞队列有了极强的提升，引用并发编程网上面对Disruptor性能的评价：

四.总结

volatile+CAS的机制能够通过自选乐观锁的情况下实现对共享变量的访问，并且CAS的原子性是通过硬件层次来体现，这样效率和性能更加相比阻塞性的synchronized和lock来说更加的快，但同时CAS也有着自己的问题，比如用于编程来说相比于阻塞性的算法，更为复杂和困难。

五.引用和参考文章：

http://blog.csdn.net/hsuxu/article/details/9467651
https://kb.cnblogs.com/page/504824/
http://www.importnew.com/18126.html
http://ifeve.com/volatile/
https://stackoverflow.com/questions/2664172/java-concurrency-cas-vs-locking
http://ifeve.com/atomic-operation/
http://ifeve.com/disruptor/

                            作者：唯品会开发工程师 黄文岳
                            日期：2018.1.7