文前说明

作为码农中的一员，需要不断的学习，我工作之余将一些分析总结和学习笔记写成博客与大家一起交流，也希望采用这种方式记录自己的学习之旅。

本文仅供学习交流使用，侵权必删。
不用于商业目的，转载请注明出处。

• 在 java.util.concurrent.locks 包中有很多 Lock 的实现类，常用的 ReentrantLock、ReadWriteLock（实现类 ReentrantReadWriteLock），内部实现都依赖 AbstractQueuedSynchronizer 类（简称 AQS）。
• AQS 定义了一套多线程访问共享资源的同步器框架，是抽象的队列式的同步器。

1. 框架整理

AQS 框架结构

• AQS 实现了一个 volatile int state 成员变量标识同步状态（此变量代表着共享资源，更改这个变量值来获取和释放锁），通过内置的 FIFO（先进先出队列） 双向队列来完成资源获取线程排队的工作。
  • 橘红色结点是默认 head 结点，是一个空结点，代表当前持有锁的线程，每当有线程竞争失败，都是插入到队列的尾结点，tail 结点始终指向队列中的最后一个元素。
  • 每个结点中，除了存储了 当前线程，前后结点的引用 以外，还有一个 waitStatus 变量，用于描述 结点当前的状态。
  • 多线程并发执行时，队列中会有多个结点存在，waitStatus 代表着对应线程的状态。
• waitStatus 有 4 种状态。

表 1

状态值	状态	说明
1	CANCELLED	取消状态
-1	SIGNAL	等待触发状态
-2	CONDITION	等待条件状态
-3	PROPAGATE	状态需要向后传播

• AQS 在判断状态时，通过用 waitStatus > 0 表示取消状态，而 waitStatus < 0 表示有效状态。
• 等待队列是 FIFO 先进先出，只有前一个结点的状态为 SIGNAL 时，当前结点的线程才能被挂起。
• 共享资源 state 的访问方式有三种。

private static final Unsafe unsafe = Unsafe.getUnsafe();

protected final int getState() {
     return this.state;
}
protected final void setState(int newState) {
     this.state = newState;
}
protected final boolean compareAndSetState(int expect, int update) {
     return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

• AQS 定义两种资源共享方式。
  • Exclusive（独占，只有一个线程能执行，如 ReentrantLock）。
  • Share（共享，多个线程可同时执行，如 Semaphore / CountDownLatch）。
• 不同的自定义同步器争用共享资源的方式也不同。
• 自定义同步器在实现时只需要实现共享资源 state 的获取与释放方式即可，至于具体线程等待队列的维护（如获取资源失败入队 / 唤醒出队等），AQS 已经在顶层实现。
• 自定义同步器实现时主要实现以下方法。

方法名称	说明
isHeldExclusively()	该线程是否正在独占资源。只有用到 condition 才需要去实现它。
tryAcquire(int)	独占方式。尝试获取资源，成功则返回 true，失败则返回 false。
tryRelease(int)	独占方式。尝试释放资源，成功则返回 true，失败则返回 false。
tryAcquireShared(int)	共享方式。尝试获取资源。负数表示失败；0 表示成功，但没有剩余可用资源；正数表示成功，且有剩余资源。
tryReleaseShared(int)	共享方式。尝试释放资源，如果释放后允许唤醒后续等待结点返回 true，否则返回 false。

• 自定义同步器要么是独占方式，要么是共享方式，也只需实现 tryAcquire - tryRelease、tryAcquireShared - tryReleaseShared 中的一种即可。
  • 但 AQS 也支持自定义同步器同时实现独占和共享两种方式，如 ReentrantReadWriteLock。

ReentrantLock

• state 初始化为 0，表示未锁定状态。A 线程 lock 时，调用 tryAcquire 独占该锁并将 state + 1。
• 其他线程再 tryAcquire 时失败，直到 A 线程 unlock 到 state = 0（即释放锁）为止，其它线程才有机会获取该锁。
• 释放锁之前，A 线程可以重复获取此锁的（state 累加），这就是可重入的概念。
  • 获取多少次就要释放多少次，这样才能保证 state 回零。

CountDownLatch

• 任务分为 N 个子线程执行，state 初始化为 N（与线程个数一致）。
• N 个子线程并行执行，每个子线程执行完成 countDown 一次，state CAS 减 1。
• 所有子线程执行完成（即 state = 0），Unsafe.unpark 主线程，然后主线程从 await 函数返回，继续后续动作。

1.1 Node 结构

结点结构

Node {
    int waitStatus;
    Node prev;
    Node next;
    Node nextWaiter;
    Thread thread;
}

属性名称	描述
int waitStatus	表示结点的状态。其中包含的状态见表 1。
Node prev	前驱结点，比如当前节点被取消，那就需要前驱结点和后继结点来完成连接。
Node next	后继结点。
Node nextWaiter	存储 condition 队列中的后继结点。
Thread thread	入队列时的当前线程。

• 其中同步队列（Sync queue），是双向链表，包括 head 结点和 tail 结点，head 结点主要用作后续的调度。而 Condition queue 不是必须的，它是一个单向链表，只有当使用 Condition 时，才会存在此单向链表。并且可能会有多个 Condition queue。

2. 实现分析整理

2.1 独占模式

2.1.1 acquire(int)（线程获取锁的过程）

• 此方法是独占模式下线程获取共享资源的顶层入口。
  • 如果获取到资源，线程直接返回。
  • 否则进入等待队列，直到获取到资源为止，且整个过程 忽略中断 的影响。

public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
}

