此篇博客全部源代码均来自JDK 1.8
在上篇博客【死磕Java并发】—–J.U.C之AQS：AQS简单介绍中提到了AQS内部维护着一个FIFO队列，该队列就是CLH同步队列。
CLH同步队列是一个FIFO双向队列，AQS依赖它来完毕同步状态的管理，当前线程假设获取同步状态失败时，AQS则会将当前线程已经等待状态等信息构造成一个节点（Node）并将其加入到CLH同步队列，同一时候会堵塞当前线程，当同步状态释放时，会把首节点唤醒（公平锁），使其再次尝试获取同步状态。
在CLH同步队列中，一个节点表示一个线程，它保存着线程的引用（thread）、状态（waitStatus）、前驱节点（prev）、后继节点（next），其定义例如以下：
static final class Node {
/** 共享 */
static final Node SHARED = new Node();
/** 独占 */
static final Node EXCLUSIVE = null;
/**
* 由于超时或者中断。节点会被设置为取消状态。被取消的节点时不会參与到竞争中的，他会一直保持取消状态不会转变为其它状态；
*/
static final int CANCELLED = 1;
/**
* 后继节点的线程处于等待状态。而当前节点的线程假设释放了同步状态或者被取消，将会通知后继节点，使后继节点的线程得以运行
*/
static final int SIGNAL = -1;
/**
* 节点在等待队列中，节点线程等待在Condition上，当其它线程对Condition调用了signal()后，改节点将会从等待队列中转移到同步队列中，加入到同步状态的获取中
*/
static final int CONDITION = -2;
/**
* 表示下一次共享式同步状态获取将会无条件地传播下去
*/
static final int PROPAGATE = -3;
/** 等待状态 */
volatile int waitStatus;
/** 前驱节点 */
volatile Node prev;
/** 后继节点 */
volatile Node next;
/** 获取同步状态的线程 */
volatile Thread thread;
Node nextWaiter;
final boolean isShared() {
return nextWaiter == SHARED;
}
final Node predecessor() throws NullPointerException {
Node p = prev;
if (p == null)
throw new NullPointerException();
else
return p;
}
Node() {
}
Node(Thread thread, Node mode) {
this.nextWaiter = mode;
this.thread = thread;
}
Node(Thread thread, int waitStatus) {
this.waitStatus = waitStatus;
this.thread = thread;
}
}CLH同步队列结构图例如以下：
入列
学了数据结构的我们，CLH队列入列是再简单只是了，无非就是tail指向新节点、新节点的prev指向当前最后的节点。当前最后一个节点的next指向当前节点。代码我们能够看看addWaiter(Node node)方法：
private Node addWaiter(Node mode) {
//新建Node
Node node = new Node(Thread.currentThread(), mode);
//高速尝试加入尾节点
Node pred = tail;
if (pred != null) {
node.prev = pred;
//CAS设置尾节点
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
//多次尝试
enq(node);
return node;
}addWaiter(Node node)先通过高速尝试设置尾节点，假设失败，则调用enq(Node node)方法设置尾节点
private Node enq(final Node node) {
//多次尝试，直到成功为止
for (;;) {
Node t = tail;
//tail不存在。设置为首节点
if (t == null) {
if (compareAndSetHead(new Node()))
tail = head;
} else {
//设置为尾节点
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}在上面代码中，两个方法都是通过一个CAS方法compareAndSetTail(Node expect, Node update)来设置尾节点，该方法能够确保节点是线程安全加入的。
在enq(Node node)方法中，AQS通过“死循环”的方式来保证节点能够正确加入。仅仅有成功加入后。当前线程才会从该方法返回，否则会一直运行下去。
过程图例如以下：
出列
CLH同步队列遵循FIFO。首节点的线程释放同步状态后，将会唤醒它的后继节点（next），而后继节点将会在获取同步状态成功时将自己设置为首节点。这个过程很easy，head运行该节点并断开原首节点的next和当前节点的prev就可以，注意在这个过程是不须要使用CAS来保证的，由于仅仅有一个线程能够成功获取到同步状态。过程图例如以下：
參考资料
Doug Lea：《Java并发编程实战》
方腾飞：《Java并发编程的艺术》
欢迎扫一扫我的公众号关注 — 及时得到博客订阅哦！
–— Java成神之路： 488391811（一起走向Java成神） –—