### 2.3.1 線程加入等待隊列 #### 2.3.1.1 加入隊列的時機 當執行Acquire(1)時，會通過tryAcquire獲取鎖。在這種情況下，如果獲取鎖失敗，就會調用addWaiter加入到等待隊列中去。 #### 2.3.1.2 如何加入隊列 獲取鎖失敗后，會執行addWaiter(Node.EXCLUSIVE)加入等待隊列，具體實現方法如下： ~~~ // java.util.concurrent.locks.AbstractQueuedSynchronizer private Node addWaiter(Node mode) { Node node = new Node(Thread.currentThread(), mode); // Try the fast path of enq; backup to full enq on failure Node pred = tail; if (pred != null) { node.prev = pred; if (compareAndSetTail(pred, node)) { pred.next = node; return node; } } enq(node); return node; } private final boolean compareAndSetTail(Node expect, Node update) { return unsafe.compareAndSwapObject(this, tailOffset, expect, update); } ~~~ 主要的流程如下： * 通過當前的線程和鎖模式新建一個節點。 * Pred指針指向尾節點Tail。 * 將New中Node的Prev指針指向Pred。 * 通過compareAndSetTail方法，完成尾節點的設置。這個方法主要是對tailOffset和Expect進行比較，如果tailOffset的Node和Expect的Node地址是相同的，那么設置Tail的值為Update的值。 ~~~ // java.util.concurrent.locks.AbstractQueuedSynchronizer static { try { stateOffset = unsafe.objectFieldOffset(AbstractQueuedSynchronizer.class.getDeclaredField("state")); headOffset = unsafe.objectFieldOffset(AbstractQueuedSynchronizer.class.getDeclaredField("head")); tailOffset = unsafe.objectFieldOffset(AbstractQueuedSynchronizer.class.getDeclaredField("tail")); waitStatusOffset = unsafe.objectFieldOffset(Node.class.getDeclaredField("waitStatus")); nextOffset = unsafe.objectFieldOffset(Node.class.getDeclaredField("next")); } catch (Exception ex) { throw new Error(ex); } } ~~~ 從AQS的靜態代碼塊可以看出，都是獲取一個對象的屬性相對于該對象在內存當中的偏移量，這樣我們就可以根據這個偏移量在對象內存當中找到這個屬性。tailOffset指的是tail對應的偏移量，所以這個時候會將new出來的Node置為當前隊列的尾節點。同時，由于是雙向鏈表，也需要將前一個節點指向尾節點。 * 如果Pred指針是Null（說明等待隊列中沒有元素），或者當前Pred指針和Tail指向的位置不同（說明被別的線程已經修改），就需要看一下Enq的方法。 ~~~ // java.util.concurrent.locks.AbstractQueuedSynchronizer private Node enq(final Node node) { for (;;) { Node t = tail; if (t == null) { // Must initialize if (compareAndSetHead(new Node())) tail = head; } else { node.prev = t; if (compareAndSetTail(t, node)) { t.next = node; return t; } } } } ~~~ 如果沒有被初始化，需要進行初始化一個頭結點出來。但請注意，初始化的頭結點并不是當前線程節點，而是調用了無參構造函數的節點。如果經歷了初始化或者并發導致隊列中有元素，則與之前的方法相同。其實，addWaiter就是一個在雙端鏈表添加尾節點的操作，需要注意的是，雙端鏈表的頭結點是一個無參構造函數的頭結點。 總結一下，線程獲取鎖的時候，過程大體如下： 1. 當沒有線程獲取到鎖時，線程1獲取鎖成功。 2. 線程2申請鎖，但是鎖被線程1占有  如果再有線程要獲取鎖，依次在隊列中往后排隊即可 回到上邊的代碼，hasQueuedPredecessors是公平鎖加鎖時判斷等待隊列中是否存在有效節點的方法。如果返回False，說明當前線程可以爭取共享資源；如果返回True，說明隊列中存在有效節點，當前線程必須加入到等待隊列中。 ~~~ // java.util.concurrent.locks.ReentrantLock 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()); } ~~~ 看到這里，我們理解一下h != t && ((s = h.next) == null || s.thread != Thread.currentThread());為什么要判斷的頭結點的下一個節點？第一個節點儲存的數據是什么？ > 雙向鏈表中，第一個節點為虛節點，其實并不存儲任何信息，只是占位。真正的第一個有數據的節點，是在第二個節點開始的。當h != t時： 如果(s = h.next) == null，等待隊列正在有線程進行初始化，但只是進行到了Tail指向Head，沒有將Head指向Tail，此時隊列中有元素，需要返回True（這塊具體見下邊代碼分析）。 如果(s = h.next) != null，說明此時隊列中至少有一個有效節點。如果此時s.thread == Thread.currentThread()，說明等待隊列的第一個有效節點中的線程與當前線程相同，那么當前線程是可以獲取資源的；如果s.thread != Thread.currentThread()，說明等待隊列的第一個有效節點線程與當前線程不同，當前線程必須加入進等待隊列。 ~~~ // java.util.concurrent.locks.AbstractQueuedSynchronizer#enq if (t == null) { // Must initialize if (compareAndSetHead(new Node())) tail = head; } else { node.prev = t; if (compareAndSetTail(t, node)) { t.next = node; return t; } } ~~~ 節點入隊不是原子操作，所以會出現短暫的head != tail，此時Tail指向最后一個節點，而且Tail指向Head。如果Head沒有指向Tail（可見5、6、7行），這種情況下也需要將相關線程加入隊列中。所以這塊代碼是為了解決極端情況下的并發問題