ReentrantLock可以有公平鎖和非公平鎖的不同實(shí)現(xiàn),只要在構(gòu)造它的時(shí)候傳入不同的布爾值,繼續(xù)跟進(jìn)下源碼我們就能發(fā)現(xiàn),關(guān)鍵在于實(shí)例化內(nèi)部變量sync的方式不同,如下所示

/**
 * Creates an instance of {@code ReentrantLock} with the
 * given fairness policy.
 *
 * @param fair {@code true} if this lock should use a fair ordering policy
 */
public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}

公平鎖內(nèi)部是FairSync,非公平鎖內(nèi)部是NonfairSync膘掰。而不管是FairSync還是NonfariSync,都間接繼承自AbstractQueuedSynchronizer這個(gè)抽象類昔逗，如下圖所示

• NonfairSync的類繼承關(guān)系

  
  
  image

• FairSync的類繼承關(guān)系

  
  
  image

該抽象類為我們的加鎖和解鎖過程提供了統(tǒng)一的模板方法冻河，只是一些細(xì)節(jié)的處理由該抽象類的實(shí)現(xiàn)類自己決定。所以在解讀ReentrantLock(重入鎖)的源碼之前,有必要了解下AbstractQueuedSynchronizer狰腌。

2.AbstractQueuedSynchronizer介紹

2.1 AQS是構(gòu)建同步組件的基礎(chǔ)

AbstractQueuedSynchronizer,簡(jiǎn)稱AQS,為構(gòu)建不同的同步組件(重入鎖,讀寫鎖,CountDownLatch等)提供了可擴(kuò)展的基礎(chǔ)框架,如下圖所示。

image

AQS以模板方法模式在內(nèi)部定義了獲取和釋放同步狀態(tài)的模板方法,并留下鉤子函數(shù)供子類繼承時(shí)進(jìn)行擴(kuò)展,由子類決定在獲取和釋放同步狀態(tài)時(shí)的細(xì)節(jié),從而實(shí)現(xiàn)滿足自身功能特性的需求轮听。除此之外,AQS通過內(nèi)部的同步隊(duì)列管理獲取同步狀態(tài)失敗的線程,向?qū)崿F(xiàn)者屏蔽了線程阻塞和喚醒的細(xì)節(jié)笋鄙。

2.2 AQS的內(nèi)部結(jié)構(gòu)(ReentrantLock的語境下)

AQS的內(nèi)部結(jié)構(gòu)主要由同步等待隊(duì)列構(gòu)成

2.2.1 同步等待隊(duì)列

AQS中同步等待隊(duì)列的實(shí)現(xiàn)是一個(gè)帶頭尾指針(這里用指針表示引用是為了后面講解源碼時(shí)可以更直觀形象,況且引用本身是一種受限的指針)且不帶哨兵結(jié)點(diǎn)(后文中的頭結(jié)點(diǎn)表示隊(duì)列首元素結(jié)點(diǎn),不是指哨兵結(jié)點(diǎn))的雙向鏈表。

/**
 * Head of the wait queue, lazily initialized.  Except for
 * initialization, it is modified only via method setHead.  Note:
 * If head exists, its waitStatus is guaranteed not to be
 * CANCELLED.
 */
private transient volatile Node head;//指向隊(duì)列首元素的頭指針

/**
 * Tail of the wait queue, lazily initialized.  Modified only via
 * method enq to add new wait node.
 */
private transient volatile Node tail;//指向隊(duì)列尾元素的尾指針

head是頭指針,指向隊(duì)列的首元素;tail是尾指針,指向隊(duì)列的尾元素互拾。而隊(duì)列的元素結(jié)點(diǎn)Node定義在AQS內(nèi)部,主要有如下幾個(gè)成員變量

volatile Node prev; //指向前一個(gè)結(jié)點(diǎn)的指針

volatile Node next; //指向后一個(gè)結(jié)點(diǎn)的指針
volatile Thread thread; //當(dāng)前結(jié)點(diǎn)代表的線程
volatile int waitStatus; //等待狀態(tài)

• prev:指向前一個(gè)結(jié)點(diǎn)的指針
• next:指向后一個(gè)結(jié)點(diǎn)的指針
• thread:當(dāng)前結(jié)點(diǎn)表示的線程,因?yàn)橥疥?duì)列中的結(jié)點(diǎn)內(nèi)部封裝了之前競(jìng)爭(zhēng)鎖失敗的線程,故而結(jié)點(diǎn)內(nèi)部必然有一個(gè)對(duì)應(yīng)線程實(shí)例的引用
• waitStatus:對(duì)于重入鎖而言,主要有3個(gè)值歪今。0:初始化狀態(tài)；-1(SIGNAL):當(dāng)前結(jié)點(diǎn)表示的線程在釋放鎖后需要喚醒后續(xù)節(jié)點(diǎn)的線程;1(CANCELLED):在同步隊(duì)列中等待的線程等待超時(shí)或者被中斷,取消繼續(xù)等待颜矿。

同步隊(duì)列的結(jié)構(gòu)如下圖所示

image

為了接下來能夠更好的理解加鎖和解鎖過程的源碼,對(duì)該同步隊(duì)列的特性進(jìn)行簡(jiǎn)單的講解:

