ReentrantLock 可重入锁
1、ReentrantLock 类图结构
由类图可以看出 ReentranLock 实现了 Lock 接口，实现了 Lock 接口中的 lock() 方法。
ReentrantLock 中有一个抽象内部类 Sync，继承自 AbstractQueneSynchronized 这个工具类，也就是所谓的 AQS 队列，Sync 内部类中，对 lock 方法进行了重写，分为公平锁和非公平锁，简单来说就是一个需要排队去获取锁，一个可以插队获取到锁。
在AQS 中可以看到 ConditionObject 和 Node 两个内部类，这就是同步队列 Node , 和 等待队列 Condition
2、ReentrantLock 无堵塞获得锁
public static void main (String args[]) {
ReentrantLock lock = new ReentrantLock();
lock.lock();
}
2.1 源码分析
当我们点进 lock 方法后会发现，先进入的是 Lock 接口的 lock 方法，因为我们这分析的 ReentrantLock , 所以我们直接看该类的方法实现
public void lock() {
sync.lock();
}
Sync 是 ReentrantLock 的一个抽象静态内部类，实现了 AQS
abstract static class Sync extends AbstractQueuedSynchronizer {
/**
* 在 Sync 中，有两种实现
* 1.需要排队的公平锁.
* 2.可以插队的非公平锁.
*/
abstract void lock();
}
先看一下非公平锁
static final class NonfairSync extends Sync {
private static final long serialVersionUID = 7316153563782823691L;
/**
* Performs lock. Try immediate barge, backing up to normal
* acquire on failure.
*/
final void lock() {
// 尝试修改状态
if (compareAndSetState(0, 1))
// 修改成功，设置当前线程
setExclusiveOwnerThread(Thread.currentThread());
else
// 修改失败，尝试抢占锁
acquire(1);
}
protected final boolean tryAcquire(int acquires) {
return nonfairTryAcquire(acquires);
}
}
在 lock() 的实现里，可以看到，首先会根据 CAS (原子操作) 将 State 由0设置为1，1也就是代表获得锁的状态，然后调用 setExclusiveOwnerThread() 方法，设置当前线程为独占锁的所属对象。
至此，若只有线程A 进行访问，现在已经获取到了锁，可以执行后面的代码。
3、ReentrantLock 堵塞获得锁
3.1、源码分析
假设线程A，线程B；线程A已经通过 CAS 修改 State 状态，也设置了当前所属者，那么线程B进入的时候，通过 CAS 进行 State 状态的设置一定会是 false,也就是会走 acquire(1) 方法，注意传进去的这个 “1” 是进行插队的关键
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
在 if 判断里，一共有 三个方法，我们一个一个看，首先是 tryAcquire(arg)
3.1.1 tryAcquire(arg)
// 可以发现，在 AQS 中这个方法仅仅是抛出了一个异常，因为代码逻辑的实现并不是在这
// 而是由 Sync 的子类实现进行
protected boolean tryAcquire(int arg) {
throw new UnsupportedOperationException();
}
protected final boolean tryAcquire(int acquires) {
return nonfairTryAcquire(acquires);
}
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;
}
首先，获取到当前的线程，也就是线程B，调用 getState() 方法，由于线程A已经通过 CAS 将 state 状态设置为1，所以 if 判断里面是走不进去的，接着 else if ，当前线程是线程B，而 getExclusiveOwnerThread 由线程A已经修改为了线程A，所以 else if 也是走不进去的，但我们可以发现，如果这时过来的还是线程A的话， else if 里面，是会对已经获取到锁的进行 state 值得增加，这也就是可重入的逻辑。
方法最终返回的是 false，我们可以发现在 if 判断里，如果这时恰巧线程A释放了锁，而这时线程C恰巧走到这，那么线程C很有可能会比线程B提前获取到锁，这里是插队的一处实现
3.1.2 addWaiter(Node.EXCLUSIVE)
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;
}
在 AQS 之中维护了一个双向的链表
首先会讲当前节点构造为一个 Node 对象，mode 为 EXCLUSIVE 表示独占状态
Node(Thread thread, Node mode) { // Used by addWaiter
this.nextWaiter = mode;
this.thread = thread;
}
prev = tail ，tail 节点目前还没有值，也就是 null，这时 if 是肯定不满足的，会直接走 enq(node) 方法
3.1.3 enq(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;
}
}
}
}
首先，我们可以看到这是一个自旋操作，找到 tail 节点，若为 null ，通过 CAS 构造 head 节点，让 head 节点和 tail 节点一致，这时 head 节点和 tail 节点都是初始化出来的节点，在自旋操作进行到第二次的时候，这是 t 已经不为 Null，这时会让线程B的 prev 节点为 head 节点，通过 CAS 操作将 tail 节点替换为 线程B，并将 t 的 next 节点标记为线程B
大体来说就是第一步，在 tail 和 head 节点都是 null 的情况下，通过 cas 初始化一个节点，让 head 和 tail 都指向这个 Node , 在线程B进来之后，将线程B 的 prev 设置为初始化出来的节点，将初始化出来的节点的 next 设置为线程B，tail 节点指向线程B，达成一个双向队列
3.1.4 acquireQueued（addWaiter(Node.EXCLUSIVE)）
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
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) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
在这里也是一个自旋操作，获取的 线程B 的 prev 节点也就是 Head 节点，满足 if 的前半段，后面段再次去尝试获取锁，这个地方是第二次可以插队获取锁的地方，如果获取成功的话，会将当前线程也就是线程B设置为 head 节点，并且将 thead 和 prev 属性都设置为 Null，将 head 节点的 nxt 设置为空，返回 false
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
if (ws == Node.SIGNAL)
/*
* This node has already set status asking a release
* to signal it, so it can safely park.
*/
return true;
if (ws > 0) {
/*
* Predecessor was cancelled. Skip over predecessors and
* indicate retry.
*/
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;
} else {
/*
* waitStatus must be 0 or PROPAGATE. Indicate that we
* need a signal, but don't park yet. Caller will need to
* retry to make sure it cannot acquire before parking.
*/
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
如果没有抢到锁，会进入此方法，获取到 waitStatus 为 0 ，将其设置为 -1 ,也就是阻塞状态，返回 false ，因为上层调用时自旋操作，所以还会在进入此方法，这时检测到 waitStatus 为 SIGNAL ，返回 true,该线程进行挂起
4、释放锁
4.1、源码分析
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;
}
调用 tryRelease() 尝试对其进行唤醒，判断 head 结点是不是 null，waitStatus 节点状态是否不等 0 ，head 节点的 waitStatus 的节点状态为 -1,调用 unparkSuccessor （） 进行唤醒
4.1.1 tryRelease(arg)
protected final boolean tryRelease(int releases) {
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;
}
因为 ReentrantLock 是可重入锁，要进行多次释放，直到 c = 0
4.1.2 unparkSuccessor
private void unparkSuccessor(Node node) {
/*
* If status is negative (i.e., possibly needing signal) try
* to clear in anticipation of signalling. It is OK if this
* fails or if status is changed by waiting thread.
*/
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
/*
* Thread to unpark is held in successor, which is normally
* just the next node. But if cancelled or apparently null,
* traverse backwards from tail to find the actual
* non-cancelled successor.
*/
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);
}
注意，这是从尾部向头部去找
因为在 enq() 中
1、 将新的节点的prev指向tail
2、 通过cas将tail设置为新的节点，因为cas是原子操作所以能够保证线程安全性
3、 t.next=node；设置原tail的next节点指向新的节点在cas操作之后， t.next=node操作之前。 存在其他线程调用unlock方法从head 开始往后遍历，由于 t.next=node 还没执行意味着链表的关系还没有建立完整。 就会导致遍历到 t 节点的时候被中断。所以从后往前遍历，一定不会存在这个问 题