我们了解到 AQS 有两个核心组成部分，一个是 int 型的同步状态 state，另一个就是一个内置的 FIFO 同步队列。上一篇文章简单的介绍了一下这个同步队列，本文将会具体的阐述这个同步队列的实现与等待线程排队的原理。

同步队列的数据结构

同步器依赖内部的同步队列来完成同步状态的管理，当前线程获取同步状态失败时，同步器会将当前线程以及等待状态等信息构造成为一个节点（Node）并将其加入同步队列，同时会阻塞当前线程，当同步状态释放时，会把首节点中的线程唤醒，使其再次尝试获取同步状态。

我们先来看一下 AQS 中该同步队列的源码。

static final class Node {
        /** 共享模式 */
        static final Node SHARED = new Node();
        /** 独占模式 */
        static final Node EXCLUSIVE = null;

        /** 
        * 由于超时或中断，在同步队列中的节点会取消等待
        * 被取消的节点时不会参与到竞争中的，并且进入该状态的节点不会转变成其他状态了
        */
        static final int CANCELLED =  1;
        /** 后继节点的线程处于等待状态，而当前节点的线程如果释放了同步状态或者被取消，将会通知后继节点，使后继节点的线程得以运行 */
        static final int SIGNAL    = -1;
        /** 
        * 节点在Condition等待队列中，节点线程等待在Condition上。
        * 当其他线程对Condition调用了signal()后，该节点将会从等待队列中转移到同步队列
        * 中，加入到同步状态的获取中 
        */
        static final int CONDITION = -2;
        /**
         * 表示下一次共享式同步状态获取将会无条件地传播下去
         */
        static final int PROPAGATE = -3;
        
        /**
         * waitStatus 除了会处于上数这几种状态中，还会处于initial状态
         * 值为1，表示初始状态
         */
        volatile int waitStatus;

        /**
         * 前驱节点.
         */
        volatile Node prev;

        /**
         * 后继节点
         */
        volatile Node next;

        /**
         * 获取同步状态的线程
         */
        volatile Thread thread;

        /**
         * nextWaiter有两种存储情况：
         * 一、存储的是Condition队列中的后继节点,
         * 二、如果自定义同步器实现的是共享锁，那么nextWaiter存储的代码最上面的常量SHARED 
         */
        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() {}

        Node(Thread thread, Node mode) { 
            this.nextWaiter = mode;
            this.thread = thread;
        }

        Node(Thread thread, int waitStatus) { 
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }

我们可以看出来，这个同步队列底层实现就是个双向链表，而且同步器中还维护了该双向链表的头尾节点。

    /**
     * Head of the wait queue, lazily initialized.  Except for
     * initialization, it is modified only via method setHead.  Note:
     * If head exists, its waitStatus is guaranteed not to be
     * CANCELLED.
     */
    private transient volatile Node head;

    /**
     * Tail of the wait queue, lazily initialized.  Modified only via
     * method enq to add new wait node.
     */
    private transient volatile Node tail;

看源码中的注释我们也会发现，这两个头尾节点的引用也是采用了延迟初始化的思想。

同步队列的基本结构如下图所示

在这里插入图片描述

值得注意的是，其实头节点有两种情况：

啥也不存，空节点，此时 Node 中的 thread 为 null
正常的 Node，携带着上面刚介绍过的一系列信息

接下来，我们来梳理一下入队与出队的过程。

一、入队

当一个线程成功地获取了同步状态（锁），其他线程将无法获取到同步状态，此时这些获取同步状态失败的线程会被构造成节点并加入到同步队列中，这就是入队过程，我们来看一下入队过程的源码。

    /**
     * 根据当前线程与锁的模式，创建新的节点并入队
     * @param mode 有两种取值：EXCLUSIVE表示独占锁，SHARED表示共享锁
     * @return 返回新创建的节点
     */
    private Node addWaiter(Node mode) {
        // new一个新的Node出来，参数是当前线程与锁的模式
        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;
    }

加入队列的过程必须要保证线程安全，因为如果保证不了入队的线程安全，那么发生并发入队时有可能产生节点覆盖、顺序乱序等问题。

因此同步器提供了一个基于 CAS 的设置尾节点的方法：
compareAndSetTail(Node expect,Node update)
，它需要传递当前线程“认为”的尾节点和当前节点，只有设置成功后，当前节点才正式与之前的尾节点建立关联。该方法借助 Unsafe 类实现，如下：

    /**
     * CAS tail field. Used only by enq.
     */
    private final boolean compareAndSetTail(Node expect, Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }

分析之前入队的方法：
addWaiter(Node node)
，它首先快速的尝试设置尾节点（入队），如果失败，则调用
enq(Node node)
方法设置尾节点并入队，我们来看一下
enq(Node node)
的源码。

    /**
     * 入队（如果head和tail为null时还会进行初始化）
     * @param node 待插入的节点
     * @return 返回插入节点的前驱
     */
    private Node enq(final Node node) {
        // 这是一个死循环，不用往下看，都能猜到这里是自旋CAS
        for (;;) {
            Node t = tail;
            // 我们上面介绍同步队列数据结构时有提到过，head和tail是延迟初始化的
            // 这里会检查tail是否为null
            if (t == null) { 
                // 如果tail为null，说明当前同步队列是空队列，需要使用CAS先设置头节点
                // 注意这里，头节点使用的是空节点
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {
                node.prev = t;
                //使用CAS设置尾节点并入队
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

在
enq(Node node)
方法中，AQS 通过“死循环”的方式来保证节点可以正确添加，只有成功添加后，当前线程才会从该方法返回，否则会一直执行下去，直到成功入队。

二、出队

同步队列遵循FIFO，首节点是获取同步状态成功的节点，首节点的线程在释放同步状态时，将会唤醒后继节点，而后继节点将会在获取同步状态成功时将自己设置为首节点。

设置首节点是通过获取同步状态成功的线程来完成的，由于只有一个线程能够成功获取到同步状态，因此设置头节点的方法并不需要使用 CAS 来保证，它只需要将首节点设置成为原首节点的后继节点并断开原首节点的 next 引用即可。

由于出队的源码不像入队时有一些单独的方法（比如
addWaiter(Node mode)
和
enq(Node node)
），出队的操作主要在 Release 相关的方法中，看过我上一篇文章的朋友应该知道，与 Release 方法相关的都是对于同步状态的释放，而本篇文章着重介绍的是同步队列，所以这里就阐述一下出队过程，至于具体的源码分析，将会在下一篇文章中给出。

原文链接：https://blog.csdn.net/u013568373/article/details/98719128

同步队列的数据结构

一、入队

二、出队

你可能也喜欢