• 1.同步隊(duì)列是個(gè)先進(jìn)先出(FIFO)隊(duì)列,獲取鎖失敗的線程將構(gòu)造結(jié)點(diǎn)并加入隊(duì)列的尾部,并阻塞自己寄猩。如何才能線程安全的實(shí)現(xiàn)入隊(duì)是后面講解的重點(diǎn),畢竟我們?cè)谥v鎖的實(shí)現(xiàn),這部分代碼肯定是不能用鎖的。
• 2.隊(duì)列首結(jié)點(diǎn)可以用來表示當(dāng)前正獲取鎖的線程骑疆。
• 3.當(dāng)前線程釋放鎖后將嘗試喚醒后續(xù)處結(jié)點(diǎn)中處于阻塞狀態(tài)的線程田篇。

為了加深理解,還可以在閱讀源碼的過程中思考下這個(gè)問題：

這個(gè)同步隊(duì)列是FIFO隊(duì)列,也就是說先在隊(duì)列中等待的線程將比后面的線程更早的得到鎖,那ReentrantLock是如何基于這個(gè)FIFO隊(duì)列實(shí)現(xiàn)非公平鎖的？

2.2.2 AQS中的其他數(shù)據(jù)結(jié)構(gòu)(ReentrantLock的語境下)

• 同步狀態(tài)變量

/**
 * The synchronization state.
 */
private volatile int state;

這是一個(gè)帶volatile前綴的int值,是一個(gè)類似計(jì)數(shù)器的東西箍铭。在不同的同步組件中有不同的含義泊柬。以ReentrantLock為例,state可以用來表示該鎖被線程重入的次數(shù)。當(dāng)state為0表示該鎖不被任何線程持有;當(dāng)state為1表示線程恰好持有該鎖1次(未重入);當(dāng)state大于1則表示鎖被線程重入state次诈火。因?yàn)檫@是一個(gè)會(huì)被并發(fā)訪問的量,為了防止出現(xiàn)可見性問題要用volatile進(jìn)行修飾兽赁。

• 持有同步狀態(tài)的線程標(biāo)志

/**
 * The current owner of exclusive mode synchronization.
 */
private transient Thread exclusiveOwnerThread;

如注釋所言,這是在獨(dú)占同步模式下標(biāo)記持有同步狀態(tài)線程的。ReentrantLock就是典型的獨(dú)占同步模式,該變量用來標(biāo)識(shí)鎖被哪個(gè)線程持有冷守。

了解AQS的主要結(jié)構(gòu)后,就可以開始進(jìn)行ReentrantLock的源碼解讀了刀崖。由于非公平鎖在實(shí)際開發(fā)中用的比較多,故以講解非公平鎖的源碼為主。以下面這段對(duì)非公平鎖使用的代碼為例:

/**
 * @author: takumiCX
 * @create: 2018-08-01
 **/
public class NoFairLockTest {

    public static void main(String[] args) {

        //創(chuàng)建非公平鎖
        ReentrantLock lock = new ReentrantLock(false);

        try {

            //加鎖
            lock.lock();

            //模擬業(yè)務(wù)處理用時(shí)
            TimeUnit.SECONDS.sleep(1);

        } catch (InterruptedException e) {
            e.printStackTrace();

        } finally {
            //釋放鎖
            lock.unlock();
        }

    }
}

3 非公平模式加鎖流程

加鎖流程從lock.lock()開始

public void lock() {
    sync.lock();
}

進(jìn)入該源碼,正確找到sycn的實(shí)現(xiàn)類后可以看到真正有內(nèi)容的入口方法

3.1加鎖流程真正意義上的入口

/**
 * Performs lock.  Try immediate barge, backing up to normal
 * acquire on failure.
 */
//加鎖流程真正意義上的入口
final void lock() {
    //以cas方式嘗試將AQS中的state從0更新為1
    if (compareAndSetState(0, 1))
        setExclusiveOwnerThread(Thread.currentThread());//獲取鎖成功則將當(dāng)前線程標(biāo)記為持有鎖的線程,然后直接返回
    else
        acquire(1);//獲取鎖失敗則執(zhí)行該方法
}

首先嘗試快速獲取鎖,以cas的方式將state的值更新為1,只有當(dāng)state的原值為0時(shí)更新才能成功,因?yàn)閟tate在ReentrantLock的語境下等同于鎖被線程重入的次數(shù),這意味著只有當(dāng)前鎖未被任何線程持有時(shí)該動(dòng)作才會(huì)返回成功教沾。若獲取鎖成功,則將當(dāng)前線程標(biāo)記為持有鎖的線程,然后整個(gè)加鎖流程就結(jié)束了蒲跨。若獲取鎖失敗,則執(zhí)行acquire方法

/**
 * Acquires in exclusive mode, ignoring interrupts.  Implemented
 * by invoking at least once {@link #tryAcquire},
 * returning on success.  Otherwise the thread is queued, possibly
 * repeatedly blocking and unblocking, invoking {@link
 * #tryAcquire} until success.  This method can be used
 * to implement method {@link Lock#lock}.
 *
 * @param arg the acquire argument.  This value is conveyed to
 *        {@link #tryAcquire} but is otherwise uninterpreted and
 *        can represent anything you like.
 */
