看AtomicInteger源码学习CAS算法

作者: itcjj | 来源:发表于2017-08-29 00:08 被阅读96次

一、线程

1.1 线程的概述

一个运行程序就是一个进程，而线程是进程中独立运行的子任务
线程是操作系统执行流中的最小单位，一个进程可以有多个线程，这些线程与该进程共享同一个内存空间
线程是系统独立调度和分派CPU的基本单位，通常有就绪、运行、阻塞三种基本状态
随着硬件水平的提高，多线程能使系统的运行效率得到大幅度的提高，同时异步操作也增加复杂度和各种并发问题

1.2 多线程的风险之一上下文切换

上下文切换： CPU通过时间片分配算法来循环执行任务，当前任务执行一个时间片后会切换到下一个任务。但是，在切换前会保存上一个任务的状态，以便下次切换回这个任务时可以重新加载这个任务的状态。所有任务从保存到再加载的过程就是一次上下文切换
多线程性能问题：由于线程有创建和上下文切换的开销，在多线程环境下，这种开销对时间和资源的利用都是一个极大的负担，很可能导致并发任务执行速度还不如串行快
减少上下文切换： 无锁并发编程、CAS算法、减少并发、使用最少线程、协程 .

二、并发编程中的锁

2.1 悲观锁

Java在JDK1.5之前都是靠synchronized关键字保证同步的，这种通过使用一致的锁定协议来协调对共享状态的访问，可以确保无论哪个线程持有共享变量的锁，都采用独占的方式来访问这些变量。独占锁其实就是一种悲观锁，所以可以说synchronized是悲观锁。存在以下问题：
在多线程竞争下，加锁、释放锁会导致比较多的上下文切换和调度延时，引起性能问题；一个线程持有锁会导致其它所有需要此锁的线程挂起；
如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置，引起性能风险。

2.2 乐观锁

乐观锁（ Optimistic Locking）其实是一种思想。相对悲观锁而言，乐观锁假设认为数据一般情况下不会造成冲突，所以在数据进行提交更新的时候，才会正式对数据的冲突与否进行检测，如果发现冲突了，则让返回用户错误的信息，让用户决定如何去做。
上面提到的乐观锁的概念中其实已经阐述了他的具体实现细节：主要就是两个步骤：冲突检测和数据更新。其实现方式有一种比较典型的就是Compare and Swap(CAS)。

三、无锁执行者CAS

3.1 无锁的概念

在谈论无锁概念时，总会关联起乐观派与悲观派，对于乐观派而言，他们认为事情总会往好的方向发展，总是认为坏的情况发生的概率特别小，可以无所顾忌地做事，但对于悲观派而已，他们总会认为发展事态如果不及时控制，以后就无法挽回了，即使无法挽回的局面几乎不可能发生。这两种派系映射到并发编程中就如同加锁与无锁的策略，即加锁是一种悲观策略，无锁是一种乐观策略，因为对于加锁的并发程序来说，它们总是认为每次访问共享资源时总会发生冲突，因此必须对每一次数据操作实施加锁策略。而无锁则总是假设对共享资源的访问没有冲突，线程可以不停执行，无需加锁，无需等待，一旦发现冲突，无锁策略则采用一种称为CAS的技术来保证线程执行的安全性，这项CAS技术就是无锁策略实现的关键，下面我们进一步了解CAS技术的奇妙之处。

3.2 CAS

CAS是项乐观锁技术，当多个线程尝试使用CAS同时更新同一个变量时，只有其中一个线程能更新变量的值，而其它线程都失败，失败的线程并不会被挂起，而是被告知这次竞争中失败，并可以再次尝试。其算法核心思想如下

执行函数：CAS(V,E,N)

其包含3个参数

V表示要更新的变量
E表示预期值
N表示新值

如果V值等于E值，则将V的值设为N。若V值和E值不同，则说明已经有其他线程做了更新，则当前线程什么都不做。通俗的理解就是CAS操作需要我们提供一个期望值，当期望值与当前线程的变量值相同时，说明还没线程修改该值，当前线程可以进行修改，也就是执行CAS操作，但如果期望值与当前线程不符，则说明该值已被其他线程修改，此时不执行更新操作，但可以选择重新读取该变量再尝试再次修改该变量，也可以放弃操作，原理图如下:

CAS原理图

四、Java对CAS的支持

我们以java.util.concurrent中的AtomicInteger为例，看一下在不使用锁的情况下是如何保证线程安全的。

