一、前言 ReentrantLock 是基於 AQS 實現的同步框架，關於 AQS 的源碼在這篇文章已經講解過，ReentrantLock 的主要實現都依賴AQS，因此在閱讀本文前應該先瞭解 AQS 機制。本文並不關註 ReentrantLock 如何使用，只敘述其具體實現。二、Reentra ...

一、前言

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，分情況討論，如下
1. head == tail，此時隊列中只有一個 dummy 節點, 無論是隊列剛初始化完畢創建了一個 dummy 節點還是鎖更替導致，只要隊列中只唯一存在一個 dummy 節點時，head 才會等於 tail。如圖為 T1 釋放了鎖後 T2 搶占鎖成功的隊列圖（一定要先看 AQS 那篇文章，參照 acquireQueued() 源碼）。返回 false。
2. 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 源碼暫且先分析至此，其他的我先研究一遍，得了閑再來寫博客。

多線程與高併發（五）—— 源碼解析 ReentrantLock