摘要：是獨占式鎖的一種，并且是不可重入的鎖，這篇文章是對鎖源代碼分析的預熱篇

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.

CLH鎖是自旋鎖的一種，對它的研究是因為AQS源代碼中使用了CLH鎖的一個變種，為了更好的理解AQS中使用鎖的思想，所以決定先好好理解CLH鎖

public class ClhSpinLock implements Lock{
    private final ThreadLocal prev;
    private final ThreadLocal node;
    private final AtomicReference tail = new AtomicReference(new Node());

    public ClhSpinLock() {
        this.node = new ThreadLocal() {
            protected Node initialValue() {
                return new Node();
            }
        };

        this.prev = new ThreadLocal() {
            protected Node initialValue() {
                return null;
            }
        };
    }

    /**
     * 1.初始狀態 tail指向一個node(head)節點 
     * +------+ 
     * | head | <---- tail 
     * +------+
     * 
     * 2.lock-thread加入等待隊列: tail指向新的Node，同時Prev指向tail之前指向的節點
     * +----------+
     * | Thread-A |
     * | := Node  | <---- tail
     * | := Prev  | -----> +------+
     * +----------+        | head |
     *                     +------+ 
     * 
     *             +----------+            +----------+
     *             | Thread-B |            | Thread-A |
     * tail ---->  | := Node  |     -->    | := Node  | 
     *             | := Prev  | ----|      | := Prev  | ----->  +------+
     *             +----------+            +----------+         | head |
     *                                                          +------+ 
     * 3.尋找當前node的prev-node然后開始自旋
     * 
     */
    public void lock() {
        final Node node = this.node.get();
        node.locked = true;
        Node pred = this.tail.getAndSet(node);
        this.prev.set(pred);
        // 自旋
        while (pred.locked);
    }

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

    @Override
    public void lockInterruptibly() throws InterruptedException {
        // TODO Auto-generated method stub
        
    }

    @Override
    public boolean tryLock() {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public Condition newCondition() {
        // TODO Auto-generated method stub
        return null;
    }
    
    private static class Node {
        private volatile boolean locked;
    }
}

簡單的看一下CLH的算法定義

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.

基于list，線程僅在一個局部變量上自旋，它不斷輪詢前一個節點狀態，如果發現前一個節點釋放鎖結束.

所以在java中使用了ThreadLocal作為具體實現,AtomicReference為了消除多個線程并發對tail引用Node的影響，核心方法lock()中分為3個步驟去實現

初始狀態 tail指向一個node(head)節點

private final AtomicReference tail = new AtomicReference(new Node());

thread加入等待隊列: tail指向新的Node，同時Prev指向tail之前指向的節點，在java代碼中使用了getAndSet即CAS操作使用

Node pred = this.tail.getAndSet(node);
this.prev.set(pred);

尋找當前線程對應的node的前驅node然后開始自旋前驅node的status判斷是否可以獲取lock

while (pred.locked);

同理unlock()方法，獲取當前線程的node，設置lock status，將當前node指向前驅node(這樣操作tail指向的就是前驅node等同于出隊操作).至此CLH Lock的過程就結束了

public class LockTest {
    static int count = 0;
    
    public static void testLock(Lock lock) {
        try {
            lock.lock();
            for (int i = 0; i < 10000000; i++) ++count;
        } finally {
            lock.unlock();
        }
    }
    
    public static void main(String[] args) throws InterruptedException, BrokenBarrierException {
        final ClhSpinLock clh = new ClhSpinLock();
        final CyclicBarrier cb = new CyclicBarrier(10, new Runnable() {
            @Override
            public void run() {
                System.out.println(count);
            }
        });
        
        for (int i = 0; i < 10; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    testLock(clh);
                    // 這段代碼是非lock比較使用
//                    for (int i = 0; i < 10000000; i++)
//                        count++;
                    try {
                        cb.await();
                    } catch (InterruptedException | BrokenBarrierException e) {
                        e.printStackTrace();
                    }
                }
            }).start();
        }
    }
}

測試代碼使用了CyclicBarrier輔助當所有子線程完成后輸出static變量count的值
結果發現輸出的值和預期一樣，CLH Lock完成了獨占式鎖的功能

CLH Lock是一種比較簡單的自旋鎖算法之一，因為鎖的CAS操作涉及到了硬件的鎖定(鎖總線或者是鎖內存)所以性能和CPU架構也密不可分，該興趣的同學可以繼續深入研究包括MCS鎖等。CLH Lock是獨占式鎖的一種，并且是不可重入的鎖，這篇文章是對AQS鎖源代碼分析的預熱篇