一、前言
本篇内容是为之后的内容AQS打下基础，AQS又称 Abstract Queued Synchronizer ，即抽象队列同步器，Java中，基于 AQS 实现了很多著名的锁，如：重入锁（ReentrantLock）、读写锁（ReadWriteLock）、共享锁（CountDownLatch）若设置为1则等同于互斥锁，等。因此，为了深入分析AQS，我将重要的内容都拆解出来，从一个一个的知识点逐个击破。
二、CLH
CLH（Craig，Landin and Hagersten）是三个人，共同发明了一个可扩展、高性能、公平且基于自旋锁的链表；链表中的每个线程只在本地自旋前一个节点的状态，即该节点（线程）不断自旋获取前一个节点的状态；每个节点都有一个状态（要么自旋，要么释放锁）。
在AQS中，用到的数据结构是 CLH 的变体：
+-------+ prev +-------+ +-------+
head | A | <----- | B | <---- | C | tail
+-------+ +-------+ +-------+
上图是AQS中CLH的变体结构，该结构是：
- 一个 FIFO（first-in-first-out）队列；
- 新的等待获取锁的线程先加入队尾（tail）；
- 如果队列是空，则第一个新加入的节点立即获得锁；
- 新加入的线程本地自旋前一个节点的状态（如 C 不断自旋获取 B 的状态）；
- (当A释放锁时，B成为第一个节点)，头节点并不能保证能够获得锁，只是有优先权，如果获取失败，则重新变为等待状态；
这里的内容，我们在分析《小白三，synchronized》时，谈到过 ContentionList、EntryList，AQS的变体CLH和它们一样，没有差别。
CLH.png
三、公平与非公平
『针对第5点进行解释』
CLH是公平队列，既然是公平队列，那么当『A』释放锁时，『B』成为首节点，应该是可以获得锁的，但为什么还会失败，而重新变成等待状态呢？如果首节点还获取不到锁，那CLH不就不公平了么？
- 『B』节点与新来的线程竞争获取锁，新的线程竞争成功，『B』失败，因此『B』重置为自旋等待状态；
- 新的线程不竞争，直接加入队尾，那么，此时『B』节点就能获取到锁；
因此，这里的公平与否，主要还是要看继承AQS的锁的实现方式：新来的竞争锁的线程，是先尝试竞争一次，还是直接加入队尾。
如果采用非公平模式，则新来的线程如果竞争成功，则直接成为 first 节点，插入在 head 与 first 节点之间，而原 first 节点排在新的 first 节点之后进入等待状态并自旋。
我们在后面分析那些继承 AQS 实现的锁时，有些锁就支持非公平方式，如 ReentrantLock。
四、CLH的结构
CLH看似是个链表，但实际上并不存在，CLH中的每个节点类型为 Node，Node 中有两个索引，分别是 prev 和 next 将所有的节点串起来；在 AQS 中也只有两个索引节点，分别是 head 和 tail ，分别指向队列的头和尾；并没有一个成员变量类似 LinkedList 来管理所有的节点。
public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer implements java.io.Serializable {
static final class Node {
// 共享模式
static final Node SHARED = new Node();
// 独占（排它）模式
static final Node EXCLUSIVE = null;
// 线程已被取消，当首节点释放锁后，
// 开始查找下一个 waitStatus < 0 的节点，
// 如果遇到已取消的线程，则移除
static final int CANCELLED = 1;
// 当前线程的后继线程需要被unpark(唤醒)
// 后继节点处于等待状态，当前节点（为-1）被取消或者中断时会通知后继节点，
// 使后继节点的线程得以运行
static final int SIGNAL = -1;
// 当前节点处于等待队列，节点线程等待在Condition上，
// 当其他线程对condition执行signall方法时，
// 等待队列转移到同步队列，加入到对同步状态的获取
static final int CONDITION = -2;
// 与共享模式相关，在共享模式中，该状态标识结点的线程处于可运行状态
static final int PROPAGATE = -3;
// 当前节点的状态，默认是 0
volatile int waitStatus;
volatile Node prev;
volatile Node next;
// 等待获取锁而自旋的线程
volatile Thread thread;
// Node既可以作为同步队列节点使用，也可以作为Condition的等待队列节点使用(将会在后面讲Condition时讲到)。
// 在作为同步队列节点时，nextWaiter可能有两个值：EXCLUSIVE、SHARED标识当前节点是独占模式还是共享模式；
// 在作为等待队列节点使用时，nextWaiter保存后继节点
Node nextWaiter;
final boolean isShared() {
return nextWaiter == SHARED;
}
final Node predecessor() throws NullPointerException {
Node p = prev;
if (p == null)
throw new NullPointerException();
else
return p;
}
Node() { // Used to establish initial head or SHARED marker
}
Node(Thread thread, Node mode) { // Used by addWaiter
this.nextWaiter = mode;
this.thread = thread;
}
Node(Thread thread, int waitStatus) { // Used by Condition
this.waitStatus = waitStatus;
this.thread = thread;
}
}
}
我们可以看到，AQS 的 Node 结构不复杂，还算比较简单，下一篇将来开始讲解 AQS。
网友评论