本文轉(zhuǎn)載自【五月的倉(cāng)頡】的博客 原文

本文知識(shí)點(diǎn)

• 前言
• 什么是AbstractQueuedSynchronizer?
• ReentrantLock的實(shí)現(xiàn)原理
• lock()實(shí)現(xiàn)原理
• unlock()實(shí)現(xiàn)原理
• ReentrantLock其他方法的實(shí)現(xiàn)
• 小結(jié)

前言

??網(wǎng)上寫(xiě)ReentrantLock的使用、ReentrantLock和synchronized的區(qū)別的文章很多筒狠，研究ReentrantLock并且能講清楚ReentrantLock的原理的文章很少田柔，本文就來(lái)研究一下ReentrantLock的實(shí)現(xiàn)原理助析。研究ReentrantLock的實(shí)現(xiàn)原理需要比較好的Java基礎(chǔ)以及閱讀代碼的能力，有些朋友看不懂沒(méi)關(guān)系，可以以后看，相信你一定會(huì)有所收獲湘纵。
ReentrantLock是基于AQS實(shí)現(xiàn)的，這在下面會(huì)講到滤淳，AQS的基礎(chǔ)又是CAS梧喷，如果不是很熟悉CAS的朋友，可以看一下這篇文章Unsafe與CAS脖咐。

什么是AbstractQueuedSynchronizer?

??ReentrantLock實(shí)現(xiàn)的前提就是AbstractQueuedSynchronizer铺敌，簡(jiǎn)稱AQS，是java.util.concurrent的核心屁擅，CountDownLatch偿凭、FutureTask、Semaphore派歌、ReentrantLock等都有一個(gè)內(nèi)部類是這個(gè)抽象類的子類弯囊。先用兩張表格介紹一下AQS。第一個(gè)講的是Node胶果，由于AQS是基于FIFO隊(duì)列的實(shí)現(xiàn)匾嘱，因此必然存在一個(gè)個(gè)節(jié)點(diǎn)，Node就是一個(gè)節(jié)點(diǎn)早抠。
Node里面的部分屬性

看完了Node昧捷，下面再看一下AQS中有哪些變量和方法：

AQS里面的部分屬性

??上面列出了AQS中最主要的一些方法和屬性鸯绿。<font color=red>整個(gè)AQS是典型的模板模式的應(yīng)用</font>跋破，設(shè)計(jì)得十分精巧簸淀，對(duì)于FIFO隊(duì)列的各種操作在AQS中已經(jīng)實(shí)現(xiàn)了，<font color=red>AQS的子類一般只需要重寫(xiě)tryAcquire(int arg)和tryRelease(int arg)兩個(gè)方法即可</font>毒返。

ReentrantLock實(shí)現(xiàn)原理(源碼較多)

ReentrantLock中有一個(gè)抽象類Sync：

    private final Sync sync;
    /**
    * Base of synchronization control for this lock. Subclassed
    * into fair and nonfair versions below. Uses AQS state to
    * represent the number of holds on the lock.
    */
   abstract static class Sync extends AbstractQueuedSynchronizer {
    ...
    }

??ReentrantLock根據(jù)傳入構(gòu)造方法的布爾型參數(shù)實(shí)例化出Sync的實(shí)現(xiàn)類FairSync和NonfairSync租幕，分別表示公平的Sync和非公平的Sync。由于ReentrantLock我們用的比較多的是非公平鎖拧簸，所以看下非公平鎖是如何實(shí)現(xiàn)的劲绪。假設(shè)線程1調(diào)用了ReentrantLock的lock()方法，那么線程1將會(huì)獨(dú)占鎖盆赤，整個(gè)調(diào)用鏈?zhǔn)趾?jiǎn)單：

image

第一個(gè)獲取鎖的線程就做了兩件事情：

• 1贾富、設(shè)置AbstractQueuedSynchronizer的state為1
• 2、設(shè)置AbstractOwnableSynchronizer的thread為當(dāng)前線程

??這兩步做完之后就表示線程1獨(dú)占了鎖牺六。然后線程2也要嘗試獲取同一個(gè)鎖颤枪，在線程1沒(méi)有釋放鎖的情況下必然是行不通的，所以線程2就要阻塞兔乞。那么汇鞭，線程2如何被阻塞？看下線程2的方法調(diào)用鏈庸追，這就比較復(fù)雜了：

