概述

  • CAS ,Compare And Swap ,即比较并交换。Doug Lea 大神在实现同步组件时,大量使用CAS 技术,鬼斧神工地实现了Java 多线程的并发操作。整个 AQS 同步组件、Atomic 原子类操作等等都是基 CAS 实现的

CAS分析

  • 在 CAS 中有三个参数:内存值 V、旧的预期值 A、要更新的值 B ,当且仅当内存值 V 的值等于旧的预期值 A 时,才会将内存值V的值修改为 B ,否则就再次尝试。其伪代码如下:

    1
    2
    3
    4
    5
    6
    if (this.value == A) {
    this.value = B
    return true;
    } else {
    return false;
    }
  • 这样说或许有些抽象,我们来看一个例子:

    • 1.在内存地址V当中,存储着值为10的变量。

    • 2.此时线程1想要把变量的值增加1。对线程1来说,旧的预期值A=10,要修改的新值B=11。

    • 3.在线程1要提交更新之前,另一个线程2抢先一步,把内存地址V中的变量值率先更新成了11。

    • 4.线程1开始提交更新,首先进行A和地址V的实际值比较(Compare),发现A不等于V的实际值,提交失败。

    • 5.线程1重新获取内存地址V的当前值,并重新计算想要修改的新值。此时对线程1来说,A=11,B=12。这个重新尝试的过程被称为自旋。

    • 6.这一次比较幸运,没有其他线程改变地址V的值。线程1进行Compare,发现A和地址V的实际值是相等的。

    • 7.线程1进行SWAP,把地址V的值替换为B,也就是12。


      *

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

  • J.U.C 下的 Atomic 类,都是通过 CAS 来实现的。下面就以 AtomicInteger 为例,来阐述 CAS 的实现。如下:

  • 我们就以 AtomicInteger 的 #addAndGet() 方法来做说明,先看源代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // AtomicInteger.java
    public final int addAndGet(int delta) {
    return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
    }

    // Unsafe.java
    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;
    }
  • 关注 public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

    1
    2
                                                  对象          对象的地址  预期值    修改值
    public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

CPU指令对CAS的支持

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

鲜为人知的指针: Unsafe类

  • Unsafe类存在于sun.misc包中,其内部方法操作可以像C的指针一样直接操作内存,单从名称看来就可以知道该类是非安全的,毕竟Unsafe拥有着类似于C的指针操作,因此总是不应该首先使用Unsafe类,Java官方也不建议直接使用的Unsafe类,但我们还是很有必要了解该类,因为Java中CAS操作的执行依赖于Unsafe类的方法,注意Unsafe类中的所有方法都是native修饰的,也就是说Unsafe类中的方法都直接调用操作系统底层资源执行相应任务,关于Unsafe类的主要功能点如下:
  • 内存管理,Unsafe类中存在直接操作内存的方法;

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    // 分配内存指定大小的内存
    public native long allocateMemory(long bytes);

    // 根据给定的内存地址address设置重新分配指定大小的内存
    public native long reallocateMemory(long address, long bytes);

    // 用于释放allocateMemory和reallocateMemory申请的内存
    public native void freeMemory(long address);

    // 将指定对象的给定offset偏移量内存块中的所有字节设置为固定值
    public native void setMemory(Object o, long offset, long bytes, byte value);//设置给定内存地址的值public native void putAddress(long address, long x);

    // 获取指定内存地址的值
    public native long getAddress(long address);

    // 设置给定内存地址的long值
    public native void putLong(long address, long x);

    // 获取指定内存地址的long值
    public native long getLong(long address);

    // 设置或获取指定内存的byte值
    // 其他基本数据类型(long,char,float,double,short等)的操作与putByte及getByte相同
    public native byte getByte(long address);

    public native void putByte(long address, byte x);
  • CAS是一些CPU直接支持的指令,也就是我们前面分析的无锁操作,在Java中无锁操作CAS基于以下3个方法实现

    1
    2
    3
    4
    5
    6
    7
    8

    //第一个参数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);

CAS缺陷

  • CAS 虽然高效地解决了原子操作,但是还是存在一些缺陷的,主要表现在三个方面:
    • 循环时间太长
      • 如果CAS一直不成功呢?这种情况绝对有可能发生,如果自旋 CAS 长时间地不成功,则会给 CPU 带来非常大的开销。在 J.U.C 中,有些地方就限制了 CAS 自旋的次数,例如: BlockingQueue 的 SynchronousQueue 。
    • 只能保证一个共享变量原子操作
      • 看了 CAS 的实现就知道这只能针对一个共享变量,如果是多个共享变量就只能使用锁了,当然如果你有办法把多个变量整成一个变量,利用 CAS 也不错。例如读写锁中 state 的高低位。
    • ABA 问题
      • CAS 需要检查操作值有没有发生改变,如果没有发生改变则更新。但是存在这样一种情况:如果一个值原来是 A,变成了 B,然后又变成了 A,那么在 CAS 检查的时候会发现没有改变,但是实质上它已经发生了改变,这就是所谓的ABA问题。对于 ABA 问题其解决方案是加上版本号,即在每个变量都加上一个版本号,每次改变时加 1 ,即 A —> B —> A ,变成1A —> 2B —> 3A 。

总结:

  • 从思想上来说,Synchronized属于悲观锁,悲观地认为程序中的并发情况严重,所以严防死守。CAS属于乐观锁,乐观地认为程序中的并发情况不那么严重,所以让线程不断去尝试更新。

参考