acquire 流程

• 执行流程。
  1. tryAcquire() 尝试直接获取资源，成功则 state 值被修改并返回 true，线程继续执行。
  2. 获取资源失败，执行 addWaiter() 将该线程加入等待队列的尾部，并标记为独占模式。
  3. acquireQueued() 使线程在等待队列中获取资源，一直获取到资源后才返回。
     • 如果在整个等待过程中被中断过，则返回 true，否则返回 false。
  4. 如果线程在等待过程中被中断过，它是不响应的。
     • 只是获取资源后才再进行自我中断 selfInterrupt()，将中断补上。
• 其中判定退出队列的条件是否满足和休眠当前线程完成了 自旋 的过程。

---

tryAcquire

• 尝试去获取独占资源。如果获取成功，则直接返回 true，否则直接返回 false。
• AQS 只定义了一个接口，具体资源的获取交由自定义同步器去实现（通过 state 的 get / set / CAS）

protected boolean tryAcquire(int arg) {
     throw new UnsupportedOperationException();
}

• 该方法需要子类来实现，但是却没有使用 abstract 来修饰。是因为 AQS 有独占和共享两种模式，而子类可以只实现其中一种功能，如果使用 abstract 来修饰，每个子类都需要同时实现两种功能的方法，对子类不太友好。

addWaiter(Node)

• 用于将当前线程加入到等待队列的队尾，并返回当前线程所在的结点。
  • 生成新 Node 结点 node，如果 tail 结点不为空，则通过 CAS 指令插入到等待队列的队尾（同一时刻可能会有多个 Node 结点插入到等待队列中），并建立前后引用关系。
  • 如果 tail 结点为空，则将 head 结点指向一个空结点。

