技術(shù)擴(kuò)展

SMP（對稱多處理器架構(gòu)）

• SMP(Symmetric Multi-Processor)，即對稱多處理器結(jié)構(gòu)，指服務(wù)器中多個CPU對稱工作，每個CPU訪問內(nèi)存地址所需時間相同。其主要特征是共享，包含對CPU，內(nèi)存，I/O等進(jìn)行共享。

image

• SMP優(yōu)點(diǎn)是能夠保證內(nèi)存一致性，缺點(diǎn)是這些共享的資源很可能成為性能瓶頸，隨著CPU數(shù)量的增加，每個CPU都要訪問相同的內(nèi)存資源，可能導(dǎo)致內(nèi)存訪問沖突，可能會導(dǎo)致CPU資源的浪費(fèi)。常用的PC機(jī)就屬于這種。

NUMA（非一致性內(nèi)存訪問）

• NUMA(Non-Uniform Memory Access)非一致存儲訪問， 將CPU分為CPU模塊，每個CPU模塊由多個CPU組成， 并且具有獨(dú)立的本地內(nèi)存、 I/O 槽口等，模塊之間可以通過互聯(lián)模塊相互訪問 ，訪問本地內(nèi)存的速度將遠(yuǎn)遠(yuǎn)高于訪問遠(yuǎn)地內(nèi)存 ( 系統(tǒng)內(nèi)其它節(jié)點(diǎn)的內(nèi)存 ) 的速度，這也是非一致存儲訪問 NUMA 的由來。

image

• NUMA優(yōu)點(diǎn)是可以較好地解決原來SMP系統(tǒng)的擴(kuò)展問題，缺點(diǎn)是由于訪問遠(yuǎn)程內(nèi)存的延時遠(yuǎn)遠(yuǎn)超過本地內(nèi)存，因此當(dāng)CPU數(shù)量增加時，系統(tǒng)性能無法線性增加。

自旋鎖和互斥鎖

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

自旋鎖

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

• 因此自旋鎖適用于鎖占用時間短的場合。

互斥鎖

• 互斥鎖說的是傳統(tǒng)意義的互斥鎖，就是多個線程并發(fā)競爭鎖的時候，沒有搶到鎖的線程會進(jìn)入休眠狀態(tài)即【sleep-waiting】，當(dāng)鎖被釋放時候，處于休眠狀態(tài)的一個線程會再次獲取到鎖。

• 缺點(diǎn)：就是這一些列過程需要線程切換，需要執(zhí)行很多CPU指令，同樣需要時間。如果CPU執(zhí)行線程切換的時間比鎖占用的時間還長，那么可能還不如使用自旋鎖。因此互斥鎖適用于鎖占用時間長的場合。

CLH鎖機(jī)制

CLH鎖其實(shí)就是一種是基于邏輯隊列非線程饑餓的一種自旋公平鎖，由于是 Craig、Landin 和 Hagersten三位大佬的發(fā)明，因此命名為CLH鎖，CLH是一種基于單向鏈表的高性能、能確保無饑餓性，提供先來先服務(wù)公平性的自旋鎖。

• 申請加鎖的線程通過前驅(qū)節(jié)點(diǎn)的變量進(jìn)行自旋。

• 前置節(jié)點(diǎn)解鎖后，當(dāng)前節(jié)點(diǎn)會結(jié)束自旋，并進(jìn)行加鎖。

CLH節(jié)點(diǎn)模型

• CLH隊列中的結(jié)點(diǎn)QNode中含有一個locked字段，該字段若為true表示該線程需要獲取鎖，且不釋放鎖，為false表示線程釋放了鎖。

• 結(jié)點(diǎn)之間是通過隱形的鏈表相連，之所以叫隱形的鏈表是因?yàn)檫@些結(jié)點(diǎn)之間沒有明顯的next指針，而是通過myPred所指向的結(jié)點(diǎn)的變化情況來影響myNode的行為。

