此篇博客所有源碼均來自JDK 1.8
在上篇博客【死磕Java并發(fā)】-----J.U.C之AQS：AQS簡介中提到了AQS內(nèi)部維護著一個FIFO隊列赋秀，該隊列就是CLH同步隊列寒跳。
CLH同步隊列是一個FIFO雙向隊列，AQS依賴它來完成同步狀態(tài)的管理啤它，當前線程如果獲取同步狀態(tài)失敗時断箫，AQS則會將當前線程已經(jīng)等待狀態(tài)等信息構(gòu)造成一個節(jié)點（Node）并將其加入到CLH同步隊列网棍，同時會阻塞當前線程兼蜈，當同步狀態(tài)釋放時，會把首節(jié)點喚醒（公平鎖）序宦，使其再次嘗試獲取同步狀態(tài)睁壁。
在CLH同步隊列中，一個節(jié)點表示一個線程互捌，它保存著線程的引用（thread）潘明、狀態(tài)（waitStatus）、前驅(qū)節(jié)點（prev）秕噪、后繼節(jié)點（next）钳降，其定義如下：
static final class Node {
/** 共享 */
static final Node SHARED = new Node();
/** 獨占 */
static final Node EXCLUSIVE = null;
/**
* 因為超時或者中斷，節(jié)點會被設(shè)置為取消狀態(tài)腌巾，被取消的節(jié)點時不會參與到競爭中的遂填，他會一直保持取消狀態(tài)不會轉(zhuǎn)變?yōu)槠渌麪顟B(tài)铲觉；
*/
static final int CANCELLED = 1;
/**
* 后繼節(jié)點的線程處于等待狀態(tài)，而當前節(jié)點的線程如果釋放了同步狀態(tài)或者被取消吓坚，將會通知后繼節(jié)點撵幽，使后繼節(jié)點的線程得以運行
*/
static final int SIGNAL = -1;
/**
* 節(jié)點在等待隊列中，節(jié)點線程等待在Condition上礁击，當其他線程對Condition調(diào)用了signal()后盐杂，改節(jié)點將會從等待隊列中轉(zhuǎn)移到同步隊列中，加入到同步狀態(tài)的獲取中
*/
static final int CONDITION = -2;
/**
* 表示下一次共享式同步狀態(tài)獲取將會無條件地傳播下去
*/
static final int PROPAGATE = -3;
/** 等待狀態(tài) */
volatile int waitStatus;
/** 前驅(qū)節(jié)點 */
volatile Node prev;
/** 后繼節(jié)點 */
volatile Node next;
/** 獲取同步狀態(tài)的線程 */
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同步隊列結(jié)構(gòu)圖如下：
入列
學(xué)了數(shù)據(jù)結(jié)構(gòu)的我們哆窿，CLH隊列入列是再簡單不過了链烈，無非就是tail指向新節(jié)點、新節(jié)點的prev指向當前最后的節(jié)點挚躯，當前最后一個節(jié)點的next指向當前節(jié)點测垛。代碼我們可以看看addWaiter(Node node)方法：
private Node addWaiter(Node mode) {
//新建Node
Node node = new Node(Thread.currentThread(), mode);
//快速嘗試添加尾節(jié)點
Node pred = tail;
if (pred != null) {
node.prev = pred;
//CAS設(shè)置尾節(jié)點
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
//多次嘗試
enq(node);
return node;
}
addWaiter(Node node)先通過快速嘗試設(shè)置尾節(jié)點，如果失敗秧均，則調(diào)用enq(Node node)方法設(shè)置尾節(jié)點
private Node enq(final Node node) {
//多次嘗試，直到成功為止
for (;;) {
Node t = tail;
//tail不存在号涯，設(shè)置為首節(jié)點
if (t == null) {
if (compareAndSetHead(new Node()))
tail = head;
} else {
//設(shè)置為尾節(jié)點
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}
在上面代碼中目胡，兩個方法都是通過一個CAS方法compareAndSetTail(Node expect, Node update)來設(shè)置尾節(jié)點，該方法可以確保節(jié)點是線程安全添加的链快。在enq(Node node)方法中誉己，AQS通過“死循環(huán)”的方式來保證節(jié)點可以正確添加，只有成功添加后域蜗，當前線程才會從該方法返回巨双，否則會一直執(zhí)行下去。
過程圖如下：
出列
CLH同步隊列遵循FIFO霉祸，首節(jié)點的線程釋放同步狀態(tài)后筑累，將會喚醒它的后繼節(jié)點（next），而后繼節(jié)點將會在獲取同步狀態(tài)成功時將自己設(shè)置為首節(jié)點丝蹭，這個過程非常簡單慢宗，head執(zhí)行該節(jié)點并斷開原首節(jié)點的next和當前節(jié)點的prev即可，注意在這個過程是不需要使用CAS來保證的奔穿，因為只有一個線程能夠成功獲取到同步狀態(tài)镜沽。過程圖如下：
參考資料
Doug Lea：《Java并發(fā)編程實戰(zhàn)》
方騰飛：《Java并發(fā)編程的藝術(shù)》