private Node addWaiter(Node mode) {
        //以给定模式构造结点。mode 有两种：EXCLUSIVE（独占）和 SHARED（共享）
        Node node = new Node(Thread.currentThread(), mode);
        //尝试快速方式直接放到队尾。
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        //上一步失败则通过 enq 入队。
        enq(node);
        return node;
}
......
private Node enq(final Node node) {
        //CAS " 自旋 "，直到成功加入队尾。
        for (;;) {
            Node t = tail;
            if (t == null) { // Must initialize //队列为空，创建一个空的标志结点作为 head 结点，并将 tail 也指向它。
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else { //正常流程，放入队尾
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
}

acquireQueued(Node, int)

• 通过 tryAcquire() 和 addWaiter()，该线程获取资源失败，被放入等待队列尾部。
  • node 插入到队尾后，该线程不会立马挂起，会进行 自旋 操作。
  • 判断该 node 的前一个结点 pred 是否为 head 结点。
  • 如果是，则表明当前结点是队列中第一个有效结点，再次尝试 tryAcquire() 获取锁。
    • 如果成功获取到锁，线程 node 无需挂起。
    • 如果获取锁失败，表示前驱线程还未完成，至少还未修改 state 的值。
  • 调用 shouldParkAfterFailedAcquire()，结点进入队尾后，检查状态，找到安全休息点。
  • 调用 parkAndCheckInterrupt()，进入 waiting 状态，等待 unpark() 或 interrupt() 唤醒。
    • 被唤醒后，看是否有资格获取资源。如果获得资源，head 指向当前结点，并返回从入队到获得资源的整个过程中是否被中断过。
    • 如果未获取资源，则重新调用 shouldParkAfterFailedAcquire()。

final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true; //标记是否成功拿到资源
        try {
            boolean interrupted = false; //标记等待过程中是否被中断过
            //自旋
            for (;;) {
                final Node p = node.predecessor(); //获得前驱结点
                //如果前驱结点 p 是 head，即该结点 node 为第二结点，那么便有资格去尝试获取资源（可能是 p 释放完资源后唤醒，也可能被 interrupt）。
                if (p == head && tryAcquire(arg)) {
                    setHead(node); //获取资源后，将 head 指向 node。
                    p.next = null; // setHead 中 node.prev 已置为 null，此处再将 p.next 置为 null，就是为了方便 GC 回收以前的 head 结点 p，也就意味着之前拿完资源的结点 p 出队。
                    failed = false;
                    return interrupted; //返回等待过程中是否被中断过
                }
                //如果自己可以休息了，就进入 waiting 状态，直到被 unpark()。
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt()) //如果等待过程中被中断过，哪怕只有那么一次，就将 interrupted 标记为 true。
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
}

shouldParkAfterFailedAcquire(Node, Node)

• 用于检查状态，看是否真的可以休息。（进入 waiting 状态）
  • 如果 pred 的 waitStatus 为 SIGNAL，则通过 parkAndCheckInterrupt() 方法把当前线程挂起，并等待被唤醒。
  • 如果 pred 的 waitStatus > 0，表明 pred 的线程状态 CANCELLED，需从队列中删除。
  • 如果 pred 的 waitStatus == 0，则通过 CAS 指令修改 waitStatus 为 SIGNAL。（每个结点的 SIGNAL 状态都是被后一个结点设置的）

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        int ws = pred.waitStatus;  //获得前驱结点状态。
        if (ws == Node.SIGNAL)
            //如果前驱结点状态为等待触发，则进入安全休息点。
            return true;
        if (ws > 0) {
            //如果前驱为取消状态，就一直往前找，直到找到最近一个正常等待的状态，并排在它的后面。
            //那些取消状态的结点，由于被当前结点 " 加塞 " 到它们前边，它们相当于形成一个无引用链，稍后会被 GC 回收。
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            //如果前驱结点正常，将前驱状态设置成 SIGNAL 等待触发
            //下一次循环进入 shouldParkAfterFailedAcquire 因为前驱状态已经设置为 SIGNAL，因此直接返回 true，执行 parkAndCheckInterrupt，对当前线程 park。
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
}

parkAndCheckInterrupt()

• 让线程真正进入等待状态。
  • park() 会让当前线程进入 waiting 状态。在此状态下，有两种途径可以唤醒该线程。
    • unpark() 和 interrupt()。
    • 需要注意 Thread.interrupted() 会 清除当前线程的中断标记位。

private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this); //调用 park() 使线程进入 waiting 状态。
        return Thread.interrupted(); //如果被唤醒，查看自己是不是被中断的。
}

• 线程每次被唤醒时，都要进行中断检测，如果发现当前线程被中断，抛出 InterruptedException 异常并退出循环。
  • 从无限循环的代码可以看出，并不是被唤醒的线程一定能获得锁，必须调用 tryAccquire() 重新竞争，因为锁是 非公平 的，有可能被新加入的线程获得，从而导致刚被唤醒的线程再次被阻塞。
    • 如果已经在队列中的线程，必须按照顺序执行（等待前驱结点的相关操作，这是 公平的），非公平是针对那种还没进队列的线程可以和队列中的第一个结点 head 抢占资源。

线程获取锁流程

selfInterrupt()

• 根据 acquireQueued() 的结果决定是否执行中断。
• acquireQueued() 中的 parkAndCheckInterrupt() 方法已经执行了中断，这里再执行一次中断的目的在于。
  • 如果当前线程是非中断状态，则在执行 parkAndCheckInterrupt 中 park 时被阻塞，这时返回中断状态是 false。不再执行 selfInterrupt()。
  • 如果当前线程是中断状态，则执行 parkAndCheckInterrupt 中 park 方法不起作用，会立即返回 true，并且将中断状态复位。由于中断状态已经复位，selfInterrupt() 用 park 方法时会阻塞线程。
• 这里判断线程中断的状态实际上是为了不让循环一直执行，让当前线程进入阻塞的状态。
  • 如果一直循环下去，会造成 CPU 使用率飙升的后果。

static void selfInterrupt() {
     Thread.currentThread().interrupt();
}

cancelAcquire(Node)

• 在 acquireQueued()方法的 finally 语句块中，如果在循环的过程中出现了异常，则执行 cancelAcquire 方法，用于将该结点标记为取消状态。

private void cancelAcquire(Node node) {
        // Ignore if node doesn't exist
        if (node == null)
            return;
        //设置该结点不再关联任何线程。
        node.thread = null;

        // 通过前继结点跳过取消状态的 node。
        Node pred = node.prev;
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;
        
        // 获取过滤后的前继结点的后继结点。
        Node predNext = pred.next;
        // 设置状态为取消状态。
        node.waitStatus = Node.CANCELLED;

        // 1.如果当前结点是 tail，尝试更新 tail 结点，设置 tail 为 pred。更新失败则返回，成功则设置 tail 的后继结点为 null。
        if (node == tail && compareAndSetTail(node, pred)) {
            compareAndSetNext(pred, predNext, null);
        } else {
            // 2.如果当前结点不是 head 的后继结点，判断当前结点的前继结点的状态是否为 SIGNAL，如果不是则尝试设置前继结点的状态为 SIGNAL。
            int ws;
            if (pred != head &&
                ((ws = pred.waitStatus) == Node.SIGNAL ||
                 (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
                pred.thread != null) {
                Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                // 3.如果是 head 的后继结点或者状态判断设置失败，则唤醒当前结点的后继结点。
                unparkSuccessor(node);
            }
            node.next = node; // help GC
        }
}

• 结点取消分三种情况。
  • 当前结点是 tail。
    • 因为 tail 是队列的最后一个结点，如果该结点需要取消，则直接把该结点的前继结点的 next 指向 null，也就是把当前结点移除队列。
    • 注意，这里并没有设置 node 的 prev 为 null。
  • 当前结点不是 head 的后继结点，也不是 tail。
    • 将 node 的前继结点的 next 指向了 node 的后继结点。
  • 当前节点是 head 的后继结点。
    • unpark 后继结点的线程，然后将 next 指向了自己。

当前结点是 tail 当前结点不是 head 的后继结点，也不是 tail 当前节点是 head 的后继结点

• 既然要删除结点，为什么没有对 prev 进行操作，仅仅是修改了 next。
  • 因为修改指针的操作都是 CAS 操作，在 AQS 中所有以 compareAndSet 开头的方法都是尝试更新，并不保证成功。
  • 不能用 CAS 操作更新 prev，因为 prev 是不确定的，更新失败有可能会导致整个队列的不完整，例如把 prev 指向一个已经移除队列的 node。
• prev 是由其他线程来修改的，通过 shouldParkAfterFailedAcquire() 方法。

do {
    node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;

• 因为 shouldParkAfterFailedAcquire() 方法是在获取锁失败的情况下才能执行。
  • 进入该方法时，说明已经有线程获得了锁。
  • 在执行该方法时，当前结点之前的结点不会发生变化（因为只有当下一个结点获得锁的时候才会设置 head），所以这里可以更新 prev，并且不必用 CAS 来更新。

2.1.2 release(int)（线程释放锁的过程）

• 此方法是独占模式下线程释放共享资源的顶层入口。
  • 释放指定量资源，如果彻底释放（即 state = 0），唤醒等待队列里的其他线程来获取资源。
    • 调用 tryRelease() 释放资源。根据返回值判断该线程是否已经完成释放资源，自定义同步器在设计时需明确这一点。

public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head; //获得头结点。
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h); //唤醒等待队列里的下一个线程。
            return true;
        }
        return false;
}

---

tryRelease(int)

• 尝试去释放指定量的资源。
  • 跟 tryAcquire() 一样，该方法需要独占模式的自定义同步器实现。
  • 正常情况下，tryRelease() 都会成功的，因为是独占模式，该线程释放资源，那么它肯定已经获得独占资源，直接减掉相应量的资源即可（state -= arg），也不需要考虑线程安全问题。
  • 但需要注意返回值，如果已经彻底释放资源（state = 0），返回 true，否则返回 false。

protected boolean tryRelease(int arg) {
     throw new UnsupportedOperationException();
}

unparkSuccessor(Node)

• 用于唤醒等待队列中下一个线程。
• 执行流程。
  1. 如果头结点 head 的 waitStatus 值为 -1，则用 CAS 指令重置为 0。
  2. 找到 waitStatus 值小于 0 的结点 s，通过 LockSupport.unpark(s.thread) 唤醒线程。

private void unparkSuccessor(Node node) {
        //node 为当前线程所在结点。
        int ws = node.waitStatus;
        if (ws < 0) //置零当前线程所在的结点状态，允许失败。
            compareAndSetWaitStatus(node, ws, 0);

        Node s = node.next; //找到下一个需要唤醒的结点 s。
        if (s == null || s.waitStatus > 0) { //如果为空或取消状态
            s = null;
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0) // <=0 的结点，都是有效结点。
                    s = t;
        }
        if (s != null)
            LockSupport.unpark(s.thread); //唤醒
}

