转载

JDK并发AQS系列(五)

鉴于自旋锁的不足，Craig,Landin,Hagersten发明了CLH锁。而在CLH锁核心思想的影响下，Java并发包的基础框架AQS以CLH锁作为基础而设计，其中主要是考虑到CLH锁更容易实现取消与超时功能。

比起原来的CLH锁已经做了很大的改造，主要从两方面进行了改造：

节点的结构与节点等待机制。在结构上引入了头结点和尾节点，他们分别指向队列的头和尾，尝试获取锁、入队列、释放锁等实现都与头尾节点相关，并且每个节点都引入前驱节点和后后续节点的引用；
在等待机制上由原来的自旋改成阻塞唤醒。如图，通过前驱后续节点的引用一节节连接起来形成一个链表队列，对于头尾节点的更新必须是原子的。

下面详细看看入队、检测挂起、释放出队、超时、取消等操作。

入队操作

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

for (;;) {
   Node t = tail;
   node.prev = t;
   if (compareAndSetTail(t, node)) {
      t.next = node;
      return node;
   }
}
复制代码

检测挂起

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

for (;;) {
    if (node.prev == head)
        if(尝试获取锁成功){
            head=node;
            node.next=null;
            return;
        }
   阻塞线程
}
复制代码

释放出队

释放出队，出队的主要工作是负责唤醒等待队列中后续节点，让所有等待节点环环相接，每条线程有序地往下执行。

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

Node s = node.next;
唤醒节点s包含的线程
复制代码

超时操作

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

for (;;) {
   尝试获取锁
   if (nanosTimeout <= 总消耗时间)
      return;
   LockSupport.parkNanos(this, nanosTimeout);
 }④超时，在支持超时的模式下需要LockSupport类的parkNanos方法支持，线程在阻塞一段时间后会自动唤醒，每次循环将累加消耗时间，当总消耗时间大于等于自定义的超时时间时就直接分返。代码简化如下：
复制代码

取消操作

取消，队列中等待锁的队列可能因为中断或超时而涉及到取消操作，这种情况下被取消的节点不再进行锁竞争。

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

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

-------------推荐阅读------------

我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、mysql协议、chatbot)

为什么写《Tomcat内核设计剖析》

我的2017文章汇总——机器学习篇

我的2017文章汇总——Java及中间件

我的2017文章汇总——深度学习篇

我的2017文章汇总——JDK源码篇

我的2017文章汇总——自然语言处理篇

我的2017文章汇总——Java并发篇

跟我交流，向我提问：