CLH鎖原理

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

CLH鎖分析

• 在SMP架構(gòu)下，CLH更具有優(yōu)勢。

• 在NUMA架構(gòu)下，如果當(dāng)前節(jié)點(diǎn)與前驅(qū)節(jié)點(diǎn)不在同一CPU模塊下，跨CPU模塊會帶來額外的系統(tǒng)開銷，而MCS鎖更適用于NUMA架構(gòu)。

image

加鎖邏輯

1. 獲取當(dāng)前線程的鎖節(jié)點(diǎn)，如果為空，則進(jìn)行初始化；

2. sync方法獲取鏈表的尾節(jié)點(diǎn)，并將當(dāng)前節(jié)點(diǎn)置為尾節(jié)點(diǎn)，此時原來的尾節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的前置節(jié)點(diǎn)。

3. 如果尾節(jié)點(diǎn)為空，表示當(dāng)前節(jié)點(diǎn)是第一個節(jié)點(diǎn)，直接加鎖成功。

4. 如果尾節(jié)點(diǎn)不為空，則基于前置節(jié)點(diǎn)的鎖值（locked==true）進(jìn)行自旋，直到前置節(jié)點(diǎn)的鎖值變?yōu)閒alse。

解鎖邏輯

1. 獲取當(dāng)前線程對應(yīng)的鎖節(jié)點(diǎn)，如果節(jié)點(diǎn)為空或者鎖值為false，則無需解鎖，直接返回；

2. 【sync方法為尾節(jié)點(diǎn)賦空值，賦值不成功表示當(dāng)前節(jié)點(diǎn)不是尾節(jié)點(diǎn)，則需要將當(dāng)前節(jié)點(diǎn)的locked=false解鎖節(jié)點(diǎn)】。如果當(dāng)前節(jié)點(diǎn)是尾節(jié)點(diǎn)，則無需為該節(jié)點(diǎn)設(shè)置。

CLHLock上還有一個尾指針，始終指向隊列的最后一個結(jié)點(diǎn)。

CLHLock的類圖如下所示：

image

image

簡易代碼

// CLHLock.java

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

   // CLHLock構(gòu)造函數(shù)，用于新建CLH鎖節(jié)點(diǎn)時做一些初始化邏輯
   public CLHLock() {
       // 初始化時尾結(jié)點(diǎn)指向一個空的CLH節(jié)點(diǎn)
       tailNode = new AtomicReference<>(new CLHNode());
       // 初始化當(dāng)前的CLH節(jié)點(diǎn)
       curNode = new ThreadLocal() {
           @Override
           protected CLHNode initialValue() {
               return new CLHNode();
           }
       };
       // 初始化前繼節(jié)點(diǎn)，注意此時前繼節(jié)點(diǎn)沒有存儲CLHNode對象，存儲的是null
       predNode = new ThreadLocal();
   }
   /**
    * 獲取鎖
    */
   public void lock() {
       // 取出當(dāng)前線程ThreadLocal存儲的當(dāng)前節(jié)點(diǎn)，初始化值總是一個新建的CLHNode，locked狀態(tài)為false。
       CLHNode currNode = curNode.get();
       // 此時把lock狀態(tài)置為true，表示一個有效狀態(tài)，
       // 即獲取到了鎖或正在等待鎖的狀態(tài)
       currNode.locked = true;
       // 當(dāng)一個線程到來時，總是將尾結(jié)點(diǎn)取出來賦值給當(dāng)前線程的前繼節(jié)點(diǎn)；
       // 然后再把當(dāng)前線程的當(dāng)前節(jié)點(diǎn)賦值給尾節(jié)點(diǎn)
       // 【注意】在多線程并發(fā)情況下，這里通過AtomicReference類能防止并發(fā)問題
       // 【注意】哪個線程先執(zhí)行到這里就會先執(zhí)行predNode.set(preNode);語句，因此構(gòu)建了一條邏輯線程等待鏈
       // 這條鏈避免了線程饑餓現(xiàn)象發(fā)生
       CLHNode preNode = tailNode.getAndSet(currNode);
       // 將剛獲取的尾結(jié)點(diǎn)（前一線程的當(dāng)前節(jié)點(diǎn)）付給當(dāng)前線程的前繼節(jié)點(diǎn)ThreadLocal
       // 【思考】這句代碼也可以去掉嗎，如果去掉有影響嗎？
       predNode.set(preNode);
       // 【1】若前繼節(jié)點(diǎn)的locked狀態(tài)為false，則表示獲取到了鎖，不用自旋等待；
       // 【2】若前繼節(jié)點(diǎn)的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é)點(diǎn)
       CLHNode node = curNode.get();
       // 進(jìn)行解鎖操作
       // 這里將locked至為false，此時執(zhí)行了lock方法正在自旋等待的后繼節(jié)點(diǎn)將會獲取到鎖
       // 【注意】而不是所有正在自旋等待的線程去并發(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());
   }
}