public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
        selfInterrupt();
}

該方法主要的邏輯都在if判斷條件中,這里面有3個(gè)重要的方法tryAcquire()，addWaiter()和acquireQueued()授翻，這三個(gè)方法中分別封裝了加鎖流程中的主要處理邏輯或悲，理解了這三個(gè)方法到底做了哪些事情，整個(gè)加鎖流程就清晰了堪唐。

3.2 嘗試獲取鎖的通用方法:tryAcquire()

tryAcquire是AQS中定義的鉤子方法,如下所示

protected boolean tryAcquire(int arg) {
    throw new UnsupportedOperationException();
}

該方法默認(rèn)會(huì)拋出異常,強(qiáng)制同步組件通過擴(kuò)展AQS來實(shí)現(xiàn)同步功能的時(shí)候必須重寫該方法,ReentrantLock在公平和非公平模式下對(duì)此有不同實(shí)現(xiàn),非公平模式的實(shí)現(xiàn)如下：

protected final boolean tryAcquire(int acquires) {
    return nonfairTryAcquire(acquires);
}

底層調(diào)用了nonfairTryAcquire()
從方法名上我們就可以知道這是非公平模式下嘗試獲取鎖的方法,具體方法實(shí)現(xiàn)如下

/**
 * Performs non-fair tryLock.  tryAcquire is implemented in
 * subclasses, but both need nonfair try for trylock method.
 */
final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();//獲取當(dāng)前線程實(shí)例
    int c = getState();//獲取state變量的值,即當(dāng)前鎖被重入的次數(shù)
    if (c == 0) {   //state為0,說明當(dāng)前鎖未被任何線程持有
        if (compareAndSetState(0, acquires)) { //以cas方式獲取鎖
            setExclusiveOwnerThread(current);  //將當(dāng)前線程標(biāo)記為持有鎖的線程
            return true;//獲取鎖成功,非重入
        }
    }
    else if (current == getExclusiveOwnerThread()) { //當(dāng)前線程就是持有鎖的線程,說明該鎖被重入了
        int nextc = c + acquires;//計(jì)算state變量要更新的值
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);//非同步方式更新state值
        return true;  //獲取鎖成功,重入
    }
    return false;     //走到這里說明嘗試獲取鎖失敗
}

這是非公平模式下獲取鎖的通用方法巡语。它囊括了當(dāng)前線程在嘗試獲取鎖時(shí)的所有可能情況：

• 1.當(dāng)前鎖未被任何線程持有(state=0),則以cas方式獲取鎖,若獲取成功則設(shè)置exclusiveOwnerThread為當(dāng)前線程,然后返回成功的結(jié)果；若cas失敗,說明在得到state=0和cas獲取鎖之間有其他線程已經(jīng)獲取了鎖,返回失敗結(jié)果淮菠。
• 2.若鎖已經(jīng)被當(dāng)前線程獲取(state>0,exclusiveOwnerThread為當(dāng)前線程),則將鎖的重入次數(shù)加1(state+1),然后返回成功結(jié)果男公。因?yàn)樵摼€程之前已經(jīng)獲得了鎖,所以這個(gè)累加操作不用同步。
• 3.若當(dāng)前鎖已經(jīng)被其他線程持有(state>0,exclusiveOwnerThread不為當(dāng)前線程),則直接返回失敗結(jié)果

因?yàn)槲覀冇胹tate來統(tǒng)計(jì)鎖被線程重入的次數(shù),所以當(dāng)前線程嘗試獲取鎖的操作是否成功可以簡(jiǎn)化為:state值是否成功累加1,是則嘗試獲取鎖成功,否則嘗試獲取鎖失敗合陵。

其實(shí)這里還可以思考一個(gè)問題:nonfairTryAcquire已經(jīng)實(shí)現(xiàn)了一個(gè)囊括所有可能情況的嘗試獲取鎖的方式,為何在剛進(jìn)入lock方法時(shí)還要通過compareAndSetState(0, 1)去獲取鎖,畢竟后者只有在鎖未被任何線程持有時(shí)才能執(zhí)行成功,我們完全可以把compareAndSetState(0, 1)去掉,對(duì)最后的結(jié)果不會(huì)有任何影響枢赔。這種在進(jìn)行通用邏輯處理之前針對(duì)某些特殊情況提前進(jìn)行處理的方式在后面還會(huì)看到,一個(gè)直觀的想法就是它能提升性能澄阳，而代價(jià)是犧牲一定的代碼簡(jiǎn)潔性。

退回到上層的acquire方法,

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&  //當(dāng)前線程嘗試獲取鎖,若獲取成功返回true,否則false
        acquireQueued(addWaiter(Node.EXCLUSIVE), arg))  //只有當(dāng)前線程獲取鎖失敗才會(huì)執(zhí)行者這部分代碼
        selfInterrupt();
}

