Java并发编程：AQS对CLH锁的优化

自旋锁适用于锁占用时间短，即锁保护临界区很小的情景AQS的自旋锁详解>。它需要保证各缓存数据的一致性，这可能会导致性能问题。因为在多处理器机器上每个线程对应的处理器都对同一个变量进行读写，而每次读写都要同步每个处理器的缓存。此外，自旋锁无法保证公平性，即不保证先到先获得，这就可能造成线程饥饿。

01

CHL锁

为了优化同步带来的花销，Craig、Landin、Hagersten三个人发明了CLH锁。其核心思想是：通过一定手段将所有线程对某一共享变量的轮询竞争转化为一个线程队列，且队列中的线程各自轮询自己的本地变量。

这个转化过程有两个要点：一是应该构建怎样的队列以及如何构建队列？为了保证公平性，我们构建的将是一个FIFO队列。构建的时候主要通过移动尾部节点tail来实现队列的排队，每个想获取锁的线程创建一个新节点并通过CAS原子操作将新节点赋给tail，然后让当前线程轮询前一节点的某个状态位。如图可以清晰看到队列结构及自旋操作，这样就成功构建了线程排队队列。二是如何释放队列？执行完线程后只需将当前线程对应的节点状态位置为解锁状态即可，由于下一节点一直在轮询，所以可获取到锁。

02

为什么自旋

下面我们提供一个简单的CLH锁实现代码，以便更好理解CLH锁的原理。其中lock与unlock两方法提供加锁和解锁操作，每次加锁解锁必须将一个CLHNode对象作为参数传入。lock方法的for循环是通过CAS操作将新节点插入队列，而while循环则是检测前驱节点的锁状态位。一旦前驱节点锁状态位允许则结束检测，让线程往下执行。解锁操作先判断当前节点是否为尾节点，如是则直接将尾节点设置为空，此时说明仅仅只有一条线程在执行，否则将当前节点的锁状态位设置为解锁状态。

03

AQS对CLH锁的优化

在CLH锁核心思想的影响下，AQS框架以CLH锁为基础。但同时考虑到为了让CLH锁更容易实现取消与超时功能，于是对CLH锁已经做了一些改造。主要从两方面进行了改造：节点的结构与节点等待机制。

在结构上引入了头结点和尾节点，它们分别指向队列的头和尾，尝试获取锁、入队列、释放锁等实现都与头尾节点相关，并且每个节点都引入前驱节点和后继节点的引用；在等待机制上由原来的自旋改为阻塞唤醒。如下图，通过前驱后继节点的引用一个个节点连接起来形成一个链表队列，对头尾节点的更新必须是原子的。下面详细看看入队、检测挂起、释放出队、超时、取消等操作。

04

入队操作

入队操作的逻辑其实是用一个无限循环进行CAS操作，即用自旋方式竞争直到成功。将尾节点tail的旧值赋予新节点node的前驱节点，并尝试CAS操作将新节点node赋予尾节点tail，原先的尾节点的后继节点指向新建节点node。完成上面步骤就建立起一条链表队列。简化代码如下。

05

阻塞操作

上面我们说到节点等待机制已经被AQS作者由自旋机制改造成阻塞机制。一个新建的节点完成入队操作后，如果是自旋则直接进入循环检测前驱节点是否为头结点即可。但如果改为阻塞机制，则当前线程将先检测是否为头结点且尝试获取锁。如果当前节点为头结点并成功获取锁则直接返回，当前线程不进入阻塞，否则将当前线程阻塞。简化代码如下。

06

出队操作

出队的主要工作是负责唤醒等待队列中的后继节点，让所有等待节点环环相扣，每条线程有序地往下执行。如果在共享模式下出队工作将变得异常复杂，主要考虑的是对释放时竞争优化而引入了另外一种状态PROPAGATE。多条线程并发执行出队操作时可能将头结点状态改为PROPAGATE，当下一节点被唤醒时根据此状态将继续往下唤醒而不用去执行尝试获取，以达到优化效果。此处只讨论独占模式，简化代码如下。

07

超时机制

超时的模式需要LockSupport类的parkNanos方法支持，线程在阻塞一段时间后会自动唤醒。每次循环将累加消耗时间，当总消耗时间大于等于自定义的超时时间时就直接返回。简化代码如下。

07

取消操作

队列中等待锁的队列可能因为中断或超时而涉及到取消操作，这种情况下被取消的节点不再进行锁竞争。此过程主要完成的工作是将取消的节点移除。先将节点node状态设置成取消状态，再将前驱节点pred的后继节点指向node的后继节点。这里由于涉及到竞争，必须通过CAS进行操作。CAS操作就算失败也不必理会，因为已经改了节点的状态，在尝试获取锁操作中会循环对节点的状态判断。

- END -