@[toc]

背景

相信大部分人在看AQS的時候都能看到注釋上有這么一段話：

The wait queue is a variant of a "CLH" (Craig, Landin, and Hagersten) lock queue.

為了更好的理解AQS中使用鎖的思想，所以決定先好好理解CLH鎖。
在網上能查到很多關于CLH的博客，但不如我想象中的那么全面，于是自己來整理一篇清晰點的。

原理解釋

論文地址
CLH的作者：Craig, Landin, and Hagersten毁嗦。

CLH lock is Craig, Landin, and Hagersten (CLH) locks, 
CLH lock is a spin lock, can ensure no hunger, provide fairness first come first service.
The CLH lock is a scalable, high performance, fairness and spin lock based on the list, 
the application thread spin only on a local variable, it constantly polling the precursor state, 
if it is found that the pre release lock end spin.

我們能看到它是一個自旋鎖，能確保無饑餓性回铛，提供先來先服務的公平性狗准。同時它也是一種基于鏈表的可擴展、高性能茵肃、公平的自旋鎖腔长，申請線程只在本地變量上自旋，它不斷輪詢前驅的狀態(tài)验残，如果發(fā)現(xiàn)前驅釋放了鎖就結束自旋饼酿。

這個算法很妙的點在于，在一個CAS操作幫助下胚膊，所有等待獲取鎖的線程之下的節(jié)點輕松且正確地構建成了全局隊列。等待中的線程正如隊列中的節(jié)點依次獲取鎖想鹰。

接下來就說一下這個算法的Java實現(xiàn)紊婉。

Java代碼實現(xiàn)

CLHLock類結構

這里面貼出的代碼是主要流程代碼，詳細代碼在GitHub中辑舷。

定義QNode

CLH隊列中的節(jié)點QNode中含有一個locked字段喻犁，該字段若為true表示該線程需要獲取鎖，且不釋放鎖何缓，為false表示線程釋放了鎖肢础。

public class QNode {
   
    volatile boolean locked;
}

定義Lock接口

public interface Lock {
 
    void lock();
 
    void unlock();
}

定義CLHLock

節(jié)點之間是通過隱形的鏈表相連，之所以叫隱形的鏈表是因為這些節(jié)點之間沒有明顯的next指針碌廓，而是通過myPred所指向的節(jié)點的變化情況來影響myNode的行為传轰。CLHLock上還有一個尾指針，始終指向隊列的最后一個節(jié)點谷婆。

public class CLHLock implements Lock {
    // 尾巴慨蛙，是所有線程共有的一個。所有線程進來后纪挎，把自己設置為tail
    private final AtomicReference<QNode> tail;
    // 前驅節(jié)點期贫，每個線程獨有一個。
    private final ThreadLocal<QNode> myPred;
    // 當前節(jié)點异袄，表示自己通砍，每個線程獨有一個。
    private final ThreadLocal<QNode> myNode;

    public CLHLock() {
        this.tail = new AtomicReference<>(new QNode());
        this.myNode = ThreadLocal.withInitial(QNode::new);
        this.myPred = new ThreadLocal<>();
    }

    @Override
    public void lock() {
        // 獲取當前線程的代表節(jié)點
        QNode node = myNode.get();
        // 將自己的狀態(tài)設置為true表示獲取鎖烤蜕。
        node.locked = true;
        // 將自己放在隊列的尾巴封孙，并且返回以前的值迹冤。第一次進將獲取構造函數(shù)中的那個new QNode
        QNode pred = tail.getAndSet(node);
        // 把舊的節(jié)點放入前驅節(jié)點。
        myPred.set(pred);
        // 在等待前驅節(jié)點的locked域變?yōu)閒alse敛瓷，這是一個自旋等待的過程
        while (pred.locked) {
        }
        // 打印myNode叁巨、myPred的信息
        peekNodeInfo();
    }

    @Override
    public void unlock() {
        // unlock. 獲取自己的node。把自己的locked設置為false呐籽。
        QNode node = myNode.get();
        node.locked = false;
        myNode.set(myPred.get());
    }
}

使用場景

public class KFC {
    private final Lock lock = new CLHLock();
    private int i = 0;

