CLH锁其实就是一种基于队列（具体为单向链表）排队的自旋锁，由于是Craig、Landin和Hagersten三人一起发明的，因此被命名为CLH锁，也叫CLH队列锁。

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

JUC中显式锁基于AQS抽象队列同步器，而AQS是CLH锁的一个变种

CLH结构如下：

        +------+  prev +-----+       +-----+
   head |      | <---- |     | <---- |     |  tail
        +------+       +-----+       +-----+

Node

为了方便理解，这里以AQS中的Node作为示例，来学习CLH，在CLH中每个节点(Node)，就代表一个线程，其源码如下：

 static final class Node {
         /**表明一个节点是共享锁模式**/
         /** Marker to indicate a node is waiting in shared mode */
         static final Node SHARED = new Node();
         /**表明一个节点是独占模式**/
         /** Marker to indicate a node is waiting in exclusive mode */
         static final Node EXCLUSIVE = null;
 
         /** waitStatus value to indicate thread has cancelled. */
         static final int CANCELLED =  1;
         /** waitStatus value to indicate successor's thread needs unparking. */
         static final int SIGNAL    = -1;
         /** waitStatus value to indicate thread is waiting on condition. */
         static final int CONDITION = -2;
         /**
          * waitStatus value to indicate the next acquireShared should
          * unconditionally propagate.
          */
         static final int PROPAGATE = -3;
 
         /**
          * Status field, taking on only the values:
          *   SIGNAL:     The successor of this node is (or will soon be)
          *               blocked (via park), so the current node must
          *               unpark its successor when it releases or
          *               cancels. To avoid races, acquire methods must
          *               first indicate they need a signal,
          *               then retry the atomic acquire, and then,
          *               on failure, block.
          *   CANCELLED:  This node is cancelled due to timeout or interrupt.
          *               Nodes never leave this state. In particular,
          *               a thread with cancelled node never again blocks.
          *   CONDITION:  This node is currently on a condition queue.
          *               It will not be used as a sync queue node
          *               until transferred, at which time the status
          *               will be set to 0. (Use of this value here has
          *               nothing to do with the other uses of the
          *               field, but simplifies mechanics.)
          *   PROPAGATE:  A releaseShared should be propagated to other
          *               nodes. This is set (for head node only) in
          *               doReleaseShared to ensure propagation
          *               continues, even if other operations have
          *               since intervened.
          *   0:          None of the above
          *
          * The values are arranged numerically to simplify use.
          * Non-negative values mean that a node doesn't need to
          * signal. So, most code doesn't need to check for particular
          * values, just for sign.
          *
          * The field is initialized to 0 for normal sync nodes, and
          * CONDITION for condition nodes.  It is modified using CAS
          * (or when possible, unconditional volatile writes).
          */
         volatile int waitStatus;
 
         /**
          * Link to predecessor node that current node/thread relies on
          * for checking waitStatus. Assigned during enqueuing, and nulled
          * out (for sake of GC) only upon dequeuing.  Also, upon
          * cancellation of a predecessor, we short-circuit while
          * finding a non-cancelled one, which will always exist
          * because the head node is never cancelled: A node becomes
          * head only as a result of successful acquire. A
          * cancelled thread never succeeds in acquiring, and a thread only
          * cancels itself, not any other node.
          */
         volatile Node prev;
 
         /**
          * Link to the successor node that the current node/thread
          * unparks upon release. Assigned during enqueuing, adjusted
          * when bypassing cancelled predecessors, and nulled out (for
          * sake of GC) when dequeued.  The enq operation does not
          * assign next field of a predecessor until after attachment,
          * so seeing a null next field does not necessarily mean that
          * node is at end of queue. However, if a next field appears
          * to be null, we can scan prev's from the tail to
          * double-check.  The next field of cancelled nodes is set to
          * point to the node itself instead of null, to make life
          * easier for isOnSyncQueue.
          */
         volatile Node next;
 
         /**
          * The thread that enqueued this node.  Initialized on
          * construction and nulled out after use.
          */
         volatile Thread thread;
 
         /**
          * Link to next node waiting on condition, or the special
          * value SHARED.  Because condition queues are accessed only
          * when holding in exclusive mode, we just need a simple
          * linked queue to hold nodes while they are waiting on
          * conditions. They are then transferred to the queue to
          * re-acquire. And because conditions can only be exclusive,
          * we save a field by using special value to indicate shared
          * mode.
          */
         Node nextWaiter;
 
         /**
          * Returns true if node is waiting in shared mode.
          */
         final boolean isShared() {
             return nextWaiter == SHARED;
         }
 
         /**
          * Returns previous node, or throws NullPointerException if null.
          * Use when predecessor cannot be null.  The null check could
          * be elided, but is present to help the VM.
          *
          * @return the predecessor of this node
          */
         final Node predecessor() {
             Node p = prev;
             if (p == null)
                 throw new NullPointerException();
             else
                 return p;
         }
 
         /** Establishes initial head or SHARED marker. */
         Node() {}
 
         /** Constructor used by addWaiter. */
         Node(Node nextWaiter) {
             this.nextWaiter = nextWaiter;
             THREAD.set(this, Thread.currentThread());
         }
 
         /** Constructor used by addConditionWaiter. */
         Node(int waitStatus) {
             WAITSTATUS.set(this, waitStatus);
             THREAD.set(this, Thread.currentThread());
         }
 
         /** CASes waitStatus field. */
         final boolean compareAndSetWaitStatus(int expect, int update) {
             return WAITSTATUS.compareAndSet(this, expect, update);
         }
 
         /** CASes next field. */
         final boolean compareAndSetNext(Node expect, Node update) {
             return NEXT.compareAndSet(this, expect, update);
         }
 
         final void setPrevRelaxed(Node p) {
             PREV.set(this, p);
         }
     }

