【騰訊阿里最全面試題】介紹下Synchronized惜索、Volatile、CAS剃浇、AQS巾兆，以及各自的使用場(chǎng)景

鎖概述

談到并發(fā)，不得不談ReentrantLock虎囚；而談ReentrantLock角塑，不得不談AbstractQueuedSynchronizer（AQS）！

類如其名淘讥，抽象的隊(duì)列式的同步器圃伶，AQS定義了一套多線程訪問共享資源的同步器框架，許多同步類實(shí)現(xiàn)都依賴于它蒲列，如常用的ReentrantLock/Semaphore/CountDownLatch...窒朋。

lock實(shí)現(xiàn)過程中的幾個(gè)關(guān)鍵詞：計(jì)數(shù)值、雙向鏈表蝗岖、CAS+自旋

lock的存儲(chǔ)結(jié)構(gòu)：一個(gè)int類型狀態(tài)值（用于鎖的狀態(tài)變更）侥猩，一個(gè)雙向鏈表（用于存儲(chǔ)等待中的線程）

lock獲取鎖的過程：本質(zhì)上是通過CAS來獲取狀態(tài)值修改，如果當(dāng)場(chǎng)沒獲取到剪侮，會(huì)將該線程放在線程等待鏈表中拭宁。

lock釋放鎖的過程：修改狀態(tài)值，調(diào)整等待鏈表瓣俯。

可以看到在整個(gè)實(shí)現(xiàn)過程中杰标，lock大量使用CAS+自旋。因此根據(jù)CAS特性彩匕，lock建議使用在低鎖沖突的情況下腔剂。目前java1.6以后，官方對(duì)synchronized做了大量的鎖優(yōu)化（偏向鎖驼仪、自旋掸犬、輕量級(jí)鎖）。因此在非必要的情況下绪爸，建議使用synchronized做同步操作湾碎。

參考資料：https://www.cnblogs.com/waterystone/p/4920797.html

Abstract Queued Synchronizer (AQS)

AbstractQueuedSynchronizer 維護(hù)了一個(gè)state（代表了共享資源）和一個(gè)FIFO線程等待隊(duì)列（多線程競(jìng)爭(zhēng)資源被阻塞時(shí)會(huì)將線程放入此隊(duì)列）。
由于state是由volatie修飾的所以該變量的改動(dòng)都是立等可見的奠货。

AQS 定義了兩種資源共享的方式 Exclusive（獨(dú)占介褥，一時(shí)間只有一個(gè)線程能訪問該資源）、Share (共享，一時(shí)間可以有多個(gè)線程訪問資源).

• 獨(dú)占： 假設(shè)state初始狀態(tài)為0,表示未鎖定狀態(tài)。線程A想使用該資源就把state修改為了1，那么線程B來訪問資源時(shí)發(fā)現(xiàn)state是1并不是0他就會(huì)被AQS送入等待隊(duì)列腻扇，
  直到線程A將該資源設(shè)置為0。

• 共享：假設(shè)state初始狀態(tài)為N,當(dāng)有線程來訪問后N就減少1個(gè)形真，直到N=0 這時(shí)就會(huì)阻塞新的線程來訪問資源。當(dāng)某一個(gè)線程執(zhí)行完畢后會(huì)將state+1超全，相當(dāng)于釋放了該線程持有的鎖咆霜。這樣新的線程就可以繼續(xù)訪問該資源。

獨(dú)占模式就像共享單車一時(shí)間只有一個(gè)人可以騎這個(gè)共享單車卵迂，共享模式就像公交車可以上去很多人裕便，但是人一旦上滿了就不能在上人了，必須要等車上的人下來后才能繼續(xù)上人见咒。

AbstractQueuedSynchronizer.png

參考資料：http://litroi.com/public/articleDetail?artId=20181015154804936010000

Example Diagram Analysis

Here's a retrospective. Let's take a simple example. If you don't understand something above, here's another chance to help you understand it.

