什么是AQS

AbstractQueuedSynchronizer(简称AQS)，是用来构建锁或者其他同步组件的基础框架。

核心思想

使用了一个int成员变量表示同步状态，通过内置的FFIFO队列来实完成资源获取线程的排队工作，并发包的作者(Dung Lea)期望它能够成为实现大部分同步需求的基础。

使用方式

AQS的主要使用方式是继承，子类通过继承同步器并实现它的抽象方法来管理同步状态。

在抽象方法的实现过程中免不了要对同步状态进行更改，这时就需要使用同步器提供的3个方法来操作：

• getState()
• setState(int newState)
• compareAndSetState(int expect,int update)

这三个方法能保证状态的改变是安全的。

子类推荐被定义为自定义同步组件的静态内部类，同步器本身没有没有实现任何同步接口，它仅仅是定义了若干同步状态获取和释放的方法来供同步组件使用，同步器既可以支持独占式地获取同步状态，也可以支持共享式地获取同步转改，这样就可以方法实现不同类型的同步组件(ReentrantLock、ReentrantReadWriteLock和CountDownLatch等)。

同步器是实现锁(也可以是任意同步组件)的关键，在锁的实现中聚合同步器，利用不同器实现锁的语义。可以这样理解：锁是面向使用者的，它定义了使用者与锁交互的接口(比如可以允许两个线程并行访问)，隐藏实现细节；同步器面向的是锁的实现者，它简化了锁的实现方式，屏蔽了同步状态管理、线程的排队，等待与唤醒等底层操作。锁和同步器很好地隔离了使用者和实现者所需关注的领域。

队列同步器的接口

同步器的设计是基于模版方法模式的，也就是说，使用者需要继承同步器并重写指定的方法，随后将同步器组合在自定义同步组件的实现中，并调用同步器提供的模板方法，而这些模版方法将会调用使用者重写的方法。

重写同步器指定的方法时，需要使用同步器提供的如下3个方法来访问或修改同步状态：

• getState()：获取当前的同步状态
• setState(int newState)：设置当前的同步状态
• compareAndSetState(int expect,int update)：使用CAS设置当前状态，该方法能够保证状态设置的原子性。

同步器可重写的方法与描述如下图所示：

实现自定义组件时，将会调用同步器的模版方法，这些(部分)模版方法的描述如下图所示：

同步器提供的模板方法，基本上可以分为三类：独占式获取与释放同步状态、共享式获取与释放同步状态、查询同步队列中的等待线程情况。

自定义同步组件将使用同步器提供的模版方法来实现自己的同步语义。

只有掌握了同步器的工作原理才能更加深入地理解并发包中其他的并发组件，下面通过一个独占锁的示例来深入了解一下同步器的工作原理。

/**
 * @ClassName : 自定义互斥同步组件
 * @Description :
 * @Author : 二师兄
 * @Date: 2021-09-18 09:45:23
 */
public class Mutex implements Lock {

    private Sync sync = new Sync();

    /**
     * 自定义同步器
     */
    private static class Sync extends AbstractQueuedSynchronizer{

        @Override
        protected boolean tryAcquire(int arg) {
            // 尝试CAS修改同步状态，修改成功则获取锁
            if(compareAndSetState(0,1)){
                setExclusiveOwnerThread(Thread.currentThread());
               return true;
            }
            else {
                // 如果CAS修改失败，判断当前加锁线程是否是当前线程，如果是,同步状态+1；如果不是，直接返回false，进入同步队列中等待唤醒
                int state = getState();
                if(state>0){
                    Thread exclusiveOwnerThread = getExclusiveOwnerThread();
                    if(Thread.currentThread() == exclusiveOwnerThread){
                        return compareAndSetState(state,state+1);
                    }
                    else {
                        return false;
                    }
                }
            }
            return false;
        }

        @Override
        protected boolean isHeldExclusively() {
            // 同步状态>=1，表示当前线程独占了同步状态
            return getState() >= 1;
        }

        @Override
        protected boolean tryRelease(int arg) {
            // 不能释放本线程加的锁
            Thread currentThread = Thread.currentThread();
            if(getExclusiveOwnerThread()!=currentThread){
                throw new IllegalMonitorStateException();
            }
            int state = getState();
            if(state>0){
                if(compareAndSetState(state,state-1)){
                    if(getState()==0){
                        setExclusiveOwnerThread(null);
                        return true;
                    }
                }
                return false;
            }
            return getState()==0;
        }
    }

