同步锁synchronized和重入锁ReentrantLock都是用于并发程序设计必不可少的手段，在JDK 5.0早期版本中，同步锁性能远远低于重入锁，但是在6.0版本之后，jdk对同步锁做了大量的优化，使得同步锁跟重入锁性能差距并不大，并且jdk团队表示，同步锁还有进一步升级优化的空间
一、重入锁的概念
重入的概念是指在同一个线程内部，这种锁是可以反复进入的。
lock.lock();
lock.lock();
// do something
lock.unlock();
lock.unlock();
一个线程可多次获取锁，但同时也要释放相同的次数，否则该线程将持续拥有锁，其他线程将无法进入临界区。
二、重入锁的几个重要方法
lock：获取锁，如果锁被其他线程占用，则休眠等待。
lockInterruptibly：获取锁，可以被其他线程所中断
tryLock：尝试获取锁，不等待
tryLock（time, timeUnit）:在一定时间内尝试获取锁
unlock: 释放锁
2.1 中断响应
对于synchronized来说，一个线程要么获取到锁开始执行，要么继续等待。但是对于重入锁来说，提供了更灵活的一种机制，那就是在等待锁的过程中，可以取消对锁的请求，这样可以有效避免死锁的可能。
2.2 锁申请等待时间
中断响应是一种通过外部通知中断对锁的请求，从而避免死锁的一种机制。除此之外，还有一种机制，那就是等待限时。
tryLock(long timeout, TimeUnit unit)
2.3 公平锁、非公平锁
重入锁默认是非公平锁
public ReentrantLock() {
sync = new NonfairSync();
}
可以通过构造函数参数实现公平锁
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}
如果是非公平锁，在并发场景下，系统会随机从等待队列中挑选一个线程。如果是公平锁，系统会维护一个有序队列，会按照进入队列的次序有序执行，因此公平锁虽然避免了饥饿现象，但是会需要更高的成本来维护这个有序队列。
2.4 AQS的组成结构
重入锁的加锁和解锁过程主要有AQS完成，AQS维护了一个双向链表，每个节点Node存储一个线程及线程的状态，Head节点代表正在持有锁的线程。
节点状态：
CANCELLED: 当前节点超时或者中断被取消
SIGNAL：当前节点的后续节点处于等待状态
CONDITION：当前节点再等待condition
PROPAGATE：状态向后传播
static final class Node {
/** waitStatus状态：当前节点被取消调度*/
static final int CANCELLED = 1;
/** waitStatus状态：后续节点等待被唤醒*/
static final int SIGNAL = -1;
/** waitStatus状态：当前节点等待在condition上，
* 当其他线程调用了Condition的signal()方法后，
* CONDITION状态的结点将从等待队列转移到同步队列中，
* 等待获取同步锁*/
static final int CONDITION = -2;
/** waitStatus状态：共享模式下，会唤醒后续节点及后续的后续节点*/
static final int PROPAGATE = -3;
/** 节点状态*/
volatile int waitStatus;
}
当线程获取锁失败之后，就通过addWaiter加入到同步队列中（加入到尾部），自旋判断自己是否是链表的头节点，如果是头节点，就不断参试获取资源，获取成功后则退出同步队列。
三、重入锁的实现原理
首先看下重入锁的类图关系
ReentrantLock定义了内部类Sync，Sync继承自AbstractQueuedSynchronizer（简称AQS），是一个同步等待队列，本质上是一个带有头尾指针的双向链表。
AQS中有一个很重要的变量, 不同的组件中代表的含义有所不同，而在重入锁组件中，代表被线程重入的次数，为0表示没有线程持有锁。
private volatile int state;
3.1 公平锁的加锁过程
sync.lock时调用AQS的acquire方法，这是一种模板设计模式，即AQS中定义了整体的处理流程，但是具体的实现细节会根据锁类型的不同，放到子类方法中执行。
public final void acquire(int arg) {
// 尝试获取锁
if (!tryAcquire(arg) &&
// 获取锁失败的线程安全的加入到等待队列中
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
// 自行了断
selfInterrupt();
}
下面来看看每一步的实现细节
公平锁的tryAcquire
tryAcquire是一个钩子方法。实现细节放在具体的子类中。
protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
//获取当前锁的状态
int c = getState();
// 没有线程占用
if (c == 0) {
// 如果当前线程排在队列中的第一个，并且CAS抢占锁成功
if (!hasQueuedPredecessors() &&
compareAndSetState(0, acquires)) {
// 设置占用锁的线程为当前线程
setExclusiveOwnerThread(current);
return true;
}
}
// 判断占有锁的线程是否是当前线程
else if (current == getExclusiveOwnerThread()) {
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
// 重入次数加1，acquires是由acquire(1)传入
setState(nextc);
return true;
}
return false;
}
acquireQueued(addWaiter())
线程在同步队列中会尝试获取锁,失败则被阻塞,被唤醒后会不停的重复这个过程,直到线程真正持有了锁,并将自身结点置于队列头部。对算法感兴趣的同学可以自行深入研究一下。
addWaiter入队过程（队列不为空时）
1、根据当前线程创建一个新的Node节点
2、如果队尾元素不为空，则通过CAS操作插入到队尾
3、如果队列为空，new一个节点并设置为对头head
private Node addWaiter(Node mode) {
Node node = new Node(Thread.currentThread(), mode);
// Try the fast path of enq; backup to full enq on failure
Node pred = tail;
if (pred != null) {
node.prev = pred;
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
enq(node);
return node;
}
//入队逻辑
private Node enq(final Node node) {
for (;;) {
Node t = tail;
if (t == null) { // Must initialize
if (compareAndSetHead(new Node()))
tail = head;
} else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}
在元素入队之后，又做了哪些操作呢？
1、通过自旋检测是否有资格获取锁，如果获取到了锁，则将当前节点设置为头节点
2、如果不是Head->next节点或获取锁失败，则阻塞当前线程
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
// 获取当前节点的prev节点
final Node p = node.predecessor();
// 如果是头节点，则去尝试获取锁
if (p == head && tryAcquire(arg)) {
// 获取锁成功，则将当前节点设置为头节点
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
// 如果没有获取到锁，先判断是否需要阻塞当前线程
if (shouldParkAfterFailedAcquire(p, node) &&
// 通过LockSupport.park(this)原语阻塞当前线程
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
这里最难理解的是这句,为什么当前节点的前节点是头节点时尝试获取锁呢？因为头节点代表当前正在持有锁的线程，该线程执行结束释放锁时，会唤醒队列中阻塞的线程，被唤醒的线程会尝试去获取锁。
if (p == head && tryAcquire(arg)) {
...
}
3.2 公平锁的解锁过程
public void unlock() {
sync.release(1);
}
public final boolean release(int arg) {
// 释放锁
if (tryRelease(arg)) {
Node h = head;
// 队列不为空
if (h != null && h.waitStatus != 0)
// 唤醒队列中阻塞的线程
unparkSuccessor(h);
return true;
}
return false;
}
释放锁的具体逻辑如下
protected final boolean tryRelease(int releases) {
// 次数-1
int c = getState() - releases;
// 判断是否是当前线程
if (Thread.currentThread() != getExclusiveOwnerThread())
throw new IllegalMonitorStateException();
boolean free = false;
// 释放后没有线程占用
if (c == 0) {
free = true;
// 将占有锁线程置为空
setExclusiveOwnerThread(null);
}
// 更新状态
setState(c);
return free;
}
释放完成后唤醒后续节点
private void unparkSuccessor(Node node) {
//node是当前线程所在节点
int ws = node.waitStatus;
// 状态置为0
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
// 找到下个需要被唤醒的节点
Node s = node.next;
if (s == null || s.waitStatus > 0) {
s = null;
for (Node t = tail; t != null && t != node; t = t.prev)
if (t.waitStatus <= 0)
s = t;
}
if (s != null)
//唤醒线程
LockSupport.unpark(s.thread);
}
3.3 非公平锁和公平锁的实现原理基本类似
非公平锁在尝试获取锁时不会判断是否是队列中的第一个元素，而是直接进行CAS比较。 释放锁的流程是一样的。
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
if (compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
}
else if (current == getExclusiveOwnerThread()) {
int nextc = c + acquires;
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
总结
重入锁的实现主要有三个关键的知识点
1、同步等待队列，线程在尝试请求锁失败后，会进入到等待队列中等待被唤醒。如果有线程释放了锁，系统会唤醒等待队列中的一个线程。
2、原子性：原子状态是通过CAS操作来存储当前锁的状态（即state：重入次数）
3、通过LockSupport.park，LockSupport.unpark来挂起和恢复线程，未获取到锁的线程会被挂起。