waitStatus属性

每个节点与等待线程关联，每个节点维护一个状态waitStatus，waitStatus的各种值以常量的形式进行定义。waitStatus的各常量值具体如下：

0. CANCELLED(1):waitStatus值为1时表示该线程节点已释放（超时、中断），已取消的节点不会再阻塞，表示线程因为中断或者等待超时，需要从等待队列中取消等待。由于该节点线程等待超时或者被中断，需要从同步队列中取消等待，因此该线程被置1。节点进入了取消状态，该类型节点不会参与竞争，且会一直保持取消状态。
1. SIGNAL(-1):waitStatus为SIGNAL（－1）时表示其后继的节点处于等待状态，当前节点对应的线程如果释放了同步状态或者被取消，就会通知后继节点，使后继节点的线程得以运行。
2. CONDITION(-2):waitStatus为－2时，表示该线程在条件队列中阻塞(主要在Condition中使用)，表示节点在等待队列中，当持有锁的线程调用了CONDITION的signal()方法之后，节点会从该CONDITION的等待队列转移到该锁的同步队列上，去竞争锁（注意：这里的同步队列就是我们讲的AQS维护的FIFO队列，等待队列则是每个CONDITION关联的队列）。
3. PROPAGATE(-3):waitStatus为－3时，表示下一个线程获取共享锁后，自己的共享状态会被无条件地传播下去，因为共享锁可能出现同时有N个锁可以用，这时直接让后面的N个节点都来工作。共享锁是可以多个线程共有的，当一个节点的线程获取共享锁后，必然要通知后继共享节点的线程也可以获取锁了，这样就不会让其他等待的线程等很久，这种向后通知（传播）的目的也是尽快通知其他等待的线程尽快获取锁。
4. 0:waitStatus为0时，表示当前节点处于初始状态。

说明：Node节点的waitStatus状态只能是以上5种状态的1种

thread

Node的thread成员用来存放进入AQS队列中的线程引用；Node的nextWaiter成员用来指向自己的后继等待节点，此成员只有线程处于条件等待队列中的时候使用。

CLH锁原理

问：请简述CLH锁

【重要】抢锁线程在队列尾部CAS加入一个节点，然后仅在前驱节点上进行普通自旋，它不断轮询前一个节点状态，如果发现前一个节点释放锁，当前节点抢锁成功。

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开始在它的前驱节点上进行普通自旋。

通过以上过程可以看出：

0. CLH自旋锁的尾指针tail总是指向最后一个线程的节点。
1. CLH自旋锁队列中的抢锁线程一直进行普通自旋，循环判断前一个线程的locked状态，如果是true，那么说明前一个线程处于自旋等待状态或正在执行临界区代码，所以自己需要自旋等待

CLH释放锁的过程