代碼流程

1. 當(dāng)一個線程需要獲取鎖時，會創(chuàng)建一個新的QNode，將其中的locked設(shè)置為true表示需要獲取鎖。
2. 然后線程對tail域調(diào)用getAndSet方法，使自己成為隊列的尾部，同時獲取一個指向其前趨的引用myPred。
3. 然后該線程就在前趨結(jié)點(diǎn)的locked字段上旋轉(zhuǎn)，直到前趨結(jié)點(diǎn)釋放鎖。
4. 當(dāng)一個線程需要釋放鎖時，將當(dāng)前結(jié)點(diǎn)的locked域設(shè)置為false，同時回收前趨結(jié)點(diǎn)。

該算法也是空間有效的，如果有n個線程，L個鎖，每個線程每次只獲取一個鎖，那么需要的存儲空間是O（L+n），n個線程有n個myNode，L個鎖有L個tail。

這種算法有一個缺點(diǎn)是在NUMA系統(tǒng)架構(gòu)下性能表現(xiàn)很差，因?yàn)樗孕膌ocked是前驅(qū)線程的，如果內(nèi)存位置較遠(yuǎn)，那么性能會受到損失?！镜窃赟MP這種cache一致性的系統(tǒng)架構(gòu)上表現(xiàn)良好?！?/strong>

流程說明

• 線程A需要獲取鎖，其myNode域?yàn)閠rue，些時tail指向線程A的結(jié)點(diǎn)，然后線程B也加入到線程A后面，tail指向線程B的結(jié)點(diǎn)。

• 然后線程A和B都在它的myPred對象上旋轉(zhuǎn)，一旦它的myPred結(jié)點(diǎn)的locked字段變?yōu)閒alse，它就可以獲取鎖進(jìn)行繼續(xù)執(zhí)行業(yè)務(wù)方法。

• 明顯線程A的myPred locked域?yàn)閒alse，此時線程A獲取到了鎖，如下圖所示。

從代碼中可以看出lock方法中有一個while循環(huán)，這 是在等待前趨結(jié)點(diǎn)的locked域變?yōu)閒alse，這是一個自旋等待的過程。unlock方法很簡單，只需要將自己的locked域設(shè)置為false即可。

image

CLH優(yōu)缺點(diǎn)

唯一的缺點(diǎn)是在NUMA系統(tǒng)結(jié)構(gòu)下性能很差，在這種系統(tǒng)結(jié)構(gòu)下，每個線程有自己的內(nèi)存，如果前趨結(jié)點(diǎn)的內(nèi)存位置比較遠(yuǎn)，自旋判斷前趨結(jié)點(diǎn)的locked域，性能將大打折扣，但是在SMP系統(tǒng)結(jié)構(gòu)下該法還是非常有效的。一種解決NUMA系統(tǒng)結(jié)構(gòu)的思路是MCS隊列鎖。