CAS算法

1. CAS算法

比较与交换（compare and swap），是一种无锁算法，即不使用锁的情况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步，所以也叫非阻塞同步（Non-blocking Synchronization）。CAS算法涉及到三个操作数：需要读写的内存值V、进行比较的值A、拟写入的新值B。当且仅当V的值等于A时，CAS通过原子方式用新值B来更新V值，否则不会执行任何操作（比较和替换是原子一个原子操作）。一般情况下是一个自旋转操作，即不断的重试。

2. CAS算法的缺点

1. ABA问题
如果一个变量V初次读取的时候是A值，并且在准备赋值的时候检查到它仍然是A值，那么我们就能说明它的值没有被其他线程修改过吗？很明显不是，因为在这段时间内它的值可能被改为其他值，然后又被改回A，那CAS操作就会认为它从来没被改过，这个问题被称为CAS操作的 “ABA” 问题。

2. 循环时间长开销大
自循环CAS（也就是不成功就一直循环执行直到成功）如果长时间不成功，会给CPU带来非常大的执行开销。如果JVM能支持处理提 pause 指令，那么效率会有一定的提升。pause指令有两个作用，第一它可以延迟流水线执行指令（pipeline），使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在推出循环的时候因内存顺序冲突（memory order violation）而引起CPU流水线被清空（CPU pipeline flush），从而提高CPU的执行效率。

3. 只能保证一个共享变量的原子操作
CAS只对单个共享变量有效，当操作涉及跨多个共享变量时CAS无效。但是 JDK1.5 开始，提供了 AtomicReference 来保证引用对象之间的原子性，你可以把多个变量放在一个对象里进行CAS操作。所以我们可以使用锁或者利用AtomicReference把多个共享变量合并成一个共享变量来操作。

自适应自旋解决的是“锁竞争时间不确定”的问题，目标是降低线程切换的成本。

3. 版本号机制

利用版本号机制解决ABA问题，一般是在数据表中加上一个数据库版本号version字段，表述数据被修改的次数当数据被修改时version值会加1。当线程A要更新数据值时，在读取数据的同时也会读取version值，在提交更新时，若刚才读取到的version值为当前数据库中的version值相等时才更新，否则重试更新操作，直到更新成功。