4.1 AtomicInteger 类的变量以及静态代码块

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 6214790243416807050L;
    
    //获取unsafe对象
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    
    //value在内存中的地址偏移量  
    private static final long valueOffset;

    static {
        try {
            //获得value的内存地址偏移量
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }
    //当前对象代表的值，注意是volatile(**下面会解释该关键字**)
    private volatile int value;

4.2 深究Unsafe类

从这个类的名字Unsafe上来说这个类就是一个不安全的类，它存在于sun.misc包中，其内部方法操作可以像C的指针一样直接操作内存，单从名称看来就可以知道该类是非安全的，毕竟Unsafe拥有着类似于C的指针操作，因此总是不应该首先使用Unsafe类，Java官方也不建议直接使用的Unsafe类，也不开放给用户直接使用的（当然我们还是可以通过其他一些方法用到）。Java 9中将移除 Sun.misc.Unsafe,原文链接：https://yq.aliyun.com/articles/87265

@CallerSensitive
    public static Unsafe getUnsafe() {

        //得到调用者的class对象，这里即是Unsafe
        Class arg = Reflection.getCallerClass();

       //判断调用Unsafe的类是否是BootstrapClassLoader加载的类 
        if (!VM.isSystemDomainLoader(arg.getClassLoader())) {
            throw new SecurityException("Unsafe");
        } else {
            return theUnsafe;
        }
    }

这个类本身是单例的，需要通过静态方法获取唯一实例。根据代码知道应该是通过类加载器限制。一般我们写的类都是由Application ClassLoader（sun.misc.Launcher$AppClassLoader）进行加载的，层级比较低，这里的SystemDomainLoader就是BootstarpClassLoader（C++写的），也就是加载rt.jar里面的类的加载器，所以Java.xx用就不会有事，我们用就会有事。
想要使用Unsafe有两种方式。一种是用反射，比较简单；另外一种是通过虚拟机启动参数-Xbootclasspath，把你的classpath变为启动路径之一，这样就是BootstarpClassLoader加载你的类，跟java.xx一个待遇了，就不会报错了。可以看到，虽然是可以调用，但是会有一步判断，判断是不是内部会检查该CallerClass是不是由系统类加载器BootstrapClassLoader加载，因为它是不安全的类，官方api也没有对这个包下的类进行解释说明，如果是开发人员引用这个包下的类则会抛错。由系统类加载器加载的类调用getClassLoader()会返回null，所以要检查类是否为bootstrap加载器加载只需要检查该方法是不是返回null。
下面会重点讲解类加载器

4.3 类加载器

从下面的注释我们可知只要是由bootstrap加载器加载的类，返回值是null，这也就进一步说明了，java官方禁止自定义使用该类。

 /**
     * Returns the class loader for the class.  Some implementations may use
     * null to represent the bootstrap class loader. This method will return
     * null in such implementations if this class was loaded by the bootstrap
     * class loader.
     *
     */
    @CallerSensitive
    public ClassLoader getClassLoader() {
        ClassLoader cl = getClassLoader0();
        if (cl == null)
            return null;

        //JVM安全管理器，这里不做重点介绍
        SecurityManager sm = System.getSecurityManager();
        if (sm != null) {
            ClassLoader.checkClassLoaderPermission(cl, Reflection.getCallerClass());
        }
        return cl;
    }

    ClassLoader getClassLoader0() { return classLoader; }

4.3.1 Class 文件有哪些来源呢?

首先，最常见的是开发者在应用程序中编写的类，这些类位于项目目录下；

然后，有 Java 内部自带的核心类如 java.lang、java.math、java.io 等 package 内部的类，位于 $JAVA_HOME/jre/lib/ 目录下，如 java.lang.String 类就是定义在 $JAVA_HOME/jre/lib/rt.jar 文件里；

另外，还有 Java 核心扩展类，位于 $JAVA_HOME/jre/lib/ext 目录下。开发者也可以把自己编写的类打包成 jar 文件放入该目录下；
最后还有一种，是动态加载远程的 .class 文件。

既然有这么多种类的来源，那么在 Java 里，是由某一个具体的 ClassLoader 来统一加载呢？还是由多个 ClassLoader 来协作加载呢？

4.3.2 哪些 ClassLoader 负责加载上面几类 Class？

首先，我们来看级别最高的 Java 核心类，即$JAVA_HOME/jre/lib 里的核心 jar 文件。这些类是 Java 运行的基础类，由一个名为 BootstrapClassLoader 加载器负责加载，它也被称作根加载器／引导加载器。注意，BootstrapClassLoader 比较特殊，它不继承 ClassLoader，而是由 JVM 内部实现；

然后，需要加载 Java 核心扩展类，即 $JAVA_HOME/jre/lib/ext 目录下的 jar 文件。这些文件由 ExtensionClassLoader 负责加载，它也被称作扩展类加载器。当然，用户如果把自己开发的 jar 文件放在这个目录，也会被 ExtClassLoader 加载；

接下来是开发者在项目中编写的类，这些文件将由 AppClassLoader 加载器进行加载，它也被称作系统类加载器 System ClassLoader；

最后，如果想远程加载如（本地文件／网络下载）的方式，则必须要自己自定义一个 ClassLoader，复写其中的 findClass() 方法才能得以实现。

因此能看出，Java 里提供了至少四类 ClassLoader 来分别加载不同来源的 Class。

4.3.4 解压查看$JAVA_HOME/jre/lib/rt.jar文件

import

isun\misc的Unsafe类

通过上面两个图，证明了，Unsafe类是由BootstrapClassLoader 加载器加载的，所以在获取classLoader时正常情况下是返回null。

4.3.5 CallerSensitive注解是什么鬼？

细心的同学可能已经发现上面获取类加载器的方法上有该注解，那么它的作用是啥呢？我们先看stackoverflow网站给出的答案

CallerSensitive

简而言之，用@CallerSensitive注解修饰的方法从一开始就知道具体调用它的对象，这样就不用再经过一系列的检查才能确定具体调用它的对象了。它实际上是调用sun.reflect.Reflection.getCallerClass方法。

4.4 说下AtomicInteger类的getAndIncrement方法

 public final int getAndIncrement() {

        // 当前值加1返回旧值，底层CAS操作
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

//Unsafe类中的getAndAddInt方法
public final int getAndAddInt(Object o, long offset, int x) {
        int expected;
        do {
            //获得给定对象的指定偏移量offset的int值，使用volatile语义，总能获取到最新的int值。
            expected= this.getIntVolatile(o, offset);

        //第一个参数o为给定对象，offset为对象内存的偏移量，通过这个偏移量迅速定位字段并设置或获取该字段的值，expected表示期望值，expected+x表示要设置的值。
        } while (!this.compareAndSwapInt(o, offset, expected, expected+ x));

        return expected;
    }

4.5 看线程的挂起与恢复理解Unsafe运行机制

将一个线程进行挂起是通过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);

4.6 通过例子加深对Unsafe的理解

 private static Unsafe unsafe;

    public static void main(String[] args) {

        try {
            //通过反射获取rt.jar下的Unsafe类
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            // 设置该Field为可访问
            field.setAccessible(true);
            // 通过Field得到该Field对应的具体对象，传入null是因为该Field为static的
            unsafe = (Unsafe) field.get(null);
            Integer target = 12;
            //compareAndSwapInt方法的属性分别是：目标对象实例，目标对象属性偏移量，当前预期值，要设的值.
            //compareAndSwapInt方法是通过反射修改对象的值，具体修改对象下面那个值，可以通过偏移量，对象字段的偏移量可以通过objectFieldOffset获取
            System.out.println(unsafe.compareAndSwapInt(target, 12, 12, 24));
        } catch (Exception e) {
            System.out.println("Get Unsafe instance occur error" + e);
        }
    }

输入不同的参数得到以下结果：

正确的期望值

错误的期望值

4.7 CAS的ABA问题及其解决方案

CAS算法实现一个重要前提需要取出内存中某时刻的数据，而在下时刻比较并替换（比较和交换是原子性），如果在取出和比较并交换之间发生数据变化而不能察觉，就出现所谓的ABA问题了。

image.png

ABA问题导致的原因，是CAS过程中只简单进行了“值”的校验，再有些情况下，“值”相同不会引入错误的业务逻辑（例如库存），有些情况下，“值”虽然相同，却已经不是原来的数据了。

优化方向：CAS不能只比对“值”，还必须确保的是原来的数据，才能修改成功。

常见实践：“版本号”的比对，一个数据一个版本，版本变化，即使值相同，也不应该修改成功。

五、对volatile关键字的理解

5.1 volatile写操作的内存语义

当写一个volatile变量时，JMM会把该线程对应的本地内存中的共享变量刷新到主内存

写操作

5.2 volatile读操作的内存语义

读操作

5.3 变量在内存中的工作过程

image.png

5.4 volatile非原子原因

多线程环境下，"数据计算"和"数据赋值"操作可能多次出现，即操作非原子

若数据在加载之后，若主内存count变量发生修改之后，由于线程工作内存中的值在此前已经加载，从而不会对变更操作做出相应变化，即私有内存和公共内存中变量不同步，进而导致数据不一致

对于volatile变量，JVM只是保证从主内存加载到线程工作内存的值是最新的，也就是数据加载时是最新的。由此可见volatile解决的是变量读时的可见性问题，但无法保证原子性，对于多线程修改共享变量的场景必须使用加锁同步

六、参考文章

偶然的机会看了下面其中一篇文章便开始对cas产生了兴趣，激起我继续看源码写文章的激情。感谢下面的作者们，深度好文！

https://www.zybuluo.com/kiraSally/note/850631
http://www.10tiao.com/html/249/201706/2651960240/1.html
https://juejin.im/entry/595c599e6fb9a06bc6042514