多執行緒與高並行（五）—— 原始碼解析 ReentrantLock
一、前言
ReentrantLock 是基於 AQS 實現的同步框架，關於 AQS 的原始碼在 這篇文章 已經講解過，ReentrantLock 的主要實現都依賴AQS，因此在閱讀本文前應該先了解 AQS 機制。本文並不關注 ReentrantLock 如何使用，只敘述其具體實現。
二、ReentrantLock 的繼承體系以及特點
AQS 是基於模板方法模式設計的，理解該設計模式可以幫助閱讀 ReentrantLock 原始碼，當然不熟悉該設計模式並不影響下文的閱讀。
首先我們來看 ReentrantLock 的類結構，該類實現了 Lock 介面，該介面定義了一些需要實現的方法，這些方法是提供給應用程式設計師編寫並行程式使用時的 API。ReentrantLock 如何提供這些 API的支援則依賴 AQS 框架，在其內部定義了一個類 Sync ，在 AQS 一文中提到過要使用 AQS 構建同步工具，主要是實現自己的 tryAccquire 和 tryRealease 方法，Sync 類即是 AQS 的模板方法具體實現，對加鎖解鎖方法進行了重新實現，但稍有不同的是，其具體實現又繼續向下委託，在對 FairSync 和 NonfairSync 類中皆有各自的實現，對應的是公平鎖和非公平鎖的實現。
public class ReentrantLock implements Lock, java.io.Serializable {
abstract static class Sync extends AbstractQueuedSynchronizer {
}
static final class FairSync extends Sync {
}
static final class NonfairSync extends Sync {
}
}
Lock 介面
Lock 介面體現了 ReentrantLock 的特性，我們看看定義了哪些方法，然後在原始碼解析篇依次對各個功能實現詳細講解。
public interface Lock {
void lock();
void lockInterruptibly() throws InterruptedException;
boolean tryLock();
boolean tryLock(long time, TimeUnit unit) throws InterruptedException;
void unlock();
Condition newCondition();
}
- lock() 加鎖操作
- unlock() 解鎖操作
- lockInterruptibly() 可中斷鎖
- tryLock() 嘗試加鎖，只嘗試一次，不阻塞等待鎖
- tryLock(long time, TimeUnit unit) 可超時鎖
- newCondition() 支援條件佇列
三、原始碼解析
3.1 加鎖過程
我們首先來看下呼叫鏈，圖中只畫出 reentrantLock 的邏輯，關於 acquire() 中的後續邏輯見 AQS 篇。
3.1.1 非公平鎖加鎖
ReentrantLock 的預設構造器實現的是非公平鎖，因此我們也先來看非公平鎖的實現。lock() 即加鎖的入口，使用時呼叫 lock.lock() 方法，在非公平鎖模式下其最終交由 NonfairSync 來實現。
首先嚐試 CAS 修改鎖狀態，即修改 AQS 中 State 的值，如果修改成功則表明加鎖成功，接下來修改 exclusiveOwnerThread 為當前執行緒，表明當前執行緒獨佔該鎖。如果修改失敗，表明已經有執行緒獲取了鎖，此時呼叫 AQS 中的方法 acquire(1) 再次嘗試獲取鎖。
該方法在 AQS 篇章有講過，首先是呼叫 tryAcquire() 嘗試獲取鎖，我們看其最終呼叫的邏輯 nonfairTryAcquire（）。
-
獲取當前鎖的狀態，並判斷鎖狀態
-
鎖處於初始化狀態則說明鎖現在是可被使用狀態，能進這個邏輯，說明剛才持有鎖的執行緒已經釋放了鎖，同 Sync.lock() 中的邏輯進行加鎖操作，因為 State 為0，因此此次加鎖必然能成功。
-
如果鎖狀態不為 0，說明鎖已經被一個執行緒所持有，判斷下是否為當前執行緒，是的話進入重入邏輯，不是的話返回 false 表明加鎖失敗，進入 acquireQueued() 邏輯去走入隊過程。
3.1.2 公平鎖加鎖
公平鎖的呼叫鏈與非公平鎖大同小異，非公平鎖與公平鎖的加鎖邏輯區別有二。
- Lock()中的實現邏輯，非公平鎖在呼叫 acquire() 方法之前先進行了一次加鎖嘗試
- tryAcquire() 邏輯，公平鎖多一個排隊的過程，hasQueuedPredecessors()
這兩處不同即是兩種鎖思想的具體體現：執行緒在獲取鎖之前是否需要排隊？
排隊的含義其實不準確，這個定義很寬泛，很難準確描述 hasQueuedPredecessors 所涉及的情形，但是我們可以用這個通俗的意義來直覺的感受這個過程，即當前執行緒在加鎖之前首先需要判斷 CLH 佇列中有沒有其他執行緒優先順序比我高，如果有的話，那我就去佇列等待（加鎖失敗，走acquire 剩餘邏輯入隊），如果沒有優先順序比我高的執行緒，那麼我就有資格獲取鎖，走 CAS 邏輯去加鎖。
有人可能不明白 CLH 佇列就是先進先出佇列，為何會出現要排隊的情況，然而搶佔鎖的執行緒實際上有兩種，一是在佇列中阻塞的執行緒，二是新來的一個執行緒，還沒進入佇列排隊。因此即使 CLH 佇列是先進先出的，這個此時正好來競爭鎖的執行緒就需要判斷自己是否有資格獲取鎖，也就是佇列中有沒有執行緒優先順序比自己高。
非公平鎖則沒有這個排隊的過程，新來的這個執行緒直接就有資格獲取鎖，因此在請求鎖時直接去 CAS 搶佔鎖。可以看到非公平鎖的搶佔和作業系統的程序搶佔是有不同的，並不是所有執行緒被喚醒去隨機搶佔，而是通常意義上也有個排隊的佇列，只是這個新來的執行緒可以插隊，直接高過隊頭執行緒的優先順序去加鎖。
那麼為什麼 lock() 中嘗試一次加鎖，tryAcquire() 中又一次加鎖呢？其實只保留一處加鎖即可，在 CAS 失敗後再嘗試一次，我猜測可能只是為了優化，多一次加鎖成功的機會。
3.2 hasQueuedPredecessors() 解析
/**
* Queries whether any threads have been waiting to acquire longer
* than the current thread.
* 查詢是否有其他執行緒比當前執行緒等待了更久的時間
*
* 這個方法有點類似下面虛擬碼的邏輯，但是更有效
* <p>An invocation of this method is equivalent to (but may be
* more efficient than):
* <pre> {@code
* getFirstQueuedThread() != Thread.currentThread() &&
* hasQueuedThreads()}</pre>
*
* 注意由於執行緒可能在任何時候因為中斷或者超時被取消，返回 true 並不能保證其他執行緒會在當前執行緒之前獲取鎖。
* 因此，其他執行緒也可能在當前執行緒返回 false 之後由於佇列為空而贏得競爭去入隊
* <p>Note that because cancellations due to interrupts and
* timeouts may occur at any time, a {@code true} return does not
* guarantee that some other thread will acquire before the current
* thread. Likewise, it is possible for another thread to win a
* race to enqueue after this method has returned {@code false},
* due to the queue being empty.
*
* <p>This method is designed to be used by a fair synchronizer to
* avoid <a href="AbstractQueuedSynchronizer#barging">barging</a>.
* Such a synchronizer's {@link #tryAcquire} method should return
* {@code false}, and its {@link #tryAcquireShared} method should
* return a negative value, if this method returns {@code true}
* (unless this is a reentrant acquire). For example, the {@code
* tryAcquire} method for a fair, reentrant, exclusive mode
* synchronizer might look like this:
*
* <pre> {@code
* protected boolean tryAcquire(int arg) {
* if (isHeldExclusively()) {
* // A reentrant acquire; increment hold count
* return true;
* } else if (hasQueuedPredecessors()) {
* return false;
* } else {
* // try to acquire normally
* }
* }}</pre>
*
* @return {@code true} if there is a queued thread preceding the
* current thread, and {@code false} if the current thread
* is at the head of the queue or the queue is empty
* 如果佇列中有比當前執行緒處於更靠前的節點返回 true，如果當前佇列為空或者當前執行緒為佇列第一個節點返回 false
* @since 1.7
*/
public final boolean hasQueuedPredecessors() {
// 如果當前執行緒為佇列中的第一個節點，那麼正確性取決於頭節點是否先於尾節點被初始化以及頭節點的 next 指標是正確的
// 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());
}
這個方法很簡短，但卻是最複雜的，我們一段一段分析這些邏輯判斷。該方法的註釋我上面已經翻譯，需要注意的是在呼叫該方法的時候使用了取反邏輯，當該方法返回 true 時，說明需要排隊，!hasQueuedPredecessors() 為false所以不能直接加鎖，當該方法返回 false 時，才有資格加鎖。
我們下面分段的去看這些與或邏輯，看什麼情況下滿足不需要排隊的條件，也就是返回 false 的情況。
h != t
-
head == null, tail == null,，佇列還未初始化，返回 false
-
head != null, tail == null，這種情況發生在初始化過程中，具體情況如下圖, 返回 true
-
head != null, tail != null，分情況討論，如下
-
head == tail，此時佇列中只有一個 dummy 節點, 無論是佇列剛初始化完畢建立了一個 dummy 節點還是鎖更替導致，只要佇列中只唯一存在一個 dummy 節點時，head 才會等於 tail。如圖為 T1 釋放了鎖後 T2 搶佔鎖成功的佇列圖（一定要先看 AQS 那篇文章，參照 acquireQueued() 原始碼）。返回 false。
-
head != tail，下圖為 T2 搶佔鎖成功，T3 執行緒還在佇列中的情形，也就是當佇列中節點數大於1時（此時佇列中節點數為2，初始化建立出來的啞節點指標已斷開，與佇列無關係），head != null。返回 true。
-
-
Head == null, tail != null，這種情況不會出現，忽略
因此佇列還未初始化時，以及佇列中沒有實際節點時（只有 dummy 節點），返回 false。
返回 true 有兩種情況，佇列中有實際節點或者佇列正在初始化還沒初始化完畢。
(s = h.next) == null
- 佇列中只有一個啞節點，條件成立，返回 true。
- 佇列中有兩個節點，next 指標為 null, 返回 true, 在 AQS 那篇講過 enq() 方法不能保證 next 指標一定正確，存在空檔期該指標為 null，返回 true。
- 佇列中有兩個節點，next 指標指向實際節點，返回 false。
因此當佇列中有兩個節點時，h != t && ((s = h.next) == null 為 false，接下來是或邏輯，因此我們還需要保證 s.thread != Thread.currentThread() 為 false。
s.thread != Thread.currentThread()
s.thread 即啞節點的下一個節點（實際節點），即實際節點
- 如果 s.thread 為 null，返回 true。
- 如果當前節點為實際節點，也就是重入，返回 false。
- 當前節點不是實際節點，說明有其他更高優先順序的執行緒，返回 true。
因此整體邏輯返回 false 的情況就是當前執行緒就是該佇列中的第二個節點，也就是優先順序最高的節點。那麼有同學可能有疑問，這裡僅考慮了佇列中的執行緒，佇列還沒初始化時，執行緒競爭的情況下都不用排隊嗎？這個問題下面分場景來分析。
PS：插些題外話，為了分析清楚這段程式碼的作用，我採用的方法是分段去分析邏輯，再倒推這些邏輯判斷具體是為了做什麼事情。分析完畢後我發現存在兩個弊端，一是要將邏輯整合起來理解比較難以釐清（主要是難以講述），二是這有通過程式碼逆推思路的嫌疑，如果要理解別人編碼上的巧妙，應該從場景遞推，也就是我們寫程式碼時的編碼思維，思考自己會怎麼寫，對比 Doug Lea 怎麼寫。不過如果從場景遞推，我想關於這段程式碼我不一定能對所有情況考慮周全，因而上面的分析過程我沒有刪除，接下來我再從場景開始遞推分析為什麼要這樣設計，首先我們來看整個流程圖。
-
場景1，佇列還沒有初始化，此時 head == null, tail == null，佇列都沒被初始化，自然不用考慮佇列中的節點，整段邏輯 （後面就以整段邏輯代指這段完整的bool邏輯，不再每次列出）h != t && ((s = h.next) == null || s.thread != Thread.currentThread()) 返回 false，不用排隊。那麼如果此時兩個執行緒都執行了該段邏輯不需要排隊，並不影響公平鎖的特性，兩個執行緒現在的資格是平等的，都嘗試去 CAS 加鎖，當鎖被佔用的時候，兩個執行緒都加鎖失敗，都開始進行入隊過程，如果鎖此時已經被釋放了，那麼只會有一個執行緒加鎖成功，另一個執行緒則進行入隊過程。
-
場景2，佇列初始化過程中，對應的就是 head != null, tail == null 。也就是場景 1 導致的至少有一個執行緒開始了入隊過程，那麼此時進來的這個執行緒優先順序必然比這個已經開始入隊的執行緒低，因此要去排隊。h != t 為true，該結果為true, 接下來判斷 (s = h.next) == null, 此時佇列中只有頭節點，因此該邏輯為 true，後面是|| 邏輯無需判斷，整段邏輯返回 true，表示需要排隊
-
場景3，佇列初始化完畢了，佇列中沒有實際節點，只有啞節點，這個啞節點無論是初次構造的還是後來執行緒替換的，怎麼生成的啞節點不影響排隊結果，只要有啞節點存在，那麼當前執行緒就需要排隊，無論此時是否有其他執行緒在入隊過程中。如下面舉例假設此時執行緒 T1 建立出了啞節點，即將在第二輪迴圈中執行連結串列維護工作，也就是執行下面程式碼 1、2、3，我們分段分析。
- 如果 T1 執行緒現在還沒來的及執行 cas 設定尾部程式碼，那麼 head 和 tail 都還是指向啞節點的，整段邏輯是 false && true || true，最終結果為 true 需要排隊。
- 如果 T1 執行完畢了 CAS 設定了尾部，還沒有執行 t.next = node，也就是此時 next 指標為 null，那麼整段邏輯是 true && true || true，也是結果為 true，需要排隊。
- 如果 T1 執行完了語句1、2、3，完整的將 T1 入隊了，此時整段邏輯是 true && false || true，結果為 true，需要排隊。
如果當前沒有其他執行緒在入隊，佇列中的情形和 T1 還沒開始執行程式碼 1 是一致的，因此返回 true，也需要排隊。
可見，只要佇列中有一個啞節點，那麼當前執行緒就必須排隊。
- 場景4，佇列中的節點數大於1，也就是包含了實際節點。上面場景3 包含了執行緒入隊過程中要不要排隊的場景，因此場景4中關注的佇列是連結串列已經維護完畢的佇列。如果佇列中節點數大於 1，那麼或之前的邏輯 h != t 為 true，(s = h.next) == null 此時是 false, 因此現在要判斷當前執行緒是不是重入，也就是當前執行緒等不等於佇列中的第二個節點。s.thread != Thread.currentThread()，即如果該條件為 false，說明當前執行緒是重入執行緒，無需排隊。
- 場景5，同場景4，只是當前執行緒不是重入執行緒，s.thread != Thread.currentThread() 該條件為 true，需要排隊。
以上就對當前執行緒是否需要排隊的所有場景分析完畢。公平鎖與非公平鎖之間的不同就已經講完了，其餘邏輯一致，在非公平鎖已經講過，接下來看解鎖流程。
3.3 解鎖過程
不管是公平鎖還是非公平鎖，在解鎖時都是呼叫 AQS 中的 realease 方法，在 AQS 篇已經講解過，不重複講了。
3.4 tryLock()
public boolean tryLock() {
return sync.nonfairTryAcquire(1);
}
對比下 lock 的原始碼
重點是 acquire 方法，lock() 方法在呼叫 tryAcquire 嘗試加鎖失敗後就開始走入隊的邏輯，也就是如果當前執行緒獲取不到鎖那麼就需要阻塞。而 tryLock() 方法呼叫 nonfairTryAcquire() 嘗試加鎖，成功則返回 true，失敗則返回 false，沒有入隊的邏輯。注意的是 tryLock() 只有非公平鎖的實現，因此我們可以理解為這個方法用於插隊獲取鎖，也就是說該方法用於公平鎖的時候實際上破壞了公平原則。如果要維持公平原則，可以使用tryLock(0, TimeUnit.SECONDS) 等效 tryLock。另外該方法也不支援打斷，帶超時的 tryLock() 才支援打斷，這也很好理解，tryLock 去搶佔鎖也不進行入隊，結果很快就能返回，中斷對該方法來說毫無意義。
3.5 tryLock(long timeout, TimeUnit unit)
public boolean tryLock(long timeout, TimeUnit unit)
throws InterruptedException {
return sync.tryAcquireNanos(1, unit.toNanos(timeout));
}
我們先看原始碼：首先該方法支援中斷，如果被設定了中斷標記，丟擲中斷異常。在呼叫該方法的時候首先會嘗試一次加鎖，即 tryAcquire(arg)，如果加鎖成功就整個方法返回 true，加鎖失敗了則進入 doAcquireNanos 邏輯。
public final boolean tryAcquireNanos(int arg, long nanosTimeout)
throws InterruptedException {
// 如果被中斷則直接丟擲中斷異常
if (Thread.interrupted())
throw new InterruptedException();
// 獲取鎖失敗就執行 doAcquireNanos 入隊，直到超時返回 false
return tryAcquire(arg) ||
doAcquireNanos(arg, nanosTimeout);
}
doAcquireNanos 才是該方法的核心，該方法中再次嘗試一次加鎖，加鎖成功的話返回結果 true，如果加鎖失敗那麼判斷下設定的超時時間有沒有到，時間到了的話直接返回 false 表明加鎖失敗。接下來呼叫 shouldParkAfterFailedAcquire 方法判斷當前節點是否需要阻塞，如果要阻塞的話還需要當前時間大於 1000 ns，如果時間小於這個值，那麼就不阻塞了。這麼設定也很有道理，如果時間太短，剛被 park 阻塞就要喚醒，這因上下文切換浪費的 CPU 時間片不如直接進行下一次迴圈嘗試加鎖。如果不用阻塞就進行下一輪迴圈重複之前流程再次嘗試加鎖。
private boolean doAcquireNanos(int arg, long nanosTimeout)
throws InterruptedException {
if (nanosTimeout <= 0L)
return false;
// 當前時間 + 超時時間，即中斷執行緒的最後期限
final long deadline = System.nanoTime() + nanosTimeout;
final Node node = addWaiter(Node.EXCLUSIVE);
boolean failed = true;
try {
for (;;) {
final Node p = node.predecessor();
// 嘗試加鎖
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
// 加鎖成功則返回
return true;
}
// 加鎖失敗，判斷需要阻塞多久
// 剩餘時間
nanosTimeout = deadline - System.nanoTime();
// 時間不足， 直接返回 false，不阻塞
if (nanosTimeout <= 0L)
return false;
// 判斷是否需要阻塞，且剩餘時間需大於 1000L，時間太短那就沒有阻塞的意義了, 不需要阻塞的話進入下一輪迴圈再次嘗試加鎖
if (shouldParkAfterFailedAcquire(p, node) &&
nanosTimeout > spinForTimeoutThreshold) // spinForTimeoutThreshold 的值為 1000L
// 阻塞執行緒，限定了阻塞時長為剩餘時間
LockSupport.parkNanos(this, nanosTimeout);
// 如果執行緒被打斷，丟擲異常
if (Thread.interrupted())
throw new InterruptedException();
}
} finally {
if (failed)
cancelAcquire(node);
}
}
parkNanos(Object blocker, long nanos) 方法阻塞執行緒，在指定的時間到達之後喚醒執行緒。
可知，該方法的作用就是在指定的時間內不斷嘗試加鎖，加鎖成功則提前返回，時間到了後無論當前執行緒是處於執行態還是阻塞態都需要返回結果 false，如果是阻塞態則還需要喚醒執行緒。
3.5 lockInterruptibly()
public void lockInterruptibly() throws InterruptedException {
sync.acquireInterruptibly(1);
}
該方法如下：支援中斷，當然這毫無疑問，該方法就是支援中斷的加鎖操作。
public final void acquireInterruptibly(int arg)
throws InterruptedException {
// 執行緒被中斷，丟擲中斷異常
if (Thread.interrupted())
throw new InterruptedException();
// 嘗試獲取鎖，獲取失敗則執行 doAcquireInterruptibly 入隊，邏輯與acquireQueued大體一致，唯一的區別是在被中斷時立馬丟擲異常，而不是修改標記等待下一次迴圈返回標記
if (!tryAcquire(arg))
doAcquireInterruptibly(arg);
}
看該方法與 lock() 預設實現 acquireQueued 的對比，主要的區別就是該方法遇到中斷時直接丟擲中斷異常，而 acquireQueued 中只是在下一輪迴圈中將中斷標記返回出去。
結合該方法整個原始碼來看，兩次處理異常，第一次處理即如果當前執行緒的中斷標識已經被修改，那麼不嘗試加鎖，直接丟擲異常；第二次處理，如果阻塞過程中，執行緒被 interrupt() 中斷那麼該執行緒恢復執行態，丟擲異常。
3.6 newCondition()
該方法的實現依賴介面 Condition，這裡就不講了，關於 Condition 是否有原始碼解析，待我看過再說。
其他
- 回看 tryAcquire() 方法，有些同學可能會疑問為什麼判斷排隊時還需要確定當前執行緒是否重入呢？重入邏輯不是在 tryAcquire 中有實現嗎？
這就要對兩個重入應對的場景區分，tryAcquire 中的重入處理是針對當前執行緒已經成功獲得鎖，排隊中的邏輯是針對鎖狀態為可用的時候，也就是鎖此時都可用了，當前執行緒作為佇列中第一個實際節點，自然有資格直接競爭鎖，何況該執行緒已經在佇列中，更無需再次重複入隊。
試看以下場景，執行緒 T 在加鎖的過程中因競爭鎖失敗將自己成功入隊成為佇列中第一個實際節點，接下來因遞迴等操作該執行緒再次嘗試加鎖，此時正好其他執行緒釋放了鎖，再次呼叫 hasQueuedPredecessors 邏輯就需要返回一個 false 來表明當前執行緒無需排隊，因此 s.thread != Thread.currentThread() 條件是不可或缺的。
2. 為什麼要設定啞節點
3. 為什麼只要佇列中有一個啞節點，那麼當前執行緒就必須排隊？
4. 為什麼 AQS 中要將當前節點狀態儲存在前一個節點？
結語
以上三個疑問，有的看到過一些回答，但不是特別有說服力，有些暫時沒想法，先擱置吧。JUC 原始碼暫且先分析至此，其他的我先研究一遍，得了閒再來寫部落格。