First, the first thread calls reentrantLock.lock(), and when you turn to the front, you can see that tryAcquire(1) returns true directly and ends. It's just state=1, not even the head is initialized, let alone the blocking queue. If thread 1 calls unlock(), then thread 2 comes, then the world is peaceful and there is no intersection at all, then why do I need AQS?

If thread 1 did not call unlock(), thread 2 called lock(), think about what would happen?

Thread 2 initializes head [new Node()], while thread 2 inserts into the blocked queue and hangs (note that this is a for loop, and the part that sets head and tail is not return ed, only if the queue is successful will it jump out of the loop)

private Node enq(final Node node) {
    for (;;) {
        Node t = tail;
        if (t == null) { // Must initialize
            if (compareAndSetHead(new Node()))
                tail = head;
        } else {
            node.prev = t;
            if (compareAndSetTail(t, node)) {
                t.next = node;
                return t;
            }
        }
    }
}

First, thread 2 initializes the head node, at which time headtail, waitStatus0

Thread 2 then queues up:

At the same time, we also need to look at the waitStatus of the node at this time. We know that the head node is initialized by thread 2. At this time, waitStatus is not set. java will be set to 0 by default. But when the shouldParkAfterFailed Acquire method is used, thread 2 will set the precursor node, that is, the waitStatus of the head, to -1 .

What is the waitStatus of the thread 2 node at this time, because it is not set, so it is 0;

If thread 3 comes in at this time, it can be inserted directly after thread 2. At this time, the waitStatus of thread 3 is 0, and the waitStatus of precursor node thread 2 is set to -1 when shouldParkAfterFailedAcquire method is used.

Here we can briefly talk about the SIGNAL(-1) state in waitStatus. Doug Lea notes that it represents that the successor node needs to be waked up. That is to say, this waitStatus actually represents not its own state, but the state of the successor nodes. We know that each node will change the state of the precursor node to SIGNAL when it joins the queue, then block and wait for the precursor to wake up. There are two issues involved here: there are threads that cancel queuing and wake-up operations. In fact, the essence is the same. Readers can also follow the idea that "waitStatus represents the status of successor nodes" to see the source code.

參考資料：https://programming.vip/docs/line-by-line-source-code-analysis-clearly-abstractqueued-synchronizer.html

J.U.C偿衰，是JDK中提供的并發(fā)工具包,java.util.concurrent。里面提供了很多并發(fā)編程中很常用的實(shí)用工具類改览，比如 : Atomic原子操作下翎、比如lock同步鎖、fork/join等宝当。

從Lock作為切入點(diǎn)

我想以lock作為切入點(diǎn)來講解AQS视事，畢竟同步鎖是解決線程安全問題的通用手段，也是我們工作中用得比較多的方式庆揩。

Lock API

Lock是一個(gè)接口俐东，方法定義如下

void lock() // 如果鎖可用就獲得鎖，如果鎖不可用就阻塞直到鎖釋放
void lockInterruptibly() // 和 lock()方法相似, 但阻塞的線程可中斷订晌，拋出 java.lang.InterruptedException異常
boolean tryLock() // 非阻塞獲取鎖;嘗試獲取鎖虏辫，如果成功返回true
boolean tryLock(long timeout, TimeUnit timeUnit) //帶有超時(shí)時(shí)間的獲取鎖方法
void unlock() // 釋放鎖

Lock的實(shí)現(xiàn)

實(shí)現(xiàn)Lock接口的類有很多，以下為幾個(gè)常見的鎖實(shí)現(xiàn)

