CLH队列是由Craig, Landin 和 Hagersten设计的队列。它是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，它不断轮询前驱的状态，如果发现前驱释放了锁就结束自旋。
首先，我们来看一下基础的检查并设置（test-and-set）自旋锁。假设锁是一个布尔值，我们用一个伪代码进行演示。
func acquire(lock):
while true:
if atomic_test_and_set(lock.flag):
return 如果当前竞争很少的话，那这段代码的运行速度会非常快。但是如果有十个线程同时竞争同一个锁呢？你会有9个线程在不断尝试，这会消耗大量的CPU资源。我们有一些常用的方法可以减少这样的CPU浪费：队列锁。
队列锁意味着你给每个线程一个自有的锁，这样就不存在竞争了。然后你可以将它们连接在一起形成一个队列。这可能比较抽象，我们用一个例子来说明：
现在你想获取一个锁。首先你会试图将自己放入一个队列。如果放入成功，且队列为空，则你成功获取锁，这时候你会将自己标记为成功。如果放入成功，但是队列不为空，你会将自己标记为等待，并监听自己之前的节点。这个时候你可以选择自旋或者sleep。Java的AQS实现利用了sleep-waiting模式，避免自旋浪费CPU资源。
如果你获取锁成功，且使用完毕释放锁了。你会将自己成功标记去除
func acquire(lock, node):
node->flag = true
prev = node->prev = swap(lock, node)
while node->flag:
// spin or sleep
func release(node [inout]):
prev = node->prev
node->flag = false
node = prev CLH锁原理如下：
- 首先有一个尾节点指针，通过这个尾结点指针来构建等待线程的逻辑队列，因此能确保线程线程先到先服务的公平性，因此尾指针可以说是构建逻辑队列的桥梁；此外这个尾节点指针是原子引用类型，避免了多线程并发操作的线程安全性问题；
- 通过等待锁的每个线程在自己的某个变量上自旋等待，这个变量将由前一个线程写入。由于某个线程获取锁操作时总是通过尾节点指针获取到前一线程写入的变量，而尾节点指针又是原子引用类型，因此确保了这个变量获取出来总是线程安全的。
CLH锁的优点:
- 避免了惊群效应。假设100个线程在等待锁，锁释放之后，只会通知队列中的第一个线程去竞争锁。避免同时唤醒大量线程，浪费CPU资源。
- CLH队列锁的长处是空间复杂度低
CLH锁的缺点:
在NUMA系统结构下性能稍差。在这样的系统结构下，每一个线程有自己的内存，假设前趋结点的内存位置比較远。自旋推断前趋结点的locked域，性能将大打折扣，在SMP结构下还是非常有效的。【CLH自旋在前驱节点上，访问的是其他线程的变量值，在NUMA架构下，其他线程变量有可能是对端CPU的高速缓存，因此更适合SMP架构】
这周是一个简单的CLH解释。最近在学习Java8的并发代码。我会慢慢更新一些Java多线程的源码。