image

調(diào)用鏈看到確實(shí)非常長(zhǎng)霍骄，沒(méi)關(guān)系，結(jié)合代碼分析一下淡溯，其實(shí)ReentrantLock沒(méi)有那么復(fù)雜读整，我們一點(diǎn)點(diǎn)來(lái)扒代碼：

lock()的實(shí)現(xiàn)原理

final void lock() {
    if (compareAndSetState(0, 1))
        setExclusiveOwnerThread(Thread.currentThread());
    else
       acquire(1);
}

??首先線程2嘗試?yán)肅AS去判斷state是不是0，是0就設(shè)置為1咱娶，當(dāng)然這一步操作肯定是失敗的米间，因?yàn)榫€程1已經(jīng)將state設(shè)置成了1，所以第2行必定是false膘侮，因此線程2走第5行的acquire方法：

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

??從字面上就很好理解這個(gè)if的意思屈糊，先走第一個(gè)判斷條件嘗試獲取一次鎖，如果獲取的結(jié)果為false即失敗琼了，走第二個(gè)判斷條件添加FIFO等待隊(duì)列逻锐。所以先看一下tryAcquire方法做了什么，這個(gè)方法最終調(diào)用到的是Sync的nonfairTryAcquire方法：

1.final boolean nonfairTryAcquire(int acquires) {
2.    final Thread current = Thread.currentThread();
3.    int c = getState();
4.    if (c == 0) {
5.        if (compareAndSetState(0, acquires)) {
6.            setExclusiveOwnerThread(current);
7.            return true;
8.        }
9.    }
10.    else if (current == getExclusiveOwnerThread()) {
11.        int nextc = c + acquires;
12.        if (nextc < 0) // overflow
13.            throw new Error("Maximum lock count exceeded");
14.        setState(nextc);
15.        return true;
16    }
17.    return false;
18.}

??由于state是volatile的雕薪，所以state對(duì)線程2具有可見(jiàn)性昧诱，線程2拿到最新的state，再次判斷一下能否持有鎖（可能線程1同步代碼執(zhí)行得比較快所袁，這會(huì)兒已經(jīng)釋放了鎖）盏档，不可以就返回false。

??注意一下第10~第16行燥爷，這段代碼的作用是讓某個(gè)線程可以多次調(diào)用同一個(gè)ReentrantLock蜈亩，每調(diào)用一次給state+1懦窘，由于某個(gè)線程已經(jīng)持有了鎖，所以這里不會(huì)有競(jìng)爭(zhēng)勺拣，因此不需要利用CAS設(shè)置state（相當(dāng)于一個(gè)偏向鎖）奶赠。從這段代碼可以看到，nextc每次加1药有，當(dāng)nextc<0的時(shí)候拋出error毅戈，那么同一個(gè)鎖最多能重入Integer.MAX_VALUE次，也就是2147483647愤惰。

??然后就走到if的第二個(gè)判斷里面了苇经，先走AQS的addWaiter方法：

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;
}

??先創(chuàng)建一個(gè)當(dāng)前線程的Node，模式為獨(dú)占模式（因?yàn)閭魅氲膍ode是一個(gè)NULL）宦言，再判斷一下隊(duì)列上有沒(méi)有節(jié)點(diǎn)扇单，沒(méi)有就創(chuàng)建一個(gè)隊(duì)列，因此走enq方法：

1.private Node enq(final Node node) {
2.    for (;;) {
3.        Node t = tail;
4.        if (t == null) { // Must initialize
5.            if (compareAndSetHead(new Node()))
6.                tail = head;
7.        } else {
8.            node.prev = t;
9.            if (compareAndSetTail(t, node)) {
10.                t.next = node;
11.                return t;
12.            }
13.        }
14.    }
15.}

這個(gè)方法其實(shí)畫(huà)一張圖應(yīng)該比較好理解奠旺，形成一個(gè)隊(duì)列之后應(yīng)該是這樣的：

image

