1 什么是自旋鎖和互斥鎖？

由于CLH鎖是一種自旋鎖，那么我們先來看看自旋鎖是什么？

自旋鎖說白了也是一種互斥鎖，只不過沒有搶到鎖的線程會一直自旋等待鎖的釋放，處于busy-waiting的狀態(tài)，此時等待鎖的線程不會進(jìn)入休眠狀態(tài)，而是一直忙等待浪費CPU周期。因此自旋鎖適用于鎖占用時間短的場合。

這里談到了自旋鎖，那么我們也順便說下互斥鎖。這里的互斥鎖說的是傳統(tǒng)意義的互斥鎖，就是多個線程并發(fā)競爭鎖的時候，沒有搶到鎖的線程會進(jìn)入休眠狀態(tài)即sleep-waiting，當(dāng)鎖被釋放的時候，處于休眠狀態(tài)的一個線程會再次獲取到鎖。缺點就是這一些列過程需要線程切換，需要執(zhí)行很多CPU指令，同樣需要時間。如果CPU執(zhí)行線程切換的時間比鎖占用的時間還長，那么可能還不如使用自旋鎖。因此互斥鎖適用于鎖占用時間長的場合。

2 什么是CLH鎖？

CLH鎖其實就是一種是基于邏輯隊列非線程饑餓的一種自旋公平鎖，由于是 Craig、Landin 和 Hagersten三位大佬的發(fā)明，因此命名為CLH鎖。

CLH鎖原理如下：

1. 首先有一個尾節(jié)點指針，通過這個尾結(jié)點指針來構(gòu)建等待線程的邏輯隊列，因此能確保線程線程先到先服務(wù)的公平性，因此尾指針可以說是構(gòu)建邏輯隊列的橋梁；此外這個尾節(jié)點指針是原子引用類型，避免了多線程并發(fā)操作的線程安全性問題；
2. 通過等待鎖的每個線程在自己的某個變量上自旋等待，這個變量將由前一個線程寫入。由于某個線程獲取鎖操作時總是通過尾節(jié)點指針獲取到前一線程寫入的變量，而尾節(jié)點指針又是原子引用類型，因此確保了這個變量獲取出來總是線程安全的。

這么說肯定很抽象，有些小伙伴可能不理解，沒關(guān)系，我們心中可以有個概念即可，后面我們會一步一圖來徹徹底底把CLH鎖弄明白。

3 為什么要學(xué)習(xí)CLH鎖？

好了，前面我們對CLH鎖有了一個概念后，那么我們?yōu)槭裁匆獙W(xué)習(xí)CLH鎖呢？

研究過AQS源碼的小伙伴們應(yīng)該知道，AQS是JUC的核心，而CLH鎖又是AQS的基礎(chǔ)，說核心也不為過，因為AQS就是用了變種的CLH鎖。如果要學(xué)好Java并發(fā)編程，那么必定要學(xué)好JUC；學(xué)好JUC，必定要先學(xué)好AQS；學(xué)好AQS，那么必定先學(xué)好CLH。因此，這就是我們?yōu)槭裁匆獙W(xué)習(xí)CLH鎖的原因。

4 CLH鎖詳解

那么，下面我們先來看CLH鎖實現(xiàn)代碼，然后通過一步一圖來詳解CLH鎖。

//?CLHLock.java