2.2 共享模式

2.2.1 acquireShared(int)（线程获取锁的过程）

• 此方法是共享模式下线程获取共享资源的顶层入口。
  • 获取指定量的资源，获取成功则直接返回，获取失败则进入等待队列，直到获取到资源为止，整个过程忽略中断。
• acquireShared() 的流程。
  1. tryAcquireShared() 尝试获取资源，成功则直接返回。
  2. 失败则通过 doAcquireShared() 进入等待队列，直到获取到资源为止才返回。
• 跟 acquire() 的流程大同小异，多了一步当前结点拿到资源后（还有资源剩余）继续唤醒后继结点的操作（共享）。

public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);
}

---

tryAcquireShared(int)

• tryAcquireShared() 需要自定义同步器实现。
  • AQS 已经定义了该方法返回值的语义。
    • 负数 代表获取失败。
    • 0 代表获取成功，但没有剩余资源。
    • 正数 表示获取成功，还有剩余资源，其他线程还可以去获取。

protected int tryAcquireShared(int arg) {
     throw new UnsupportedOperationException();
}

doAcquireShared(int)

• 此方法用于将当前线程加入等待队列尾部休息，直到其他线程释放资源唤醒自己，自己成功拿到相应量的资源后才返回。

private void doAcquireShared(int arg) {
        final Node node = addWaiter(Node.SHARED); //加入队列尾部，SHARED 模式。
        boolean failed = true; //是否成功标志
        try {
            boolean interrupted = false; //等待过程中是否被中断过的标志
            for (;;) {
                final Node p = node.predecessor(); //获得前驱结点
                if (p == head) { //如果结点为 head 结点的下一个，因为 head 是拿到资源的线程，此时 node 被唤醒，很可能是 head 用完资源来唤醒自己的。
                    int r = tryAcquireShared(arg); //尝试获取资源
                    if (r >= 0) { //获取资源成功
                        setHeadAndPropagate(node, r); //将 head 指向自己，如果还有剩余资源可以再唤醒之后的线程。
                        p.next = null; // help GC
                        if (interrupted) //如果等待过程中被打断过，此时将中断补上。
                            selfInterrupt();
                        failed = false;
                        return;
                    }
                }
                //判断状态，寻找安全点，进入 waiting 状态，等着被 unpark() 或 interrupt()。
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
}

• 与 acquireQueued() 相似，流程并没有太大区别。
  • 跟独占模式比，只有当前结点 node 的前驱结点是 head 时，才会去尝试获取资源，资源有剩余的情况再去唤醒之后的结点。如果资源不够，当前结点会继续 park() 等待其他线程释放资源，而 不会去唤醒后续结点（即使后续结点所需资源量更小）。
    • 独占模式下，同一时刻只有一个线程执行，这样做未尝不可。
    • 共享模式下，多个线程是可以同时执行的，因为当前结点资源需求量大，而将后续量小的结点阻塞。这是 AQS 保证 严格按照入队顺序唤醒（保证了公平，降低了并发）。

setHeadAndPropagate(Node, int)

• 此方法在 setHead() 的基础上多了一步，自己苏醒的同时，如果条件符合（还有剩余资源），还会去唤醒后继结点。

private void setHeadAndPropagate(Node node, int propagate) {
        Node h = head; //获得 head 结点
        setHead(node); //head 指向当前结点
        // 如果还有剩余量，继续唤醒下一个结点
        if (propagate > 0 || h == null || h.waitStatus < 0 ||
            (h = head) == null || h.waitStatus < 0) {
            Node s = node.next;
            if (s == null || s.isShared())
                doReleaseShared();
        }
}

2.2.2 releaseShared()（线程释放锁的过程）

• 此方法是共享模式下线程释放共享资源的顶层入口。
  • 会释放指定量的资源，如果成功释放且允许唤醒等待线程，会唤醒等待队列里的其他线程来获取资源。
  • 独占模式下的 tryRelease() 需要在完全释放掉资源（state = 0）后，才会返回 true 去唤醒其他线程，主要是基于独占下可重入的考量。
  • 共享模式下的 releaseShared() 没有这种要求，共享模式实质就是控制一定量的线程并发执行，只要拥有资源的线程在释放掉部分资源后就可以唤醒后继等待结点。
    • 例如，资源总量是 13，A（5）和 B（7）分别获取到资源并发运行，C（4）到来时只剩 1 个资源就需要等待。
    • A 在运行过程中释放掉 2 个资源量，然后 tryReleaseShared(2) 返回 true 唤醒 C，C只有 3 个资源量仍不够，继续等待。
    • 随后 B 又释放 2 个资源量，tryReleaseShared(2) 返回 true 唤醒 C，C 发现资源量 5 个足够自己使用，然后 C 就可以跟 A 和 B 一起运行。
    • ReentrantReadWriteLock 读锁的 tryReleaseShared() 只有在完全释放掉资源（state = 0）才返回 true，所以自定义同步器可以根据需要决定 tryReleaseShared() 的返回值。

public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
}

---

tryReleaseShared(int)

protected boolean tryReleaseShared(int arg) {
        throw new UnsupportedOperationException();
}

doReleaseShared()

• 主要用于唤醒后继。

private void doReleaseShared() {
       
        for (;;) {
            Node h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == Node.SIGNAL) {
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue;            
                    unparkSuccessor(h); //唤醒后继
                }
                else if (ws == 0 &&
                         !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue; 
            }
            if (h == head)  // head 发生变化
                break;
        }
}

