CAS原理解析及源码分析
CAS锁
CAS是一种无锁算法；它的全称：Compare and Swap（比较和交换）
算法思想
CAS在操作的过程中主要有三个参数：一、内存中的值V(可以理解为实际当前时刻真实的值)；二、旧值A(可以理解为上次记录的修改的值)；三、要修改的新值B(可以理解为需要修改后的值)
CAS的整体思路是：它首先会将内存中的值V与旧值A进行比较；如果一样就会将内存中的值V修改为要修改的新值B；如果不一样则就说明同一时刻该值被另一个线程修改过，此时就什么也不做。整个操作都属于原子操作。（下个循环继续）
拿案例说明
new Thread(()-->{
int i = 10;
i++;
})
假设此时有两个线程A、B同时执行上面代码；他们会有各自的工作内存；线程A、B竞争，假设线程A首先读取内存值，与就是比较符合预期，即10 == 10；此时就是将11更新到内存；但是此时线程B已经将10读入了工作内存，这个是作为旧值，此时再与内存中的值比较会发现11 != 10；说明共享数据已经被修改，放弃已经所做的操作，然后拿新的内存的作为旧值，重新执行刚才的操作。直至下一次的重新操作则会成功修改；
记住：CAS这里会有个不停的循环过程
Java中CAS的应用
在java.util.concurrent.atomic包下有一系列的类，这些类基本上都使用了CAS；
下面我们以AtomicInteger进行说明（代码主要是使用了20个线程进行自增10000次来证明原子性.运行结果是：200000）：
public class MyThread {
private static AtomicInteger race = new AtomicInteger(0);
private static final int THREADS_COUNT = 20;
private static void increase() {
race.incrementAndGet();
}
public static void main(String[] args) throws InterruptedException {
Thread[] threads = new Thread[THREADS_COUNT];
for (int i = 0; i < THREADS_COUNT; i++) {
threads[i] = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 10000; i++) {
increase();
}
}
});
threads[i].start();
threads[i].join();
}
System.out.println(race);
}
}
//程序运行结果为：200000
程序输出正确结果，一切都要归功于AtomicInteger的incrementAndGet()方法的原子性，该方法无限循环，不断尝试将一个一个比当前值大1的新值赋给自己，如果失败了那说明在执行“获取-设置“操作的时候值已经有了修改，于是再次循环进行下一次操作，只带设置成功为止，它的原理实现其实非常简单。
下面我们看下AtomicInteger的incrementAndGet()方法的源码：
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
实际调用的是unsafe的getAndAddInt方法：
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;
}
由AtomicInteger源码我们可以看出；CAS的实现就是Unsafe类中的各个方法；Unsafe中的方法都是native本地方法；这是完全依赖于硬件的功能，通过他实现了原子操作。在执行过程中不允许被中断。同样这个内存的值value是用volatile关键字进行修饰这保证了可见性；防止了数据不一致问题。
- 1、Unsafe。是CAS的核心类，由于Java方法无法直接访问底层系统，需要通过本地（native）方法来访问，Unsafe相当于一个后门，基于该类可以直接操作特定内存的数据。Unsafe类存在于sun.misc包中，其内部方法操作可以像C指针一样直接操作内存。
- 2、保证原子性的atmicInteger中的incrementAndGet方法中使用了Unsafe的getAndAddInt方法，包含三个参数，this指当前操作对象，valueOffset表示该变量值在内存中的偏移地址，因为Unsafe就是根据内存偏移地址去获取数据的，最后一个参数是增加值，固定为1。
- 3、在compareAndSwapInt方法中，var1就是AtomicInteger对象本身，var2是该对象值的引用地址，var4是指需要变动的数量，而var5指的是用var1、var2找出的主内存中真实的值。用该对象当前的值与var5（也就是预期值）比较，如果相同，则更新值并返回true，如果不同，继续取值然后再比较，直至更新完成。
- 4、变量value用volatile修饰，保证了多线程之间的内存可见性。
CAS与synchronizedb比对
- synchronized是属于独占资源，同一时间段只允许有一个线程来访问，一致性得到了保障，但是并发性下降。
- CAS并没有加锁而是进行多次地取值并比较，这样既保障了一致性，又提高了并发性。
CAS如何保证原子性
这里我们先回已一下CAS的思想：
它首先会将内存中的值V与旧值A进行比较；如果一样就会将内存中的值V修改为要修改的新值B；如果不一样则就说明同一时刻该值被另一个线程修改过，此时会将内存中的值V更新到旧值A；然后继续下面循环比较工作，直至成功。
这里其实存在一个问题，一个线程在进行内存中的值V与旧值A进行比较的时候通过，当需要修改的前一时刻，内存中的值V内存中的值发生变化；这个时候就会出现线程安全的问题。所以CAS保证了这个比较与更新的过程是原子性的；这样就会线程安全。
那么CAS如何保证原子性？这里简单说下
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
var5 = this.getIntVolatile(var1, var2);
// CAS的实现就是 compareAndSwapInt方法；此方法是native方法
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
所以说这里保证原子性就在本地方法，也就是C++进行实现的；再底层的最终实现是通过lock cmpxchg 指令；其中lock是一个锁总线的一个锁；保证了多核CPU下的指令同步。
CAS缺点
- 循环时间长，开销很大。如果CAS失败，会一直进行尝试，如果长时间一直不成功，可能会给CPU带来很大的开销。
- 只能保证一个共享变量的原子操作。
- 引发ABA问题
ABA问题
何为ABA问题？
如果一个内存中的值V初次读取的时候是A，当我们在准备更新的时候检查它的值还是A，在初次读取到开始检查之前我们不能确保内存中的值V有没有被其他线程改过！
因为在这段时间如果我们有一个线程将内存中的值V先改成B，然后又改成了A；那么CAS在前面的操作就会认为内存中的值V一直没有变过；这个就是ABA问题。
代码模拟ABA
public class AtomicTest extends Thread {
private static AtomicInteger atomicInteger = new AtomicInteger(19);
public static void main(String[] args) throws InterruptedException {
AtomicTest thread01 = new AtomicTest();
thread01.start();
// 设置账户初始值小于20，这是一个需要被充值的客户
System.out.println("主线程将19先修改20：" + atomicInteger.compareAndSet(19, 20));
System.out.println("主线程将20又修改19：" + atomicInteger.compareAndSet(20, 19));
thread01.join();
System.out.println("atomicInteger最终结果：" + atomicInteger.get());
}
@Override
public void run() {
try {
Thread.sleep(100);
System.out.println("子线程将19修改21：" + atomicInteger.compareAndSet(19, 21));
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
//程序输出：
主线程将19先修改20：true
主线程将20又修改19：true
子线程将19修改21：true
atomicInteger最终结果：21
如果需要解决ABA问题，原子引用类提供了一个带有标记的类 - AtomicStampedReference;或者改用传统的互斥同步（典型的就是synchronized 和Lock）可能会比原子类更高效。
AtomicStampedReference
AtomicStampedReference内部维护了一个stamp版本号，主要用来解决ABA问题。
示例代码
public class AtomicTest extends Thread {
private static AtomicStampedReference<Integer> atomicStampedReference =
new AtomicStampedReference<>(1, 1);
public static void main(String[] args) throws InterruptedException {
AtomicTest thread01 = new AtomicTest();
thread01.start();
Thread.sleep(100);
System.out.println("主线程将AtomicStampedReference(1,1)修改为(2,2)：" +
atomicStampedReference.compareAndSet(1, 2, atomicStampedReference.getStamp(), atomicStampedReference.getStamp() + 1));
System.out.println("主线程将AtomicStampedReference(2,2)又修改(1,3)：" +
atomicStampedReference.compareAndSet(2, 1, atomicStampedReference.getStamp(), atomicStampedReference.getStamp() + 1));
thread01.join();
}
@Override
public void run() {
try {
int stamp = atomicStampedReference.getStamp();
System.out.println("子线程获取AtomicStampedReference版本号：" + stamp);
Thread.sleep(300);
System.out.println("子线程将AtomicStampedReference(1,1)修改(3,2)：" +
atomicStampedReference.compareAndSet(1, 3, stamp, atomicStampedReference.getStamp() + 1));
System.out.println("子线程获取AtomicStampedReference实际版本号：" + atomicStampedReference.getStamp());
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
}
//程序输出：
子线程获取AtomicStampedReference版本号：1
主线程将AtomicStampedReference(1,1)修改为(2,2)：true
主线程将AtomicStampedReference(2,2)又修改(1,3)：true
子线程将AtomicStampedReference(1,1)修改(3,2)：false
子线程获取AtomicStampedReference实际版本号：3
AtomicStampedReference内存需要自己手动去维护这个版本号stamp；如果版本号维护的有问题（类似值变化的问题）其实依旧也会出现ABA问题；所以注意版本号的维护，AtomicStampedReference其实是把ABA问题交由我们开发人员自己去控制了
AtomicReference
