### 等待隊列中線程出隊列時機 回到最初的源碼： ~~~ // java.util.concurrent.locks.AbstractQueuedSynchronizer public final void acquire(int arg) { if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); } ~~~ 上文解釋了addWaiter方法，這個方法其實就是把對應的線程以Node的數據結構形式加入到雙端隊列里，返回的是一個包含該線程的Node。而這個Node會作為參數，進入到acquireQueued方法中。acquireQueued方法可以對排隊中的線程進行“獲鎖”操作。 總的來說，一個線程獲取鎖失敗了，被放入等待隊列，acquireQueued會把放入隊列中的線程不斷去獲取鎖，直到獲取成功或者不再需要獲取（中斷）。 下面我們從“何時出隊列？”和“如何出隊列？”兩個方向來分析一下acquireQueued源碼： ~~~ // java.util.concurrent.locks.AbstractQueuedSynchronizer final boolean acquireQueued(final Node node, int arg) { // 標記是否成功拿到資源 boolean failed = true; try { // 標記等待過程中是否中斷過 boolean interrupted = false; // 開始自旋，要么獲取鎖，要么中斷 for (;;) { // 獲取當前節點的前驅節點 final Node p = node.predecessor(); // 如果p是頭結點，說明當前節點在真實數據隊列的首部，就嘗試獲取鎖（別忘了頭結點是虛節點） if (p == head && tryAcquire(arg)) { // 獲取鎖成功，頭指針移動到當前node setHead(node); p.next = null; // help GC failed = false; return interrupted; } // 說明p為頭節點且當前沒有獲取到鎖（可能是非公平鎖被搶占了）或者是p不為頭結點，這個時候就要判斷當前node是否要被阻塞（被阻塞條件：前驅節點的waitStatus為-1），防止無限循環浪費資源。具體兩個方法下面細細分析 if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) interrupted = true; } } finally { if (failed) cancelAcquire(node); } } ~~~ 注：setHead方法是把當前節點置為虛節點，但并沒有修改waitStatus，因為它是一直需要用的數據。 ~~~ // java.util.concurrent.locks.AbstractQueuedSynchronizer private void setHead(Node node) { head = node; node.thread = null; node.prev = null; } // java.util.concurrent.locks.AbstractQueuedSynchronizer // 靠前驅節點判斷當前線程是否應該被阻塞 private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { // 獲取頭結點的節點狀態 int ws = pred.waitStatus; // 說明頭結點處于喚醒狀態 if (ws == Node.SIGNAL) return true; // 通過枚舉值我們知道waitStatus>0是取消狀態 if (ws > 0) { do { // 循環向前查找取消節點，把取消節點從隊列中剔除 node.prev = pred = pred.prev; } while (pred.waitStatus > 0); pred.next = node; } else { // 設置前任節點等待狀態為SIGNAL compareAndSetWaitStatus(pred, ws, Node.SIGNAL); } return false; } ~~~ parkAndCheckInterrupt主要用于掛起當前線程，阻塞調用棧，返回當前線程的中斷狀態。 ~~~ // java.util.concurrent.locks.AbstractQueuedSynchronizer private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted(); } ~~~ 上述方法的流程圖如下：  從上圖可以看出，跳出當前循環的條件是當“前置節點是頭結點，且當前線程獲取鎖成功”。為了防止因死循環導致CPU資源被浪費，我們會判斷前置節點的狀態來決定是否要將當前線程掛起，具體掛起流程用流程圖表示如下（shouldParkAfterFailedAcquire流程）：  從隊列中釋放節點的疑慮打消了，那么又有新問題了： * shouldParkAfterFailedAcquire中取消節點是怎么生成的呢？什么時候會把一個節點的waitStatus設置為-1？ * 是在什么時間釋放節點通知到被掛起的線程呢？ ### CANCELLED狀態節點生成 acquireQueued方法中的Finally代碼： ~~~ // java.util.concurrent.locks.AbstractQueuedSynchronizer final boolean acquireQueued(final Node node, int arg) { boolean failed = true; try { ... for (;;) { final Node p = node.predecessor(); if (p == head && tryAcquire(arg)) { ... failed = false; ... } ... } finally { if (failed) cancelAcquire(node); } } ~~~ 通過cancelAcquire方法，將Node的狀態標記為CANCELLED。接下來，我們逐行來分析這個方法的原理： ~~~ // java.util.concurrent.locks.AbstractQueuedSynchronizer private void cancelAcquire(Node node) { // 將無效節點過濾 if (node == null) return; // 設置該節點不關聯任何線程，也就是虛節點 node.thread = null; Node pred = node.prev; // 通過前驅節點，跳過取消狀態的node while (pred.waitStatus > 0) node.prev = pred = pred.prev; // 獲取過濾后的前驅節點的后繼節點 Node predNext = pred.next; // 把當前node的狀態設置為CANCELLED node.waitStatus = Node.CANCELLED; // 如果當前節點是尾節點，將從后往前的第一個非取消狀態的節點設置為尾節點 // 更新失敗的話，則進入else，如果更新成功，將tail的后繼節點設置為null if (node == tail && compareAndSetTail(node, pred)) { compareAndSetNext(pred, predNext, null); } else { int ws; // 如果當前節點不是head的后繼節點，1:判斷當前節點前驅節點的是否為SIGNAL，2:如果不是，則把前驅節點設置為SINGAL看是否成功 // 如果1和2中有一個為true，再判斷當前節點的線程是否為null // 如果上述條件都滿足，把當前節點的前驅節點的后繼指針指向當前節點的后繼節點 if (pred != head && ((ws = pred.waitStatus) == Node.SIGNAL || (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) && pred.thread != null) { Node next = node.next; if (next != null && next.waitStatus <= 0) compareAndSetNext(pred, predNext, next); } else { // 如果當前節點是head的后繼節點，或者上述條件不滿足，那就喚醒當前節點的后繼節點 unparkSuccessor(node); } node.next = node; // help GC } } ~~~ 當前的流程： * 獲取當前節點的前驅節點，如果前驅節點的狀態是CANCELLED，那就一直往前遍歷，找到第一個waitStatus <= 0的節點，將找到的Pred節點和當前Node關聯，將當前Node設置為CANCELLED。 * 根據當前節點的位置，考慮以下三種情況： (1) 當前節點是尾節點。 (2) 當前節點是Head的后繼節點。 (3) 當前節點不是Head的后繼節點，也不是尾節點。 根據上述第二條，我們來分析每一種情況的流程。 當前節點是尾節點  當前節點是Head的后繼節點  當前節點不是Head的后繼節點，也不是尾節點  通過上面的流程，我們對于CANCELLED節點狀態的產生和變化已經有了大致的了解，但是為什么所有的變化都是對Next指針進行了操作，而沒有對Prev指針進行操作呢？什么情況下會對Prev指針進行操作？ > 執行cancelAcquire的時候，當前節點的前置節點可能已經從隊列中出去了（已經執行過Try代碼塊中的shouldParkAfterFailedAcquire方法了），如果此時修改Prev指針，有可能會導致Prev指向另一個已經移除隊列的Node，因此這塊變化Prev指針不安全。 shouldParkAfterFailedAcquire方法中，會執行下面的代碼，其實就是在處理Prev指針。shouldParkAfterFailedAcquire是獲取鎖失敗的情況下才會執行，進入該方法后，說明共享資源已被獲取，當前節點之前的節點都不會出現變化，因此這個時候變更Prev指針比較安全。 > > ~~~ > do { > node.prev = pred = pred.prev; > } while (pred.waitStatus > 0); > ~~~