• acquire() 和 acquireShared() 两种方法下，线程在等待队列中都是忽略中断的。
  • AQS也支持响应中断，acquireInterruptibly() 和 acquireSharedInterruptibly() 即是。

---

acquireInterruptibly(int)

• 线程中断，则抛出异常，并将中断标志位设置为 false。
• 未中断尝试 tryAcquire() 获取资源。
• 获取失败，则将当前线程加入到等待队列的队尾，与 acquire() 后续流程类似，同时仍需要响应中断。
• 在每次被唤醒时，进行中断检测，如果发现当前线程被中断，抛出 InterruptedException 并退出循环。

public final void acquireInterruptibly(int arg) throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        if (!tryAcquire(arg))
            doAcquireInterruptibly(arg);
}

acquireSharedInterruptibly(int)

• 与共享模式线程获取锁类似，多了响应中断的处理。

public final void acquireSharedInterruptibly(int arg)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        if (tryAcquireShared(arg) < 0)
            doAcquireSharedInterruptibly(arg);
}

tryAcquireNanos(int, long)

• 该方法提供了具备有超时功能的获取状态的调用。
  • 在指定的 nanosTimeout 内没有获取到状态，那么返回 false，反之返回 true。
  • 是 acquireInterruptibly() 的升级版，在判断是否被中断的基础上增加了超时控制。

public final boolean tryAcquireNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        return tryAcquire(arg) ||
            doAcquireNanos(arg, nanosTimeout);
}

---

doAcquireNanos(int, long)

• 针对超时控制这部分的实现，主要需要计算出睡眠的间隔值。
  • 间隔可以表示为 nanosTimeout = System.nanoTime()（睡眠之前记录的时间） + 原有 nanosTimeout – System.nanoTime()（当前时间） 。
  • 如果 nanosTimeout 大于 0，那么还需要当前线程睡眠，反之则返回 false。

private boolean doAcquireNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (nanosTimeout <= 0L)
            return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final Node node = addWaiter(Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return true;
                }
                //计算时间，最后期限减去当前时间，得到了还应该睡眠的时间。
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L)
                    return false;
                if (shouldParkAfterFailedAcquire(p, node) &&
                    nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
}

• doAcquireNanos() 的流程。
  1. 将当前结点 node 加入到队列中。
  2. 如果前驱结点是 head 结点并且成功获取到状态，那么设置自己为 head 结点并退出，返回 true，在指定的 nanosTimeout 之前获取了锁。
  3. 获取状态失败，通过 LockSupport.park 指定当前线程休眠一段时间。
  4. 唤醒后的线程，计算仍需要休眠的时间。尝试再获取状态，如果失败后查看其 nanosTimeout 是否大于0，如果小于 0，那么返回超时（false），没有获取到锁。
     • 如果 nanosTimeout 小于等于 1000L 纳秒，则进入快速的自旋过程。
     • Doug Lea 应该测算了在线程调度器上的切换造成的额外开销，因此在短时 1000 纳秒内就让当前线程进入快速自旋状态，如果这时再休眠相反会让 nanosTimeout 的获取时间变得更加不精确。