tryAcquire(arg)返回成功,則說明當(dāng)前線程成功獲取了鎖(第一次獲取或者重入),由取反和&&可知,整個(gè)流程到這結(jié)束踏拜，只有當(dāng)前線程獲取鎖失敗才會(huì)執(zhí)行后面的判斷碎赢。先來看addWaiter(Node.EXCLUSIVE)
部分,這部分代碼描述了當(dāng)線程獲取鎖失敗時(shí)如何安全的加入同步等待隊(duì)列。這部分代碼可以說是整個(gè)加鎖流程源碼的精華,充分體現(xiàn)了并發(fā)編程的藝術(shù)性速梗。

3.3 獲取鎖失敗的線程如何安全的加入同步隊(duì)列:addWaiter()

這部分邏輯在addWaiter()方法中

/**
 * Creates and enqueues node for current thread and given mode.
 *
 * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
 * @return the new node
 */
private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);//首先創(chuàng)建一個(gè)新節(jié)點(diǎn),并將當(dāng)前線程實(shí)例封裝在內(nèi)部,mode這里為null
    // 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);//入隊(duì)的邏輯這里都有
    return node;
}

首先創(chuàng)建了一個(gè)新節(jié)點(diǎn),并將當(dāng)前線程實(shí)例封裝在其內(nèi)部,之后我們直接看enq(node)方法就可以了,中間這部分邏輯在enq(node)中都有,之所以加上這部分“重復(fù)代碼”和嘗試獲取鎖時(shí)的“重復(fù)代碼”一樣,對(duì)某些特殊情況
進(jìn)行提前處理,犧牲一定的代碼可讀性換取性能提升肮塞。

/**
 * Inserts node into queue, initializing if necessary. See picture above.
 * @param node the node to insert
 * @return node's predecessor
 */
private Node enq(final Node node) {
    for (;;) {
        Node t = tail;//t指向當(dāng)前隊(duì)列的最后一個(gè)節(jié)點(diǎn),隊(duì)列為空則為null
        if (t == null) { // Must initialize  //隊(duì)列為空
            if (compareAndSetHead(new Node())) //構(gòu)造新結(jié)點(diǎn),CAS方式設(shè)置為隊(duì)列首元素,當(dāng)head==null時(shí)更新成功
                tail = head;//尾指針指向首結(jié)點(diǎn)
        } else {  //隊(duì)列不為空
            node.prev = t;
            if (compareAndSetTail(t, node)) { //CAS將尾指針指向當(dāng)前結(jié)點(diǎn),當(dāng)t(原來的尾指針)==tail(當(dāng)前真實(shí)的尾指針)時(shí)執(zhí)行成功
                t.next = node;    //原尾結(jié)點(diǎn)的next指針指向當(dāng)前結(jié)點(diǎn)
                return t;
            }
        }
    }
}

這里有兩個(gè)CAS操作:

• compareAndSetHead(new Node()),CAS方式更新head指針,僅當(dāng)原值為null時(shí)更新成功

/**
 * CAS head field. Used only by enq.
 */
private final boolean compareAndSetHead(Node update) {
    return unsafe.compareAndSwapObject(this, headOffset, null, update);
}

• compareAndSetTail(t, node),CAS方式更新tial指針,僅當(dāng)原值為t時(shí)更新成功

/**
 * CAS tail field. Used only by enq.
 */
private final boolean compareAndSetTail(Node expect, Node update) {
    return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
}

外層的for循環(huán)保證了所有獲取鎖失敗的線程經(jīng)過失敗重試后最后都能加入同步隊(duì)列。因?yàn)锳QS的同步隊(duì)列是不帶哨兵結(jié)點(diǎn)的,故當(dāng)隊(duì)列為空時(shí)要進(jìn)行特殊處理,這部分在if分句中姻锁。注意當(dāng)前線程所在的結(jié)點(diǎn)不能直接插入
空隊(duì)列,因?yàn)樽枞木€程是由前驅(qū)結(jié)點(diǎn)進(jìn)行喚醒的枕赵。故先要插入一個(gè)結(jié)點(diǎn)作為隊(duì)列首元素,當(dāng)鎖釋放時(shí)由它來喚醒后面被阻塞的線程,從邏輯上這個(gè)隊(duì)列首元素也可以表示當(dāng)前正獲取鎖的線程,雖然并不一定真實(shí)持有其線程實(shí)例。

首先通過new Node()創(chuàng)建一個(gè)空結(jié)點(diǎn)位隶，然后以CAS方式讓頭指針指向該結(jié)點(diǎn)(該結(jié)點(diǎn)并非當(dāng)前線程所在的結(jié)點(diǎn)),若該操作成功,則將尾指針也指向該結(jié)點(diǎn)拷窜。這部分的操作流程可以用下圖表示

image

當(dāng)隊(duì)列不為空,則執(zhí)行通用的入隊(duì)邏輯,這部分在else分句中

else {
            node.prev = t;//step1:待插入結(jié)點(diǎn)pre指針指向原尾結(jié)點(diǎn)
            if (compareAndSetTail(t, node)) { step2:CAS方式更改尾指針
                t.next = node; //原尾結(jié)點(diǎn)next指針指向新的結(jié)點(diǎn)
                return t;
            }
        }

