AQS结点数据结构

AbstractQueuedSynchronizer是JAVA并发包的核心组件，AbstractQueuedSynchronizer中封装了对锁的操作。锁主要有两种操作：获取和释放。获取锁首先判断当前状态是否允许获取锁，如果是就获取锁，否则就阻塞操作或者获取失败;释放锁就是修改状态位，如果有线程因为状态位阻塞的话就唤醒队列中的一个或者更多线程。要支持这两个操作，需要有一个有序的队列，JAVA中，有序队列是由一个个node组成的，刚看了Node的源码，作个笔记。

 这个有序队列是一种CLH(Craig, Landin, and Hagersten)队列，整个是一个包含头结点的双向链表，每个结点其实对应着一个线程，前趋结点上含有控制信息，有一个状态字段waitStatus，这个字段不同的取值代表不同的含义，特别当waitStatus=-1的时候，表示当前结点在释放锁或者被中断的时候，需要唤醒它的后继结点。注意：waitStatus并不会控制一个线程是否获取锁，只是控制线程获取锁的机会，至于被唤醒的线程是否真的获取锁，要看它的造化。

和数据结构中的队列的操作一样，入队时会插入一个新结点，放到队列的尾部，出队时需要修改头结点的next指针，出队需要做更多的工作就是要重新确定队头结点，可能还要处理因超时或者中断引起的被取消的结点，这些结点是不能作为队头结点的。     

当waitStatus=1表示这个结点被取消了，被取消的结点没有获取锁的机会了，如果一个结点被取消了，它的

后继结点必须是未被取消的结点，因此在确定它的后继结点时，可能会跳过n个被取消的结点，也就是说这些被取消的结点最终会脱离列表。

前面讲到双向链表，有next和prev两个指针，正是通过next指针来确定后继接点的，当一个结点的后继结点为空时，这个时候有必要从队列尾部反向查找继任结点。当我们遍历这些被取消的结点的过程中，如果发一个结点被取消了，并不会挂起它，而是让它保持在原来的位置。直到我们找到一个没有被取消的结点。（？）

头结点是一个傀儡结点，我们自己是不能创建傀儡结点的，因为如果没有竞争者（或者说没有线程，没有除头结点以外的结点）时会浪费资源。

我们常说的条件队列也在这个同步队列里面，如图所示橙色框，只是用一个字段（nextWaiter字段）来把这些在等待条件的这些结点串起来，注意条件队列只在互斥的情况下使用。

    

下来分别解释一下Node的几个字段：

waitStatus：结点的状态字段，取以下值：

SIGNAL（-1）:如果后继结点已被挂起，或者将要被挂起，当前结点在释放锁或者被取消时，需要唤醒它的后继结点。为了避免竞争，获取锁时第一步就要通知它的后继结点，然后才是尝试获取锁等操作。

CANCELLED（1）:指示这个结点因为某种原因（超时或者中断）被取消了， 一旦结点处于该状态，其状态就不能被改变，特别是不可能再被阻塞。

CONDITION（-2）:指示这个结点在条件队列中，在满足条件之前，它不会被当成同步队列中的结点。满足条件之后它的值为变为0.

0：None of the above

对于一个正常的结点，该值被设置为0，如果该结点属于条件队列，则被设置为CONDITION,修改status需要采用CAS操作（或者说，原子修改）。

prev字段：指向前趋结点，因为当前结点依赖于前趋结点。入队时设置这个字段，在出队之后为NULL.当前趋结点被取消时，需要找一个非取消的后继结点，这些被取消的结点就会被短路。对于一个结点来说，prev始终有值，因为有头结点的存在，而且头结点永远不会被取消。一个结点只有在获取锁之后才会处于队头，被取消的线程永远不会成功获取锁。

next字段:指向继任结点，当前结点在释放锁时，可能会通知它的后继结点。在入队时分配该字段，出队列时为空。入队时只是分配并不会设置该字段，当有新的结点附在它的后面时才会设置。所以当我们看到一个结点的next域为NULL,并不代表它处于队列尾部。当next域为NULL时，我们需从队尾向前找它的后继结点。被取消的结点它的next域指向自己，而不是设置为NULL。

thread字段：入队时，线程都附着在结点上。结点被用过之后，thread为NULL。

nextWaiter:对于条件队列来说，它的值指向下一个等待条件的结点。因为条件队列只会在互斥模式下有效，我们正是用这个字段来串起这些条件结点的。这些结点在等到条件后会被转移到同步队列重新获取锁。由于条件队列只会在互斥模式下使用，可以把这个字段设置为SHARD来代表共享模式。

具体的获取锁，释放锁操作，共享与互斥等下次再写。