2.3 等待队列

• AQS 维护的队列是当前等待资源的队列。
  • 当前线程获取同步状态失败时，同步器会将当前线程以及等待状态等信息构造成为一个结点并将其加入同步队列，同时会阻塞当前线程，当同步状态释放时，会把首结点中的线程唤醒，使其再次尝试获取同步状态。

同步队列

• 每个 Condition 维护着一个队列，该队列的作用是维护一个等待 singal 信号的队列。

等待队列

• 同步队列和等待队列使用的是同一种结点类型 AQS.Node。

2.3.1 Condition 接口

• 同步队列和等待队列的作用是不同的。每个线程只能存在于同步队列或等待队列中的一个。
• 任意一个 Java 对象，都拥有一组监视器方法定义在（ java.lang.Object 上），主要包括 wait()、notify()、notifyAll() 方法，这些方法与 synchronized 同步关键字配合，可以实现等待/通知模式。
• Condition 接口提供了类似 Object 的监视器方法，与 lock 配合可以实现等待/通知模式。

public interface Condition {
    void await() throws InterruptedException;
    void awaitUninterruptibly();
    long awaitNanos(long nanosTimeout) throws InterruptedException;
    boolean await(long time, TimeUnit unit) throws InterruptedException;
    boolean awaitUntil(Date deadline) throws InterruptedException;
    void signal();
    void signalAll();
}

方法	说明
await()	调用此方法后，会使当前线程在接收到唤醒信号（signal）之前或被中断之前一直处于等待休眠状态。调用此方法后，当前线程会释放持有的锁。如果当前等待线程从该方法返回（被唤醒），那么在返回之前会重新获取锁（获取到锁才能继续执行）。
await(long time,TimeUnit unit)	调用此方法后，会使当前线程在接收到唤醒信号之前、被中断之前或到达指定等待时间之前一直处于等待状态。如果在从此方法返回前检测到等待时间超时，则返回 false，否则返回 true。
awaitNanos(long nanosTimeout)	该方法等效于 await(long time,TimeUnit unit) 方法，只是等待的时间是 nanosTimeout 指定的以毫微秒数为单位的等待时间。该方法返回值是所剩毫微秒数的一个估计值，如果超时，则返回一个小于等于 0 的值。可以根据该返回值来确定是否要再次等待，以及再次等待的时间。
awaitUninterruptibly()	当前线程进入等待状态直到被通知，该方法对中断忽略。
awaitUntil(Date deadline)	当前线程进入等待状态直到被通知，中断或者到某个时间，如果没有到指定时间就被通知，返回 true，否则表示到了指定时间，返回 false。
signal()	唤醒一个等待线程，如果所有的线程都在等待此条件，则选择其中的一个唤醒。在从 await 返回之前，该线程必须重新获取锁。
signalAll()	唤醒所有等待线程，如果所有的线程都在等待此条件，则唤醒所有线程。 在从 await 返回之前，每个线程必须重新获取锁。

2.3.2 Condition 的实现

• Condition 的实现类是 ConditionObject。
  • ConditionObject 是 AQS 的内部类，Condition 的操作需要获取相关联的锁，需要和同步器挂钩。
  • 每个 Condition 对象都包含着一个队列（等待队列），Condition 中也有结点的概念，在将线程放到等待队列中时会构造结点。
• 等待队列也是一个 FIFO 的队列，在队列中的每个节点都包含了一个线程引用，该线程就是在 Condition 对象上等待的线程，如果一个线程调用了 await 方法，那么该线程将会释放锁，构造成结点加入等待队列并进入等待状态。
• 一个 Condition 包含一个等待队列，Condition 拥有首结点（firstWaiter）和尾结点（lastWaiter）。
• 以下使用 生产者和消费者模式 用例进行说明同步队列和等待队列之间的区别与协同工作。
  • 在一个有大小的队列 queue 中，生产者往队列中放数据，消费者从队列中取数据，当队列不满时，生产者可以继续生产数据，当队列不空时，消费者可以继续取数据，如果不符合条件，则等待，直到符合条件为止。

public class TestQueue<T> {

    //队列大小
    private int size;
    //list 充当队列
    private List<T> queue;
    //锁
    private Lock lock = new ReentrantLock();
    //保证队列大小不 <0 的 condition
    private Condition notEmpty = lock.newCondition();
    //保证队列大小不 >size 的 condition
    private Condition notFull = lock.newCondition();

    public TestQueue(int size) {
        this.size = size;
        queue = new ArrayList<T>();
    }

