CAS

之前讲锁的实现的时候讲到了CAS，但没有详细的讲述CAS是什么，只是说明了CAS能保证原子性，那么原子性是什么？CAS到底又是什么呢？

对于原子性、可见性、有序性可以自行学习，如果有时间，可以单开一篇讲述。

在讲CAS之前，我们先来想想，在多线程下，Java如何保证同步，首先会想到的就是synchronized关键字
但是众所周知，synchronized是一个重量级的关键字，它会导致有锁，导致性能不高。
而volatile只能保证可见性，并不能保证原子性。（volatile的相关知识可自行学习）
那么为了保证同步，锁机制是必然需要的。
synchronized是一种独占锁，也是一种悲观锁，他相信一定有线程去修改他，那么他要让其他线程挂起等待，直到锁被释放，这样的效率是较低的。
那么相对的，乐观锁的效率会更高一些，所谓乐观锁，就是相信没有其他线程去修改他（如果修改失败了，继续重试，直到成功）。

CAS:Compare And Swap
CAS指的是现代CPU广泛支持的一种对内存中的共享数据进行操作的特殊指令。
简单讲一下这个指令的操作过程：首先CPU会将内存中需要被更改的数据与期望值进行对比。当两个值相等时，CPU才会将值替换成新的值，否则认为更改失败，不做任何操作。这一系列的操作是原子的。
简单的说，CAS指令有三个参数，内存值V，旧的预期值A，新的修改的值B，当且仅当内存值V和旧的预期值A相同时，内存值V才会修改成B。

CAS会带来一个著名的ABA问题
1.进程P1在共享变量中读到值为A
2.P1被抢占了，进程P2执行
3.P2把共享变量里的值从A改成了B，再改回到A，此时被P1抢占。
4.P1回来看到共享变量里的值没有被改变，于是继续执行。
尽管CAS还是会成功执行，但是这样会带来隐藏的问题。

例如现在有一个队列A->B->C，此时head=A, 通过CAS操作将A替换成B,此时进程P1在内存的共享变量中读到值为A
在这个时候进程P1被抢占了，进程P2执行
P2把A,B,C三个值都pop掉，再将A,C,D三个值push进来，此时队列变成了A->C->D，但是head仍为A，此时被P1抢占
P1回来看到共享变量里面的值没有被改变，于是继续执行，此时head就变成了B，此时B.next = null, 队列里就只剩下了B，丢失了C、D两个值。
对于ABA问题，一般的解决方案是加上版本号来区分是否真的没有被修改过，在Java中AtomicStampedReference<E>也实现了这个作用，有兴趣的可以了解一下，其实质是将共享变量和版本号包装成一个对象来进行CAS操作, 每次CAS传入共享变量和版本号的旧值和新值，来判断共享变量是否真的没有被改变过。