作者：小傅哥
博客：https://

沉淀、分享、成長(zhǎng)，讓自己和他人都能有所收獲！😄

一、前言

Java學(xué)多少才能找到工作？

最近經(jīng)常有小伙伴問我，以為我的經(jīng)驗(yàn)來看，學(xué)多少夠，好像更多的是看你的野心有多大。如果你只是想找個(gè)10k以內(nèi)的二線城市的工作，那還是比較容易的。也不需要學(xué)數(shù)據(jù)結(jié)構(gòu)、也不需要會(huì)算法、也需要懂源碼、更不要有多少項(xiàng)目經(jīng)驗(yàn)。

但反之我遇到一個(gè)國內(nèi)大學(xué)TOP2畢業(yè)的娃，這貨兼職是Offer收割機(jī)：騰訊、阿里、字節(jié)還有國外新加坡的工作機(jī)會(huì)等等，薪資待遇也是賊高，可能超過你對(duì)白菜價(jià)的認(rèn)知。上學(xué)無用、學(xué)習(xí)無用，純屬扯淡！

你能在這條路上能付出的越多，能努力的越早，收獲就會(huì)越大！

二、面試題

謝飛機(jī)，小記，剛?cè)ザ屠萃昴_放松的飛機(jī)，因?yàn)槟涂艘m子丟了，罵罵咧咧的赴約面試官。

面試官：咋了，飛機(jī)，怎么看上去不高興。

謝飛機(jī)：沒事，沒事，我心思我學(xué)的 synchronized 呢！

面試官：那正好，飛機(jī)你會(huì)鎖嗎？

謝飛機(jī)：啊。。。我沒去會(huì)所呀！！！你咋知道

面試官：我說 Java 鎖，你想啥呢！你了解公平鎖嗎，知道怎么實(shí)現(xiàn)的嗎，給我說說！

謝飛機(jī)：公平鎖！？嗯，是不 ReentrantLock 中用到了，我怎么感覺似乎有印象，但是不記得了。

面試官：哎，回家搜搜 CLH 吧！

三、ReentrantLock 和 公平鎖

1. ReentrantLock 介紹

鑒于上一篇小傅哥已經(jīng)基于，HotSpot虛擬機(jī)源碼分析 synchronized 實(shí)現(xiàn)和相應(yīng)核心知識(shí)點(diǎn)，本來想在本章直接介紹下 ReentrantLock。但因?yàn)?ReentrantLock 知識(shí)點(diǎn)較多，因此會(huì)分幾篇分別講解，突出每一篇重點(diǎn)，避免豬八戒吞棗。

介紹：ReentrantLock 是一個(gè)可重入且獨(dú)占式鎖，具有與 synchronized 監(jiān)視器(monitor enter、monitor exit)鎖基本相同的行為和語意。但與 synchronized 相比，它更加靈活、強(qiáng)大、增加了輪訓(xùn)、超時(shí)、中斷等高級(jí)功能以及可以創(chuàng)建公平和非公平鎖。

2. ReentrantLock 知識(shí)鏈條

ReentrantLock 是基于 Lock 實(shí)現(xiàn)的可重入鎖，所有的 Lock 都是基于 AQS 實(shí)現(xiàn)的，AQS 和 Condition 各自維護(hù)不同的對(duì)象，在使用 Lock 和 Condition 時(shí)，其實(shí)就是兩個(gè)隊(duì)列的互相移動(dòng)。它所提供的共享鎖、互斥鎖都是基于對(duì) state 的操作。而它的可重入是因?yàn)閷?shí)現(xiàn)了同步器 Sync，在 Sync 的兩個(gè)實(shí)現(xiàn)類中，包括了公平鎖和非公平鎖。

這個(gè)公平鎖的具體實(shí)現(xiàn)，就是我們本章節(jié)要介紹的重點(diǎn)，了解什么是公平鎖、公平鎖的具體實(shí)現(xiàn)。學(xué)習(xí)完基礎(chǔ)的知識(shí)可以更好的理解 ReentrantLock

3. ReentrantLock 公平鎖代碼

3.1 初始化

ReentrantLock lock = new ReentrantLock(true);  // true：公平鎖
lock.lock();
try {
    // todo
} finally {
    lock.unlock();
}

• 初始化構(gòu)造函數(shù)入?yún)?#xff0c;選擇是否為初始化公平鎖。
• 其實(shí)一般情況下并不需要公平鎖，除非你的場(chǎng)景中需要保證順序性。
• 使用 ReentrantLock 切記需要在 finally 中關(guān)閉，lock.unlock()。

3.2 公平鎖、非公平鎖，選擇

public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}

• 構(gòu)造函數(shù)中選擇公平鎖（FairSync）、非公平鎖（NonfairSync）。

3.3 hasQueuedPredecessors

static final class FairSync extends Sync {