    public void product(T t) throws Exception {
        lock.lock();
        try {
            //如果队列满，则不能生产，等待消费者消费数据。
            while (size == queue.size()) {
                notFull.await();
            }
            //队列已经有空位置，放入一个数据。
            queue.add(t);
            //通知消费者可以继续消费。
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }

    public T consume() throws Exception {
        lock.lock();
        try {
            //队列为空，则不能消费，等待生产者生产数据。
            while (queue.size() == 0) {
                notEmpty.await();
            }
            //队列已经有数据，拿掉一个数据
            T t = queue.remove(0);
            //通知生产者可以继续生产。
            notFull.signal();
            return t;
        } finally {
            lock.unlock();
        }
    }
}

1. 假设存在线程 a 和线程 b。
   • 线程 a 调用 product() 方法，执行了 lock.lock()，线程 a 加入到 AQS 同步队列中，构建结点 A。
   • 线程 b 调用 consume() 方法，执行了 lock.lock()，线程 b 加入到 AQS 同步队列中，构建结点 B。
   • 结点 B 是结点 A 的后继结点，结点 A 是结点 B 的前驱结点。
   • 同步队列初始状态为下图。

同步队列的初始状态

2. 假设自定义队列 queue 已满，线程 a（结点 A）调用 notFull.await() 方法。
   • 线程 a（结点 A）从 AQS 同步队列中被移除，对应操作是锁的释放。
   • 线程 a（结点 A）被加入到 Condition 等待队列，线程 a 需要等待 singal 信号。
3. 线程 b（结点 B）由于线程 a（结点 A）释放锁被唤醒，成为同步队列的头结点且同步状态为 0 可以获取锁。
   • 线程 b（结点 B）获取锁。

结点 A 进入等待队列

4. 假设线程 b（结点 B）调用 notFull.singal() 方法，Condition 等待队列中只有结点 A，把它取出来加入到 AQS 同步队列中。
   • 这时候线程 a（结点 A）并没有被唤醒。

结点 A 重新进入 AQS 队列

5. 线程 b（结点 B）notFull.signal() 方法执行完毕，调用 lock.unlock() 方法释放锁。线程 a（结点 A）成为 AQS 首结点并且同步状态可获取，线程 a（结点 A）被唤醒，继续执行。

6. AQS 按从头到尾的顺序唤醒线程，直到等待队列中的线程被执行完毕结束。

---

await（等待）

public final void await() throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                LockSupport.park(this);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null) // clean up if cancelled
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
}

• await（等待）的流程。

  1. 如果线程被中断，抛出中断异常。
  2. 生成一个结点 node（与当前线程绑定），并将该结点加入等待队列中。
     • 如果尾结点状态不是 CONDITION，也就是线程任务被取消了，那么需要从等待队列中清除掉。
  3. 释放该线程的锁（状态）。
     • 因为某线程可能多次调用（重入）了 lock() 方法，需要将状态全部释放，这样后面的线程才能重新从 state = 0 开始竞争锁。
  4. 直到当前结点不在同步队列中，挂起该线程。
     • 如果当前结点的的状态等于 CONDITION 或者前驱结点 pre 为空，则不表示不在同步队列中。
     • 如果当前结点的 next 结点不为空，则表示在同步队列中，next 和 pre 只在同步队列中使用，等待队列不会使用。
     • 如果只是当前结点的前驱结点 pre 不为空，是不能说明该结点就在同步队列中的。
       • 因为同步队列中添加结点的方法，是先设置 node.prev = pred，然后再 CAS 设置 tail，但是 CAS 设置可能失败，从而导致设置了 node 的前驱结点，确并没有把 node 加入同步队列。
  5. 线程唤醒后，获取同步状态（锁）。
     • 执行 acquireQueued()，重新加入到获取同步状态的竞争中（挂起前释放了锁）。
  6. 线程唤醒后，如果不是尾节点，那么检查队列，清除一些取消的节点。

• 因为在执行 await 前，线程获取了锁，所以没有使用 CAS 来保证线程安全。

• 调用 await 后，线程会释放 全部 锁，然后被挂起。

• 如果 await 返回，表明当前线程已经重新获取到了锁。

signal（通知）

public final void signal() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            if (first != null)
                doSignal(first);
}

• signal（通知）的流程。
  • 如果当前不是独占模式，那么就会抛出异常，也就是说 Condition 对于 共享模式 不适用。
  • 获取第一个等待结点，然后进行唤醒工作。
    • 重新设置 firstWaiter，指向第一个 waiter 的 nextWaiter。
    • 如果第一个 waiter 的 nextWaiter 为 null，说明当前队列中只有一个 waiter，将 lastWaiter 置空，然后执行 transferForSignal() 方法。
    • transferForSignal() 方法将一个结点从等待队列转换到同步队列。
      • 尝试将 node 的 waitStatus 从 CONDITION 置为 0，如果失败直接返回 false。
      • 当前结点调用 enq 方法进入同步队列。
      • 当前结点通过 CAS 机制将 waitStatus 置为 SIGNAL，返回 true，代表唤醒成功。
• 某个被 await() 的节点被唤醒后并不意味着它后面的代码会立即执行，它会被加入到同步队列的尾部。
• 如果 transferForSignal() 执行失败，会返回 false，然后会对下个结点进行唤醒，同时 firstWaiter 也会被重新设置，最终取消状态的结点会被移出等待队列。

final boolean transferForSignal(Node node) {
        /*
         * If cannot change waitStatus, the node has been cancelled.
         */
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;
        /*
         * Splice onto queue and try to set waitStatus of predecessor to
         * indicate that thread is (probably) waiting. If cancelled or
         * attempt to set waitStatus fails, wake up to resync (in which
         * case the waitStatus can be transiently and harmlessly wrong).
         */
        Node p = enq(node);
        int ws = p.waitStatus;
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            LockSupport.unpark(node.thread);
        return true;
    }

2.4 问题

2.4.1 插入节点的代码顺序

源码

• addWaiter() 和 enq() 方法中，先将 node.prev 设置为 tail 结点，再尝试 CAS 修改。