前面举例说明了CLH锁的加锁过程，那么CLH锁释放过程又是怎样的呢？

第一步：线程A执行完临界区代码后开始unlock（释放）操作，设置nodeA的前驱引用为null(方便垃圾回收器回收)，锁状态locked为false。

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

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

AQS解读

AQS是CLH队列的一个变种，主要原理和CLH队列差不多，AQS队列内部维护的是一个FIFO的双向链表，这种结构的特点是每个数据结构都有两个指针，分别指向直接的前驱节点和直接的后继节点。所以双向链表可以从任意一个节点开始很方便地访问前驱节点和后继节点。每个节点其实是由线程封装的，当线程争抢锁失败后会封装成节点加入AQS队列中；当获取锁的线程释放锁以后，会从队列中唤醒一个阻塞的节点（线程）。

 public abstract class AbstractQueuedSynchronizer
     extends AbstractOwnableSynchronizer
     implements java.io.Serializable {
     static final class Node {
         //省略Node内代码
     }
     //记录队列的首节点
     private transient volatile Node head;
 
     /**
      * Tail of the wait queue, lazily initialized.  Modified only via
      * method enq to add new wait node.
      * 记录队列尾结点
      */
     private transient volatile Node tail;
 
     /**
      * The synchronization state.
      * 表示每个节点(线程)的锁状态，是否获取到锁
      */
     private volatile int state;
     
     
 }

AQS执行流程

0. AQS的执行流程大体为当线程获取锁失败时，会加入到同步队列中，在同步队列中的线程会按照从头至尾的顺序依次再去尝试获取锁执行。
1. 当线程获取锁后如果调用了condition.await()方法，那么线程就加入到等待队列排队，当被唤醒(signal()，signalAll())时再从等待队列中按照从头至尾的顺序加入到同步队列中，然后再按照同步队列的执行流程去获取锁。
2. 所以AQS最核心的数据结构其实就两个队列，同步队列和等待队列，然后再加上一个获取锁的同步状态。

AQS加锁