    @Override
    public void lock() {
        // 调用独占式获取同步状态模版方法
        sync.acquire(1);
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {
        //调用可中断的独占式获取同步状态模版方法
        sync.acquireInterruptibly(1);
    }

    @Override
    public boolean tryLock() {
        return sync.tryAcquire(1);
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        // 调用可中断的、有超时限制的独占式获取同步状态模版方法
        return sync.tryAcquireNanos(1,unit.toNanos(time));
    }

    @Override
    public void unlock() {
        // 调用独占式释放同步状态的模版方法
        sync.release(1);
    }

    @Override
    public Condition newCondition() {
        // 返回一个Condition,每个Condition都包含了一个队列
        return sync.new ConditionObject();
    }
}

上述实例中，独占锁Mutex是一个自定义同步组件，它在同一时刻只允许一个线程占有锁。Mutex定义了一个静态内部类，该内部类继承了同步器并实现了独占锁获取和释放同步状态的方法。在tryAcquire方法中，如果经过CAS把同步状态从0改成1成功，则代表获取到了同步状态。同时，如果同步状态>0，则需要判断获取到同步状态的线程是否是当前线程，如果是，同步状态+1，这就实现了锁的可重入，如果不是，代表其他线程已经获取了同步状态，当前线程加入到同步队列中。而在tryRelease方法中，CAS操作对同步状态-1，如果-1后同步状态为0，返回true，代表释放同步状态，这是会唤醒同步队列中第一个线程。

用户使用Mutex时并不会直接和内部同步器打交道，而是调用Mutex提供的方法，这样就大大降低了实现一个可靠自定义同步组C件的门槛。

队列同步器的实现分析

接下来从实现角度分析同步器是如何完成过线程同步的，主要包括：同步队列、独占式同步状态获取与释放、共享式同步状态与释放、以及超时空获取同步状态等核心数据结构与模版方法。

同步队列

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

同步队列中的节点用来保存获取同步状态失败的线程引用、等待状态、以及前驱和后继节点，节点的属性类型与名称以及描述如下：

int waitStatus

等待状态。包含如下状态：

• CANCELED(0)：由于在同步队列中等待的线程等待超时或者被中断，需要从同步队列中取消等待，节点进入该状态将不会变化。
• SIGN(-1)：后继节点的线程处于等待状态，而当前节点的线程如果释放了同步状态或者被取消，将会通知后继节点，使后继节点的线程得以运行。
• CONDITION(-2)：节点在等待队列中，节点线程等待在Condition上，当其他线程对Condition调用signal()方法后，该节点会从等待队列中转移到同步队列，加入对同步状态的获取中。
• PROPAGATE(-3)：下一次共享式同步状态获取将会无条件传播下去
• INITIAL(0)：初始状态

Node prev：前驱节点，当节点加入同步队列中被设置(尾部添加)

Node next：后继节点

Node nextWaiter：等待队列中的后继节点，如果当前节点是共享的，那么该字段是一个SHARED常量

Thread thread：获取同步状态的线程

节点是构成同步队列的基础，同步器拥有首节点(head)和尾节点(tail)，没有成功获取同步状态的线程将会成为节点添加到该队列的尾部，同步队列的基本结构如下图所示：

同步器包含了两个节点类型的引用，一个指向头节点，一个指向尾节点。试想一下，当一个线程成功地获取了同步状态，其他线程将无法获取到同步状态，转而被构造成为节点并加入到同步队列中，而这个加入同步队列的过程必须保证线程安全，因为同步器提供了一个基于CAS的设置尾节点的方法：compareAndSetTail(Node expect，Node update)，它需要传递当前线程认为的尾节点和当前节点，只有设置成功后，当前节点才会与之前的尾节点建立关联。

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

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

独占式同步状态的获取与释放

通过调用同步器的acquire方法可以获取同步状态，该方法对中断不敏感，也就是由于线程同获取同步状态失败后进入同步队列中，后续对线程进行中断操作时，线程不会从队列中移除，该方法的代码如下图所示：

/**
 * 获取独占锁
 */
public final void acquire(int arg) {
  //尝试获取锁
  if (!tryAcquire(arg) &&
      acquireQueued(addWaiter(Node.EXCLUSIVE), arg))//独占模式
    selfInterrupt();
}

上述代码主要完成了同步状态获取、节点构造、加入同步队列以及在同步队列中自旋等待的相关工作，其主要逻辑是：首先调用自定义同步器实现的tryAcquire(int arg)方法，该方法保证线程安全地获取同步状态，如果同步状态获取失败，则构造同步节点(独占式Node.Exclusive，同一时刻只能有一个线程成功获取同步状态)并通过addWaiter(Node node)方法将该节点加入到同步队列的尾部，最后调用acquireQueued(Node node,int arg)方法，使得该节点以“死循环”的方式获取同步状态。如果获取不到则阻塞节点中的线程个，而被阻塞线程的唤醒主要依靠前驱节点的出队或者阻塞线程被中断来实现。

下面分析一下相关工作。首先是节点的构造以及加入同步队列。