??每一步都用圖表示出來(lái)了蜘澜，由于線程2所在的Node是第一個(gè)要等待的Node，因此FIFO隊(duì)列上肯定沒(méi)有內(nèi)容响疚，tail為null鄙信，走的就是第4行~第6行的代碼邏輯。這里用了CAS設(shè)置頭Node忿晕，當(dāng)然有可能線程2設(shè)置頭Node的時(shí)候CPU切換了装诡，線程3已經(jīng)把頭Node設(shè)置好了形成了上圖所示的一個(gè)隊(duì)列，這時(shí)線程2再循環(huán)一次獲取tail践盼，由于tail是volatile的鸦采，所以對(duì)線程2可見(jiàn)，線程2看見(jiàn)tail不為null咕幻，就走到了7行的else里面去往尾Node后面添加自身渔伯。整個(gè)過(guò)程下來(lái)，形成了一個(gè)雙向隊(duì)列肄程。最后走AQS的acquireQueued(node, 1)：

1.final boolean acquireQueued(final Node node, int arg) {
2.   boolean failed = true;
3.    try {
4.        boolean interrupted = false;
5.        for (;;) {
6.            final Node p = node.predecessor();
7.            if (p == head && tryAcquire(arg)) {
8.                setHead(node);
9.                p.next = null; // help GC
10.                failed = false;
11.                return interrupted;
12.            }
13.            if (shouldParkAfterFailedAcquire(p, node) &&
14.                parkAndCheckInterrupt())
15.                interrupted = true;
16.        }
17.    } finally {
18.        if (failed)
19.            cancelAcquire(node);
20.    }
21.}

??此時(shí)再做判斷锣吼，由于線程2是雙向隊(duì)列的真正的第一個(gè)Node（前面還有一個(gè)h），所以第5行~第11行再次判斷一下線程2能不能獲取鎖（可能這段時(shí)間內(nèi)線程1已經(jīng)執(zhí)行完了把鎖釋放了绷耍，state從1變?yōu)榱?），如果還是不行鲜侥，先調(diào)用AQS的shouldParkAfterFailedAcquire(p, node)方法：

1.private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
2.    int ws = pred.waitStatus;
3.    if (ws == Node.SIGNAL)
4.        /*
5.         * This node has already set status asking a release
6.         * to signal it, so it can safely park.
7.         */
9.        return true;
10.    if (ws > 0) {
11.        /*
12.         * Predecessor was cancelled. Skip over predecessors and
13.         * indicate retry.
14.         */
15.        do {
16.            node.prev = pred = pred.prev;
17.        } while (pred.waitStatus > 0);
18.        pred.next = node;
19.    } else {
20.        /*
21.         * waitStatus must be 0 or PROPAGATE.  Indicate that we
22.         * need a signal, but don't park yet.  Caller will need to
23.         * retry to make sure it cannot acquire before parking.
24.         */
25.        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
26.    }
27.    return false;
28.}

??這個(gè)waitStatus是h的waitStatus褂始，很明顯是0，所以此時(shí)把h的waitStatus設(shè)置為Noed.SIGNAL即-1并返回false描函。既然返回了false崎苗，上面的acquireQueued的13行if自然不成立狐粱，再走一次for循環(huán)，還是先嘗試獲取鎖胆数，不成功肌蜻，繼續(xù)走shouldParkAfterFailedAcquire，此時(shí)waitStatus為-1必尼，走第3行的判斷蒋搜，返回true。然后走acquireQueued的13行if的第二個(gè)判斷條件parkAndCheckInterrupt：

private final boolean parkAndCheckInterrupt() {
    LockSupport.park(this);
    return Thread.interrupted();
}

public static void park(Object blocker) {
    Thread t = Thread.currentThread();
    setBlocker(t, blocker);
    UNSAFE.park(false, 0L);
    setBlocker(t, null);
}

??最后一步判莉，調(diào)用LockSupport（阻塞原語(yǔ)）的park方法阻塞住了當(dāng)前的線程豆挽。至此，使用ReentrantLock讓線程1獨(dú)占鎖券盅、線程2進(jìn)入FIFO隊(duì)列并阻塞的完整流程已經(jīng)整理出來(lái)了帮哈。

lock()的操作明了之后，就要探究一下unlock()的時(shí)候代碼又做了什么了锰镀，接著看下一部分娘侍。

unlock的實(shí)現(xiàn)原理

就不畫(huà)流程圖了，直接看一下代碼流程泳炉，比較簡(jiǎn)單憾筏，調(diào)用ReentrantLock的unlock方法：

public void unlock() {
    sync.release(1);
}

走AQS的release：