• ReentrantLock：表示重入鎖锈拨，它是唯一一個(gè)實(shí)現(xiàn)了Lock接口的類砌庄。重入鎖指的是線程在獲得鎖之后，再次獲取該鎖不需要阻塞奕枢，而是直接關(guān)聯(lián)一次計(jì)數(shù)器增加重入次數(shù)
• ReentrantReadWriteLock：重入讀寫鎖娄昆，它實(shí)現(xiàn)了ReadWriteLock接口，在這個(gè)類中維護(hù)了兩個(gè)鎖缝彬，一個(gè)是ReadLock萌焰，一個(gè)是WriteLock，他們都分別實(shí)現(xiàn)了Lock接口谷浅。讀寫鎖是一種適合讀多寫少的場(chǎng)景下解決線程安全問題的工具扒俯，基本原則是：讀和讀不互斥族购、讀和寫互斥、寫和寫互斥陵珍。也就是說涉及到影響數(shù)據(jù)變化的操作都會(huì)存在互斥。
• StampedLock： stampedLock是JDK8引入的新的鎖機(jī)制违施，可以簡(jiǎn)單認(rèn)為是讀寫鎖的一個(gè)改進(jìn)版本互纯，讀寫鎖雖然通過分離讀和寫的功能使得讀和讀之間可以完全并發(fā)，但是讀和寫是有沖突的磕蒲，如果大量的讀線程存在留潦，可能會(huì)引起寫線程的饑餓。stampedLock是一種樂觀的讀策略辣往，使得樂觀鎖完全不會(huì)阻塞寫線程

ReentrantLock的簡(jiǎn)單實(shí)用

如何在實(shí)際應(yīng)用中使用ReentrantLock呢兔院？我們通過一個(gè)簡(jiǎn)單的demo來演示一下

public class Demo {
    private static int count=0;
    static Lock lock=new ReentrantLock();
    public static void inc(){
        lock.lock();
        try {
            Thread.sleep(1);
            count++;
        } catch (InterruptedException e) {
            e.printStackTrace();
        }finally{
            lock.unlock();
        }
    }

這段代碼主要做一件事，就是通過一個(gè)靜態(tài)的incr()方法對(duì)共享變量count做連續(xù)遞增站削，在沒有加同步鎖的情況下多線程訪問這個(gè)方法一定會(huì)存在線程安全問題坊萝。所以用到了ReentrantLock來實(shí)現(xiàn)同步鎖，并且在finally語句塊中釋放鎖许起。
那么我來引出一個(gè)問題十偶，大家思考一下

多個(gè)線程通過lock競(jìng)爭(zhēng)鎖時(shí)，當(dāng)競(jìng)爭(zhēng)失敗的鎖是如何實(shí)現(xiàn)等待以及被喚醒的呢?

什么是AQS

AQS园细，全稱為AbstractQueuedSynchronizer惦积，它提供了一個(gè)FIFO隊(duì)列，可以看成是一個(gè)用來實(shí)現(xiàn)同步鎖以及其他涉及到同步功能的核心組件猛频，常見的有:ReentrantLock狮崩、CountDownLatch等。
AQS是一個(gè)抽象類鹿寻，主要是通過繼承的方式來使用睦柴，它本身沒有實(shí)現(xiàn)任何的同步接口，僅僅是定義了同步狀態(tài)的獲取以及釋放的方法來提供自定義的同步組件烈和。
可以這么說爱只，只要搞懂了AQS，那么J.U.C中絕大部分的api都能輕松掌握招刹。

AQS的兩種功能

從使用層面來說恬试，AQS的功能分為兩種：獨(dú)占和共享

• 獨(dú)占鎖，每次只能有一個(gè)線程持有鎖疯暑，比如前面給大家演示的ReentrantLock就是以獨(dú)占方式實(shí)現(xiàn)的互斥鎖
• 共享鎖训柴，允許多個(gè)線程同時(shí)獲取鎖，并發(fā)訪問共享資源妇拯，比如ReentrantReadWriteLock

ReentrantLock的類圖

仍然以ReentrantLock為例幻馁，來分析AQS在重入鎖中的使用洗鸵。畢竟單純分析AQS沒有太多的含義。先理解這個(gè)類圖仗嗦，可以方便我們理解AQS的原理

AQS的內(nèi)部實(shí)現(xiàn)

AQS的實(shí)現(xiàn)依賴內(nèi)部的同步隊(duì)列,也就是FIFO的雙向隊(duì)列膘滨，如果當(dāng)前線程競(jìng)爭(zhēng)鎖失敗，那么AQS會(huì)把當(dāng)前線程以及等待狀態(tài)信息構(gòu)造成一個(gè)Node加入到同步隊(duì)列中稀拐，同時(shí)再阻塞該線程火邓。當(dāng)獲取鎖的線程釋放鎖以后，會(huì)從隊(duì)列中喚醒一個(gè)阻塞的節(jié)點(diǎn)(線程)德撬。

AQS隊(duì)列內(nèi)部維護(hù)的是一個(gè)FIFO的雙向鏈表铲咨，這種結(jié)構(gòu)的特點(diǎn)是每個(gè)數(shù)據(jù)結(jié)構(gòu)都有兩個(gè)指針，分別指向直接的后繼節(jié)點(diǎn)和直接前驅(qū)節(jié)點(diǎn)蜓洪。所以雙向鏈表可以從任意一個(gè)節(jié)點(diǎn)開始很方便的訪問前驅(qū)和后繼纤勒。每個(gè)Node其實(shí)是由線程封裝，當(dāng)線程爭(zhēng)搶鎖失敗后會(huì)封裝成Node加入到ASQ隊(duì)列中去

Node類的組成如下

static final class Node {
        static final Node SHARED = new Node();
        static final Node EXCLUSIVE = null;
        static final int CANCELLED =  1;
        static final int SIGNAL    = -1;
        static final int CONDITION = -2;
        static final int PROPAGATE = -3;
        volatile int waitStatus;
        volatile Node prev; //前驅(qū)節(jié)點(diǎn)
        volatile Node next; //后繼節(jié)點(diǎn)
        volatile Thread thread;//當(dāng)前線程
        Node nextWaiter; //存儲(chǔ)在condition隊(duì)列中的后繼節(jié)點(diǎn)
        //是否為共享鎖
        final boolean isShared() { 
            return nextWaiter == SHARED;
        }