public?class?CLHLock?{
????/**
?????*?CLH鎖節(jié)點
?????*/
????private?static?class?CLHNode?{
????????//?鎖狀態(tài)：默認(rèn)為false，表示線程沒有獲取到鎖；true表示線程獲取到鎖或正在等待
????????//?為了保證locked狀態(tài)是線程間可見的，因此用volatile關(guān)鍵字修飾
????????volatile?boolean?locked?=?false;
????}
????//?尾結(jié)點，總是指向最后一個CLHNode節(jié)點
????//?【注意】這里用了java的原子系列之AtomicReference，能保證原子更新
????private?final?AtomicReference?tailNode;
????//?當(dāng)前節(jié)點的前繼節(jié)點
????private?final?ThreadLocal?predNode;
????//?當(dāng)前節(jié)點
????private?final?ThreadLocal?curNode;

????//?CLHLock構(gòu)造函數(shù)，用于新建CLH鎖節(jié)點時做一些初始化邏輯
????public?CLHLock()?{
????????//?初始化時尾結(jié)點指向一個空的CLH節(jié)點
????????tailNode?=?new?AtomicReference<>(new?CLHNode());
????????//?初始化當(dāng)前的CLH節(jié)點
????????curNode?=?new?ThreadLocal()?{
????????????@Override
????????????protected?CLHNode?initialValue()?{
????????????????return?new?CLHNode();
????????????}
????????};
????????//?初始化前繼節(jié)點，注意此時前繼節(jié)點沒有存儲CLHNode對象，存儲的是null
????????predNode?=?new?ThreadLocal();
????}

????/**
?????*?獲取鎖
?????*/
????public?void?lock()?{
????????//?取出當(dāng)前線程ThreadLocal存儲的當(dāng)前節(jié)點，初始化值總是一個新建的CLHNode，locked狀態(tài)為false。
????????CLHNode?currNode?=?curNode.get();
????????//?此時把lock狀態(tài)置為true，表示一個有效狀態(tài)，
????????//?即獲取到了鎖或正在等待鎖的狀態(tài)
????????currNode.locked?=?true;
????????//?當(dāng)一個線程到來時，總是將尾結(jié)點取出來賦值給當(dāng)前線程的前繼節(jié)點；
????????//?然后再把當(dāng)前線程的當(dāng)前節(jié)點賦值給尾節(jié)點
????????//?【注意】在多線程并發(fā)情況下，這里通過AtomicReference類能防止并發(fā)問題
????????//?【注意】哪個線程先執(zhí)行到這里就會先執(zhí)行predNode.set(preNode);語句，因此構(gòu)建了一條邏輯線程等待鏈
????????//?這條鏈避免了線程饑餓現(xiàn)象發(fā)生
????????CLHNode?preNode?=?tailNode.getAndSet(currNode);
????????//?將剛獲取的尾結(jié)點（前一線程的當(dāng)前節(jié)點）付給當(dāng)前線程的前繼節(jié)點ThreadLocal
????????//?【思考】這句代碼也可以去掉嗎，如果去掉有影響嗎？
????????predNode.set(preNode);
????????//?【1】若前繼節(jié)點的locked狀態(tài)為false，則表示獲取到了鎖，不用自旋等待；
????????//?【2】若前繼節(jié)點的locked狀態(tài)為true，則表示前一線程獲取到了鎖或者正在等待，自旋等待
????????while?(preNode.locked)?{
????????????System.out.println("線程"?+?Thread.currentThread().getName()?+?"沒能獲取到鎖，進(jìn)行自旋等待。。。");
????????}
????????//?能執(zhí)行到這里，說明當(dāng)前線程獲取到了鎖
????????System.out.println("線程"?+?Thread.currentThread().getName()?+?"獲取到了鎖?。?！");
????}

????/**
?????*?釋放鎖
?????*/
????public?void?unLock()?{
????????//?獲取當(dāng)前線程的當(dāng)前節(jié)點
????????CLHNode?node?=?curNode.get();
????????//?進(jìn)行解鎖操作
????????//?這里將locked至為false，此時執(zhí)行了lock方法正在自旋等待的后繼節(jié)點將會獲取到鎖
????????//?【注意】而不是所有正在自旋等待的線程去并發(fā)競爭鎖
????????node.locked?=?false;
????????System.out.println("線程"?+?Thread.currentThread().getName()?+?"釋放了鎖?。?！");
????????//?小伙伴們可以思考下，下面兩句代碼的作用是什么？？
????????CLHNode?newCurNode?=?new?CLHNode();
????????curNode.set(newCurNode);

????????//?【優(yōu)化】能提高GC效率和節(jié)省內(nèi)存空間，請思考：這是為什么？
????????//?curNode.set(predNode.get());
????}
}

4.1 CLH鎖的初始化邏輯