首先當(dāng)前線程所在的結(jié)點(diǎn)的前向指針pre指向當(dāng)前線程認(rèn)為的尾結(jié)點(diǎn),源碼中用t表示。然后以CAS的方式將尾指針指向當(dāng)前結(jié)點(diǎn),該操作僅當(dāng)tail=t,即尾指針在進(jìn)行CAS前未改變時(shí)成功钓试。若CAS執(zhí)行成功,則將原尾結(jié)點(diǎn)的后向指針next指向新的尾結(jié)點(diǎn)装黑。整個(gè)過程如下圖所示

image

整個(gè)入隊(duì)的過程并不復(fù)雜,是典型的CAS加失敗重試的樂觀鎖策略副瀑。其中只有更新頭指針和更新尾指針這兩步進(jìn)行了CAS同步,可以預(yù)見高并發(fā)場(chǎng)景下性能是非常好的弓熏。但是本著質(zhì)疑精神我們不禁會(huì)思考下這么做真的線程安全嗎？

image

• 1.隊(duì)列為空的情況:
  因?yàn)殛?duì)列為空,故head=tail=null,假設(shè)線程執(zhí)行2成功,則在其執(zhí)行3之前,因?yàn)閠ail=null,其他進(jìn)入該方法的線程因?yàn)閔ead不為null將在2處不停的失敗,所以3即使沒有同步也不會(huì)有線程安全問題糠睡。
• 2.隊(duì)列不為空的情況:
  假設(shè)線程執(zhí)行5成功,則此時(shí)4的操作必然也是正確的(當(dāng)前結(jié)點(diǎn)的prev指針確實(shí)指向了隊(duì)列尾結(jié)點(diǎn),換句話說tail指針沒有改變,如若不然5必然執(zhí)行失敗),又因?yàn)?執(zhí)行成功,當(dāng)前節(jié)點(diǎn)在隊(duì)列中的次序已經(jīng)確定了,所以6何時(shí)執(zhí)行對(duì)線程安全不會(huì)有任何影響,比如下面這種情況

image

為了確保真的理解了它,可以思考這個(gè)問題:把enq方法圖中的4放到5之后,整個(gè)入隊(duì)的過程還線程安全嗎挽鞠？

到這為止,獲取鎖失敗的線程加入同步隊(duì)列的邏輯就結(jié)束了知染。但是線程加入同步隊(duì)列后會(huì)做什么我們并不清楚,這部分在acquireQueued方法中

3.4 線程加入同步隊(duì)列后會(huì)做什么:acquireQueued()

先看acquireQueued方法的源碼

/**
 * Acquires in exclusive uninterruptible mode for thread already in
 * queue. Used by condition wait methods as well as acquire.
 *
 * @param node the node
 * @param arg the acquire argument
 * @return {@code true} if interrupted while waiting
 */
final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        //死循環(huán),正常情況下線程只有獲得鎖才能跳出循環(huán)
        for (;;) {
            final Node p = node.predecessor();//獲得當(dāng)前線程所在結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
            //第一個(gè)if分句
            if (p == head && tryAcquire(arg)) { 
                setHead(node); //將當(dāng)前結(jié)點(diǎn)設(shè)置為隊(duì)列頭結(jié)點(diǎn)
                p.next = null; // help GC
                failed = false;
                return interrupted;//正常情況下死循環(huán)唯一的出口
            }
            //第二個(gè)if分句
            if (shouldParkAfterFailedAcquire(p, node) &&  //判斷是否要阻塞當(dāng)前線程
                parkAndCheckInterrupt())      //阻塞當(dāng)前線程
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

這段代碼主要的內(nèi)容都在for循環(huán)中,這是一個(gè)死循環(huán),主要有兩個(gè)if分句構(gòu)成郁妈。第一個(gè)if分句中,當(dāng)前線程首先會(huì)判斷前驅(qū)結(jié)點(diǎn)是否是頭結(jié)點(diǎn),如果是則嘗試獲取鎖,獲取鎖成功則會(huì)設(shè)置當(dāng)前結(jié)點(diǎn)為頭結(jié)點(diǎn)(更新頭指針)喧锦。為什么必須前驅(qū)結(jié)點(diǎn)為頭結(jié)點(diǎn)才嘗試去獲取鎖乞封？因?yàn)轭^結(jié)點(diǎn)表示當(dāng)前正占有鎖的線程,正常情況下該線程釋放鎖后會(huì)通知后面結(jié)點(diǎn)中阻塞的線程,阻塞線程被喚醒后去獲取鎖,這是我們希望看到的校仑。然而還有一種情況,就是前驅(qū)結(jié)點(diǎn)取消了等待,此時(shí)當(dāng)前線程也會(huì)被喚醒,這時(shí)候就不應(yīng)該去獲取鎖,而是往前回溯一直找到一個(gè)沒有取消等待的結(jié)點(diǎn),然后將自身連接在它后面尚洽。一旦我們成功獲取了鎖并成功將自身設(shè)置為頭結(jié)點(diǎn),就會(huì)跳出for循環(huán)磨隘。否則就會(huì)執(zhí)行第二個(gè)if分句:確保前驅(qū)結(jié)點(diǎn)的狀態(tài)為SIGNAL,然后阻塞當(dāng)前線程脖隶。

先來看shouldParkAfterFailedAcquire(p, node)油挥，從方法名上我們可以大概猜出這是判斷是否要阻塞當(dāng)前線程的,方法內(nèi)容如下