    protected final boolean tryAcquire(int acquires) {
        final Thread current = Thread.currentThread();
        int c = getState();
        if (c == 0) {
            if (!hasQueuedPredecessors() &&
                compareAndSetState(0, acquires)) {
                setExclusiveOwnerThread(current);
                return true;
            }
        }
...
    }
}

• 公平鎖和非公平鎖，主要是在方法 tryAcquire 中，是否有 !hasQueuedPredecessors() 判斷。

3.4 隊(duì)列首位判斷

public final boolean hasQueuedPredecessors() {
    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());
}

• 在這個(gè)判斷中主要就是看當(dāng)前線程是不是同步隊(duì)列的首位，是：true、否：false
• 這部分就涉及到了公平鎖的實(shí)現(xiàn)，CLH（Craig，Landin andHagersten）。三個(gè)作者的首字母組合

四、什么是公平鎖

公平鎖就像是馬路邊上的衛(wèi)生間，上廁所需要排隊(duì)。當(dāng)然如果有人不排隊(duì)，那么就是非公平鎖了，比如領(lǐng)導(dǎo)要先上。

CLH 是一種基于單向鏈表的高性能、公平的自旋鎖。AQS中的隊(duì)列是CLH變體的虛擬雙向隊(duì)列（FIFO），AQS是通過將每條請(qǐng)求共享資源的線程封裝成一個(gè)節(jié)點(diǎn)來實(shí)現(xiàn)鎖的分配。

為了更好的學(xué)習(xí)理解 CLH 的原理，就需要有實(shí)踐的代碼。接下來一 CLH 為核心分別介紹4種公平鎖的實(shí)現(xiàn)，從而掌握最基本的技術(shù)棧知識(shí)。

五、公平鎖實(shí)現(xiàn)

1. CLH

1.1 看圖說話

1.2 代碼實(shí)現(xiàn)

public class CLHLock implements Lock {

    private final ThreadLocal<CLHLock.Node> prev;
    private final ThreadLocal<CLHLock.Node> node;
    private final AtomicReference<CLHLock.Node> tail = new AtomicReference<>(new CLHLock.Node());

    private static class Node {
        private volatile boolean locked;
    }

    public CLHLock() {
        this.prev = ThreadLocal.withInitial(() -> null);
        this.node = ThreadLocal.withInitial(CLHLock.Node::new);
    }

    @Override
    public void lock() {
        final Node node = this.node.get();
        node.locked = true;
        Node pred_node = this.tail.getAndSet(node);
        this.prev.set(pred_node);
        // 自旋
        while (pred_node.locked);
    }

    @Override
    public void unlock() {
        final Node node = this.node.get();
        node.locked = false;
        this.node.set(this.prev.get());
    }

}

1.3 代碼講解

CLH（Craig，Landin and Hagersten），是一種基于鏈表的可擴(kuò)展、高性能、公平的自旋鎖。

在這段代碼的實(shí)現(xiàn)過程中，相當(dāng)于是虛擬出來一個(gè)鏈表結(jié)構(gòu)，由 AtomicReference 的方法 getAndSet 進(jìn)行銜接。getAndSet 獲取當(dāng)前元素，設(shè)置新的元素

lock()

• 通過 this.node.get() 獲取當(dāng)前節(jié)點(diǎn)，并設(shè)置 locked 為 true。
• 接著調(diào)用 this.tail.getAndSet(node)，獲取當(dāng)前尾部節(jié)點(diǎn) pred_node，同時(shí)把新加入的節(jié)點(diǎn)設(shè)置成尾部節(jié)點(diǎn)。
• 之后就是把 this.prev 設(shè)置為之前的尾部節(jié)點(diǎn)，也就相當(dāng)于鏈路的指向。
• 最后就是自旋 while (pred_node.locked)，直至程序釋放。

unlock()

• 釋放鎖的過程就是拆鏈，把釋放鎖的節(jié)點(diǎn)設(shè)置為false node.locked = false。
• 之后最重要的是把當(dāng)前節(jié)點(diǎn)設(shè)置為上一個(gè)節(jié)點(diǎn)，這樣就相當(dāng)于把自己的節(jié)點(diǎn)拆下來了，等著垃圾回收。

CLH隊(duì)列鎖的優(yōu)點(diǎn)是空間復(fù)雜度低，在SMP（Symmetric Multi-Processor）對(duì)稱多處理器結(jié)構(gòu)（一臺(tái)計(jì)算機(jī)由多個(gè)CPU組成，并共享內(nèi)存和其他資源，所有的CPU都可以平等地訪問內(nèi)存、I/O和外部中斷）效果還是不錯(cuò)的。但在 NUMA(Non-Uniform Memory Access) 下效果就不太好了，這部分知識(shí)可以自行擴(kuò)展。

2. MCSLock

2.1 代碼實(shí)現(xiàn)

public class MCSLock implements Lock {

