深入剖析AQS和CAS，看了都说好
前言
不知不觉写文章已经快半年了，本来之前写文章只是为了自己总结知识，不知不觉中关注的朋友越来越多了。
现在写文章不单单只是为了考虑自己能看懂，还要考虑各位读者大大是否能看懂，考虑输出文章的质量。
现在的每一次写作就好像在搞一次艺术品，细细雕琢，进行每一次的加工。文章的「逻辑性」，「易懂性」，还有「文章的排版的美观度」，都要细细斟酌。
写在前面先来一碗鸡汤：「世界上并没有什么救世主，假如有那便是你自己；世界上也没有什么奇迹，假如有那只是努力的另一个名字罢了。」
想想自己毕业差不多一年来走过来的路，看看现在的自己，一切都值得，往后还会不断的努力，看到越来越强的自己。
上一篇讲到Redis篇的内存满了的问题，并带说明了这篇文章[看完这篇Redis缓存三大问题，保你能和面试官互扯。]比较受欢迎，然后一下子的阅读量升到1.1k，感谢读者大大们的肯定。
话不多说下面就直接上干货了，今天来深入的了解CAS和AQS，文章采用层次式、图文并茂的方式一层一层的进行剖析，让各位读者大大能够深入理解。
AQS简介
AQS（AbstractQueuedSynchronizer）为「抽象队列同步器」，简单的说「AQS就是一个抽象类」，抽象类就是AbstractQueuedSynchronizer，没有实现任何的接口，「仅仅定义了同步状态（state）的获取和释放的方法」。
它提供了一个「FIFO队列」，多线程竞争资源的时候，没有竞争到的线程就会进入队列中进行等待，并且「定义了一套多线程访问共享资源的同步框架」。
在AQS中的锁类型有两种：分别是「Exclusive(独占锁)「和」Share(共享锁)」。
「独占锁」就是「每次都只有一个线程运行」，例如ReentrantLock。关于ReentrantLock之前写过一篇详细的源码文章，喜欢的可以看一看[【源码篇】深入Lock锁底层原理实现，手写一个可重入锁]。
「共享锁」就是「同时可以多个线程运行」，如Semaphore、CountDownLatch、ReentrantReadWriteLock。
AQS源码分析
在AQS的源码可以看到对于「state共享变量」，使用「volatile关键字」进行修饰，从而「保证了可见性」，若是对于volatile关键字不熟悉的可以参考这一篇[面试造飞机系列：volatile面试的连环追击，你还好吗？]。
从上面的源码中可以看出，对于state的修改操作提供了setState和compareAndSetState，「那么为什么要提供这两个对state的修改呢？」
因为compareAndSetState方法「通常使用在获取到锁之前」，当前线程不是锁持有者，对于state的修改可能存在线程安全问题，所以「需要保证对state修改的原子性操作」。
而setState方法通常用于当前正持有锁的线程对「state共享变量」进行修改，因为不存在竞争，是线程安全的，所以没必要使用CAS操作。
分析了AQS的源码的实现，接下来我们看看AQS的实现的原理。这里AQS的实现源码和理论都会比较简单，因为还没有涉及到具体的实现类。
AQS实现原理
上面说到AQS中维护了一个「FIFO队列」，并且「该队列是一个双向链表」，链表中的每一个节点为「Node节点」，「Node类是AbstractQueuedSynchronizer中的一个内部类」。
让我们来看看AQS中Node内部类的源码，这样有助于我们能够对AQS的内部的实现更加的清晰：
static final class Node {
static final Node SHARED = new Node();
static final Node EXCLUSIVE = null;
static final int CANCELLED = 1;
static final int SIGNAL = -1;
static final int CONDITION = -2;
static final int PROPAGATE = -3;
volatile int waitStatus;
volatile Node prev;
volatile Node next;
volatile Thread thread;
Node nextWaiter;
final boolean isShared() {
return nextWaiter == SHARED;
}
final Node predecessor() throws NullPointerException {
Node p = prev;
if (p == null)
throw new NullPointerException();
else
return p;
}
Node() { // Used to establish initial head or SHARED marker
}
Node(Thread thread, Node mode) { // Used by addWaiter
this.nextWaiter = mode;
this.thread = thread;
}
Node(Thread thread, int waitStatus) { // Used by Condition
this.waitStatus = waitStatus;
this.thread = thread;
}
}
可以看到上面的Node类比较简单，只是对于每个Node节点拥有的属性进行维护，在Node内部类中最重要的基本构成就是这几个：
volatile Node prev; volatile Node next; volatile Thread thread;「根据源码的分析和线程的竞争共享资源的原理」，关于AQS的实现原理，我这里画了一张图：
在FIFO队列中，「头节点占有锁」，也就是头节点才是锁的持有者，尾指针指向队列的最后一个等待线程节点，除了头节点和尾节点，节点之间都有「前驱指针」和「后继指针」
在AQS中维护了一个「共享变量state」，标识当前的资源是否被线程持有，多线程竞争的时候，会去判断state是否为0，尝试的去把state修改为1
分析了AQS的源码的实现和原理实现，但是AQS里面具体是没有做同步的具体实现，如果要什么了解AQS的具体的实现原理，要需要看AQS的具体实现类，这边就以ReentrantLock为例。
ReentrantLock实现原理
如果多线程在竞争共享资源时，「竞争失败的线程就会添加入FIFO队列的尾部」。
在ReentrantLock的的具体实现中，这边以在ReentrantLock的非公平锁的实现为例，因为公平锁的实现，之前已经写过一篇文章分析过了。
我们来看看新添加节点的源码写的实现逻辑：
当竞争锁资源的线程失败后直接进入acquire(1)方法，来来看看acquire(1)的具体实现：
从源码中可以看出，acquire(1)的实现主要有这三步的逻辑：
tryAcquire(arg)：尝试再次获取锁。addWaiter(Node.EXCLUSIVE)：若是获取锁失败，就会将当前线程组装成一个Node节点，进行入队操作。acquireQueued(addWaiter(Node.EXCLUSIVE), arg))：acquireQueued方法以addWaiter返回的头节点作为参数，内部实现进行锁自旋，以及判断是否应该执行线程挂起。
下面我们再来看看tryAcquire(arg)的源码，从上面的看一看出arg的值为1，具体的实现源码如下：
从源码的分析中可以看出，tryAcquire(arg)的实现也就是判断state的值是否已经被释放，「若释放则当前线程就会CAS操作将state设置为1，若是没有释放，就会判断是否可以进行锁的重入」。
分析完tryAcquire(arg)的实现，来看看addWaiter，入队操作的实现源码如下：
从上面的源码分析，可以看出对于新加入的线程添加到双向链表中使用尾插法，具体的实现原理图如下所示。
从上图分析，当线程加入队列中，主要进行这几步操作「新加入的节点prev指针指向原来的tail节点，原来的tail节点的next指针指向新加入的节点」，这个也就是常见的「双向链表尾插法」的操作。
「最后把tail指向新加入的节点」，如此一来就完成了新加入节点的入队操作，接下来我们接着分析源码。
当然这里的前提是「队列中不为空」，若是为空的话，不会走上面的逻辑，而是走enq(node)，进行初始化节点，我们来看看enq(node)操作，源码如下：
执行完上面的入对操作后，接着执行acquireQueued方法，来看看它的具体实现源码：
从上上面的源码中可以看出，涉及到「头节点head的出队」操作，并且将「当前线程的node节点晋升为head节点」。
因为只有「头节点才是锁的持有者」，所以对于head节点的出队操作，head的指向会随时改变，我这里画了一张原理图如下所示：
具体实现如上图所示，会把「原来的头节点进行出队操作，也就是把原来的头节点next指针指向null，原来第二节点的prev指针指向null」。
最后把head指针指向第二节点，当然thread2同时还会修改共享状态变量state的值，如此一来就完成了锁的释放。
当释放完锁之后，就会执行shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt()判断当前的线程是否应该被挂起，我们来看看它的源码实现：
在shouldParkAfterFailedAcquire中的实现，当前驱节点的状态量waitStatus为SIGNAL的时候，就会挂起。
通过上面的分析对于AQS的实现基本有比较清晰的认识，主要是对实现类ReentrantLock的实现原理进行深入的分析，并且是基于「非公平锁」和「独占锁」的实现。
在AQS的底层维护了一个「FIFO队列」，多线程竞争共享资源的时候，「失败的线程会被添加入队列中」，「非公平锁」实现中，新加入的线程节点会「自旋」尝试的获取锁。
分析完AQS我们来分析CAS，「那么什么是CAS呢？」
CAS简介
在分析ReentrantLock的具体实现的源码中，可以看出所有涉及设置共享变量的操作，都会指向CAS操作，保证原子性操作。
CAS(compare and swap)原语理解就是比较并交换的意思，「CAS是一种乐观锁的实现」。
在CAS的算法实现中有三个值：「更新的变量」、「旧的值」、「新值」。在修改共享资源时候，会与原值进行比较，若是等于原值，就修改为新值。
于是在这里的算法实现下，即使不加锁，也能保证数据的可见性，即使的发现数据是否被更改，若是数据已经被更新则写操作失败。
但是CAS也会引发ABA的问题，「什么是ABA问题呢？」 不慌请听我详细道来
ABA问题
ABA问题就是假如有两个线程，同一时间读取一个共享变量state=1，此时两个线程都已经将state的副本赋值到自己的工作内存中。
当线程一对state修改state=state+1，并且写入到主存中，然后线程一又对state=state-1写入到主存，此时主存的state是变化了两次，只不过又变回了原来的值。
那么此时线程二修改state的时候就会修改成功，这就是ABA问题。对于「ABA问题的解决方案就是加版本号（version）」，每次进行比较的时候，也会比较版本号。
因为版本版是只增不减，比如以时间作为版本号，每一时刻的时间都不一样，这样就能避免ABA的问题。
CAS性能分析
相对于「synchronized的阻塞算法」的实现，「CAS采用的是乐观锁的非阻塞算法」的实现，一般CPU在进行线程的上下文切换的时间比执行CPU的指令集的时间长，所以CAS操作在性能上也有了很大的提升。
但是所有的算法都是没有最完美的，在执行CAS的操作中，没有更新成功的就会自旋，这样也会消耗CPU的资源，对于CPU来说是不友好的。
-End-