CLH 锁

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框架的困惑，在看到AQS共享锁的实现时，不得要领，先看点简单的。
CLH锁，通过对前一个节点的自旋提供公平的竞争锁的机会，严格的先到先得。
CLH的实现很巧妙，对于多线程的控制值得学习，要点如下：

1. 两个ThreadLocal变量，一个保存当前节点，一个保存前继节点
2. 队列是隐式存在的，多个线程安全的竞争tail（由CAS方式实现），继而加入队列
3. 每个线程尝试用自己去替换tail节点，并把之前的tail节点记录自己的为prev节点，通过循环访问prev节点的lock标志位，来等待获取锁
4. 线程释放锁之后，将当前节点设置为前继节点，相当于队列的出队（个人认为这行代码即使没写，也不影响实现，只是加上之后，所有释放锁的线程都指向同一个节点，有利于垃圾回收）

public class CLHLock {
    private final ThreadLocal<Node> prev; //保存当前线程的前继节点
    private final ThreadLocal<Node> node; //保存当前线程的节点
    //类在初始化时会初始化tail节点，相当于head节点(注意对隐式队列的理解)
    private final AtomicReference<Node> tail = new AtomicReference<Node>(new Node());

    public CLHLock() {
        this.prev = new ThreadLocal<Node>() {
            @Override
            protected Node initialValue() {
                return null;
            }
        };
        this.node = new ThreadLocal<Node>() {
            @Override
            protected Node initialValue() {
                return new Node();
            }
        };
    }

    public void lock() {
        Node node = this.node.get(); //获取Threadlocal变量，每个线程私有
        node.lock = true;
        //CAS方式设置tail节点，设置成功，相当于加入队列
        Node pred = this.tail.getAndSet(node); 
        //把之前的tail节点，存入自己的prev节点，并循环访问其lock标志位，等待释放
        this.prev.set(pred); 
        while (pred.lock) ;
    }

    public void unlock() {
        Node node = this.node.get();
        node.lock = false;
        //线程释放锁之后，将当前节点设置为前继节点，相当于队列的出队（利于GC）
        this.node.set(this.prev.get());
    }

    private class Node {
        //默认初始化值为false
        private volatile boolean lock;
    }
}

画了个草图，辅助理解：

CLH.jpg

参考: 克雷格.兰丁&hagersten (CLH Lock)