透过ReentrantLock窥探AQS
背景
JDK1.5引入的并发包提供了一系列支持中等并发的类，这些组件是一系列的同步器，几乎任一同步器都可以实现其他形式的同步器，例如，可以用可重入锁实现信号量或者用信号量实现可重入锁。但是，这样做带来的复杂性，开销，不灵活使其至多只能是个二流工程，且缺乏吸引力。如果任何这样的构造方式不能在本质上比其他形式更简洁，那么开发者就不应该随意地选择其中的某个来构建另一个同步器，所以JSR166建立了一个小框架-AQS（由Doug Lea设计），对这些同步器做了统一的抽象，为构造同步器提供了通用的机制，之后并发包中大部分同步器都基于AQS来实现。
注：本文通过ReentrantLock来窥探AQS的结构以及运行原理，因为AQS是并发包实现大部分同步器的框架，所以本文只对ReentrantLock相关方法做了解释说明，其他的方法在后面的文章中会继续做深入的解释
AQS设计
这是ReentrantLock中的内部类Sync的类图，图中可以看出Sync抽象类实现了AbstractQueuedSynchronizer。
ReentrantLock实现
ReentrantLock提供了非公平锁以及公平锁的能力，实现Lock接口，通过把功能实现委托给Sync同步器来实现。下面以非公平锁为例子，开始图解ReentrantLock类在调用lock方法时候的过程：
首先看下AQS的数据结构以及Node节点的结构
AQS的数据结构中state是最核心的变量，用来判断当前同步器是否有被线程占用，以及被同一个线程重入了多少次(重入锁实现的关键)；
exclusiveOwerThread表示当前是哪个线程占用着同步器；
head是一个指向空的头结点的引用地址；
tail是一个指向等待同步器的最后一个节点的引用地址；
Node节点中最核心的是waitStatus，此处waitStatus的取值分别可以为：
- 1表示等待的线程已经取消或者中断；
- -1表示后一个节点需要唤醒，当前节点如果释放锁，则需要唤醒后继节点；
- -2表示当前的节点是一个条件等待，即需要等待其他的条件满足才能够被加入到同步队列，等待被唤醒
- -3表示下一个acquireShared应无条件传播(在读写锁中会遇到，后面会专门写文章分析读写锁)
- 0表示初始状态
看完AQS的数据结构之后，我们再图解ReentrantLock非公平锁的lock方法，看下代码
整个lock流程如下（这里只画了大概的流程，细节太多了，后面对着代码实现图解里面会有体现）：
图解ReentrantLock非公平锁lock方法
下面代码是我写这个图解例子用的，有兴趣可以自己尝试下，其中Thread.sleep(60*60*1000)为了让线程一致占有锁(即同步器)，这样后面增加的对该同步器的抢占才会形成同步队列，方便分析。
1. 初始状态，没有线程获取到AQS同步器
2. 按照上面的代码线程thread5第一个发起了lock，所以同步器的state变为1，exclusiveOwnerThread=thread5，此时还没有竞争同步器，所以head以及tail都是null。
3. 由于Thread.sleep方法是不会释放锁的，所以thread5会一直抢占着锁。当线程thread6执行lock的时候，由于同步器的state=1，所以抢占失败，执行acquires(1)方法
进入acquire(1)方法之后，其实还会再尝试抢一次锁，不管有没有等待节点在排队，所以非公平锁其实一个线程进来之后有两次机会抢占锁，如果抢不到就乖乖去排队，下图中选中的代码就是第二次抢占机会。
如果两次抢占都失败以后就只能增加一个等待节点，然后添加到同步队列的尾部。
非公平锁是独占模式，所以创建等待节点的时候会传入Node.EXCLUSIVE，设置到nextWaiter中
而这个Node.EXCLUSIVE的值其实是null，nextWaiter在AQS中其实有三种含义
- NULL：独占模式
- SHARD：共享模式
- 其他非空值：条件等待节点（调用Condition的await方法的时候）
节点创建成功之后需要把新创建的等待节点加入到同步队列的尾部
选中代码的意思就是如果已经有等待节点，那么直接插入到等待节点链表尾部（认为大部分情况下竞争其实并没有那么激烈，所以是可以直接插入成功的，所以代码如此设计），当然如果在高并发情况下插入失败了，那就执行常规的插入等待节点尾部的方法enq(node)（当没有等待队列的时候也需要执行enq方法，因为要初始化head以及tail节点）。
此处选中的代码就是当AQS的head以及tail为空的时候，初始化一个空节点，执行完以后是这样的结构
因为enq是在for的死循环里面的，所以会继续执行插入，直到成功插入到等待队列的尾部，再返回前继节点，那么线程thread6插入成功之后结构是这样的
到这里还没有结束，那么再继续再看下面的acquireQueued方法，代码如下
选中代码是一个死循环，可以认为是自旋，这里面可以分成两部分内容，如果node节点的前继节点是head节点（Empty Node），并且尝试把state从0设置为1，如果成功，就把当前节点设置为head节点（Empty Node），并且清空thread以及prev的值，这是在setHead方法中处理的。选中代码中的p.next=null，其实用意是前一个节点已经没有用了，把链接信息清空，再下一次垃圾回收的时候可以回收掉。
如果抢占锁没有成功，则会执行shouldParkAfterFailedAcquire方法，这个方法主要是用来设置前继节点的状态以及拿掉等待队列中已经取消的节点
新创建的节点加入到等待队列以后，其实还有一个事情没有做，就是要设置前继节点的waitStatus。
尾节点的waitStatus为默认值0，因为waitStatus的意义是为了标记后继节点的状态以及行为的。
所以for循环第一次进入shouldParkAfterFailedAcquire方法的时候，前继节点的waitStatus为0，会设置成-1，当再一次进入的时候会判断该值为-1，直接返回true。
中间的这段，就是从尾部开始往前，直到找到第一个小于等于0的等待节点，如下图：
大于0的值只有1，就是取消状态的节点，节点状态有4中，中间的节点状态不可能为0，因为每次添加进来之后都会被设置成-1，也不可能是-2，因为waitStatus值为-2的节点会进入条件等待队列，只有条件满足之后才会进入到同步队列，等待获取锁，同时把前继节点的waitStatus设置为-1，-3也是不可能的，因为-3是共享模式下才有，所以非公平锁独占模式下前继节点的值只可能为-1，0，1，最后的那段逻辑，直接设置前继节点的waitStatus为Node.SIGNAL（-1）就没有问题。
按照上面的逻辑处理完成之后，AQS的状态变成下面的样子
如果成功把新创建的线程加入到等待队列，那么需要让当前线程进入阻塞状态，执行方法parkAndCheckInterrupt，LockSupport就是前面文章写得AQS的基础
当该线程被唤醒的时候，会返回线程是否被中断，并清空中断标志，从这里就可以知道acquireQueued方法中的局部变量interrupted是干嘛用的了，就是判断线程被阻塞的时候有没有被中断，如果中断了，则返回之后执行selfInterrupt方法中断当前线程。
按照测试代码，最终形成的等待同步队列如下：
此时通过debug模式查看head以及后继节点如下：
其中线程thread5是在exclusiveOwnerThread变量中，如下图：
ReentrantLock公平锁
公平锁相对于非公平锁，其实就只有lock方法的区别，看下面的代码
lock方法中直接使用了acquire方法，相比于非公平锁的lock实现，公平锁少了第一次先尝试把state的值从0变1的过程。
再看tryAcquire方法也有点小区别，如果state=0，说明前一个执行的线程刚好执行完，但是后面还需要检查下是否后节点在同步队列排队，如果有节点在排队，那就不抢占了，直接加到同步队列尾部。
以上两点是公平锁实现和非公平锁实现的细微差别。
后续文章
AQS条件队列和同步队列的关系
透过ReentrantReadWriteLock窥探AQS
透过CountDownLatch窥探AQS
通过Semaphore窥探AQS