通過上面代碼，我們縷一縷CLH鎖的初始化邏輯先：

1. 定義了一個 CLHNode節(jié)點，里面有一個 locked屬性，表示線程線程是否獲得鎖，默認(rèn)為 false。 false表示線程沒有獲取到鎖或已經(jīng)釋放鎖； true表示線程獲取到了鎖或者正在自旋等待。

注意，為了保證locked屬性線程間可見，該屬性被volatile修飾。

2. CLHLock有三個重要的成員變量尾節(jié)點指針 tailNode,當(dāng)前線程的前繼節(jié)點 preNode和當(dāng)前節(jié)點 curNode。其中 tailNode是 AtomicReference類型，目的是為了保證尾節(jié)點的線程安全性；此外， preNode和 curNode都是 ThreadLocal類型即線程本地變量類型，用來保存每個線程的前繼 CLHNode和當(dāng)前 CLHNode節(jié)點。
3. 最重要的是我們新建一把 CLHLock對象時，此時會執(zhí)行構(gòu)造函數(shù)里面的初始化邏輯。此時給尾指針 tailNode和當(dāng)前節(jié)點 curNode初始化一個 locked狀態(tài)為 false的 CLHNode節(jié)點，此時前繼節(jié)點 preNode存儲的是 null。

4.2 CLH鎖的加鎖過程

我們再來看看CLH鎖的加鎖過程，下面再貼一遍加鎖lock方法的代碼：

//?CLHLock.java

/**
?*?獲取鎖
?*/
public?void?lock()?{
????//?取出當(dāng)前線程ThreadLocal存儲的當(dāng)前節(jié)點，初始化值總是一個新建的CLHNode，locked狀態(tài)為false。
????CLHNode?currNode?=?curNode.get();
????//?此時把lock狀態(tài)置為true，表示一個有效狀態(tài)，
????//?即獲取到了鎖或正在等待鎖的狀態(tài)
????currNode.locked?=?true;
????//?當(dāng)一個線程到來時，總是將尾結(jié)點取出來賦值給當(dāng)前線程的前繼節(jié)點；
????//?然后再把當(dāng)前線程的當(dāng)前節(jié)點賦值給尾節(jié)點
????//?【注意】在多線程并發(fā)情況下，這里通過AtomicReference類能防止并發(fā)問題
????//?【注意】哪個線程先執(zhí)行到這里就會先執(zhí)行predNode.set(preNode);語句，因此構(gòu)建了一條邏輯線程等待鏈
????//?這條鏈避免了線程饑餓現(xiàn)象發(fā)生
????CLHNode?preNode?=?tailNode.getAndSet(currNode);
????//?將剛獲取的尾結(jié)點（前一線程的當(dāng)前節(jié)點）付給當(dāng)前線程的前繼節(jié)點ThreadLocal
????//?【思考】這句代碼也可以去掉嗎，如果去掉有影響嗎？
????predNode.set(preNode);
????//?【1】若前繼節(jié)點的locked狀態(tài)為false，則表示獲取到了鎖，不用自旋等待；
????//?【2】若前繼節(jié)點的locked狀態(tài)為true，則表示前一線程獲取到了鎖或者正在等待，自旋等待
????while?(preNode.locked)?{
????????try?{
????????????Thread.sleep(1000);
????????}?catch?(Exception?e)?{

????????}
????????System.out.println("線程"?+?Thread.currentThread().getName()?+?"沒能獲取到鎖，進(jìn)行自旋等待。。。");
????}
????//?能執(zhí)行到這里，說明當(dāng)前線程獲取到了鎖
????System.out.println("線程"?+?Thread.currentThread().getName()?+?"獲取到了鎖?。?！");
}

雖然代碼的注釋已經(jīng)很詳細(xì)，我們還是縷一縷線程加鎖的過程：

