并发之AQS原理(二) CLH队列与Node解析

1.CLH队列与Node节点

就像通常医院看病排队一样，医生一次能看的病人数量有限，那么超出医生看病速度之外的病人就要排队。

一条队列是队列中每一个人的组织形式。那么每个人决定怎么看待自己在队列中的形态决定了整个队列的形态。比如当每个人都遵守先来后到的原则时，那么最先来的人会站到第一个，之后每个人都会顺序排开。

同样的队列这个类不存在，让他们形成队列的是每个节点类的组织形式。所以想分析队列就必须要先分析节点。

所谓的CLH队列本质上就是一个双向链表Node就是该链表的节点。当然CLH队列并不是简单的双向链表

上图直观的向我们展示了节点的组织状态，我们可以看看node节点的源代码。

2.node节点属性的解析

node节点作为CLH队列的一个节点，有着5条属性，分别是waitStatus 、prev、next、thread、nextWater。下面我们将一一解析这五种属性的作用。

waitStatus介绍

waitStatus是当前节点的一个等待状态标志位，该标志位决定了该节点在当前情况下处于何种状态。

不用再说了，直接看注释吧。这里我们说下Node。Node结点是对每一个访问同步代码的线程的封装，其包含了需要同步的线程本身以及线程的状态，如是否被阻塞，是否等待唤醒，是否已经被取消等。变量waitStatus则表示当前被封装成Node结点的等待状态，共有4种取值CANCELLED、SIGNAL、CONDITION、PROPAGATE。

CANCELLED：值为1，在同步队列中等待的线程等待超时或被中断，需要从同步队列中取消该Node的结点，其结点的waitStatus为CANCELLED，即结束状态，进入该状态后的结点将不会再变化。

SIGNAL：值为-1，被标识为该等待唤醒状态的后继结点，当其前继结点的线程释放了同步锁或被取消，将会通知该后继结点的线程执行。说白了，就是处于唤醒状态，只要前继结点释放锁，就会通知标识为SIGNAL状态的后继结点的线程执行。

CONDITION：值为-2，与Condition相关，该标识的结点处于等待队列中，结点的线程等待在Condition上，当其他线程调用了Condition的signal()方法后，CONDITION状态的结点将从等待队列转移到同步队列中，等待获取同步锁。

PROPAGATE：值为-3，与共享模式相关，在共享模式中，该状态标识结点的线程处于可运行状态。

AQS运用该属性时的状态判断

状态	判断结果	说明
waitStatus=0	代表初始化状态	该节点尚未被初始化完成
waitStatus>0	取消状态	说明该线程中断或者等待超时，需要移除该线程
waitStatus<0	有效状态	该线程处于可以被唤醒的状态

prve next thread介绍

prve 是同步线程队列中保存的前置节点的地址。
next 是同步线程队列中保存的后续节点的地址。
thread 同步线程队列主要存储的线程信息。

nextWaiter介绍

AQS中阻塞队列采用的是用双向链表保存，用prve和next相互链接。而AQS中条件队列是使用单向列表保存的，用
nextWaiter来连接。阻塞队列和条件队列并不是使用的相同的数据结构。

在Node节点的源码中有两个常量属性

// 共享模式
static final Node SHARED = new Node();
// 独占模式
static final Node EXCLUSIVE = null;
// 其他模式
// 其他非空值：条件等待节点（调用Condition的await方法的时候）

nextWaiter实际上标记的就是在该节点唤醒后依据该节点的状态判断是否依据条件唤醒下一个节点。

nextWaiter状态标志	说明
SHARED(共享模式)	直接唤醒下一个节点
EXCLUSIVE(独占模式)	等待当前线程执行完成后再唤醒
其他非空值	依据条件决定怎么唤醒下一个线程。类似semaphore中控制几个线程通过

node节点的属性介绍完了，下面来介绍node节点的方法以及各个方法的用户

3.node节点方法解析

构造方法

// 构造方法为空参构造，一般用于创建head节点，或者为nextWaiter设置共享标志。
Node() {
}
// 构造方法用于创建一个带有条件队列的节点
Node(Thread thread, Node mode) {
    this.nextWaiter = mode;
    this.thread = thread;
}
// 用于创建一个带有初始等waitStatus的节点
Node(Thread thread, int waitStatus) {
    this.waitStatus = waitStatus;
    this.thread = thread;
}

isShared方法

显而易见这个方法使用来检查当前节点是否为共享节点。


      final boolean isShared() {
          return nextWaiter == SHARED;
      }

predecessor方法

该方法用来查找前置节点是否存在,相当于为前置节点查空。

final Node predecessor() throws NullPointerException {
  Node p = prev;
  if (p == null)
    throw new NullPointerException();
  else
    return p;
}

4.基于Node的的CLH阻塞队列是如何运作的

首先 CLH队列锁通常使用自旋锁来阻塞线程执行，使用本节点和前置节点的waitStatus来判断线程是否阻塞。在前置节点获取执行权限的时候发出信号。每个节点都有一个单独等待通知的监视器，waitStatus不会控制线程是否获取到了锁。获取锁的过程是通过查看队列中的第一个node中的waitStatus是否处于可以执行的状态。如果可执行则继续执行，线程被中断或者超时了就寻找后续node.

CLH锁出列只设置更新头部节点，插入队列只需要原子更新尾部的节点。

首先确定自己是否为头部节点，如果是头部节点则直接获取资源开始执行，如果不是则自旋前置节点直到前置节点执行完成状态修改为CANCELLED,然后断开前置节点的链接，获取资源开始执行。

这部分操作的具体详情会在后续的系列中详细讲解。

5.总结

CLH阻塞队列采用的是双向链表队列，头部节点默认获取资源获得执行权限。后续节点不断自旋方式查询前置节点是否执行完成，直到头部节点执行完成将自己的waitStatus状态修改以通知后续节点可以获取资源执行。CLH锁是一个有序的无饥饿的公平锁。