    private AtomicReference<MCSLock.Node> tail = new AtomicReference<>(null);
    ;
    private ThreadLocal<MCSLock.Node> node;

    private static class Node {
        private volatile boolean locked = false;
        private volatile Node next = null;
    }

    public MCSLock() {
        node = ThreadLocal.withInitial(Node::new);
    }

    @Override
    public void lock() {
        Node node = this.node.get();
        Node preNode = tail.getAndSet(node);
        if (null == preNode) {
            node.locked = true;
            return;
        }
        node.locked = false;
        preNode.next = node;
        while (!node.locked) ;
    }

    @Override
    public void unlock() {
        Node node = this.node.get();
        if (null != node.next) {
            node.next.locked = true;
            node.next = null;
            return;
        }
        if (tail.compareAndSet(node, null)) {
            return;
        }
        while (node.next == null) ;
    }

}

2.1 代碼講解

MCS 來自于發(fā)明人名字的首字母： John Mellor-Crummey和Michael Scott。

它也是一種基于鏈表的可擴(kuò)展、高性能、公平的自旋鎖，但與 CLH 不同。它是真的有下一個(gè)節(jié)點(diǎn) next，添加這個(gè)真實(shí)節(jié)點(diǎn)后，它就可以只在本地變量上自旋，而 CLH 是前驅(qū)節(jié)點(diǎn)的屬性上自旋。

因?yàn)樽孕?jié)點(diǎn)的不同，導(dǎo)致 CLH 更適合于 SMP 架構(gòu)、MCS 可以適合 NUMA 非一致存儲(chǔ)訪問架構(gòu)。你可以想象成 CLH 更需要線程數(shù)據(jù)在同一塊內(nèi)存上效果才更好，MCS 因?yàn)槭窃诒镜曜兞孔赃x，所以無論數(shù)據(jù)是否分散在不同的CPU模塊都沒有影響。

代碼實(shí)現(xiàn)上與 CLH 沒有太多差異，這里就不在敘述了，可以看代碼學(xué)習(xí)。

3. TicketLock

3.1 看圖說話

3.2 代碼實(shí)現(xiàn)

public class TicketLock implements Lock {

    private AtomicInteger serviceCount = new AtomicInteger(0);
    private AtomicInteger ticketCount = new AtomicInteger(0);
    private final ThreadLocal<Integer> owner = new ThreadLocal<>();

    @Override
    public void lock() {
        owner.set(ticketCount.getAndIncrement());
        while (serviceCount.get() != owner.get());
    }

    @Override
    public void unlock() {
        serviceCount.compareAndSet(owner.get(), owner.get() + 1);
        owner.remove();
    }
}

3.3 代碼講解

TicketLock 就像你去銀行、呷哺給你的一個(gè)排號(hào)卡一樣，叫到你號(hào)你才能進(jìn)去。屬于嚴(yán)格的公平性實(shí)現(xiàn)，但是多處理器系統(tǒng)上，每個(gè)進(jìn)程/線程占用的處理器都在讀寫同一個(gè)變量，每次讀寫操作都需要進(jìn)行多處理間的緩存同步，非常消耗系統(tǒng)性能。

代碼實(shí)現(xiàn)上也比較簡(jiǎn)單，lock() 中設(shè)置擁有者的號(hào)牌，并進(jìn)入自旋比對(duì)。unlock() 中使用 CAS 進(jìn)行解鎖操作，并處理移除。

六、總結(jié)

• ReentrantLock 是基于 Lock 實(shí)現(xiàn)的可重入鎖，對(duì)于公平鎖 CLH 的實(shí)現(xiàn)，只是這部分知識(shí)的冰山一角，但有這一腳，就可以很好熱身便于后續(xù)的學(xué)習(xí)。
• ReentrantLock 使用起來更加靈活，可操作性也更大，但一定要在 finally 中釋放鎖，目的是保證在獲取鎖之后，最終能夠被釋放。同時(shí)不要將獲取鎖的過程寫在 try 里面。
• 公平鎖的實(shí)現(xiàn)依據(jù)不同場(chǎng)景和SMP、NUMA的使用，會(huì)有不同的優(yōu)劣效果。在實(shí)際的使用中一般默認(rèn)會(huì)選擇非公平鎖，即使是自旋也是耗費(fèi)性能的，一般會(huì)用在較少等待的線程中，避免自旋時(shí)過長(zhǎng)。

七、系列推薦

• synchronized 解毒，剖析源碼深度分析！
• 面試官，ThreadLocal 你要這么問，我就掛了！
• 掃盲java.util.Collections工具包，學(xué)習(xí)排序、二分、洗牌、旋轉(zhuǎn)算法
• HashMap核心知識(shí)，擾動(dòng)函數(shù)、負(fù)載因子、擴(kuò)容鏈表拆分
• Netty+JavaFx實(shí)戰(zhàn)：仿桌面版微信聊天！