1. 首先獲得當(dāng)前線程的當(dāng)前節(jié)點 curNode，這里每次獲取的 CLHNode節(jié)點的 locked狀態(tài)都為 false；
2. 然后將當(dāng)前 CLHNode節(jié)點的 locked狀態(tài)賦值為 true，表示當(dāng)前線程的一種有效狀態(tài)，即獲取到了鎖或正在等待鎖的狀態(tài)；
3. 因為尾指針 tailNode的總是指向了前一個線程的 CLHNode節(jié)點，因此這里利用尾指針 tailNode取出前一個線程的 CLHNode節(jié)點，然后賦值給當(dāng)前線程的前繼節(jié)點 predNode，并且將尾指針重新指向最后一個節(jié)點即當(dāng)前線程的當(dāng)前 CLHNode節(jié)點，以便下一個線程到來時使用；
4. 根據(jù)前繼節(jié)點（前一個線程）的 locked狀態(tài)判斷，若 locked為 false，則說明前一個線程釋放了鎖，當(dāng)前線程即可獲得鎖，不用自旋等待；若前繼節(jié)點的locked狀態(tài)為true，則表示前一線程獲取到了鎖或者正在等待，自旋等待。

為了更通俗易懂，我們用一個圖來說明。

**假如有這么一個場景：**有四個并發(fā)線程同時啟動執(zhí)行l(wèi)ock操作，假如四個線程的實際執(zhí)行順序為：threadA<--threadB<--threadC<--threadD

第一步，線程A過來，執(zhí)行了lock操作，獲得了鎖，此時locked狀態(tài)為true，如下圖：

第二步，線程B過來，執(zhí)行了lock操作，由于線程A還未釋放鎖，此時自旋等待，locked狀態(tài)也為true，如下圖：第三步，線程C過來，執(zhí)行了lock操作，由于線程B處于自旋等待，此時線程C也自旋等待（因此CLH鎖是公平鎖），locked狀態(tài)也為true，如下圖：第四步，線程D過來，執(zhí)行了lock操作，由于線程C處于自旋等待，此時線程D也自旋等待，locked狀態(tài)也為true，如下圖：

這就是多個線程并發(fā)加鎖的一個過程圖解，當(dāng)前線程只要判斷前一線程的locked狀態(tài)如果是true，那么則說明前一線程要么拿到了鎖，要么也處于自旋等待狀態(tài)，所以自己也要自旋等待。而尾指針tailNode總是指向最后一個線程的CLHNode節(jié)點。

4.3 CLH鎖的釋放鎖過程

前面用圖解結(jié)合代碼說明了CLH鎖的加鎖過程，那么，CLH鎖的釋放鎖的過程又是怎樣的呢？同樣，我們先貼下釋放鎖的代碼：

//?CLHLock.java

/**
?*?釋放鎖
?*/
public?void?unLock()?{
????//?獲取當(dāng)前線程的當(dāng)前節(jié)點
????CLHNode?node?=?curNode.get();
????//?進(jìn)行解鎖操作
????//?這里將locked至為false，此時執(zhí)行了lock方法正在自旋等待的后繼節(jié)點將會獲取到鎖
????//?【注意】而不是所有正在自旋等待的線程去并發(fā)競爭鎖
????node.locked?=?false;
????System.out.println("線程"?+?Thread.currentThread().getName()?+?"釋放了鎖?。?！");
????//?小伙伴們可以思考下，下面兩句代碼的作用是什么？？？
????CLHNode?newCurNode?=?new?CLHNode();
????curNode.set(newCurNode);

????//?【優(yōu)化】能提高GC效率和節(jié)省內(nèi)存空間，請思考：這是為什么？
????//?curNode.set(predNode.get());
}

可以看到釋放CLH鎖的過程代碼比加鎖簡單多了，下面同樣縷一縷：

1. 首先從當(dāng)前線程的線程本地變量中獲取出當(dāng)前 CLHNode節(jié)點，同時這個 CLHNode節(jié)點被后面一個線程的 preNode變量指向著；
2. 然后將 locked狀態(tài)置為 false即釋放了鎖；

注意：locked因為被volitile關(guān)鍵字修飾，此時后面自旋等待的線程的局部變量preNode.locked也為false，因此后面自旋等待的線程結(jié)束while循環(huán)即結(jié)束自旋等待，此時也獲取到了鎖。這一步驟也在異步進(jìn)行著。

