并发编程(七)CAS

1.CAS

在AQS的加锁和释放锁阶段，多次使用了一种通用操作：compareAndSetXXX.这种操作最终会调用Unsafe中的api进行CAS操作

• CAS全称是 Compare And Swap，意思为比较和替换，是一种通过硬件实现并发安全的常用技术

  • 底层通过利用CPU的CAS指令对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作。

• CAS的实现过程主要有3个操作数：

  • 内存值V，旧的预期值E，要修改的新值U
  • 当且仅当预期值E和内存值V相同时，才将内存值V修改为U，否则什么都不做。

1.CAS执行过程.png

• CAS底层会根据操作系统和处理器的不同来选择对应的调用代码。
  • 以Windows和X86处理器为例，如果是多处理器，通过带lock前缀的cmpxchg指令对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作
  • 如果是单处理器，通过cmpxchg指令完成原子操作

2.CAS存在的问题

• CAS实现原子操作的三大问题

• • ABA问题：因为CAS需要在操作值的时候检查值有没有发生变化，如果没有发生变化则更新，如果A->B->A,那么CAS检查时会认为值没有发生变化，但是实际上却变化了；

  • • 解决办法：在变量前面追加版本号;变成1A->2B->3A

  • 循环时间长开销大：自旋CAS对CPU开销大

  • 只能保证一个共享变量的原子操作，多个共享变量操作时CAS无法保证操作的原子性；

  • • 解决办法：用锁；或者将多个共享变量合并成一个共享变量

3.CAS实现: ActomicInteger

• ActomicInteger是对int类型的一个封装，提供原子性的访问和更新操作，其原子性操作的实现是基于CAS技术

public class AtomicInteger extends Number implements java.io.Serializable {

    private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
    private static final long VALUE;

    static {
        try {
            VALUE = U.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (ReflectiveOperationException e) {
            throw new Error(e);
        }
    }

    private volatile int value;

    public AtomicInteger(int initialValue) {
        value = initialValue;
    }

    public AtomicInteger() {
    }

    public final int get() {
        return value;
    }

    public final void set(int newValue) {
        value = newValue;
    }
    
    public final int getAndSet(int newValue) {
        return U.getAndSetInt(this, VALUE, newValue);
    }

    public final boolean compareAndSet(int expect, int update) {
        return U.compareAndSwapInt(this, VALUE, expect, update);
    }

    public final boolean weakCompareAndSet(int expect, int update) {
        return U.compareAndSwapInt(this, VALUE, expect, update);
    }

    public final int getAndIncrement() {
        return U.getAndAddInt(this, VALUE, 1);
    }

    public final int getAndDecrement() {
        return U.getAndAddInt(this, VALUE, -1);
    }

    public final int getAndAdd(int delta) {
        return U.getAndAddInt(this, VALUE, delta);
    }

    public final int incrementAndGet() {
        return U.getAndAddInt(this, VALUE, 1) + 1;
    }

    public final int decrementAndGet() {
        return U.getAndAddInt(this, VALUE, -1) - 1;
    }

    public final int addAndGet(int delta) {
        return U.getAndAddInt(this, VALUE, delta) + delta;
    }
}

• 解析
  • AtomicInteger类的同步实现依赖于Unsafe提供的底层能力
  • 变量value使用volatile修饰，保证了多线程之间的内存可见性
• 以getAndIncrement方法为例,该方法会调用Unsafe的getAndAddInt方法

public class AtomicInteger {
    
    public final int getAndIncrement() {
        return U.getAndAddInt(this, VALUE, 1);
    }
}

public final class Unsafe {
    private static final Unsafe theUnsafe;
    
    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);

}

• 在Unsafe的getAndAddInt方法中，会首先去获取AtomicInteger属性VALUE的值（调用方法getIntVolatile）赋值为var5，然后调用native方法compareAndSwapInt去修改VALUE的值，其中涉及到三个操作变量
  • 内存值V：AtomicInteger属性VALUE指针
  • 旧的预期值E：VALUE的原来的值var5
  • 要修改的新值U：var5+var4
• 如果native方法compareAndSwapInt返回true，则说明cas原子操作value的值成功

多线程场景下原子操作

1. 假设线程1和线程2通过getIntVolatile拿到value的值都为1，线程1被挂起，线程2继续执行
2. 线程2在compareAndSwapInt操作中由于预期值和内存值都为1，因此成功将内存值更新为2
3. 线程1继续执行，在compareAndSwapInt操作中，预期值为1，而当前的内存值为2，cas操作失败，什么都做，返回false
4. 线程1重新通过getIntVolatile拿到最新的value值为2，再进行一次compareAndSwapInt操作，这次操作成功，内存值更新为3.