JUC学习笔记（1）-CAS

作者: 胖小白_d797 | 来源:发表于2018-11-12 09:51 被阅读0次

1.什么是CAS

CAS是一种无锁执行的算法原理。全称Compare And Swap
其算法核心思想如下

/**  ***以下为伪代码***
 * V : 要更新的变量
 * E : 预期更新前的值
 * U : 更新后的值
 */
boolean CAS(V, E, U) {
   if (V == E) {
       V = U;              // 当V与预期值相等，则更新并返回true
       return true;
   } else {
       return false;       // 否则什么也不做
   }
}

2.Unsafe类

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

获取Unsafe实例对象
获取Unsafe实例对象不能直接new Unsafe()或调用Unsafe.getUnsafe(),Unsafe类的构造方法是私有的，是单例的，getUnsafe()方法，只提供给高级的Bootstrap类加载器使用，普通用户调用将抛出异常.

    @CallerSensitive
    public static Unsafe getUnsafe() {
        Class var0 = Reflection.getCallerClass();
        if(!VM.isSystemDomainLoader(var0.getClassLoader())) {
            throw new SecurityException("Unsafe");
        } else {
            return theUnsafe;
        }
    }

获取方法：

//方法一：我们可以令我们的代码“受信任”。运行程序时，使用bootclasspath选项，指定系统类路径加上你使用的一个Unsafe路径
java -Xbootclasspath:/usr/jdk1.7.0/jre/lib/rt.jar:. com.xxx.xxx.UnsafeClient(你的class)

// 方法二
static {
    try {
        Field field = Unsafe.class.getDeclaredField("theUnsafe");
        field.setAccessible(true);
        UNSAFE = (Unsafe) field.get(null);
    } catch (Exception e) {
    }
}

Unsafe里的CAS 操作相关

CAS是一些CPU直接支持的指令，在Java中无锁操作CAS基于以下3个方法实现

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

3.原子操作类(Atomic)

java.util.concurrent.atomic包中提供了许多基于CAS实现的原子操作类，用法方便，性能高效，主要分以下4种类型。

原子更新基本类型
原子更新基本类型主要包括3个类：
AtomicBoolean：原子更新布尔类型
AtomicInteger：原子更新整型
AtomicLong：原子更新长整型
这3个类的实现原理和使用方式几乎是一样的，以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在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变量value
    private volatile int value;
 
  
   //获取当前最新值，
    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;
    }
   //....
}

通过上述的分析，可以发现AtomicInteger原子类的内部几乎是基于前面分析过Unsafe类中的CAS相关操作的方法实现的，这也同时证明AtomicInteger是基于无锁实现的，这里重点分析自增操作实现过程，其他方法自增实现原理一样。

我们发现AtomicInteger类中所有自增或自减的方法都间接调用Unsafe类中的getAndAddInt()方法实现了CAS操作，从而保证了线程安全，关于getAndAddInt其实前面已分析过，它是Unsafe类中1.8新增的方法，源码如下

//Unsafe类中的getAndAddInt方法
public final int getAndAddInt(Object o, long offset, int delta) {
        int v;
        do {
            v = getIntVolatile(o, offset);
        } while (!compareAndSwapInt(o, offset, v, v + delta));
        return v;
    }

可看出getAndAddInt通过一个while循环不断的重试更新要设置的值，直到成功为止，调用的是Unsafe类中的compareAndSwapInt方法，是一个CAS操作方法。这里需要注意的是，上述源码分析是基于JDK1.8的，如果是1.8之前的方法，AtomicInteger源码实现有所不同，是基于for死循环的，如下

//JDK 1.7的源码，由for的死循环实现，并且直接在AtomicInteger实现该方法，
//JDK1.8后，该方法实现已移动到Unsafe类中，直接调用getAndAddInt方法即可
public final int incrementAndGet() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return next;
    }
}

CAS的ABA问题及其解决方案
假设这样一种场景，当第一个线程执行CAS(V,E,U)操作，在获取到当前变量V，准备修改为新值U前，另外两个线程已连续修改了两次变量V的值，使得该值又恢复为旧值，这样的话，我们就无法正确判断这个变量是否已被修改过.这就是典型的CAS的ABA问题，一般情况这种情况发现的概率比较小，可能发生了也不会造成什么问题，比如说我们对某个做加减法，不关心数字的过程，那么发生ABA问题也没啥关系。但是在某些情况下还是需要防止的，那么该如何解决呢？在Java中解决ABA问题，我们可以使用以下两个原子类
AtomicReference类

public class AtomicLearn {
    private static AtomicReference<MyObject>  user;

    public static void main(String [] args) {

        user = new AtomicReference<>();
        MyObject object = new MyObject();
        object.setId(100001);
        object.setName("胖小白");
        object.setAcBal(new BigDecimal("0"));
        user.set(object);

        for (int i = 0; i < 5; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    MyObject expect = user.get();
                    MyObject object = new MyObject();
                    object.setId(100001);
                    object.setName("胖小白");
                    object.setAcBal(expect.getAcBal().add(new BigDecimal("100")));
                    System.out.println(Thread.currentThread().getName() +":用户100001-胖小白当前余额:" + expect.getAcBal());
                    boolean result = user.compareAndSet(expect, object);
                    System.out.println(Thread.currentThread().getName() +":用户100001-胖小白更新为:" + object.getAcBal() +"结果:" + result);
                }
            }).start();
            new Thread(new Runnable() {
                @Override
                public void run() {
                    MyObject expect = user.get();
                    MyObject object = new MyObject();
                    object.setId(100001);
                    object.setName("胖小白");
                    object.setAcBal(expect.getAcBal().subtract(new BigDecimal("100")));
                    System.out.println(Thread.currentThread().getName() +":用户100001-胖小白当前余额:" + expect.getAcBal());
                    boolean result = user.compareAndSet(expect, object);
                    System.out.println(Thread.currentThread().getName() +":用户100001-胖小白更新为:" + object.getAcBal() +"结果:" + result);
                }
            }).start();
        }

    }
}

AtomicReference与其他的Atomic基础类一样存在ABA的问题。

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问题发生的概率。

自旋锁
自旋锁是一种假设在不久将来，当前的线程可以获得锁，因此虚拟机会让当前想要获取锁的线程做几个空循环(这也是称为自旋的原因)，在经过若干次循环后，如果得到锁，

就顺利进入临界区。如果还不能获得锁，那就会将线程在操作系统层面挂起，这种方式确实也是可以提升效率的。但问题是当线程越来越多竞争很激烈时，

占用CPU的时间变长会导致性能急剧下降，因此Java虚拟机内部一般对于自旋锁有一定的次数限制，可能是50或者100次循环后就放弃，直接挂起线程，让出CPU资源。

通过AtomicReference可实现简单的自旋锁。

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);
  }
}

使用CAS原子操作作为底层实现，lock()方法将要更新的值设置为当前线程，并将预期值设置为null。unlock()函数将要更新的值设置为null，并预期值设置为当前线程。然后我们通过lock()和unlock来控制自旋锁的开启与关闭，注意这是一种非公平锁。事实上AtomicInteger(或者AtomicLong)原子类内部的CAS操作也是通过不断的自循环(while循环)实现，不过这种循环的结束条件是线程成功更新对于的值，但也是自旋锁的一种。

JUC.png

JUC学习笔记（1）-CAS

1.什么是CAS

2.Unsafe类

3.原子操作类(Atomic)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读