1.public final boolean release(int arg) {
2.    if (tryRelease(arg)) {
3.        Node h = head;
4.        if (h != null && h.waitStatus != 0)
5.            unparkSuccessor(h);
6.        return true;
7.    }
8.    return false;
9.}

先調(diào)用Sync的tryRelease嘗試釋放鎖：

protected final boolean tryRelease(int releases) {
        int c = getState() - releases;
        if (Thread.currentThread() != getExclusiveOwnerThread())
            throw new IllegalMonitorStateException();
        boolean free = false;
        if (c == 0) {
            free = true;
            setExclusiveOwnerThread(null);
        }
        setState(c);
        return free;
    }

??首先，只有當(dāng)c==0的時(shí)候才會(huì)讓free=true胡桃，這和上面一個(gè)線程多次調(diào)用lock方法累加state是對(duì)應(yīng)的踩叭，調(diào)用了多少次的lock()方法自然必須調(diào)用同樣次數(shù)的unlock()方法才行，這樣才把一個(gè)鎖給全部解開(kāi)翠胰。

??當(dāng)一條線程對(duì)同一個(gè)ReentrantLock全部解鎖之后容贝，AQS的state自然就是0了，AbstractOwnableSynchronizer的exclusiveOwnerThread將被設(shè)置為null之景，這樣就表示沒(méi)有線程占有鎖斤富，方法返回true。代碼繼續(xù)往下走锻狗，上面的release方法的第4行满力，h不為null成立，h的waitStatus為-1轻纪，不等于0也成立油额，所以走第5行的unparkSuccessor方法：

1.private void unparkSuccessor(Node node) {
2.    int ws = node.waitStatus;
3.    if (ws < 0)
4.        compareAndSetWaitStatus(node, ws, 0);
5.    Node s = node.next;
6.    if (s == null || s.waitStatus > 0) {
7.        s = null;
8.        for (Node t = tail; t != null && t != node; t = t.prev)
9.            if (t.waitStatus <= 0)
10.                s = t;
11.    }
12.    if (s != null)
13.        LockSupport.unpark(s.thread);
14.}

??s即h的下一個(gè)Node，這個(gè)Node里面的線程就是線程2刻帚，由于這個(gè)Node不等于null潦嘶，所以走12行，線程2被unPark了崇众，得以運(yùn)行掂僵。有一個(gè)很重要的問(wèn)題是：鎖被解了怎樣保證整個(gè)FIFO隊(duì)列減少一個(gè)Node呢航厚？這是一個(gè)很巧妙的設(shè)計(jì)，又回到了AQS的acquireQueued方法了：

1.final boolean acquireQueued(final Node node, int arg) {
2.   boolean failed = true;
3.    try {
4.        boolean interrupted = false;
5.        for (;;) {
6.            final Node p = node.predecessor();
7.            if (p == head && tryAcquire(arg)) {
8.                setHead(node);
9.                p.next = null; // help GC
10.                failed = false;
11.                return interrupted;
12.            }
13.            if (shouldParkAfterFailedAcquire(p, node) &&
14.                parkAndCheckInterrupt())
15.                interrupted = true;
16.        }
17.    } finally {
18.        if (failed)
19.            cancelAcquire(node);
20.    }
21.}

??<font color=red>被阻塞的線程2是被阻塞在第14行锰蓬，注意這里并沒(méi)有return語(yǔ)句幔睬，也就是說(shuō)，阻塞完成線程2依然會(huì)進(jìn)行for循環(huán)芹扭。</font>然后麻顶，阻塞完成了，線程2所在的Node的前驅(qū)Node是p冯勉，線程2嘗試tryAcquire澈蚌，成功，然后線程2就成為了head節(jié)點(diǎn)了灼狰，把p的next設(shè)置為null宛瞄，這樣原頭Node里面的所有對(duì)象都不指向任何塊內(nèi)存空間，h屬于棧內(nèi)存的內(nèi)容交胚，方法結(jié)束被自動(dòng)回收份汗，這樣隨著方法的調(diào)用完畢，原頭Node也沒(méi)有任何的引用指向它了蝴簇，這樣它就被GC自動(dòng)回收了杯活。此時(shí)，遇到一個(gè)return語(yǔ)句熬词，acquireQueued方法結(jié)束旁钧，后面的Node也是一樣的原理。

這里有一個(gè)細(xì)節(jié)互拾，看一下setHead方法：

