CAS（比较与交换，Compare and swap） 是一种有名的无锁算法，它是乐观锁的一种实现方式。所以在进行CAS原理分析的时候，我们先来了解什么是乐观锁，什么是悲观锁~
乐观锁与悲观锁
乐观锁和悲观锁是在数据库中引入的名词，但是在我们Java的JUC里面的锁也引入类似的思想！我们来看看两种锁的概念
悲观锁
悲观锁指对数据被外界修改持保守态度，认为数据很容易就会被其他线程修改，所有在数据被处理前先对数据进行加锁，并在整个数据处理过程中，使数据处于锁定状态。我们的传统数据库就会用到这种排它锁的机制，比如行锁，表锁等，读锁，写锁等，都是在操作之前上锁，操作结束提交事务之后释放锁！在Java中像Synchronized同步术语，ReentrantLock等也是悲观锁！而像volatile关键字虽然是synchronized关键字的轻量级实现，但是其无法保证原子性，所以一般也要搭配锁使用。
乐观锁
乐观锁是相对悲观锁来说，它认为数据在一般情况下不会造成冲突，别人不会去修改，所以在访问记录前不会加排它锁。但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号，时间戳来等记录。因为不加锁，所以乐观锁在多读的情况下，可以极大的提升我们的吞吐量。在我们的数据库中提供了类似write_condition机制，在Java中JUC下的原子变量类也是使用了乐观锁的一种实现方式CAS，也就是我们下面即将介绍的！
CAS（Compare And Swap）原理解析
Java中，锁在并发处理中占据了一席之地，但是使用锁有一个不好的地方，就是当一个线程没有获取到锁时会被阻塞挂起，这会导致线程上下文的切换和重新调度开销。Java提供了非阻塞的volatile关键字来解决共享变量的可见性问题，这在一定程度上弥补了锁带来的开销问题，但是volatile只能保证共享变量的可见性，不能解决读改一写等的原子性问题。
CAS就是是JDK提供的非阻塞原子性操作，通过硬件保证了比较-更新操作的原子性。它的主要原理如下：
CAS有三个操作数
- 内存值v
- 旧的预期值A
- 要修改的新值B
当多个线程尝试使用CAS同时更新一个变量的时候，只有一个能够更新成功。那就是当我们的内存值V和旧的预期值A相等的情况下，才能将内存值V修改成B！然后失败的线程不会挂起，而是被告知失败，可以继续尝试（自旋）或者什么都不做！
尝试重试
我们可以假设有两个线程，一个线程1，一个线程2,同时对我们的内存值进行自增！我们的内存值刚开始是0，旧的预期值也是0。
- 这个时候线程1进来了，由于我们的内存值和旧的预期值相等，所以更新我们的内存值为要修改的新值1
- 当线程1结束之后，线程2进来了，要对我们的内存值进行修改。但是发现我们的内存A（此时为1）和我们的旧的预期值不相等（此时为0）不相等，所以不能将内存值更新为我们的预期值（预期值为2），所以只能进行将旧的预期值更新为内存值（此时旧的预期值 == 内存值），并告知下一次再试试！
- 当我们的线程2重试更新内存值，此时内存值（此时为1）与我们的旧的预期值（此时为1）相等，所以可以将我们的内存值更新为我们的预期值（此时为2）。
所以，哪怕没有加锁，我们也能实现线程安全。
什么都不做
同样的，我们举例有两个线程，一个线程1，一个线程2；我们两个线程都要对内存进行更新为10。
- 我们假设线程1先进来，此时内存值与我们的旧的预期值都为0，所以可以更新，将我们要修改的新值10赋值给了内存值，完成了更新
- 当线程1完成之后，线程2进来要对我们的内存值进行修改为10，但是发现内存值与旧的预期值不相同（此时一个为10，一个为0），所以只能将旧的预期值更新为内存值，同时被告知了下次不用重试了。（因为我们的目的是将内存值更新为10，显然我们的目的已经完成了）
原子变量类简单分析
我们在开头也提到了，在我们JUC下的原子变量类也是使用CAS来保证操作的原子性。而我们的具体原子变量类有以下这些：
我们以AtomicInteger为例，找一个其中自增的方法分析一下：
public final int getAndIncrement() {
return unsafe.getAndAddInt(this, valueOffset, 1);
}
该方法主要为了自增，它调用了getAndAddInt方法。这个是方法是我们的Unsafe类下面
//var1 是this指针
//var2 是地址偏移量
//var4 是自增的数值，是自增1还是自增N
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
//获取我们的的期望值赋值给var5
var5 = this.getIntVolatile(var1, var2);
//调用了Unsafe下面的另一个方法，是一个native方法
//如果期望值var5与内存值var2相等的话，更新内存值为var5+var4，否则更新期望值为期望值为内存值
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
compareAndSwapInt方法是我们的调用native方法
// 第一和第二个参数代表对象的实例以及地址，第三个参数代表期望值，第四个参数代表更新值
public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);
它是由我们的底层c代码调用汇编使用的，最后生成出一条CPU指令cmpxchg，完成操作。这也就为啥CAS是原子性的，因为它是一条CPU指令，不会被打断。这个指令在我们早期的硬件厂商就在芯片大量使用了，比如intel。
ABA 问题
关于CAS还有一个比较典型的问题，那就是ABA问题。
ABA问题的产生是因为变量的状态值产生了环形转换，就是变量的值可以从A到B，然后再从B到A。举个例子：
- 现在我有一个变量
count=10，现在有三个线程，分别为A、B、C - 线程A和线程C同时读到count变量，所以线程A和线程C的内存值和预期值都为10
- 此时线程A使用CAS将count值修改成100
- 修改完后，就在这时，线程B进来了，读取得到count的值为100(内存值和预期值都是100)，将count值修改成10
- 线程C拿到执行权，发现内存值是10，预期值也是10，将count值修改成11
我们重点放在C上面，虽然我们的C成功的修改了值。但是内存值和预期值和我们原来的相同，C就不知道之前这个变量已经被两个线程操作过了。所以就会有一定的风险。举个风险通俗的例子：
小明在提款机，提取了50元，因为提款机问题，有两个线程，同时把余额从100变为50。
- 线程1（提款机）：获取当前值100，期望更新为50
- 线程2（提款机）：获取当前值100，期望更新为50
- 线程1成功执行，线程2某种原因block了，这时，某人给小明汇款50
- 线程3（默认）：获取当前值50，期望更新为100。这时候线程3成功执行，余额变为100
- 线程2从Block中恢复，获取到的也是100，compare之后，继续更新余额为50！！！
此时可以看到，实际余额应该为100（100-50+50），但是实际上变为了50（100-50+50-50）这就是ABA问题带来的成功提交。
我们针对这个思考，如果变量的值只能朝着一个方向转换，比如A到B，B再到C，不构成环形，就不会存在问题。在我们的Java中提供了两个原子类，为我们提供了版本号（时间戳）的方法解决了该问题！
（AtomicStampedReference和AtomicMarkableReference）。
这样我们的A-B-A就会变成1A-2B-3A这种存在，就不存在环形问题了。
总结
我们的CAS虽然解决了原子性，避免了锁的不必要开销。但是还是存在三个问题。
第一个问题就是自旋时间长开销大！有时候自旋时间过长，消耗CPU资源，如果资源竞争激烈，多线程自旋长时间消耗资源。所以我们通过具体场景来选择加锁还是通过CAS来解决，CAS是适用于多读的环境的，如果是大量读写的操作的话，还是加锁吧！
第二个问题就是我们的ABA问题！在上面已经具体介绍了，以及给上了解决方法。
第三个问题就是我们的CAS只能保证一个共享变量的原子操作。也就是说我们只能对一个变量进行赋值，不能同时更新多个。 解决的方法：把多个共享变量合并成一个共享变量。然后使用我们的AtomicReference类来保证引用对象之间的原子性。
参考资料
Java并发编程之美
公众号《Java3y》多线程系列文章
网友评论