        final Node predecessor() throws NullPointerException {
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }

        Node() {    // Used to establish initial head or SHARED marker
        }
        //將線程構(gòu)造成一個(gè)Node隆檀，添加到等待隊(duì)列
        Node(Thread thread, Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }
        //這個(gè)方法會(huì)在Condition隊(duì)列使用摇天，后續(xù)單獨(dú)寫一篇文章分析condition
        Node(Thread thread, int waitStatus) { // Used by Condition
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }

ReentrantLock的時(shí)序圖

調(diào)用ReentrantLock中的lock()方法，源碼的調(diào)用過程我使用了時(shí)序圖來展現(xiàn)

從圖上可以看出來恐仑，當(dāng)鎖獲取失敗時(shí)闸翅，會(huì)調(diào)用addWaiter()方法將當(dāng)前線程封裝成Node節(jié)點(diǎn)加入到AQS隊(duì)列，基于這個(gè)思路菊霜，我們來分析AQS的源碼實(shí)現(xiàn)坚冀。

ReentrantLock.lock()

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

這個(gè)是獲取鎖的入口，調(diào)用sync這個(gè)類里面的方法鉴逞，sync是什么呢记某？

abstract static class Sync extends AbstractQueuedSynchronizer

sync是一個(gè)靜態(tài)內(nèi)部類，它繼承了AQS這個(gè)抽象類构捡，前面說過AQS是一個(gè)同步工具液南，主要用來實(shí)現(xiàn)同步控制。我們?cè)诶眠@個(gè)工具的時(shí)候勾徽，會(huì)繼承它來實(shí)現(xiàn)同步控制功能滑凉。
通過進(jìn)一步分析，發(fā)現(xiàn)Sync這個(gè)類有兩個(gè)具體的實(shí)現(xiàn)喘帚，分別是NofairSync(非公平鎖),FailSync(公平鎖).

• 公平鎖 表示所有線程嚴(yán)格按照FIFO來獲取鎖
• 非公平鎖 表示可以存在搶占鎖的功能畅姊，也就是說不管當(dāng)前隊(duì)列上是否存在其他線程等待，新線程都有機(jī)會(huì)搶占鎖

acquire

acquire是AQS中的方法吹由，如果CAS操作未能成功若未，說明state已經(jīng)不為0，此時(shí)繼續(xù)acquire(1)操作,這里大家思考一下倾鲫，acquire方法中的1的參數(shù)是用來做什么呢粗合？如果沒猜中萍嬉，往前面回顧一下state這個(gè)概念

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

這個(gè)方法的主要邏輯是

• 通過tryAcquire嘗試獲取獨(dú)占鎖，如果成功返回true隙疚，失敗返回false
• 如果tryAcquire失敗壤追，則會(huì)通過addWaiter方法將當(dāng)前線程封裝成Node添加到AQS隊(duì)列尾部
• acquireQueued，將Node作為參數(shù)供屉，通過自旋去嘗試獲取鎖大诸。

Synchronized源碼分析

NonfairSync.tryAcquire

這個(gè)方法的作用是嘗試獲取鎖，如果成功返回true贯卦，不成功返回false
它是重寫AQS類中的tryAcquire方法，并且大家仔細(xì)看一下AQS中tryAcquire方法的定義焙贷，并沒有實(shí)現(xiàn)撵割，而是拋出異常。按照一般的思維模式辙芍，既然是一個(gè)不實(shí)現(xiàn)的模版方法啡彬，那應(yīng)該定義成abstract，讓子類來實(shí)現(xiàn)呀故硅？大家想想為什么

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

nonfairTryAcquire

tryAcquire(1)在NonfairSync中的實(shí)現(xiàn)代碼如下

ffinal boolean nonfairTryAcquire(int acquires) {
    //獲得當(dāng)前執(zhí)行的線程
    final Thread current = Thread.currentThread();
    int c = getState(); //獲得state的值
    if (c == 0) { //state=0說明當(dāng)前是無鎖狀態(tài)
        //通過cas操作來替換state的值改為1庶灿，大家想想為什么要用cas呢？
        //理由是吃衅，在多線程環(huán)境中往踢，直接修改state=1會(huì)存在線程安全問題，你猜到了嗎徘层？
        if (compareAndSetState(0, acquires)) {
             //保存當(dāng)前獲得鎖的線程
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    //這段邏輯就很簡(jiǎn)單了峻呕。如果是同一個(gè)線程來獲得鎖，則直接增加重入次數(shù)
    else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires; //增加重入次數(shù)
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
        setState(nextc);
        return true;
    }
    return false;
}

• 獲取當(dāng)前線程趣效，判斷當(dāng)前的鎖的狀態(tài)
• 如果state=0表示當(dāng)前是無鎖狀態(tài)瘦癌，通過cas更新state狀態(tài)的值
• 如果當(dāng)前線程是屬于重入，則增加重入次數(shù)

addWaiter

當(dāng)tryAcquire方法獲取鎖失敗以后跷敬，則會(huì)先調(diào)用addWaiter將當(dāng)前線程封裝成Node讯私，然后添加到AQS隊(duì)列

private Node addWaiter(Node mode) { //mode=Node.EXCLUSIVE
        //將當(dāng)前線程封裝成Node，并且mode為獨(dú)占鎖
        Node node = new Node(Thread.currentThread(), mode); 
        // Try the fast path of enq; backup to full enq on failure
        // tail是AQS的中表示同步隊(duì)列隊(duì)尾的屬性西傀，剛開始為null斤寇，所以進(jìn)行enq(node)方法
        Node pred = tail;
        if (pred != null) { //tail不為空的情況，說明隊(duì)列中存在節(jié)點(diǎn)數(shù)據(jù)
            node.prev = pred;  //講當(dāng)前線程的Node的prev節(jié)點(diǎn)指向tail
            if (compareAndSetTail(pred, node)) {//通過cas講node添加到AQS隊(duì)列
                pred.next = node;//cas成功拥褂，把舊的tail的next指針指向新的tail
                return node;
            }
        }
        enq(node); //tail=null抡驼，將node添加到同步隊(duì)列中
        return node;
    }

• 將當(dāng)前線程封裝成Node
• 判斷當(dāng)前鏈表中的tail節(jié)點(diǎn)是否為空，如果不為空肿仑，則通過cas操作把當(dāng)前線程的node添加到AQS隊(duì)列
• 如果為空或者cas失敗致盟，調(diào)用enq將節(jié)點(diǎn)添加到AQS隊(duì)列

enq

enq就是通過自旋操作把當(dāng)前節(jié)點(diǎn)加入到隊(duì)列中

private Node enq(final Node node) {
        //自旋碎税，不做過多解釋，不清楚的關(guān)注公眾號(hào)[架構(gòu)師修煉寶典]
        for (;;) {
            Node t = tail; //如果是第一次添加到隊(duì)列馏锡，那么tail=null
            if (t == null) { // Must initialize
                //CAS的方式創(chuàng)建一個(gè)空的Node作為頭結(jié)點(diǎn)
                if (compareAndSetHead(new Node()))
                   //此時(shí)隊(duì)列中只一個(gè)頭結(jié)點(diǎn)雷蹂，所以tail也指向它
                    tail = head;
            } else {
//進(jìn)行第二次循環(huán)時(shí)，tail不為null杯道，進(jìn)入else區(qū)域匪煌。將當(dāng)前線程的Node結(jié)點(diǎn)的prev指向tail，然后使用CAS將tail指向Node
                node.prev = t;
                if (compareAndSetTail(t, node)) {
//t此時(shí)指向tail,所以可以CAS成功党巾，將tail重新指向Node萎庭。此時(shí)t為更新前的tail的值，即指向空的頭結(jié)點(diǎn)齿拂，t.next=node驳规，就將頭結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)指向Node，返回頭結(jié)點(diǎn)
                    t.next = node;
                    return t;
                }
            }
        }
    }

假如有兩個(gè)線程t1,t2同時(shí)進(jìn)入enq方法署海，t==null表示隊(duì)列是首次使用吗购，需要先初始化
另外一個(gè)線程cas失敗，則進(jìn)入下次循環(huán)砸狞，通過cas操作將node添加到隊(duì)尾

到目前為止捻勉，通過addwaiter方法構(gòu)造了一個(gè)AQS隊(duì)列，并且將線程添加到了隊(duì)列的節(jié)點(diǎn)中

acquireQueued

將添加到隊(duì)列中的Node作為參數(shù)傳入acquireQueued方法刀森，這里面會(huì)做搶占鎖的操作

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (;;) {
            final Node p = node.predecessor();// 獲取prev節(jié)點(diǎn),若為null即刻拋出NullPointException
            if (p == head && tryAcquire(arg)) {// 如果前驅(qū)為head才有資格進(jìn)行鎖的搶奪
                setHead(node); // 獲取鎖成功后就不需要再進(jìn)行同步操作了,獲取鎖成功的線程作為新的head節(jié)點(diǎn)
//凡是head節(jié)點(diǎn),head.thread與head.prev永遠(yuǎn)為null, 但是head.next不為null
                p.next = null; // help GC
                failed = false; //獲取鎖成功
                return interrupted;
            }
//如果獲取鎖失敗踱启，則根據(jù)節(jié)點(diǎn)的waitStatus決定是否需要掛起線程
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())// 若前面為true,則執(zhí)行掛起,待下次喚醒的時(shí)候檢測(cè)中斷的標(biāo)志
                interrupted = true;
        }
    } finally {
        if (failed) // 如果拋出異常則取消鎖的獲取,進(jìn)行出隊(duì)(sync queue)操作
            cancelAcquire(node);
    }
}