/**
 * Checks and updates status for a node that failed to acquire.
 * Returns true if thread should block. This is the main signal
 * control in all acquire loops.  Requires that pred == node.prev.
 *
 * @param pred node's predecessor holding status
 * @param node the node
 * @return {@code true} if thread should block
 */
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL) //狀態(tài)為SIGNAL

        /*
         * This node has already set status asking a release
         * to signal it, so it can safely park.
         */
        return true;
    if (ws > 0) { //狀態(tài)為CANCELLED,
        /*
         * Predecessor was cancelled. Skip over predecessors and
         * indicate retry.
         */
        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else { //狀態(tài)為初始化狀態(tài)(ReentrentLock語境下)
        /*
         * waitStatus must be 0 or PROPAGATE.  Indicate that we
         * need a signal, but don't park yet.  Caller will need to
         * retry to make sure it cannot acquire before parking.
         */
        compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
    }
    return false;
}

可以看到針對(duì)前驅(qū)結(jié)點(diǎn)pred的狀態(tài)會(huì)進(jìn)行不同的處理

• 1.pred狀態(tài)為SIGNAL,則返回true,表示要阻塞當(dāng)前線程潦蝇。
• 2.pred狀態(tài)為CANCELLED,則一直往隊(duì)列頭部回溯直到找到一個(gè)狀態(tài)不為CANCELLED的結(jié)點(diǎn),將當(dāng)前節(jié)點(diǎn)node掛在這個(gè)結(jié)點(diǎn)的后面。
• 3.pred的狀態(tài)為初始化狀態(tài),此時(shí)通過compareAndSetWaitStatus(pred, ws, Node.SIGNAL)方法將pred的狀態(tài)改為SIGNAL深寥。

其實(shí)這個(gè)方法的含義很簡(jiǎn)單,就是確保當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的狀態(tài)為SIGNAL,SIGNAL意味著線程釋放鎖后會(huì)喚醒后面阻塞的線程攘乒。畢竟,只有確保能夠被喚醒，當(dāng)前線程才能放心的阻塞惋鹅。

但是要注意只有在前驅(qū)結(jié)點(diǎn)已經(jīng)是SIGNAL狀態(tài)后才會(huì)執(zhí)行后面的方法立即阻塞,對(duì)應(yīng)上面的第一種情況则酝。其他兩種情況則因?yàn)榉祷豧alse而重新執(zhí)行一遍
for循環(huán)。這種延遲阻塞其實(shí)也是一種高并發(fā)場(chǎng)景下的優(yōu)化,試想我如果在重新執(zhí)行循環(huán)的時(shí)候成功獲取了鎖,是不是線程阻塞喚醒的開銷就省了呢闰集？

最后我們來看看阻塞線程的方法parkAndCheckInterrupt

shouldParkAfterFailedAcquire返回true表示應(yīng)該阻塞當(dāng)前線程,則會(huì)執(zhí)行parkAndCheckInterrupt方法,這個(gè)方法比較簡(jiǎn)單,底層調(diào)用了LockSupport來阻塞當(dāng)前線程,源碼如下:

/**
 * Convenience method to park and then check if interrupted
 *
 * @return {@code true} if interrupted
 */
private final boolean parkAndCheckInterrupt() {
    LockSupport.park(this);
    return Thread.interrupted();
}

該方法內(nèi)部通過調(diào)用LockSupport的park方法來阻塞當(dāng)前線程,不清楚LockSupport的可以看看這里沽讹。LockSupport功能簡(jiǎn)介及原理淺析

下面通過一張流程圖來說明線程從加入同步隊(duì)列到成功獲取鎖的過程

image

概括的說,線程在同步隊(duì)列中會(huì)嘗試獲取鎖,失敗則被阻塞,被喚醒后會(huì)不停的重復(fù)這個(gè)過程,直到線程真正持有了鎖,并將自身結(jié)點(diǎn)置于隊(duì)列頭部般卑。

3.5 加鎖流程源碼總結(jié)

ReentrantLock非公平模式下的加鎖流程如下

image

4.非公平模式解鎖流程

4.1 解鎖流程源碼解讀

解鎖的源碼相對(duì)簡(jiǎn)單,源碼如下：

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

public final boolean release(int arg) {
    if (tryRelease(arg)) { //釋放鎖(state-1),若釋放后鎖可被其他線程獲取(state=0),返回true
        Node h = head;
        //當(dāng)前隊(duì)列不為空且頭結(jié)點(diǎn)狀態(tài)不為初始化狀態(tài)(0)   
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);  //喚醒同步隊(duì)列中被阻塞的線程
        return true;
    }
    return false;
}

正確找到sync的實(shí)現(xiàn)類,找到真正的入口方法,主要內(nèi)容都在一個(gè)if語句中,先看下判斷條件tryRelease方法

protected final boolean tryRelease(int releases) {
    int c = getState() - releases; //計(jì)算待更新的state值
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) { //待更新的state值為0,說明持有鎖的線程未重入,一旦釋放鎖其他線程將能獲取
        free = true; 
        setExclusiveOwnerThread(null);//清除鎖的持有線程標(biāo)記
    }
    setState(c);//更新state值
    return free;
}