    private Node addWaiter(Node mode) {
        // 1. 将当前线程构建成Node类型
        Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        Node pred = tail;
        // 2. 1当前尾节点是否为null？
        if (pred != null) {
            // 2.2 将当前节点尾插入的方式
            node.prev = pred;
            // 2.3 CAS将节点插入同步队列的尾部
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }
    /**
     * 节点加入CLH同步队列
     */
    private Node enq(final Node node) {
        for (;;) {
            Node t = tail;
            if (t == null) { // Must initialize
                //队列为空需要初始化，创建空的头节点
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {
                node.prev = t;
                //set尾部节点
                if (compareAndSetTail(t, node)) {//当前节点置为尾部
                    t.next = node; //前驱节点的next指针指向当前节点
                    return t;
                }
            }
        }
    }

上述代码通过使用compareAndSetTail(Node expect,Node update)方法来确保节点能够被线程安全添加。试想一下，如果使用一个普通的LinkedList来维护节点之间的关系，如果一个线程获取到了同步状态，而其他多个线程由于调用tryAcquire(int arg)方法获取同步状态失败而并发的被添加到LinkedList时，LinkedList将难以保证Node的正确添加，最终的结果可能是节点的数量有偏差，而且顺序也是混乱的。

在enq(final Node node)方法中，同步器通过“死循环”来保证节点的正确添加，在“死循环”中只有通过CAS将节点设置成为尾节点之后，当前线程才能从该方法返回，否则，当前线程不断地尝试设置。可以看出，enq(final Node node)方法将并发添加节点的请求通过CAS变得“串行化”了。

节点进入同步队列之后，就进入一个自旋的过程。每个节点(或者说每个线程)都在自省地观察，当条件满足，获取到了同步状态，就可以从这个自旋过程中退出，否则依旧留在这个自旋过程中(并会阻塞节点的线程)，代码如下所示：

   /**
     * 已经在队列当中的Thread节点，准备阻塞等待获取锁
     */
    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {//死循环
                final Node p = node.predecessor();//找到当前结点的前驱结点
                if (p == head && tryAcquire(arg)) {//如果前驱结点是头结点，才tryAcquire，其他结点是没有机会tryAcquire的。
                    setHead(node);//获取同步状态成功，将当前结点设置为头结点。
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                /**
                 * 如果前驱节点不是Head，通过shouldParkAfterFailedAcquire判断是否应该阻塞
                 * 前驱节点信号量为-1，当前线程可以安全被parkAndCheckInterrupt用来阻塞线程
                 */
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

acquireQueued(final Node node,int arg)方法中，当前线程在“死循环”中尝试获取同步状态，而只有前驱节点是头节点才能够尝试获取同步状态，这是为什么？原因主要有两个：

1. 头节点是成功获取到同步状态的节点，而头节点的线程释放了同步状态后，将会唤醒其后继节点，后继节点的线程被唤醒后需要检查自己的前驱节点是否头节点。
2. 维护同步队列的FIFO原则。由于非首节点线程前驱节点出队或者被中断而从等待状态返回，随后检查自己的前驱是否头节点，如果是则尝试获取同步状态。可以看到节点和节点之间在循环检查的过程中基本不相互通信，而是简单地判断自己的前驱节点是否是头节点，这样就使得节点的释放规则符合FIFO，并且也便于对过早通知的处理(过早通知是指前驱节点不是头节点的线程由于中断而被唤醒)。

独占式同步状态获取流程，如下图所示：

当前线程获取同步状态并执行了相关逻辑之后，就需要释放同步状态，使得后继节点能够继续获取同步状态。通过同步器的release(int arg)方法可以释放同步状态，该方法在释放同步状态之后，会唤醒其后继节点，进而使后继节点重新尝试获取同步状态，该方法代码如下所示：

   /**
     * 释放独占模式持有的锁
     */
    public final boolean release(int arg) {
        if (tryRelease(arg)) {//释放一次锁
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);//唤醒后继结点
            return true;
        }
        return false;
    }

    private void unparkSuccessor(Node node) {
        //获取wait状态
        int ws = node.waitStatus;
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);// 将等待状态waitStatus设置为初始值0

        /**
         * 若后继结点为空，或状态为CANCEL（已失效），则从后尾部往前遍历找到最前的一个处于正常阻塞状态的结点
         * 进行唤醒
         */
        Node s = node.next; 
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        if (s != null)
            LockSupport.unpark(s.thread);
    }

该方法执行时，会唤醒头节点的后继节点线程，unparkSuccessor方法使用LockSupport来唤醒处于等待状态的线程。

独占式同步状态获取与释放总结：

1. 在获取同步状态时，同步器维护一个同步队列，获取同步状态失败的线程都会被加到同步队列中并在同步队列中进行自旋；
2. 移除队列或停止自旋的条件是前驱节点为头节点且成功获取了同步状态
3. 在释放同步状态时，同步器调用tryRelease(int arg) 释放同步状态，然后唤醒头节点的后继节点。

共享式同步状态的获取与释放

共享式获取与独占式获取最主要的区别在于同一时刻能否有多个线程同时获取到同步状态。

通过调用同步器的acquireShared(int arg)方法可以共享式地获取同步状态，该方法的代码如下：

   /**
     * 请求获取共享锁
     */
    public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0)//返回值小于0，获取同步状态失败，排队去；获取同步状态成功，直接返回去干自己的事儿。
            doAcquireShared(arg);
    }