    public void takeout() {
        try {
            lock.lock();
            System.out.println(Thread.currentThread().getName() + ": 拿了第" + ++i + "份外賣");
            Thread.sleep(100);
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
}

運行代碼

public static void main(String[] args) {
    final KFC kfc = new KFC();
    Executor executor = Executors.newFixedThreadPool(5);
    for (int i = 1; i <= 35; i++) {
        executor.execute(kfc::takeout);
    }
}

代碼輸出

為什么輸出這么多日志后面有解釋锋勺。

thread-1 acquire lock success. myNode(QNode_2_locked:true), myPred(QNode_1_locked:false)
thread-1: 拿了第1份外賣
thread-2 acquire lock success. myNode(QNode_3_locked:true), myPred(QNode_2_locked:false)
thread-2: 拿了第2份外賣
thread-3 acquire lock success. myNode(QNode_4_locked:true), myPred(QNode_3_locked:false)
thread-3: 拿了第3份外賣
thread-4 acquire lock success. myNode(QNode_5_locked:true), myPred(QNode_4_locked:false)
thread-4: 拿了第4份外賣
thread-5 acquire lock success. myNode(QNode_6_locked:true), myPred(QNode_5_locked:false)
thread-5: 拿了第5份外賣
----------------------------------------------------------------------------------------
thread-1 acquire lock success. myNode(QNode_1_locked:true), myPred(QNode_6_locked:false)
thread-1: 拿了第6份外賣
thread-2 acquire lock success. myNode(QNode_2_locked:true), myPred(QNode_1_locked:false)
thread-2: 拿了第7份外賣
thread-3 acquire lock success. myNode(QNode_3_locked:true), myPred(QNode_2_locked:false)
thread-3: 拿了第8份外賣
thread-4 acquire lock success. myNode(QNode_4_locked:true), myPred(QNode_3_locked:false)
thread-4: 拿了第9份外賣
thread-5 acquire lock success. myNode(QNode_5_locked:true), myPred(QNode_4_locked:false)
thread-5: 拿了第10份外賣
----------------------------------------------------------------------------------------
thread-1 acquire lock success. myNode(QNode_6_locked:true), myPred(QNode_5_locked:false)
thread-1: 拿了第11份外賣
thread-2 acquire lock success. myNode(QNode_1_locked:true), myPred(QNode_6_locked:false)
thread-2: 拿了第12份外賣
thread-3 acquire lock success. myNode(QNode_2_locked:true), myPred(QNode_1_locked:false)
thread-3: 拿了第13份外賣
thread-4 acquire lock success. myNode(QNode_3_locked:true), myPred(QNode_2_locked:false)
thread-4: 拿了第14份外賣
thread-5 acquire lock success. myNode(QNode_4_locked:true), myPred(QNode_3_locked:false)
thread-5: 拿了第15份外賣
----------------------------------------------------------------------------------------
thread-1 acquire lock success. myNode(QNode_5_locked:true), myPred(QNode_4_locked:false)
thread-1: 拿了第16份外賣
thread-2 acquire lock success. myNode(QNode_6_locked:true), myPred(QNode_5_locked:false)
thread-2: 拿了第17份外賣
thread-3 acquire lock success. myNode(QNode_1_locked:true), myPred(QNode_6_locked:false)
thread-3: 拿了第18份外賣
thread-4 acquire lock success. myNode(QNode_2_locked:true), myPred(QNode_1_locked:false)
thread-4: 拿了第19份外賣
thread-5 acquire lock success. myNode(QNode_3_locked:true), myPred(QNode_2_locked:false)
thread-5: 拿了第20份外賣
----------------------------------------------------------------------------------------
thread-1 acquire lock success. myNode(QNode_4_locked:true), myPred(QNode_3_locked:false)
thread-1: 拿了第21份外賣
thread-2 acquire lock success. myNode(QNode_5_locked:true), myPred(QNode_4_locked:false)
thread-2: 拿了第22份外賣
thread-3 acquire lock success. myNode(QNode_6_locked:true), myPred(QNode_5_locked:false)
thread-3: 拿了第23份外賣
thread-4 acquire lock success. myNode(QNode_1_locked:true), myPred(QNode_6_locked:false)
thread-4: 拿了第24份外賣
thread-5 acquire lock success. myNode(QNode_2_locked:true), myPred(QNode_1_locked:false)
thread-5: 拿了第25份外賣
----------------------------------------------------------------------------------------
thread-1 acquire lock success. myNode(QNode_3_locked:true), myPred(QNode_2_locked:false)
thread-1: 拿了第26份外賣
thread-2 acquire lock success. myNode(QNode_4_locked:true), myPred(QNode_3_locked:false)
thread-2: 拿了第27份外賣
thread-3 acquire lock success. myNode(QNode_5_locked:true), myPred(QNode_4_locked:false)
thread-3: 拿了第28份外賣
thread-4 acquire lock success. myNode(QNode_6_locked:true), myPred(QNode_5_locked:false)
thread-4: 拿了第29份外賣
thread-5 acquire lock success. myNode(QNode_1_locked:true), myPred(QNode_6_locked:false)
thread-5: 拿了第30份外賣
----------------------------------------------------------------------------------------
thread-1 acquire lock success. myNode(QNode_2_locked:true), myPred(QNode_1_locked:false)
thread-1: 拿了第31份外賣
thread-2 acquire lock success. myNode(QNode_3_locked:true), myPred(QNode_2_locked:false)
thread-2: 拿了第32份外賣
thread-3 acquire lock success. myNode(QNode_4_locked:true), myPred(QNode_3_locked:false)
thread-3: 拿了第33份外賣
thread-4 acquire lock success. myNode(QNode_5_locked:true), myPred(QNode_4_locked:false)
thread-4: 拿了第34份外賣
thread-5 acquire lock success. myNode(QNode_6_locked:true), myPred(QNode_5_locked:false)
thread-5: 拿了第35份外賣

代碼解釋

CLHLock的加鎖、釋放鎖過程

當一個線程需要獲取鎖時狡蝶，會創(chuàng)建一個新的QNode庶橱，將其中的locked設置為true表示需要獲取鎖，然后線程對tail域調用getAndSet方法贪惹，使自己成為隊列的尾部苏章，同時返回舊的尾部節(jié)點作為其前驅引用myPred,然后該線程就在前驅節(jié)點的locked字段上自旋，直到前驅節(jié)點釋放鎖奏瞬。
當一個線程需要釋放鎖時枫绅，將當前節(jié)點的locked域設置為false，同時回收前驅節(jié)點硼端。如下圖所示并淋，線程A需要獲取鎖，其myNode域為true珍昨，此時tail指向線程A的節(jié)點县耽，然后線程B也加入到線程A后面，tail指向線程B的節(jié)點镣典。然后線程A和B都在它的myPred域上旋轉兔毙，一旦它的myPred節(jié)點的locked字段變?yōu)閒alse，它就可以獲取到鎖兄春。明顯線程A的myPred locked值為false澎剥，此時線程A獲取到了鎖。
<img src="https://img-blog.csdnimg.cn/20200719100502129.png" width="60%" alt="CLHLock示意圖"/>

第一個使用CLHLock的線程自動獲取到鎖

初始狀態(tài)的tail的值是一個新的QNode神郊，locked的值是默認的false肴裙。后面新加入的QNode在獲取鎖的時候都把locked置為true后放入尾節(jié)點并成為前驅節(jié)點。

為什么使用ThreadLocal保存myNode和myPred涌乳？

因為每個線程使用lock方法的時候蜻懦，將QNode綁定到當前線程上，等unlock操作的時候還可以獲取到本線程之前調用lock方法里創(chuàng)建的QNode對象夕晓。

為什么tail要用AtomicReference修飾宛乃？

因為我們在把尾節(jié)點更新成當前節(jié)點并返回舊的尾節(jié)點作為前驅節(jié)點的時候，我們希望這個操作是原子性的，AtomicReference的getAndSet()方法正好能滿足我們的需求征炼。

unlock中的set操作怎么理解析既？

也就是這一段代碼：

myNode.set(myPred.get());

它有以下幾點影響：

將當前node指向前驅node，lock方法中再也拿不到當前node的引用了谆奥。這樣操作等于把當前node從鏈表頭部刪除（并不是被JVM回收眼坏，第二個線程的myPred還引用它）
當前線程若要在unlock之后再次拿鎖需重新排隊（每個線程自己都維護了兩個QNode，一個在釋放鎖的時候把當前node置為前驅node酸些，另一個在lock方法的時候重新獲取尾node作為前驅node）
如果所有的任務都是由固定數(shù)量的線程池執(zhí)行的話宰译，你會看到所有的QNode的使用會形成一個環(huán)形鏈表（實際不是），在打印日志中可看到魄懂，日志“拿了第31份”和日志“拿了第1份”的myNode和myPred一樣沿侈。

為什么要有myPred，不用行不行市栗？

也就是代碼改成這樣：

public void lock() {
    QNode node = myNode.get();
    node.locked = true;

    // spin on pre-node
    QNode pred = tail.getAndSet(node);
    while (pred.locked) {
    }
}

public void unlock() {
    QNode node = myNode.get();
    node.locked = false;
}

答案肯定是不行啦缀拭。
假設有兩個線程：T1 & T2，T1持有鎖填帽，T2等待T1釋放鎖蛛淋。
這時候T1.node.locked為true套鹅，T2.node.locked也為true枕荞，tail變量指向T2.node瀑粥，卻T2正在pred.locked自旋音比。這里的pred也是T1.node。

現(xiàn)在T1開始釋放鎖（設置T1.node.locked為false）并且在T2搶占到鎖之前再次獲取鎖苫拍，此時T1.node.locked再次變成true，但是此時的尾節(jié)點是T2.node，所以T1只好等待T2釋放鎖绘迁。而T2也在等待T1釋放鎖，死鎖發(fā)生了卒密。

再結合上面myNode.set(myPred.get())代碼的解釋缀台，myPred變量提供了兩點好處：

防止死鎖發(fā)生，釋放鎖的時候也就釋放了當前節(jié)點的引用哮奇。
等待隊列中節(jié)點具有順序性（看日志打犹鸥）可保證鎖競爭公平，每個等待鎖的線程都持有前驅節(jié)點的引用（getAndSet返回）鼎俘，n個線程最后有n+1的節(jié)點（有一個是初始tail的node）哲身，所有的節(jié)點按照順序循環(huán)使用。借助于myPred在釋放鎖后若要再次拿鎖需排隊且排在最后贸伐。

CLH優(yōu)缺點

CLH隊列鎖的優(yōu)點是空間復雜度低（如果有n個線程勘天，L個鎖，每個線程每次只獲取一個鎖，那么需要的存儲空間是O（L+n）脯丝，n個線程有n個QNode商膊，L個鎖有L個tail）。

CLH的一種變體被應用在了JAVA并發(fā)框架中宠进。唯一的缺點是在NUMA系統(tǒng)結構下性能很差晕拆，在這種系統(tǒng)結構下，每個線程有自己的內存材蹬，如果前趨結點的內存位置比較遠实幕，自旋判斷前趨結點的locked域，性能將大打折扣赚导，但是在SMP系統(tǒng)結構下該法還是非常有效的茬缩。一種解決NUMA系統(tǒng)結構的思路是MCS隊列鎖。

NUMA與SMP

SMP(Symmetric Multi-Processor)吼旧，即對稱多處理器結構凰锡，指服務器中多個CPU對稱工作，每個CPU訪問內存地址所需時間相同圈暗。其主要特征是共享掂为，包含對CPU，內存员串，I/O等進行共享勇哗。SMP的優(yōu)點是能夠保證內存一致性，缺點是這些共享的資源很可能成為性能瓶頸寸齐，隨著CPU數(shù)量的增加欲诺，每個CPU都要訪問相同的內存資源，可能導致內存訪問沖突渺鹦，可能會導致CPU資源的浪費扰法。常用的PC機就屬于這種。

NUMA(Non-Uniform Memory Access)非一致存儲訪問毅厚，將CPU分為CPU模塊塞颁，每個CPU模塊由多個CPU組成，并且具有獨立的本地內存吸耿、I/O槽口等祠锣，模塊之間可以通過互聯(lián)模塊相互訪問，訪問本地內存的速度將遠遠高于訪問遠地內存(系統(tǒng)內其它節(jié)點的內存)的速度咽安，這也是非一致存儲訪問NUMA的由來伴网。NUMA優(yōu)點是可以較好地解決原來SMP系統(tǒng)的擴展問題，缺點是由于訪問遠地內存的延時遠遠超過本地內存妆棒，因此當CPU數(shù)量增加時是偷，系統(tǒng)性能無法線性增加拳氢。

最后

我的疑惑點都在上文敘述了，如果還有不清晰的地方蛋铆，希望可以在評論區(qū)指出馋评，謝謝??

參考

A Hierarchical CLH Queue Lock
JAVA并發(fā)編程學習筆記之CLH隊列鎖
 CLH lock 原理及JAVA實現(xiàn)
Why CLH Lock need prev-Node in java

CLH lock queue的原理解釋及Java實現(xiàn)