tryRelease其實(shí)只是將線程持有鎖的次數(shù)減1,即將state值減1,若減少后線程將完全釋放鎖(state值為0),則該方法將返回true,否則返回false。由于執(zhí)行該方法的線程必然持有鎖,故該方法不需要任何同步操作爽雄。
若當(dāng)前線程已經(jīng)完全釋放鎖,即鎖可被其他線程使用,則還應(yīng)該喚醒后續(xù)等待線程椭微。不過在此之前需要進(jìn)行兩個(gè)條件的判斷：

• h!=null是為了防止隊(duì)列為空,即沒有任何線程處于等待隊(duì)列中,那么也就不需要進(jìn)行喚醒的操作
• h.waitStatus != 0是為了防止隊(duì)列中雖有線程,但該線程還未阻塞,由前面的分析知,線程在阻塞自己前必須設(shè)置前驅(qū)結(jié)點(diǎn)的狀態(tài)為SIGNAL,否則它不會(huì)阻塞自己。

接下來就是喚醒線程的操作,unparkSuccessor(h)源碼如下

private void unparkSuccessor(Node node) {
    /*
     * If status is negative (i.e., possibly needing signal) try
     * to clear in anticipation of signalling.  It is OK if this
     * fails or if status is changed by waiting thread.
     */
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);

    /*
     * Thread to unpark is held in successor, which is normally
     * just the next node.  But if cancelled or apparently null,
     * traverse backwards from tail to find the actual
     * non-cancelled successor.
     */
    Node s = node.next;
    if (s == null || s.waitStatus > 0) {
        s = null;
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
    if (s != null)
        LockSupport.unpark(s.thread);
}

一般情況下只要喚醒后繼結(jié)點(diǎn)的線程就行了,但是后繼結(jié)點(diǎn)可能已經(jīng)取消等待,所以從隊(duì)列尾部往前回溯,找到離頭結(jié)點(diǎn)最近的正常結(jié)點(diǎn),并喚醒其線程盲链。

4.2 解鎖流程源碼總結(jié)

image

5. 公平鎖相比非公平鎖的不同

公平鎖模式下,對(duì)鎖的獲取有嚴(yán)格的條件限制蝇率。在同步隊(duì)列有線程等待的情況下,所有線程在獲取鎖前必須先加入同步隊(duì)列。隊(duì)列中的線程按加入隊(duì)列的先后次序獲得鎖刽沾。
從公平鎖加鎖的入口開始,

image

對(duì)比非公平鎖,少了非重入式獲取鎖的方法,這是第一個(gè)不同點(diǎn)

接著看獲取鎖的通用方法tryAcquire(),該方法在線程未進(jìn)入隊(duì)列,加入隊(duì)列阻塞前和阻塞后被喚醒時(shí)都會(huì)執(zhí)行本慕。

image

在真正CAS獲取鎖之前加了判斷,內(nèi)容如下

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

從方法名我們就可知道這是判斷隊(duì)列中是否有優(yōu)先級(jí)更高的等待線程,隊(duì)列中哪個(gè)線程優(yōu)先級(jí)最高？由于頭結(jié)點(diǎn)是當(dāng)前獲取鎖的線程,隊(duì)列中的第二個(gè)結(jié)點(diǎn)代表的線程優(yōu)先級(jí)最高侧漓。
那么我們只要判斷隊(duì)列中第二個(gè)結(jié)點(diǎn)是否存在以及這個(gè)結(jié)點(diǎn)是否代表當(dāng)前線程就行了锅尘。這里分了兩種情況進(jìn)行探討:

1. 第二個(gè)結(jié)點(diǎn)已經(jīng)完全插入,但是這個(gè)結(jié)點(diǎn)是否就是當(dāng)前線程所在結(jié)點(diǎn)還未知,所以通過s.thread != Thread.currentThread()進(jìn)行判斷,如果為true,說明第二個(gè)結(jié)點(diǎn)代表其他線程。
2. 第二個(gè)結(jié)點(diǎn)并未完全插入,我們知道結(jié)點(diǎn)入隊(duì)一共分三步：

• 1.待插入結(jié)點(diǎn)的pre指針指向原尾結(jié)點(diǎn)
• 2.CAS更新尾指針
• 3.原尾結(jié)點(diǎn)的next指針指向新插入結(jié)點(diǎn)

所以(s = h.next) == null 就是用來判斷2剛執(zhí)行成功但還未執(zhí)行3這種情況的布蔗。這種情況第二個(gè)結(jié)點(diǎn)必然屬于其他線程藤违。
以上兩種情況都會(huì)使該方法返回true,即當(dāng)前有優(yōu)先級(jí)更高的線程在隊(duì)列中等待,那么當(dāng)前線程將不會(huì)執(zhí)行CAS操作去獲取鎖,保證了線程獲取鎖的順序與加入同步隊(duì)列的順序一致，很好的保證了公平性,但也增加了獲取鎖的成本纵揍。

6. 一些疑問的解答

6.1 為什么基于FIFO的同步隊(duì)列可以實(shí)現(xiàn)非公平鎖顿乒？