Node pred = tail;
if (pred != null) {
      node.prev = pred;
      if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
     }
}

修改

• 尝试 CAS 修改后，再设置结点之间的双向链接。

Node pred = tail;
if (pred != null) {
      //node.prev = pred;  // del
      if (compareAndSetTail(pred, node)) {
            node.prev = pred; // add
            pred.next = node;
            return node;
     }
}

分析

• 双向链表目前没有基于 CAS 原子插入的手段，代码按上述修改后执行，会导致这一瞬间的 tail 的 prev 为 null，使得这一瞬间队列处于一种不一致的中间状态。

2.4.2 唤醒节点从 tail 向前遍历

源码

• unparkSuccessor 方法中唤醒后继结点时，是从 tail 向前查找最接近 node 的非取消节点。

Node s = node.next; //找到下一个需要唤醒的结点 s。
if (s == null || s.waitStatus > 0) { //如果为空或取消状态
      s = null;
      for (Node t = tail; t != null && t != node; t = t.prev)
           if (t.waitStatus <= 0) // <=0 的结点，都是有效结点。
                s = t;
}

分析

• node.next 为 null，不代表 node 为 tail。
• 当有新线程结点通过 addWaiter 中的 if 分支或者 enq 方法添加自己，并且 compareAndSetTail 成功，但是还未进行 node.next = 新结点 设置。
• 这时 node.next 虽然为 null，但实际上 node 对象已经拥有后续结点。

2.4.3 PROPAGATE 状态存在的意义

源码

private void setHeadAndPropagate(Node node, int propagate) {
        Node h = head; // Record old head for check below
        setHead(node);
        if (propagate > 0 || h == null || h.waitStatus < 0 ||
            (h = head) == null || h.waitStatus < 0) { //Node.PROPAGATE 状态就是为了此处可以读取到 h.waitStatus < 0（PROPAGATE 值为 -3）。
            Node s = node.next;
            if (s == null || s.isShared())
                doReleaseShared();
        }
}

• JSR 166 repository 上 Revision1.73 中，PROPAGATE 状态被引入用以修复 bug 6801020。

修复前版本

private void setHeadAndPropagate(Node node, int propagate) {
        Node h = head; 
        setHead(node);
        if (propagate > 0 && node.waitStatus != 0) {
            Node s = node.next;
            if (s == null || s.isShared())
                unparkSuccessor(node);
        }
}

分析

• 假设存在将要信号量释放的 T3 和 T4，释放顺序为先 T3 后 T4。
• 假设存在某次循环中队列里排队的结点情况为 head -> T1 node -> tail。
• 修复前版本执行流程。
  1. T3 调用 releaseShared()，直接调用了 unparkSuccessor(head)，head 的等待状态从 -1 变为 0。
  2. T1 由于 T3 释放信号量被唤醒，调用 tryAcquireShared，假设返回值为 0（获取锁成功，但没有剩余资源量）。
  3. T4 调用 releaseShared()，此时 head.waitStatus 为 0（此时读到的 head 和 1 中为同一个head），不满足条件，因此不调用 unparkSuccessor(head)。
  4. T1 获取信号量成功，调用 setHeadAndPropagate 时，因为不满足 propagate > 0（2 的返回值也就是 propagate（剩余资源量） == 0），从而不会唤醒后继结点，出现线程 hang 住问题。
• 修复后版本（源码）执行流程。
  1. T3 调用 releaseShared()，直接调用了 unparkSuccessor(head)，head 的等待状态从 -1 变为 0。
  2. T1 由于 T3 释放信号量被唤醒，调用 tryAcquireShared，假设返回值为 0（获取锁成功，但没有剩余资源量）。
  3. T4 调用 releaseShared()，此时 head.waitStatus 为 0（此时读到的 head 和 1 中为同一个 head），调用 doReleaseShared() 将等待状态置为 PROPAGATE。
  4. T1 获取信号量成功，调用 setHeadAndPropagate 时，读到 h.waitStatus < 0，从而调用doReleaseShared() 唤醒 T2。
• 在 PROPAGATE 引入之前，之所以可能会出现线程 hang 住的情况，在于 releaseShared() 有竞争的情况下，可能会有队列中处于等待状态的结点因为第一个线程完成释放唤醒，第二个线程获取到锁，但还没设置好 head，又有新线程释放锁，但是读到老的 head 状态为 0，导致释放但不唤醒，最终后一个等待线程既没有被释放线程唤醒，也没有被持锁线程唤醒。仅仅靠 tryAcquireShared() 的返回值来决定是否要将唤醒传递下去是不充分的。

2.4.4 AQS 如何防止内存泄露

• AQS 在无竞争条件下，甚至都不会 new 出 head 和 tail 节点。
• 线程成功获取锁时设置 head 节点的方法为 setHead。
  • 由于头结点的 thread 并不重要，此时会置 node 的 thread 和 prev 为 null。
  • 会置原先 head 的 next 为 null，从而实现队首元素的安全移出。
• 取消结点时，会令 node.thread = null，在 node 不为 tail 的情况下，使 node.next = node。

参考资料

http://www.cnblogs.com/waterystone/p/4920797.html
https://www.jianshu.com/p/d8eeb31bee5c
https://www.cnblogs.com/micrari/p/6937995.html
https://blog.csdn.net/u014634338/article/details/77428108
http://www.importnew.com/26300.html