private void setHead(Node node) {
    head = node;
    node.thread = null;
    node.prev = null;
}

??setHead方法里面的前驅(qū)Node是Null歪今，也沒(méi)有線程，那么為什么不用一個(gè)在等待的線程作為Head Node呢颜矿？

??因?yàn)橐粋€(gè)線程隨時(shí)有可能因?yàn)橹袛喽∠男桑∠脑挘琋ode自然就要被GC了骑疆，那GC前必然要把頭Node的后繼Node變?yōu)橐粋€(gè)新的頭而且要應(yīng)對(duì)多種情況田篇，這樣就很麻煩。用一個(gè)沒(méi)有thread的Node作為頭箍铭，相當(dāng)于起了一個(gè)引導(dǎo)作用泊柬，因?yàn)閔ead沒(méi)有線程，自然也不會(huì)被取消诈火。

??再看一下上面unparkSuccessor的5行~10行兽赁，就是為了防止head的下一個(gè)node被取消的情況，這樣，就從尾到頭遍歷闸氮，找出離head最近的一個(gè)node，對(duì)這個(gè)node進(jìn)行unPark操作教沾。

ReentrantLock其他方法的實(shí)現(xiàn)

??如果能理解ReentrantLock的實(shí)現(xiàn)方式蒲跨，那么你會(huì)發(fā)現(xiàn)ReentrantLock中其余一些方法的實(shí)現(xiàn)還是很簡(jiǎn)單的，從JDK API關(guān)于ReentrantLock方法的介紹這部分授翻，舉幾個(gè)例子：

• 1或悲、int getHoldCount()

final int getHoldCount() {
    return isHeldExclusively() ? getState() : 0;
}

獲取ReentrantLock的lock()方法被調(diào)用了幾次，就是state的當(dāng)前值

• 2堪唐、Thread getOwner()

final Thread getOwner() {
    return getState() == 0 ? null : getExclusiveOwnerThread();
}

獲取當(dāng)前占有鎖的線程巡语，就是AbstractOwnableSynchronizer中exclusiveOwnerThread的值

• 3、Collection<Thread> getQueuedThreads()

public final Collection<Thread> getQueuedThreads() {
    ArrayList<Thread> list = new ArrayList<Thread>();
    for (Node p = tail; p != null; p = p.prev) {
        Thread t = p.thread;
        if (t != null)
            list.add(t);
    }
    return list;
}

從尾到頭遍歷一下淮菠，添加進(jìn)ArrayList中

• 4男公、int getQueuedLength()

public final int getQueueLength() {
    int n = 0;
    for (Node p = tail; p != null; p = p.prev) {
        if (p.thread != null)
            ++n;
    }
    return n;
}

??從尾到頭遍歷一下，累加n合陵。當(dāng)然這個(gè)方法和上面那個(gè)方法可能是不準(zhǔn)確的枢赔，因?yàn)楸闅v的時(shí)候可能別的線程又往隊(duì)列尾部添加了Node。

??其余方法也都差不多拥知，可以自己去看一下踏拜。

小結(jié)

??本文從源碼分析了ReentrantLock的非公平加鎖和釋放鎖的原理，通過(guò)源碼我們得知ReentrantLock的基石是AQS低剔，AQS的基石是Node速梗，多線程競(jìng)爭(zhēng)鎖時(shí)通過(guò)自旋方式等待資源，通過(guò)Unsafe提供的compareAndSwapObject方法達(dá)到多線程競(jìng)爭(zhēng)鎖時(shí)只有一個(gè)線程可以獲取鎖的效果襟齿，從而實(shí)現(xiàn)了線程安全姻锁。
??翻看了一下公平加鎖的源碼，每次在獲取鎖時(shí)都去檢查FIFO隊(duì)列是否已經(jīng)有等待線程蕊唐，如果有就把自己追加到FIFO隊(duì)列的末尾屋摔，而非公平加鎖則是每次都先去嘗試獲取鎖，獲取不到再加入到FIFO隊(duì)列替梨。
??另外本文代碼并非照搬原博主的代碼钓试，而是在jdk8的源碼基礎(chǔ)上復(fù)制過(guò)來(lái)的，與原博主貼的代碼有稍許偏差副瀑，不過(guò)核心實(shí)現(xiàn)是一致的弓熏。