AQS中使用到的公平与非公平锁，公平锁是由Node这个内部类实现的，其一系列的操作是CLH算法的一个变种
简介
CLH算法是为了解决CC-NUMA结构下，多处理器对同一内存数据的使用，保证在不同处理器操作同一个内存数据的一致性，这是硬件层面的算法。CLH的实现是HCLH算法，在多个处理器获取数据时，对其中有竞争的数据进行队列操作，在处理器内部使用一个本地队列，在其他处理器竞争时使用一个全局队列，以两个队列的方式对数据访问一致性做出保证
个人理解：Java中，我们使用这个类的目的就是在多线程环境（对应上面的多处理器）下对数据（对应内存数据）进行加锁时对锁中的数据一致性进行保证，算法本身是作为硬件处理cpu多线程的
从方法入手
写的时候看的是1.8的源码，后续版本有差异，大体一致
AQS公平锁中常判断使用到的一个方法如下，判断队列中第二个请求是否为当前线程
public final boolean hasQueuedPredecessors() {
// The correctness of this depends on head being initialized
// before tail and on head.next being accurate if the current
// thread is first in queue.
Node t = tail; // Read fields in reverse initialization order
Node h = head;
Node s;
return h != t &&
((s = h.next) == null || s.thread != Thread.currentThread());
}
默认实现的队列是先进先出的，新的线程请求添加到队列尾部，方法将node自身的前一个节点置为全局队列的tail,将前一节点的下一个节点置为自身，实现了一个链表的结构
下图是不同情况下锁和Node的状态，微博传图麻烦就没切
1.在锁的初始状以及单个锁的态下（图中一二行）head与tail都为空
我们观察公式
h != t &&((s = h.next) == null || s.thread != Thread.currentThread())
false&&((s = h.next) == null || s.thread != Thread.currentThread())
由于第一个条件就为false,直接返回调用者当前锁没有锁的队列
2.有第二个线程请求锁时（图中的第三第四行）
head为node1，其next指向后请求的node2，prev为空，node中表明请求所属线程的thread为空
当前锁的state为1
tail为node2，其next为空，thread记录请求线程
再看公式
true&&(false||s.thread != Thread.currentThread())
s = h.next在前一步将node2赋值给s
这里分了两种情况：
1）非node2请求
那么node2.thread != Thread.currentThread()结果是true
hasQueuedPredecessors方法返回true
2）node2对象请求
hasQueuedPredecessors方法返回false
队列是怎样工作的
依然是在公平锁当中，记住上面的状态，我们可以再看看队列是怎么添加的以及竞争时锁的交替
ReentrantLock的lock方法调用倒了AQS中的方法acquire
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
tryAcquire方法
if (c == 0) {
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");
setState(nextc);
return true;
}
1）尝试成功
尝试获取锁的时候，首先判断锁状态是否为0，这个状态就是加锁的次数，只有当锁的状态为0的时候，线程才会判断是否需要队列中的第二个节点来获取锁
如果状态不为0，则要判断线程是否为持有锁的线程，是的话就继续加锁，这里就是重入锁
2）尝试失败
尝试获取锁，假如已有线程加了锁，返回失败，
在尝试失败的情况下才会执行后面的方法acquireQueued，首先执行下一个方法中的addWaiter将当前线程创建一个Node使用cas添加到队列尾部并且返回当前的node，方法再执行进入acquireQueued
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);
}
}
循环体不断的进行加锁尝试循环，一旦成功，说明了当前节点的前一个节点刚刚持有了锁，并且进行了解锁操作，轮到了自己，此时，将自己置为队列的头部，并且将p.next持有的当前node引用置为空方便GC之后的回收（结合图中第四行的node1，其所有属性都将变为null，而且当前持有锁的node在setHead方法中将自身的prev置为空，引用自己和自己的引用都清理了，太干净了），由此锁的交替完成了一次
--前一任锁持有者的销毁从unlock方法追踪到unparkSuccessor方法可以看到
场景其实不多，还可以带入其他场景来看这些节点与锁的状态来理解aqs
