Java CAS

2020-05-28

本文主要是对于Java CAS 的学习整理加深记忆。
有时候，很多知识都停留在印象中的大概了解，或者认识了名称，知道xxx名字概念的存在，
或者曾经在xxx博客中看到过。对于学习这件事，如果只停留在看、思考的过程。即使有所有收获，没有真正的去实践，
相信过不了多久也会遗之脑后。好记性不如烂笔头，至少也应该以文字记录自己的思考、实践过程作为输出，这样学习过程更为完美。

一、什么是CAS？

CAS 全称是 Compare And Swap 意思是比较并且交换。CAS 其实就是乐观锁的一种实现方式，首先假设数据没有被修改，所以每次去操作数据时没有上锁。
在 Java 中 java.util.concurrent.atomic包的原子操作类就是使用 CAS 实现的。下面以AtomicInteger的部分代码片段来看，当需要更新变量值时，
会检查有没有冲突，如果存在冲突，则会重试，直到更新成功。

/**
 * Atomically increments by one the current value.
 *
 * @return the previous value
 */
public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);
}


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

二、CAS 的操作是怎样的？

CAS 的操作中包含有三个操作数，分别是：

V--内存值
A--需要进行比较的原预期值
B--拟写入的新值

更新变量时，会对 V内存值与 A预期值进行比较，如果相等则把 V内存值修改为 B新值

举一个栗子：
最初内存值V = 10
1. 对线程1 ：来说 A预期值=10 ， B拟更新值=11；
2. 此时存在线程2 抢先一步修改 V值=11
3. 线程1 要提交更新 V值，会比较内存值V 和预期值B 是否相等，如果相等则提交更新，否则更新失败，然后重试（也就是自旋）直到成功为止。
因为线程2 抢先更新了内存值V=11, 线程1 进行内存值V 与预期值A 比较发现 V!=A 线程1提交修改失败。
4. 线程1 自旋重新获取到内存值V=11，此时预期值A=11, 新值B=12，因为没有其他线程争抢改变内存值V，比较Compare 相等更新SWAP 成功。此时内存值V=12

与 Synchronized 对比来看，Synchronized属于悲观锁，一开始悲观的认为程序并发很严重，需要严格的防控，避免出现线程不安全问题出现。
而 CAS 则是乐观锁，乐观认为程序并发并不严重，可以让线程尝试不断的获取内存值比较并且更新。

三、CAS缺点

CPU 开销大
在并发较高的情况下，多个线程同时尝试争抢更新同一个资源，而又一直不成功，一直在不停的自旋，这样不停的重复，就会给CPU带来非常大的开销。
只能保证一个共享变量的原子操作，不能保证代码块的原子性操作。
ABA问题
比如两个线程
1. 线程1 查询V=a 与预期值 A=a比较
2. 线程2 查询V=a 与预期值 A=a 比较相等更新V=b
3. 线程2 查询V=b 与预期值 A=b 比较相等更新V=a
4. 线程1 与预期值 A=a 比较相等更新V=b
从上面2、3步骤来看，V的值经历了 a->b b->a 的赋值过程。这就是著名的ABA问题。

有可能出现的场景：
比如后台取款减少金额、转账收款增加金额分别在两个不同的线程。
甲账户余额100，提现取款金额50
线程1 内存值V=100 预期值A=100 拟更新值B=50
假设甲误操作多了一次，重复点击提现，又发起了一次提现请求后台新增加一个线程2
线程2 内存值V=100 预期值A=100 拟更新值B=50
由于某种原因线程2 被阻塞block 了，线程1 更新内存值V=50 此时乙向甲的账号转账 50
线程3 内存值V=50 预期值A=50 拟更新值B=100
线程3执行完成后，内存值V=100，此时线程2从block 中恢复过来，比较 V=A 然后更新内存值V=50
最后甲的账户余额 = (100-50+50-50) 而实际上应该是 =(100-50+50)

看到一个很有意思的解答是，A的女朋友出轨了，然后又回到A的身边，那么这个女朋友还是A的女朋友吗？哈哈哈。

模拟出现ABA代码如下

public static void main(String[] arg){
      AtomicInteger atomicInteger = new AtomicInteger(10);
      Thread t1 = new Thread(new Runnable() {
          @Override
          public void run() {
              atomicInteger.compareAndSet(10,11);
              atomicInteger.compareAndSet(11,10);
              System.out.println("t2 atomicInteger value is :"+atomicInteger.get());
          }
      });

      Thread t2 = new Thread(new Runnable() {
          @Override
          public void run() {
              try {
                  Thread.sleep(1000);
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
              atomicInteger.compareAndSet(10,11);
              System.out.println("t2 atomicInteger value is :"+atomicInteger.get());
          }
      });

      t1.start();
      t2.start();
  }

那么如何避免出现ABA问题呢？
在java.util.concurrent.atomic包下，提供了带有版本和标记的的原子引用类 AtomicStampedReference、AtomicMarkableReference
可以通过版本控制来确保CAS操作中内存值的正确性。
使用如下:

public static void main(String[] arg){
    AtomicStampedReference<Integer> atomicInteger = new AtomicStampedReference<Integer>(10,1);

    Thread t1 = new Thread(new Runnable() {
        @Override
        public void run() {
            atomicInteger.compareAndSet(10,11,atomicInteger.getStamp(),atomicInteger.getStamp()+1);
            atomicInteger.compareAndSet(11,10,atomicInteger.getStamp(),atomicInteger.getStamp()+1);
            System.out.println("t2 atomicInteger value is :"+atomicInteger.getReference());
        }
    });

    Thread t2 = new Thread(new Runnable() {
        @Override
        public void run() {
            int stamp = atomicInteger.getStamp();
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("t2 compareAndSet:"+atomicInteger.compareAndSet(10,11,stamp,stamp+1));
            System.out.println("t2 atomicInteger value is :"+atomicInteger.getReference());
        }
    });
    t1.start();
    t2.start();
}

四、CAS与Synchronized的使用情景：

对于资源竞争较少（线程冲突较轻）的情况，使用synchronized同步锁进行线程阻塞和唤醒切换以及用户态内核态间的切换操作额外浪费消耗cpu资源；
而CAS基于硬件实现，不需要进入内核，不需要切换线程，操作自旋几率较少，因此可以获得更高的性能。
对于资源竞争严重（线程冲突严重）的情况，CAS自旋的概率会比较大，从而浪费更多的CPU资源，效率低于synchronized。

想要获取更多关于CAS的信息，推荐 https://zh.wikipedia.org/wiki/%E6%AF%94%E8%BE%83%E5%B9%B6%E4%BA%A4%E6%8D%A2