CLH锁学习

CLH锁即Craig, Landin, and Hagersten (CLH) locks，CLH锁是一个自旋锁，能确保无饥饿性，提供先来先服务的公平性。
何谓自旋锁？它是为实现保护共享资源而提出一种锁机制。其实，自旋锁与互斥锁比较类似，它们都是为了解决对某项资源的互斥使用。无论是互斥锁，还是自旋锁，在任何时刻，最多只能有一个保持者，也就说，在任何时刻最多只能有一个执行单元获得锁。但是两者在调度机制上略有不同。对于互斥锁，如果资源已经被占用，资源申请者只能进入睡眠状态。但是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁，"自旋"一词就是因此而得名。

CLHLock的java实现逻辑:

 

public class CLHLock implements Lock {
    private final AtomicReference tail;
    private final ThreadLocal myPred;
    private final ThreadLocal myNode;

    public CLHLock() {
        tail = new AtomicReference(new QNode());
        myNode = new ThreadLocal() {
            protected QNode initialValue() {
                return new QNode();
            }
        };

        myPred = new ThreadLocal();
    }

    @Override
    public void lock() {
        QNode node = myNode.get();
        node.locked = true;
        QNode pred = tail.getAndSet(node);
        myPred.set(pred);
        while (pred.locked) {
        }
    }

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

    private static class QNode {
        volatile boolean locked;
    }
}

 

锁本身被表示成QNode的虚拟链表。共享的tail保存申请的最后的一个申请lock的线程的myNode域。每个申请lock的线程通过一个本地线程变量pred指向它的前驱。另外一个本地线程变量myNode的locked保存本身的状态，true：正在申请锁或已申请到锁；false：已释放锁。每个线程通过监视自身的前驱状态，自旋等待锁被释放。释放锁时，把自身myNode的locked设为false，使后继线程获的锁，并回收前驱的QNode，等待下次使用，因为自身的QNode可能被tail获后继引用，而前驱不再使用老的QNode。

AbstractQueuedSynchronizer的实现也是部分基于"CLH"队列的思想。具体见AbstractQueuedSynchronizer的doAcquireSharedInterruptibly方法实现
AbstractQueuedSynchronizer 为实现依赖于先进先出 (FIFO) 等待队列的阻塞锁定和相关同步器（信号量、事件，等等）提供一个框架。用java的人都知道synchronized能够对一个需要确保线程安全的对象，方法实现多线程并发控制，这是在java语法层次的实现，而AbstractQueuedSynchronizer 则是在应用层次而不是语法层次（更高的层次）提供了实现多线程并发控制组件的基础。