acquire是AQS封装好的获取资源的公共入口，它是AQS提供的利用独占的方式获取资源的方法，源码实现如下：

 public final void acquire(int arg) {
     //tryAcquire()如果返回true,则表示抢到锁，如果返回false，说明有竞争
     //此时会初始化同步队列
     if (!tryAcquire(arg) &&
         //注意：Node.EXCLUSIVE==null
         acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
         selfInterrupt();
 }
 protected final boolean tryAcquire(int acquires) {
             return nonfairTryAcquire(acquires);
 }
 final boolean nonfairTryAcquire(int acquires) {
             //获取当前线程
         final Thread current = Thread.currentThread();
             //获取同步状态的当前值，state初始化为0，表示未锁定状态，抢到锁后将state加1
         int c = getState();
             //如果当前同步状态为0
         if (c == 0) {
             //如果状态为0，就修改为1，表示当前线程抢占了锁
             if (compareAndSetState(0, acquires)) {
                 //设置当前线程独占锁
                 setExclusiveOwnerThread(current);
                 return true;
             }
         }
         //如果同步状态不为0，并且当前的线程就是正在执行的线程，说这里是重入操作
         else if (current == getExclusiveOwnerThread()) {
             int nextc = c + acquires;
             if (nextc < 0) // overflow
                     throw new Error("Maximum lock count exceeded");
                     //设置获取锁的次数
                 setState(nextc);
                 return true;
             }
         return false;
     }

 static final class NonfairSync extends Sync {
     private static final long serialVersionUID = 7316153563782823691L;
     protected final boolean tryAcquire(int acquires) {
         return nonfairTryAcquire(acquires);
     }
 }

通过源码可以发现，acquire(arg)至少执行一次tryAcquire(arg)钩子方法。若调用tryAcquire(arg)尝试成功，则acquire()将直接返回，表示已经抢到锁；若不成功，则将线程加入等待队列。继续查看源码。

 final boolean acquireQueued(final Node node, int arg) {
         boolean interrupted = false;
         try {
             for (;;) {
                 //获取前置节点
                 final Node p = node.predecessor();
                 //如果前置节点是头节点，并尝试获取锁
                 if (p == head && tryAcquire(arg)) {
                     //设置该节点为头节点，因为只有头节点能抢到锁
                     setHead(node);
                     //当前节点已经是头节点了，断开原头节点和当前节点的连接
                     p.next = null; // help GC
                     return interrupted;
                 }
                 //检查头节点的状态，预判当前获取锁失败的线程是否要挂起
                 //如果需要挂起调用方法使线程挂起
                 if (shouldParkAfterFailedAcquire(p, node))
                     interrupted |= parkAndCheckInterrupt();
             }
         } catch (Throwable t) {
             cancelAcquire(node);
             if (interrupted)
                 selfInterrupt();
             throw t;
         }
     }
 private Node addWaiter(Node mode) {
             //创建新的节点
         Node node = new Node(mode);
                 //自旋
         for (;;) {
             //保存原来的尾结点
             Node oldTail = tail;
             //如果原来的尾结点不为null
             //假设有2个线程抢锁，A线程抢到锁，B线程抢锁时发生竞争
             //此时会创建队列，而此时链表首位节点都为null。会进入到else中初始化链表
             //初始化链表后便有了首位节点，此时即可进入该if分支
             if (oldTail != null) {
                 //设置新节点的前置节点为尾结点
                 node.setPrevRelaxed(oldTail);
                 //CAS设置新节点为尾结点
                 if (compareAndSetTail(oldTail, node)) {
                     //将原来的尾结点next设置为新节点
                     oldTail.next = node;
                     //返回新的节点
                     return node;
                 }
             } else {
                 //如果尾结点为null，则证明队列没有被初始化，则初始化队列
                 initializeSyncQueue();
             }
         }
     }
 private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
         //获取节点的等待状态
         int ws = pred.waitStatus;
         //如果节点值等于-1，说明前驱的等待标志已经设置好了，返回true表示设置完毕
         if (ws == Node.SIGNAL)
             return true;
         if (ws > 0) {
             //如果前驱节点已经取消
             do {
                 //不断循环，直到找到非取消的前驱节点
                 node.prev = pred = pred.prev;
             } while (pred.waitStatus > 0);
             //调整前驱节点的next指针
             pred.next = node;
         } else {
             //如果前驱节点不是-1也不是1，就CAS设置为-1
             pred.compareAndSetWaitStatus(ws, Node.SIGNAL);
         }
         //设置以后此方法返回值还是false，表示当前线程不可用，阻塞
         return false;
     }
 private final boolean parkAndCheckInterrupt() {
         //阻塞线程
         LockSupport.park(this);
         return Thread.interrupted();
     }
     private void setHead(Node node) {
         head = node;
         node.thread = null;
         node.prev = null;
     }
 private final void initializeSyncQueue() {
         Node h;
             //创建新的节点，并设置该节点为首节点和位节点
         if (HEAD.compareAndSet(this, null, (h = new Node())))
             tail = h;
     }
 

在独占锁的场景中，
shouldParkAfterFailedAcquire()方法是在acquireQueued()方法的死循环中被调用的，由于此方法返回false时acquireQueued()不会阻塞当前线程，只有此方法返回true时当前线程才阻塞，因此在一般情况下，此方法至少需要执行两次，当前线程才会被阻塞。

在第一次进入此方法时，首先会进入后一个if判断的else分支，通过CAS设置pred前驱的waitStatus为SIGNAL，然后返回false。

此方法返回false之后，获取独占锁的acquireQueued()方法会继续进行for循环去抢锁：

0. 假设node的前驱节点是头节点，tryAcquire()抢锁成功，则获取到锁。
1. 假设node的前驱节点不是头节点，或者tryAcquire()抢锁失败，仍然会再次调用此方法。

AQS释放锁

 public final boolean release(int arg) {
         if (tryRelease(arg)) {
             //保存头节点
             Node h = head;
             //如果头结点不为null，并且等待状态不为0
             if (h != null && h.waitStatus != 0)
                 unparkSuccessor(h);
             return true;
         }
         return false;
     }
 protected final boolean tryRelease(int releases) {
             int c = getState() - releases;
             //如果当前线程不是占用锁的线程，则抛出异常
             if (Thread.currentThread() != getExclusiveOwnerThread())
                 throw new IllegalMonitorStateException();
             boolean free = false;
                     //如果c==0，只有1中情况，就是当前线程状态为1
             if (c == 0) {
                 free = true;
                 //设置锁没有被线程占用
                 setExclusiveOwnerThread(null);
             }
             setState(c);
             return free;
         }