一 AQS
1 AbstractQueuedSynchronizer
AbstractQueuedSynchronizer简称AQS，是一个用于构建锁和相关同步器的框架，它依赖于FIFO的等待队列实现。见AbstractQueuedSynchronizer的描述：
Provides a framework for implementing blocking locks and related synchronizers (semaphores, events, etc) that rely on first-in-first-out (FIFO) wait queues.
事实上concurrent包内许多类都是基于AQS构建，例如ReentrantLock，Semaphore，CountDownLatch，ReentrantReadWriteLock，FutureTask等。AQS解决了在实现同步容器时设计的大量细节问题。
AQS中维护了一个FIFO队列，用于记录等待的线程，上锁和释放锁的过程可以认为是线程入队列和出队列的过程；获取不到锁，入队列等待；出队列时被唤醒。
AQS中有一个表示状态的字段state，ReentrantLock用它表示线程重入锁的次数，Semaphore用它表示剩余的许可数量，FutureTask用它表示任务的状态。对state变量值的更新都采用CAS操作保证更新操作的原子性。
AbstractQueuedSynchronizer继承了AbstractOwnableSynchronizer，这个类只有一个变量：exclusiveOwnerThread，表示当前占用该锁的线程，并且提供了相应的get，set方法。AQS使用此字段记录当前占有锁的线程。
2 队列
1) 队列
AQS使用一个FIFO的等待队列表示排队等待锁的线程，队列结构如图：
队列头节点称作“哨兵节点”或者“哑节点”，它不与任何线程关联，其他的节点与一个等待线程关联。
每次一个线程释放锁以后，从Head开始向后寻找，找到一个waitStatus是SIGNAL的节点，然后通过LockSupport.unpark唤醒被挂起的线程，被挂起的线程继续执行尝试上锁逻辑。新的线程尝试获取锁时，如果获取不到锁，将会创建一个Node并加入到队尾，然后将自己挂起，等待挂起时间到或者等待被prev对应的节点唤醒。
说明：代码的中是从tail向head遍历查找waitStatus=SIGNAL的节点，但结果与这里说的是一样的，即最终也是找Head后的第一个waitStatus=SIGNAL的节点。见unparkSuccessor方法
2) Node的主要属性
类型
属性名
描述
int
waitStatus
等待状态
Node
prev
指向队列中前一个节点
next
指向队列中后一个节点
Thread
thread
Node的持有线程
nextWaiter
下一个等待condition的Node
3) Node的waitStatus取值
状态
状态值
CANCELLED
1
取消状态，例如因为等待锁超时而取消的线程；处于这种状态的Node会被踢出队列，被GC回收
SIGNAL
-1
表示这个Node的继任Node被阻塞了，到时需要通知它
CONDITION
-2
表示这个Node在条件队列中，因为等待某个条件而被阻塞
PROPAGATE
-3
使用在共享模式头Node有可能处于这种状态， 表示锁的下一次获取可以无条件传播
其他
初始状态
4) 队列示例
接下来我们以一个简单的示例描述ReentrantLock的等待锁、释放锁的原理。为了方便描述，以下示例中节点和线程一一对应，例如Node1与Thread1对应，依次类推。
假设初始状态，如下图所示：
Thread3申请锁时，因为无法获取锁，所以创建一个Node，然后加入到等待队列中；如下图所示：
假设3s中到了以后，Thread1被唤醒（挂起的时候指定了时间，所以等待时间到后会被唤醒），此时会将自己的状态改成CANCELLED，表示等待被从队列中移除；如下图所示：
如果此时有新线程申请锁，那么在入队列过程中会顺便将处于CANCLE状态的节点移除。如下图所示：
Thread0执行完毕后，释放线程，将唤醒Head后面第一个状态为等待SIGNAL的节点对应的线程。
注意：新Node入队列时会检查并删除被CANCELLED的节点；其实Node1在等待时间到后被唤醒后，在将自己状态改为CANCELLED时，如果发现自己是最后一个节点也会将Node1删除。
二 流程
这一部分简要的介绍加锁、释放锁的流程，让大家对ReentrantLock有一个整体的概念，后面将通过源码详细分析实现细节。
1 NonfairSync#lock
非公平锁上锁主要流程如下所示：
这里仅给出流程图，后面会通过代码详细讲述这个流程。
2 FairSync#lock
如流程图中所示，主要流程基本和非公平锁一致，有两个差别：
NonfairSync执行lock的第一步就是尝试通过compareAndSetState(0, 1)获取锁；而FairSync不会进行此操作。
NonfairSync通过nonfairTryAcquire获取锁；FairSync通过tryAcquire获取锁。这两个方法的主要逻辑相同，唯一的差别在于FairSync在获取锁前会先检查FIFO队列中是否有Node存在，如果没有，则当前线程执行compareAndSetState(0, 1)操作，尝试获取锁。
3 unlock
公平锁和非公平锁的释放锁的过程是相同的，释放锁的流程图如下。
三 lock & unlock 源码分析
因为公平锁、非公平锁的大部分逻辑相同，所以这里主要以非公平锁的源码来讨论。
1 构造器
以下是ReentrantLock的两个构造器，如下所示：
我们可以看到，ReentrantLock默认构造器是非公平的。
2 获取锁
1) lock
如下代码示例中，可以看到公平锁和非公平锁的第一个差别：非公平锁lock的第一步就是尝试通过compareAndSetState(0, 1)获取锁，因为他不要求公平，所以他上来就争抢锁。
a) ReentrantLock#lock
b) NonfairSync#lock
exclusiveOwnerThread代表持有所得线程信息，所以一旦上锁成功，需要将exclusiveOwnerThread设置为当前线程。
c) FairSync#lock
2) compareAndSetState
compareAndSetState(0, 1)方法是基于CAS操作，尝试将state从0改为1。这是基于硬件指令集的原子操作，当且仅当state=0时将其修改为1。
在AQS部分我们提到ReentrantLock中state记录的锁次数（当然也包括重入次数）。state=0代表当前没有线程持有锁。state>0代表加锁次数，第一次lock成功state=1，重入一次state++。
Java中的CAS操作基本上都是通过unsafe实现的，代码如下：
3) acquire
acquire属于AbstractQueuedSynchronizer中的方法；此方法主要逻辑如下：
尝试获取锁，如果成功，那么直接返回。
如果获取锁失败，创建一个Node.EXCLUSIVE类型的Node，然后加入到队列中。这里的队列就是在AQS中的FIFO队列，其head为一个空节点，其余的每个Node与一个线程相关联。
已经入队列的线程尝试获取锁，如果获取成功，那么返回，获取失败，则将被挂起（这里有一定的条件：要求Node的prev节点的waitStatus=SIGNAL）
4) tryAcquire
此方法是尝试获取锁。此时如果state=0，说明所已经被释放了，所以可以重新尝试上锁操作，即进行compareAndSetState(0, 1)操作；如果state!=0，并且当前线程持有锁，那么重入，更新state，即state++。
当且仅当以下两中情况，此方法返回true。
如果锁已经被释放了，并且当前线程的compareAndSetState(0, 1)成功。
当前线程持有锁，此时相当于重入，更新state
a) NonfairSync#tryAcquire
b) NonfairSync#nonfairTryAcquire
c) FairSync#tryAcquire
5) addWaiter
addWaiter是属于AbstractQueuedSynchronizer中的方法。此方法主要逻辑是：创建一个Node，与当前线程关联，然后尝试加入到FIFO队列的尾部。加入到FIFO队列时，如果发现队列没有初始化过，即Head为空，那么先创建一个空的不与任何线程相关联的Node最为Head；然后将Node加入到队列尾部。
a) addWaiter
b) enq
如果FIFO队列尚未初始化，那么先初始化；如果已经初始化了，那么尝试将node加入到队尾，失败则再试一次。
6) acquireQueued
addWaiter是属于AbstractQueuedSynchronizer中的方法。此方法主要逻辑为：
获取node的prev节点。
如果prev节点是head节点，则说明当前node是第二个节点，那么可以尝试让当前线程获取锁。如果获取成功，那么重新设置head，并返回interrupted标志位。
如果prev节点不是head，那么认为不用尝试获取锁，此时判断判断是否应该挂起(pack)当前线程，如果应该挂起，那么通过LockSupport#park挂起线程。
注意，如果线程获取锁失败，那么会在parkAndCheckInterrupt()方法中被挂起。一个线程彻底释放锁资源以后，会唤醒head后的一个节点对应的线程，当某一个线程被唤醒以后，继续执行parkAndCheckInterrupt()方法中LockSupport#park以后的代码。
a) acquireQueued
b) shouldParkAfterFailedAcquire
此方法是用来判断是否应该挂起当前节点对应的线程。允许挂起的条件是：prev节点的waitStatus=SIGNAL。这个状态的意思是：prev节点对应的线程在释放锁以后应该唤醒（unpack）node节点对应的线程。
如果prev节点waitStatus>0，即为CANCELLED状态时，需要将prev从队列中移除。重试此操作直到找到一个prve节点的状态不为CANCELLED。
如果prev节点waitStatus<=0（当然不包括SIGNAL状态），那么通过CAS操作设置waitStatus= SIGNAL
3 等待超时则放弃获取锁
以下三个方法时获取超时放弃锁的源码，其中主要逻辑在doAcquireNanos中，和前面讨论的“获取锁”部分的（见acquireQueued方法）主要区别在于：在循环中会检测等待时间是否已经超过指定时间，如果超过了，那么将Node的waitStatus改为CANCELLED状态。
1) tryLock
2) tryAcquireNanos
3) doAcquireNanos
4 释放锁
1) unlock
2) release
释放锁，主要逻辑是：
尝试释放锁。
如果此次释放完以后，state=0，即持有锁的线程已经将锁（包括重入）彻底释放了，那么尝试唤醒（unpack）head后面Node对应的线程（这里有一个检查Node节点对应的线程是否已经被CANCELLED的过程，对于这种节点会将他们从队列中移除）。
3) tryRelease
此方法主要逻辑是：
如果当前线程不是占用所得线程，不允许释放。
设置state=state-releases。
如果state=0，那么将锁的占用线程清理掉。
释放后如果state=0，那么返回true；即只有在Sync不被任何线程占用，才返回true。
4) unparkSuccessor
如果node的waitStatus！=CANCELLED状态，那么将node的waitStatus改成0。这其实是一个清理head节点状态的过程，这里的清理指的是改成初始状态。
如果node的next节点处于CANCELLED状态，那么将此next节点移除队列；重试此过程直到找到一个不处于CANCELLED状态的节点或者队列中没有节点为止。
如果上一步找到这样的一个节点，那么通过LockSupport.unpark去唤醒这个节点对应的线程。
四 Condition
Condition提供了这样一种能力：线程获取锁以后，如果条件不满足，挂起线程释放资源；如果条件满足，则唤醒线程继续处理。
ReentrantLock可以支持多条件等待，其实现原理如下：每次调用newCondition()方法，都会创建一个ConditionObject对象，每个ConditionObject对象都可以挂一个等待队列；如果希望同时等待多个条件，只需要简单的多次调用newCondition创建多个条件对象就好了。
说明：先区分两个概念，本节中同步等待队列指的是指的是AQS中的FIFO的队列。条件等待队列指的是ConditionObject对象上的等待队列。
1 源码分析
1) newCondition
创建ConditionObject对象，一个ConditionObject对象就是一个普通的对象，没有什么特别的地方，只是提供了await、signal等方法，这一部分将在后面详细分析。
2) await
释放锁，挂起当前线程，等待其他线程发起唤醒信号（signal）；被唤醒以后重新获取锁。此方法可以认为和Object的wait等价。
此方法主要逻辑如下：
创建一个条件等待Node（waitStatus= CONDITION），加入到条件等待队列队尾。
释放ReentrantLock上的锁。因为后面要休眠了，所以需要先将此ReentrantLock对象的锁释放掉，这样其他线程才能获取锁。
判断Node是否在同步等待队列中，如果不在，那么挂起当前线程。因为Node是await时新创建的，故不在同步队列中，所以当前线程在这里会被挂起。
线程被挂起，等待signal信号。
线程被唤醒以后，尝试获取锁。acquireQueued方法在前面已经将结果了，所以这里就不在累述。因为之前将锁释放了，所以线程被唤醒以后需要重新尝试获取锁，获取锁的次数为之前释放的次数。
清理掉已经被取消的节点。
3) addConditionWaiter
此方法的主要逻辑如下：
如果lastWaiter已经被cancel了，那么直接清理掉他们。
接着创建一个Node，加入到条件等待队列的尾部。
4) isOnSyncQueue
判断当前Node的状态，如果是CONDITION，表明是正常的没有被唤醒的节点，返回false。此时当前的Node还没进入到同步等待队列。
判断Node的下一个节点是否为null，不为null表明在同步等待队列中，返回true。
遍历整个Node的同步等待队列，如果存在返回true ；注意：如果条件已经满足，这里有一个条件等待队列向同步等待队列的转化过程。
5) signal
简单来说是：唤醒线程。
具体来说是：遍历等待队列，找出第一个等待被唤醒的节点Node，然后将它插入到同步等待队列尾部，然后就是等待被唤醒（具体的过程与一个线程释放锁以后其他线程获取所得过程相同）。
从条件等待队列中取出第一个Node。
遍历条件等待队列，清理已经不再CONDITION状态的节点，接着将Node加入到同步等待队列中，然后将Node加入之前的队尾Node设置为SIGNAL状态，最后如果状态修改失败，则唤醒Node对应的线程。
2 使用示例伪代码
五 ReentrantLock与synchronized对比
1 Synchronized
Synchronized是通过同步互斥来实现线程安全的；即同一时间只能有一个线程访问synchronized修饰的代码块或方法。其特性与功能如下：
synchronized是java的关键字，由jvm支持。
支持重入，即一个线程在获取对象的锁以后可以再次对此对象上锁。
修饰普通方法，锁是当前实例对象；修饰静态方法，锁是当前类的class对象；包裹代码块，锁是括号中的对象。
不支持等待中断。
synchronized是非公平的。
2 ReentrantLock
ReentrantLock是一种非常常见的临界区处理手段，通过在执行代码前上锁保证同一时间只有一个线程能执行指定的代码块。ReentrantLock的特性与功能如下：
ReentrantLock是java api层面的实现，有Unsafe支持。
支持重入。
支持公平锁、非公平锁，默认是非公平锁。公平锁指：多个线程在等待同一个线程的锁时，必须按照申请所得时间顺序来获取锁。非公平锁指：在锁被释放时，任何一个等待锁的线程都有机会获取锁。
支持等待中断。例如：A线程获取对象O的锁， B线程等待获取O的锁，当B长时间无法获取锁时，B可以放弃获取锁。
锁可以绑定多个条件。线程进入临界区，却发现在某一条件满足之后才能执行，条件对象就是用来管理那些已经获得了锁，但是却不能做有用工作的线程。一个ReentrantLock对象可以同时绑定多个Condition对象。
3 总结
ReentrantLock本质上是通过一个队列来完成同步的。因为每个Node与一个线程关联，只需要做好对队列节点的同步处理，既可以完成多线程的同步处理。
相比于synchronized关键字，ReentrantLock等多的类似于我们使用zookeeper实现的等待队列。Zookeeper的队列示例可以参考博客《Zookeeper使用案例》地址为：https://yq.aliyun.com/articles/272103
六 博客
关于线程、synchronized的更多内容，可以参考《线程-基础知识》，地址为：https://yq.aliyun.com/articles/414908
关于synchronized的原理，可以参考《互斥同步-锁》，地址为：https://yq.aliyun.com/articles/414939