    /**
     * 尝试获取共享锁
     */
    private void doAcquireShared(int arg) {
        final Node node = addWaiter(Node.SHARED);//入队
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();//前驱节点
                if (p == head) {
                    int r = tryAcquireShared(arg); //非公平锁实现，再尝试获取锁
                    //state==0时tryAcquireShared会返回>=0(CountDownLatch中返回的是1)。
                    // state为0说明共享次数已经到了，可以获取锁了
                    if (r >= 0) {//r>0表示state==0,前继节点已经释放锁，锁的状态为可被获取
                        //这一步设置node为head节点设置node.waitStatus->Node.PROPAGATE，然后唤醒node.thread
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        if (interrupted)
                            selfInterrupt();
                        failed = false;
                        return;
                    }
                }
                //前继节点非head节点，将前继节点状态设置为SIGNAL，通过park挂起node节点的线程
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

在acquireShared(int arg)方法中，同步器调用tryAcquireShared(int arg)方法尝试获取同步状态，当返回值大于等于0时，表示能够获取到同步状态。因此，在共享式获取的自旋过程中，成功获取到同步状态并退出自旋的条件是tryAcquireShared(int arg)方法返回值大于等于0。可以看到，在doRequireShared(int arg)方法的自旋中过程中，如果当前节点的前驱节点为头节点时，尝试获取同步状态，如果返回值大于等于0，表示该次获取同步状态成功并从自旋过程中退出。

与独占式一样，共享式获取也需要释放同步状态，通过调用releaseShared(int arg)方法可以释放同步状态，该方法代码如下：

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

/**
     * 把当前结点设置为SIGNAL或者PROPAGATE
     * 唤醒head.next(B节点)，B节点唤醒后可以竞争锁，成功后head->B，然后又会唤醒B.next，一直重复直到共享节点都唤醒
     * head节点状态为SIGNAL，重置head.waitStatus->0，唤醒head节点线程，唤醒后线程去竞争共享锁
     * head节点状态为0，将head.waitStatus->Node.PROPAGATE传播状态，表示需要将状态向后继节点传播
     */
    private void doReleaseShared() {
        for (;;) {
            Node h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == Node.SIGNAL) {//head是SIGNAL状态
                    /* head状态是SIGNAL，重置head节点waitStatus为0，E这里不直接设为Node.PROPAGAT,
                     * 是因为unparkSuccessor(h)中，如果ws < 0会设置为0，所以ws先设置为0，再设置为PROPAGATE
                     * 这里需要控制并发，因为入口有setHeadAndPropagate跟release两个，避免两次unpark
                     */
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue; //设置失败，重新循环
                    /* head状态为SIGNAL，且成功设置为0之后,唤醒head.next节点线程
                     * 此时head、head.next的线程都唤醒了，head.next会去竞争锁，成功后head会指向获取锁的节点，
                     * 也就是head发生了变化。看最底下一行代码可知，head发生变化后会重新循环，继续唤醒head的下一个节点
                     */
                    unparkSuccessor(h);
                    /*
                     * 如果本身头节点的waitStatus是出于重置状态（waitStatus==0）的，将其设置为“传播”状态。
                     * 意味着需要将状态向后一个节点传播
                     */
                }
                else if (ws == 0 &&
                        !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue;                // loop on failed CAS
            }
            if (h == head) //如果head变了，重新循环
                break;
        }
    }

该方法在释放同步状态后，将会唤醒后续处于等待状态的节点。对于能够支持多个线程同时访问的并发组件，它和独占式主要区别在于：tryReleaseShared(int arg)方法必须确保同步状态线程安全释放，一般通过循环和CAS来保证，因为释放同步状态的操作会同时来自多个线程。