• 獲取當(dāng)前節(jié)點(diǎn)的prev節(jié)點(diǎn)
• 如果prev節(jié)點(diǎn)為head節(jié)點(diǎn)，那么它就有資格去爭(zhēng)搶鎖研底，調(diào)用tryAcquire搶占鎖
• 搶占鎖成功以后禽捆，把獲得鎖的節(jié)點(diǎn)設(shè)置為head，并且移除原來的初始化head節(jié)點(diǎn)
• 如果獲得鎖失敗飘哨，則根據(jù)waitStatus決定是否需要掛起線程
• 最后胚想，通過cancelAcquire取消獲得鎖的操作

前面的邏輯都很好理解，主要看一下shouldParkAfterFailedAcquire這個(gè)方法和parkAndCheckInterrupt的作用

shouldParkAfterFailedAcquire

從上面的分析可以看出芽隆，只有隊(duì)列的第二個(gè)節(jié)點(diǎn)可以有機(jī)會(huì)爭(zhēng)用鎖浊服，如果成功獲取鎖，則此節(jié)點(diǎn)晉升為頭節(jié)點(diǎn)胚吁。對(duì)于第三個(gè)及以后的節(jié)點(diǎn)牙躺，if (p == head)條件不成立，首先進(jìn)行shouldParkAfterFailedAcquire(p, node)操作
shouldParkAfterFailedAcquire方法是判斷一個(gè)爭(zhēng)用鎖的線程是否應(yīng)該被阻塞腕扶。它首先判斷一個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)的狀態(tài)是否為Node.SIGNAL孽拷，如果是，是說明此節(jié)點(diǎn)已經(jīng)將狀態(tài)設(shè)置-如果鎖釋放半抱，則應(yīng)當(dāng)通知它脓恕，所以它可以安全的阻塞了膜宋，返回true。

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus; //前繼節(jié)點(diǎn)的狀態(tài)
    if (ws == Node.SIGNAL)//如果是SIGNAL狀態(tài)炼幔，意味著當(dāng)前線程需要被unpark喚醒
               return true;
