AQS原理和用法：http://ifeve.com/introduce-abstractqueuedsynchronizer/
AQS源码分析：http://cmsblogs.com/?p=2205
AQS源码分析：https://zhuanlan.zhihu.com/p/38010971
ConditionObject源码：https://www.jianshu.com/p/4d4c7398e187
CLH锁的基本原理
使用FIFO队列保证公平性
有当前节点和前置节点，当前节点不断自旋，查询(监听)前置节点的状态（isLocked)(保证了FIFO)
一系列的前置节点和当前节点构成队列
当前节点运行完成后，更改自己的状态，那监听当前节点状态的线程就会结束自旋
节点状态
1、CANCELLED，值为1 。场景：当该线程等待超时或者被中断，需要从同步队列中取消等待，则该线程被置1，即被取消（这里该线程在取消之前是等待状态）。节点进入了取消状态则不再变化；
2、SIGNAL，值为-1。当前节点正在等待一个release的信号；
3、CONDITION，值为-2。在等待队列中值为-2，当转移到同步队列时候，-2改为0；
4、PROPAGATE，值为-3。场景：表示下一次的共享状态会被无条件的传播下去；
5、INITIAL，值为0，初始状态。
共享锁代码分析
共享锁获取
public final void acquireShared(int arg) {
if (tryAcquireShared(arg) < 0)
doAcquireShared(arg);
}
1、如果获取资源成功，则不阻塞，代码继续往后走。
2、doAcquireShared方法详细见下
3、tryAcquireShared是非阻塞的。<0 获取资源失败；0：获取资源成功，后续节点不可能成功；>1:获取资源成功，且后续节点获取资源也可能成功。
4、共享锁允许多个线程持有同一个锁，所以唤醒时候需要进行传播，以便唤醒全部等待线程。
private void doAcquireShared(int arg) {
final Node node = addWaiter(Node.SHARED); //把节点加入同步队列的队尾
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
final Node p = node.predecessor();
if (p == head) {
int r = tryAcquireShared(arg);
if (r >= 0) { // 自旋退出条件：前驱节点是头节点，并且try成功。本线程由前驱节点线程进行unpark
setHeadAndPropagate(node, r);//删除前驱节点，把当前节点设置为head，如果满足propagate，则调用doReleaseShared
p.next = null; // help GC
if (interrupted)
selfInterrupt();
failed = false;
return;
}
}
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
if (ws == Node.SIGNAL) //前驱节点正在等待信号，所以当前节点必然也要等待
return true;
if (ws > 0) { //前驱节点已经被取消
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;//删除所有已取消的节点，并继续自旋
} else { //ws=0,-2,-3
compareAndSetWaitStatus(pred, ws, Node.SIGNAL); //设置前驱节点为signal，并继续自旋
}
return false;
}
共享锁的释放
public final boolean releaseShared(int arg) {
if (tryReleaseShared(arg)) {
doReleaseShared();
return true;
}
return false;
}
private void doReleaseShared() {
for (;;) {
Node h = head;
if (h != null && h != tail) { //如果队列为空则直接退出
int ws = h.waitStatus;
if (ws == Node.SIGNAL) {
if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0)) //重置头结点状态为0
continue;
unparkSuccessor(h);
}
else if (ws == 0 &&
!compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
continue; // loop on failed CAS
}
if (h == head) // 头节点变化，说明有线程已经唤醒，可以退出循环
break;
}
}
private void unparkSuccessor(Node node) { //传入的是头节点
int ws = node.waitStatus;
if (ws < 0) //再次设置确保头结点为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) //参考https://www.zhihu.com/question/50724462
if (t.waitStatus <= 0)
s = t;
}
if (s != null)
LockSupport.unpark(s.thread);
}
为什么unparkSuccessor在后续节点断裂，从tail开始查找，原因在于enq方法插入时：新节点pre指向tail，tail指向新节点，这里后继指向前驱的指针是由CAS操作保证线程安全的。而cas操作之后t.next=node之前，可能会有其他线程进来。所以出现了问题，从尾部向前遍历是一定能遍历到所有的节点。
独占锁分析
独占锁获取
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
1、acquireQueued类似doAcquireShared
2、
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);
}
}
独占锁释放
public final boolean release(int arg) {
if (tryRelease(arg)) {
Node h = head;
if (h != null && h.waitStatus != 0)
unparkSuccessor(h); //独占锁不需要考虑共享锁的级联解锁问题
return true;
}
return false;
}
条件变量CondtionObject
await和signal配合操作原理
public final void await() throws InterruptedException {
if (Thread.interrupted())
throw new InterruptedException();
Node node = addConditionWaiter();
int savedState = fullyRelease(node);
int interruptMode = 0;
while (!isOnSyncQueue(node)) {
LockSupport.park(this);
if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
break;
}
if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
interruptMode = REINTERRUPT;
if (node.nextWaiter != null) // clean up if cancelled
unlinkCancelledWaiters();
if (interruptMode != 0)
reportInterruptAfterWait(interruptMode);
}
1、构造等待节点，并加入等待队列；
2、释放当前持有的排他锁；
3、如果不在同步队列中，则进行park，挂起线程；
4、当调用signal后，会把节点加入同步队列，并唤醒await中的的线程；
5、await在park后继续运行，退出自旋，并尝试强锁；
6、得到锁后运行后续程序。
final boolean transferForSignal(Node node) {
if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
return false;
Node p = enq(node);
int ws = p.waitStatus;
if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
LockSupport.unpark(node.thread);
return true;
}
