源码阅读笔记：J.U.C CLH lock

2019-11-06 07:32:01

字体：大中小

来源：转载

供稿：网友

java.utils.concurrency（J.U.C）中提供了一系列对锁的封装，如ReentrantLock、CountDownLatch等，而这其中用到的实现又都基于AbstractQueuedSynchronizer（AQS）。而CLH算法又是AQS实现的基础，所以网上查阅了一些资料，总结在此。

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是一种独占、公平锁，可以每个线程总会等到自己能征用锁的机会，并严格按照征用的先后顺序。看到自旋锁（spinlock），指的应该是JDK1.4.2引入的一种锁的优化方式。通常意义上的锁，会使等待该锁的线程进入BLOCK状态，而对于实现于内核线程之上Java线程而言，每次挂起与恢复都需要切换到内核态，这对性能是极大的开销。而自旋锁即是让线程进行忙循环（自旋），直到锁得到释放为止。但由于自旋本身也是对CPU的占用（并不处理任何有用逻辑），并且如果大量线程都长时间处于自旋，反而会带来性能的下降。详细的看看CLH的实现：

public class CLHLock implements Lock { private static class Qnode { // volatile保证了可见性 // 当解锁时，等待中的线程可以立刻获知 public volatile boolean locked = false; } AtomicReference<QNode> tail = new AtomicReference<QNode>(new QNode()); ThreadLocal<QNode> myPred; ThreadLocal<QNode> myNode; public CLHLock() { tail = new AtomicReference<QNode>(new QNode()); myNode = new ThreadLocal<QNode>() { protected QNode initialValue() { return new QNode(); } }; myPred = new ThreadLocal<QNode>() { protected QNode initialValue() { return null; } }; } @Override public void lock() { QNode qnode = myNode.get(); qnode.locked = true; QNode pred = tail.getAndSet(qnode); myPred.set(pred); while (pred.locked) {} //spinning, 自旋 } @Override public void unlock() { QNode qnode = myNode.get(); qnode.locked = false; myNode.set(myPred.get()); }}

从代码可以看出，CLH本质是一个链表，每个线程利用ThreadLocalStorage记录自己以及自己的前驱节点，一直自旋观察着前驱节点的状态，直到前驱节点不再征用（可能也在自旋等待锁，也可能是未释放锁）这个锁为止。这所有的信息通过一个AutomaticReference类型的tail（始终指向最后一个征用锁的线程）来相互传递。当一个新的线程征用CLH锁时，状态变化如下图所示。

CLH lock 示意