如果前節(jié)點(diǎn)的狀態(tài)大于0秋茫，即為CANCELLED狀態(tài)時(shí)，則會(huì)從前節(jié)點(diǎn)開始逐步循環(huán)找到一個(gè)沒有被“CANCELLED”節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的前節(jié)點(diǎn)乃秀，返回false肛著。在下次循環(huán)執(zhí)行shouldParkAfterFailedAcquire時(shí)，返回true跺讯。這個(gè)操作實(shí)際是把隊(duì)列中CANCELLED的節(jié)點(diǎn)剔除掉枢贿。
    if (ws > 0) {// 如果前繼節(jié)點(diǎn)是“取消”狀態(tài)，則設(shè)置 “當(dāng)前節(jié)點(diǎn)”的 “當(dāng)前前繼節(jié)點(diǎn)” 為 “‘原前繼節(jié)點(diǎn)'的前繼節(jié)點(diǎn)”刀脏。

        do {
            node.prev = pred = pred.prev;
        } while (pred.waitStatus > 0);
        pred.next = node;
    } else { // 如果前繼節(jié)點(diǎn)為“0”或者“共享鎖”狀態(tài)局荚，則設(shè)置前繼節(jié)點(diǎn)為SIGNAL狀態(tài)。
        /*
         * 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;
}

parkAndCheckInterrupt

如果shouldParkAfterFailedAcquire返回了true火本，則會(huì)執(zhí)行：parkAndCheckInterrupt()方法，它是通過LockSupport.park(this)將當(dāng)前線程掛起到WATING狀態(tài)聪建，它需要等待一個(gè)中斷钙畔、unpark方法來喚醒它，通過這樣一種FIFO的機(jī)制的等待金麸，來實(shí)現(xiàn)了Lock的操作擎析。

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

LockSupport
LockSupport類是Java6引入的一個(gè)類，提供了基本的線程同步原語挥下。LockSupport實(shí)際上是調(diào)用了Unsafe類里的函數(shù)揍魂，歸結(jié)到Unsafe里，只有兩個(gè)函數(shù)：

public native void unpark(Thread jthread);  
public native void park(boolean isAbsolute, long time);  

unpark函數(shù)為線程提供“許可(permit)”棚瘟，線程調(diào)用park函數(shù)則等待“許可”现斋。這個(gè)有點(diǎn)像信號(hào)量，但是這個(gè)“許可”是不能疊加的偎蘸，“許可”是一次性的庄蹋。
permit相當(dāng)于0/1的開關(guān)，默認(rèn)是0迷雪，調(diào)用一次unpark就加1變成了1.調(diào)用一次park會(huì)消費(fèi)permit限书，又會(huì)變成0。 如果再調(diào)用一次park會(huì)阻塞章咧，因?yàn)閜ermit已經(jīng)是0了倦西。直到permit變成1.這時(shí)調(diào)用unpark會(huì)把permit設(shè)置為1.每個(gè)線程都有一個(gè)相關(guān)的permit，permit最多只有一個(gè)赁严，重復(fù)調(diào)用unpark不會(huì)累積

鎖的釋放

ReentrantLock.unlock

加鎖的過程分析完以后扰柠，再來分析一下釋放鎖的過程粉铐，調(diào)用release方法，這個(gè)方法里面做兩件事耻矮，1秦躯，釋放鎖 ；2裆装，喚醒park的線程

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

tryRelease

這個(gè)動(dòng)作可以認(rèn)為就是一個(gè)設(shè)置鎖狀態(tài)的操作踱承，而且是將狀態(tài)減掉傳入的參數(shù)值（參數(shù)是1），如果結(jié)果狀態(tài)為0哨免，就將排它鎖的Owner設(shè)置為null茎活，以使得其它的線程有機(jī)會(huì)進(jìn)行執(zhí)行。
在排它鎖中琢唾，加鎖的時(shí)候狀態(tài)會(huì)增加1（當(dāng)然可以自己修改這個(gè)值）载荔，在解鎖的時(shí)候減掉1，同一個(gè)鎖采桃，在可以重入后懒熙，可能會(huì)被疊加為2、3普办、4這些值工扎，只有unlock()的次數(shù)與lock()的次數(shù)對(duì)應(yīng)才會(huì)將Owner線程設(shè)置為空，而且也只有這種情況下才會(huì)返回true衔蹲。

protected final boolean tryRelease(int releases) {
    int c = getState() - releases; // 這里是將鎖的數(shù)量減1
    if (Thread.currentThread() != getExclusiveOwnerThread())// 如果釋放的線程和獲取鎖的線程不是同一個(gè)肢娘，拋出非法監(jiān)視器狀態(tài)異常
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) { 
// 由于重入的關(guān)系，不是每次釋放鎖c都等于0舆驶，
    // 直到最后一次釋放鎖時(shí)橱健，才會(huì)把當(dāng)前線程釋放
        free = true;
        setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
}

unparkSuccessor

在方法unparkSuccessor(Node)中，就意味著真正要釋放鎖了沙廉，它傳入的是head節(jié)點(diǎn)（head節(jié)點(diǎn)是占用鎖的節(jié)點(diǎn)）拘荡，當(dāng)前線程被釋放之后，需要喚醒下一個(gè)節(jié)點(diǎn)的線程

private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);
    Node s = node.next;
    if (s == null || s.waitStatus > 0) {//判斷后繼節(jié)點(diǎn)是否為空或者是否是取消狀態(tài),
        s = null;
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0) //然后從隊(duì)列尾部向前遍歷找到最前面的一個(gè)waitStatus小于0的節(jié)點(diǎn), 至于為什么從尾部開始向前遍歷撬陵，因?yàn)樵赿oAcquireInterruptibly.cancelAcquire方法的處理過程中只設(shè)置了next的變化俱病，沒有設(shè)置prev的變化，在最后有這樣一行代碼：node.next = node袱结，如果這時(shí)執(zhí)行了unparkSuccessor方法亮隙，并且向后遍歷的話，就成了死循環(huán)了垢夹，所以這時(shí)只有prev是穩(wěn)定的
                s = t;
    }
//內(nèi)部首先會(huì)發(fā)生的動(dòng)作是獲取head節(jié)點(diǎn)的next節(jié)點(diǎn)溢吻，如果獲取到的節(jié)點(diǎn)不為空，則直接通過：“LockSupport.unpark()”方法來釋放對(duì)應(yīng)的被掛起的線程，這樣一來將會(huì)有一個(gè)節(jié)點(diǎn)喚醒后繼續(xù)進(jìn)入循環(huán)進(jìn)一步嘗試tryAcquire()方法來獲取鎖
    if (s != null)
        LockSupport.unpark(s.thread); //釋放許可
}

參考資料：
https://segmentfault.com/a/1190000017372067