由FIFO隊(duì)列的特性知,先加入同步隊(duì)列等待的線程會(huì)比后加入的線程更靠近隊(duì)列的頭部,那么它將比后者更早的被喚醒,它也就能更早的得到鎖。從這個(gè)意義上,對(duì)于在同步隊(duì)列中等待的線程而言,它們獲得鎖的順序和加入同步隊(duì)列的順序一致泽谨，這顯然是一種公平模式璧榄。然而,線程并非只有在加入隊(duì)列后才有機(jī)會(huì)獲得鎖,哪怕同步隊(duì)列中已有線程在等待,非公平鎖的不公平之處就在于此“杀ⅲ回看下非公平鎖的加鎖流程,線程在進(jìn)入同步隊(duì)列等待之前有兩次搶占鎖的機(jī)會(huì):

• 第一次是非重入式的獲取鎖,只有在當(dāng)前鎖未被任何線程占有(包括自身)時(shí)才能成功;
• 第二次是在進(jìn)入同步隊(duì)列前,包含所有情況的獲取鎖的方式骨杂。

只有這兩次獲取鎖都失敗后,線程才會(huì)構(gòu)造結(jié)點(diǎn)并加入同步隊(duì)列等待。而線程釋放鎖時(shí)是先釋放鎖(修改state值),然后才喚醒后繼結(jié)點(diǎn)的線程的雄卷。試想下這種情況,線程A已經(jīng)釋放鎖,但還沒來得及喚醒后繼線程C,而這時(shí)另一個(gè)線程B剛好嘗試獲取鎖,此時(shí)鎖恰好不被任何線程持有,它將成功獲取鎖而不用加入隊(duì)列等待搓蚪。線程C被喚醒嘗試獲取鎖,而此時(shí)鎖已經(jīng)被線程B搶占,故而其獲取失敗并繼續(xù)在隊(duì)列中等待。整個(gè)過程如下圖所示

image

轉(zhuǎn)自：https://www.cnblogs.com/takumicx/p/9402021.html

如果以線程第一次嘗試獲取鎖到最后成功獲取鎖的次序來看,非公平鎖確實(shí)很不公平丁鹉。因?yàn)樵陉?duì)列中等待很久的線程相比還未進(jìn)入隊(duì)列等待的線程并沒有優(yōu)先權(quán),甚至競(jìng)爭(zhēng)也處于劣勢(shì):在隊(duì)列中的線程要等待其他線程喚醒,在獲取鎖之前還要檢查前驅(qū)結(jié)點(diǎn)是否為頭結(jié)點(diǎn)妒潭。在鎖競(jìng)爭(zhēng)激烈的情況下,在隊(duì)列中等待的線程可能遲遲競(jìng)爭(zhēng)不到鎖。這也就非公平在高并發(fā)情況下會(huì)出現(xiàn)的饑餓問題鳄炉。那我們?cè)匍_發(fā)中為什么大多使用會(huì)導(dǎo)致饑餓的非公平鎖杜耙？很簡(jiǎn)單,因?yàn)樗阅芎冒　?/p>

6.2 為什么非公平鎖性能好

非公平鎖對(duì)鎖的競(jìng)爭(zhēng)是搶占式的(隊(duì)列中線程除外),線程在進(jìn)入等待隊(duì)列前可以進(jìn)行兩次嘗試,這大大增加了獲取鎖的機(jī)會(huì)。這種好處體現(xiàn)在兩個(gè)方面:

• 1.線程不必加入等待隊(duì)列就可以獲得鎖,不僅免去了構(gòu)造結(jié)點(diǎn)并加入隊(duì)列的繁瑣操作,同時(shí)也節(jié)省了線程阻塞喚醒的開銷,線程阻塞和喚醒涉及到線程上下文的切換和操作系統(tǒng)的系統(tǒng)調(diào)用,是非常耗時(shí)的拂盯。在高并發(fā)情況下,如果線程持有鎖的時(shí)間非常短,短到線程入隊(duì)阻塞的過程超過線程持有并釋放鎖的時(shí)間開銷,那么這種搶占式特性對(duì)并發(fā)性能的提升會(huì)更加明顯佑女。

• 2.減少CAS競(jìng)爭(zhēng)。如果線程必須要加入阻塞隊(duì)列才能獲取鎖,那入隊(duì)時(shí)CAS競(jìng)爭(zhēng)將變得異常激烈,CAS操作雖然不會(huì)導(dǎo)致失敗線程掛起,但不斷失敗重試導(dǎo)致的對(duì)CPU的浪費(fèi)也不能忽視。除此之外,加鎖流程中至少有兩處通過將某些特殊情況提前來減少CAS操作的競(jìng)爭(zhēng),增加并發(fā)情況下的性能团驱。一處就是獲取鎖時(shí)將非重入的情況提前,如下圖所示

  
  
  image

另一處就是入隊(duì)的操作,將同步隊(duì)列非空的情況提前處理

image

這兩部分的代碼在之后的通用邏輯處理中都有,很顯然屬于重復(fù)代碼,但因?yàn)楸苊饬藞?zhí)行無意義的流程代碼,比如for循環(huán),獲取同步狀態(tài)等,高并發(fā)場(chǎng)景下也能減少CAS競(jìng)爭(zhēng)失敗的可能摸吠。