面试系列之-CLH自旋锁（JAVA基础）

CLHCLH锁其实就是一种基于队列（具体为单向链表）排队的自旋锁，也叫CLH队列锁；简单的CLH锁可以基于单向链表实现，申请加锁的线程首先会通过CAS操作在单向链表的尾部增加一个节点，之后该线程只需要在其前驱节点上进行普通自旋，等待前驱节点释放锁即可。由于CLH锁只有在节点入队时进行一下CAS的操作，在节点加入队列之后，抢锁线程不需要进行CAS自旋，只需普通自旋即可。因此在争用激烈的场景下，CLH锁能大大减少CAS操作的数量，以避免CPU的总线风暴；

CLH锁的原理分析

（1）初始状态队列尾部属性（tail）指向一个EMPTY节点，tail属性使用AtomicReference类型是为了使得多个线程并发操作tail时不会发生线程安全问题；

/**
* CLHLock队列的尾部指针，使用AtomicReference，方便进行CAS操作
*/
private AtomicReference<Node> tail = new AtomicReference<>(null);
public CLHLock()
{
    //设置尾部节点
    tail.getAndSet(Node.EMPTY);
}

（2）Thread在抢锁时会创建一个新的Node加入等待队列尾部：tail指向新的Node，同时新的Node的preNode属性指向tail之前指向的节点，并且以上操作通过CAS自旋完成，以确保操作成功；

Node curNode = new Node(true, null);
Node preNode = tail.get();
//CAS自旋：将当前节点插入队列的尾部
while (!tail.compareAndSet(preNode, curNode))
{
    preNode = tail.get();
}
//设置前驱节点
curNode.setPrevNode(preNode);

（3）Thread加入抢锁队列之后，会在前驱节点上自旋：循环判断前驱节点的locked属性是否为false，如果为false就表示前驱节点释放了锁，当前线程抢占到锁；

// 普通自旋，监听前驱节点的locked变量，直到其值为false
// 若前驱节点的locked状态为true，则表示前一个线程还在抢占或者占有锁
while (curNode.getPrevNode().isLocked())
{
    //让出CPU时间片，提高性能
    Thread.yield();
}
// 能执行到这里，说明当前线程获取到了锁
//将当前节点缓存在线程本地变量中，释放锁会用到
curNodeLocal.set(curNode);

（4）Thread抢到锁之后，它的locked属性一直为true，一直到临界区代码执行完，然后调用unlock()方法释放锁，释放之后其locked属性才为false；

public void unlock()
{
    Node curNode = curNodeLocal.get();
    curNode.setPrevNode(null); //help for GC
    curNodeLocal.set(null); //以便下一次抢锁
    curNode.setLocked(false);
}

释放锁操作为：线程从本地变量curNodeLocal中获取当前节点curNode，将其状态设置为false，以便其后继节点能获得锁。线程在设置当前节点curNode的locked状态为false前，为了GC能回收前驱节点，需要将curNode前驱节点引用设置为空。另外，为了使得线程下一次抢锁不会出错，需要将线程本地变量curNodeLocal中的节点引用设置为空；

CLH锁的抢占过程

有三个并发线程同时抢占CLHLock锁，三个线程的实际执行顺序为Thread A<--Thread B<--Thread C。

第一步：线程A开始执行了lock操作，创建一个节点nodeA，设置它的locked状态为true，然后设置它的前驱为CLHLock.tail（此时为EMPTY），并将CLHLock.tail设置为nodeA，之后线程A开始在它的前驱节点上进行普通自旋；

第二步：线程B开始执行lock操作，创建一个节点nodeB，设置它的locked状态为true，然后设置它的前驱节点为CLHLock.tail（此时为nodeA），并将CLHLock.tail设置为nodeB，之后线程B开始在它的前驱节点上进行普通自旋；

第三步：线程C开始执行lock操作，创建一个节点nodeC，设置它的locked状态为true，然后设置它的前驱节点为CLHLock.tail（此时为nodeB），并将CLHLock.tail设置为nodeC，之后线程C开始在它的前驱节点上进行普通自旋；

（1）CLHLock的尾指针tail总是指向最后一个线程的节点。

（2）CLHLock队列中的抢锁线程一直进行普通自旋，循环判断前

一个线程的locked状态，如果是true，那么说明前一个线程处于自旋等待状态或正在执行临界区代码，所以自己需要自旋等待。

CLH锁的释放过程

第一步：线程A执行完临界区代码后开始unlock（释放）操作，设置nodeA的前驱引用为null，锁状态locked为false；

第二步：线程B执行抢到锁并且完成临界区代码的执行后，开始unlock（释放）操作，设置nodeB的前驱引用为null，锁状态locked为false。线程B释放锁之后，nodeA对象已经没有任何强引用，可以被GC回收了；

第三步：线程C执行抢到锁并且完成临界区代码的执行后，开始unlock（释放）操作，设置nodeC的前驱引用为null，锁状态locked为false；

CLH锁的优缺点

CLH锁是一种队列锁，其优点是空间复杂度低。如果有N个线程、L个锁，每个线程每次只获取一个锁，那么需要的存储空间是O(L+N)，N个线程有N个Node，L个锁有L个Tail；

CLH队列锁的一个显著缺点是它在NUMA架构的CPU平台上性能很差。CLH队列锁在NUMA架构的CPU平台上，每个CPU内核有自己的内存，如果前驱节点在不同的CPU内核上，它的内存位置比较远，在自旋判断前驱节点的locked属性时，性能将大打折扣。然而CLH锁在SMP架构的CPU平台上则不存在这个问题，性能还是挺高的；