3. 然后給當(dāng)前線程的表示當(dāng)前節(jié)點的線程本地變量重新賦值為一個新的 CLHNode。

思考：這一步看上去是多余的，其實并不是。請思考下為什么這么做？我們后續(xù)會繼續(xù)深入講解。

我們還是用一個圖來說說明CLH鎖釋放鎖的場景，接著前面四個線程加鎖的場景，假如這四個線程加鎖后，線程A開始釋放鎖，此時線程B獲取到鎖，結(jié)束自旋等待，然后線程C和線程D仍然自旋等待，如下圖：以此類推，線程B釋放鎖的過程也跟上圖類似，這里不再贅述。

4.4 同個線程加鎖釋放鎖再次正常獲取鎖

在前面4.3小節(jié)講到釋放鎖unLock方法中有下面兩句代碼：

??CLHNode?newCurNode?=?new?CLHNode();
??curNode.set(newCurNode);

這兩句代碼的作用是什么？這里先直接說結(jié)果：若沒有這兩句代碼，若同個線程加鎖釋放鎖后，然后再次執(zhí)行加鎖操作，這個線程就會陷入自旋等待的狀態(tài)。這是為啥，可能有些下伙伴也沒明白，勁越也是搞了蠻久才搞明白，嘿嘿。

下面我們同樣通過一步一圖的形式來分析這兩句代碼的作用。假如有下面這樣一個場景：線程A獲取到了鎖，然后釋放鎖，然后再次獲取鎖。

第一步：?線程A執(zhí)行了lock操作，獲取到了鎖，如下圖：

上圖的加鎖操作中，線程A的當(dāng)前CLHNode節(jié)點的locked狀態(tài)被置為true；然后tailNode指針指向了當(dāng)前線程的當(dāng)前節(jié)點；最后因為前繼節(jié)點的locked狀態(tài)為false，不用自旋等待，因此獲得了鎖。

第二步：?線程A執(zhí)行了unLock操作，釋放了鎖，如下圖：

上圖的釋放鎖操作中，線程A的當(dāng)前CLHNode節(jié)點的locked狀態(tài)被置為false，表示釋放了鎖；然后新建了一個新的CLHNode節(jié)點newCurNode，線程A的當(dāng)前節(jié)點線程本地變量值重新指向了newCurNode節(jié)點對象。

第三步：?線程A再次執(zhí)行l(wèi)ock操作，重新獲得鎖，如下圖：

上圖的再次獲取鎖操作中，首先將線程A的當(dāng)前CLHNode節(jié)點的locked狀態(tài)置為true；然后首先通過tailNode尾指針獲取到前繼節(jié)點即第一，二步中的curNode對象，然后線程A的前繼節(jié)點線程本地變量的值重新指向了重新指向了curNode對象；然后tailNode尾指針重新指向了新創(chuàng)建的CLHNode節(jié)點newCurNode對象。最后因為前繼節(jié)點的locked狀態(tài)為false，不用自旋等待，因此獲得了鎖。

擴(kuò)展：?注意到以上圖片的preNode對象此時沒有任何引用，所以當(dāng)下一次會被GC掉。前面是通過每次執(zhí)行unLock操作都新建一個新的CLHNode節(jié)點對象newCurNode，然后讓線程A的當(dāng)前節(jié)點線程本地變量值重新指向newCurNode。因此這里完全不用重新創(chuàng)建新的CLHNode節(jié)點對象，可以通過curNode.set(predNode.get());這句代碼進(jìn)行優(yōu)化，提高GC效率和節(jié)省內(nèi)存空間。

4.5 考慮同個線程加鎖釋放鎖再次獲取鎖異常的情況

現(xiàn)在我們把unLock方法的CLHNode newCurNode = new CLHNode();和curNode.set(newCurNode);這兩句代碼注釋掉，變成了下面這樣：

//?CLHLock.java

public?void?unLock()?{
????CLHNode?node?=?curNode.get();
????node.locked?=?false;
????System.out.println("線程"?+?Thread.currentThread().getName()?+?"釋放了鎖！?。?);
????/*CLHNode?newCurNode?=?new?CLHNode();
????curNode.set(newCurNode);*/
}

那么結(jié)果就是線程A通過加鎖，釋放鎖后，再次獲取鎖時就會陷入自旋等待的狀態(tài)，這又是為什么呢？我們下面來詳細(xì)分析。

第一步：?線程A執(zhí)行了lock操作，獲取到了鎖，如下圖：

上圖的加鎖操作中，線程A的當(dāng)前CLHNode節(jié)點的locked狀態(tài)被置為true；然后tailNode指針指向了當(dāng)前線程的當(dāng)前節(jié)點；最后因為前繼節(jié)點的locked狀態(tài)為false，不用自旋等待，因此獲得了鎖。這一步?jīng)]有什么異常。

第二步：?線程A執(zhí)行了unLock操作，釋放了鎖，如下圖：

現(xiàn)在已經(jīng)把unLock方法的CLHNode newCurNode = new CLHNode();和curNode.set(newCurNode);這兩句代碼注釋掉了，因此上圖的變化就是線程A的當(dāng)前CLHNode節(jié)點的locked狀態(tài)置為false即!可。

第三步:?線程A再次執(zhí)行l(wèi)ock操作，此時會陷入一直自旋等待的狀態(tài)，如下圖：通過上圖對線程A再次獲取鎖的lock方法的每一句代碼進(jìn)行分析，得知雖然第二步中將線程A的當(dāng)前CLHNode的locked狀態(tài)置為false了，但是在第三步線程A再次獲取鎖的過程中，將當(dāng)前CLHNode的locked狀態(tài)又置為true了，且尾指針tailNode指向的依然還是線程A的當(dāng)前當(dāng)前CLHNode節(jié)點。又因為每次都是將尾指針tailNode指向的CLHNode節(jié)點取出來給當(dāng)前線程的前繼CLHNode節(jié)點，之后執(zhí)行while(predNode.locked) {}語句時，此時因為predNode.locked = true，因此線程A就永遠(yuǎn)自旋等待了。

5 測試CLH鎖

下面我們通過一個Demo來測試前面代碼實現(xiàn)的CLH鎖是否能正常工作，直接上測試代碼：

//?CLHLockTest.java

/**
?*?用來測試CLHLocke生不生效
?*
?*?定義一個靜態(tài)成員變量cnt，然后開10個線程跑起來，看能是否會有線程安全問題
?*/
public?class?CLHLockTest?{
????private?static?int?cnt?=?0;

????public?static?void?main(String[]?args)?throws?Exception?{
????????final?CLHLock?lock?=?new?CLHLock();

????????for?(int?i?=?0;?i?100;?i++)?{
????????????new?Thread(()?->?{
????????????????lock.lock();

????????????????cnt++;

????????????????lock.unLock();
????????????}).start();
????????}
????????//?讓main線程休眠10秒，確保其他線程全部執(zhí)行完
????????Thread.sleep(10000);
????????System.out.println();
????????System.out.println("cnt----------->>>"?+?cnt);

????}
}

下面附運行結(jié)果截圖：

PS：?這里為了截圖全面，因此只開了10個線程。經(jīng)過勁越測試，開100個線程，1000個線程也不會存在線程安全問題。

6 小結(jié)

好了，前面我們通過多圖詳細(xì)說明了CLH鎖的原理與實現(xiàn)，那么我們再對前面的知識進(jìn)行一次小結(jié)：

1. 首先我們學(xué)習(xí)了自旋鎖和互斥鎖的概念與區(qū)別；
2. 然后我們學(xué)習(xí)了什么是CLH鎖以及為什么要學(xué)習(xí)CLH鎖；
3. 最后我們通過圖示+代碼實現(xiàn)的方式來學(xué)習(xí)CLH鎖的原理，從而為學(xué)習(xí)后面的AQS打好堅實的基礎(chǔ)。

特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：

長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