Java并发：AbstractQueuedSynchronizer（AQS）

队列同步器 AbstractQueuedSynchronizer 是一个公共抽象类。提供一个同步器框架，用于实现依赖于先进先出（FIFO）等待队列的阻塞锁和相关同步器（信号量，事件等）。使用一个 int 成员变量表示同步状态，通过内置的 FIFO 队列来完成资源获取线程的排队工作。

同步器的使用主要是通过集成这个抽象类并实现它的抽象方法来管理同步状态，这个抽象提供了三个方法来对同步状态进行更改操作，分别是 getState()，setState(int) 和 compareAndSetState(int, int)，这三个方法能保证状态的改变是安全的。抽象类的子类最好定义为同步器的静态内部类。

AQS 的设计是基于模板方法模式的，使用者需要继承并重写指定这些方法。随后在实现自定义的同步器的实现中调用这些模板方法，这些模板方法将会调用使用者重写的方法。

同步器提供的模板方法

public final void acquire(int arg)	独占式获取同步状态，如果当前线程获取同步状态成功，则由该方法返回，否则，将会进入同步队列等待，该方法会调用重写的 tryAcquire(int)。
public final void acquireInterruptibly (int arg)	与 acquire(int) 相同，但是该方法相应中断，当前线程未获取到同步状态而进入同步队列中，如果当前线程被中断，则会抛出中断异常并返回。
public final boolean tryAcquireNanos (int arg, long nanosTimeout)	在 acquireInterruptibly(int) 基础上加了超时限制，如果当前线程在规定时间内没有获取到同步状态，则将返回 false，反之，返回 true。
public final void acquireShared(int arg)	共享式的获取同步状态，如果当前线程未获取到同步状态，将会进入同步队列等待，与独占式获取的主要区别是在同一时刻可以有多个线程获取到同步状态。
public final void acquireSharedInterruptibly (int arg)	与 acquireShared(int) 相同，该方法响应中断。
public final boolean tryAcquireSharedNanos (int arg, long nanosTimeout)	在 acquireSharedInterruptibly(int) 基础上增加了超时限制。
public final boolean releaseShared(int arg)	独占式的释放同步状态，该方法会在释放同步状态之后，将同步队列的定义一个线程唤醒。
public final boolean releaseShared(int arg)	共享式的释放同步状态
public final Collection<Thread> getWaitingThreads(ConditionObject condition)	获取等待在同步队列上的线程集合

这些模板方法基本上分为3类：独占式获取与释放同步状态、共享式获取与释放同步状态和查询等待队列中的等待线程情况。这些模板方法在实现自定义同步组件时被调用。

 同步器中可重写的方法

protected boolean tryAcquire(int arg)	独占式获取同步状态，实现该方法需要查询当前状态并判断同步状态是否符合预期，然后在进行CAS设置同步状态。
protected boolean tryRelease(int arg)	独占式释放同步状态，等待获取同步状态的线程将会有机会获取同步状态。
protected int tryAcquireShared(int arg)	共享式获取同步状态，返回大于等于0的值，表示获取成功，反之，获取失败。
protected boolean tryReleaseShared (int arg)	共享式释放同步状态。
protected boolean isHeldExclusively()	当前同步器是否在独占模式下被线程占用，一般方法表示是否被当前线程所独占。

下面是一个自定义同步组件的例子：独占锁 Mutex，同一时刻只有一个线程占有锁，里面定义了一个静态内部类，该内部类继承了同步器并实现了独占式获取和释放同步状态。

public class Mutex implements Lock {

    /**
     * 静态内部类，继承了同步器并实现了独占式获取和释放同步状态。
     */
    private static class Sync extends AbstractQueuedSynchronizer {
        // 是否处于占用状态
        @Override
        protected boolean isHeldExclusively() {
            return getState() == 1;
        }
        // 当状态为0的时候获取锁
        public boolean tryAcquire(int acquires) {
            if (compareAndSetState(0, 1)) {
                setExclusiveOwnerThread(Thread.currentThread());
                return true;
            }
            return false;
        }
        // 释放锁，将状态设置为0
        @Override
        protected boolean tryRelease(int releases) {
            if (getState() == 0)
                throw new IllegalMonitorStateException();
            setExclusiveOwnerThread(null);
            setState(0);
            return true;
        }
        // 返回一个Condition，每个condition都包含了一个condition队列
        Condition newCondition() {
            return new ConditionObject();
        }
    }

    // 只需要将操作代理到Sync上即可
    private final Sync sync = new Sync();

    @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() {
        return sync.newCondition();
    }

    public boolean isLocked() {
        return sync.isHeldExclusively();
    }

    public boolean hasQueuedThreads() {
        return sync.hasQueuedThreads();
    }
}

 AQS的类图：

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

在 Node 类中有以下几种等待状态：

① SIGNAL，值为-1，后继结点的线程处于等待状态，若当前节点的线程释放了同步状态或者说被取消了，则会唤醒后继节点。

② CANCELLED，值为1，由于在同步队列中等待的线程由于超时或中断，需要从同步队列中取消等待。处于取消状态的节点不会再去竞争锁，也就是说不会再被阻塞。节点会一直保持取消状态，而不会转换为其他状态。

③ CONDITION，值为-2，节点在等待队列中，节点线程在等待在 Condition 上，当其他的线程对 Condition 调用了signal() 方法后，该节点将会从等待队列中转移到同步队列中，加入到对同步状态的获取中。

④ PROPAGATE，值为-3，当前线程被唤醒之后，可能还有剩余的资源可以唤醒其他线程，该状态用来表明后续节点会传播唤醒的操作。需要注意的是只有头节点才可以设置为该状态。

⑤ 初始状态，值为 0。

独占式同步状态的核心形式如下：

Acquire:
     while (!tryAcquire(arg)) {
        enqueue thread if it is not already queued;
        possibly block current thread;
     }

Release:
     if (tryRelease(arg))
        unblock the first queued thread;

在JDK 8 中 AQS 中的源代码为：

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

同步状态获取失败时，addWaiter 方法可以把构造的同步节点加入到队列尾部。

　　private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);
        // 尝试在尾部快速添加，后面还有enq方法完善整个添加过程
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
 　}

　　private Node enq(final Node node) {
        for (;;) {
            Node t = tail;
            if (t == null) { // 必须初始化
                if (compareAndSetHead(new Node())) 
                    tail = head;
            } else {
                node.prev = t;
                if (compareAndSetTail(t, node)) { // 通过CAS将节点设置为尾节点
                    t.next = node;
                    return t;
                }
            }
        }
    }

最后调用 acquireQueued方法使得该节点以“死循环”的方式获取同步状态。acquireQueueud(final Node node, int arg) 源码如下，节点自旋获取同步状态。

　　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)) {
                    setHead(node);
                    p.next = null; // GC帮助回收
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())　　　　// 检查并跟新无法获取状态的节点，如果线程应该阻塞，则返回true；第二个函数停下来并检查是否应该中断
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
　　}

同步器的 release方法，当前线程获取同步状态并执行了相应逻辑之后，就需要释放同步状态，使得后续节点能够继续获取同步状态。

    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }

独占式超时获取同步状态 doAcquireNanos方法

    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);
        }
    }

样例代码，其中 withoutMutex() 和 withMutex() 分别是使用和不使用自定义同步器的样例，执行之后会明显发现带自定义同步器 Mutex 的线程不会交替执行。

package concurrent.lock;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;

/**
 * @program: MyPractice
 * @description: 自定义同步组件Mutex，他只允许同一时刻只允许一个线程占有锁
 * @author: Mr.Wu
 * @create: 2019-09-18 20:43
 **/
public class Mutex implements Lock {

    /**
     * 静态内部类，继承了同步器并实现了独占式获取和释放同步状态。
     */
    private static class Sync extends AbstractQueuedSynchronizer {
        // 是否处于占用状态
        @Override
        protected boolean isHeldExclusively() {
            return getState() == 1;
        }
        // 当状态为0的时候获取锁
        public boolean tryAcquire(int acquires) {
            if (compareAndSetState(0, 1)) {
                setExclusiveOwnerThread(Thread.currentThread());
                return true;
            }
            return false;
        }
        // 释放锁，将状态设置为0
        @Override
        protected boolean tryRelease(int releases) {
            if (getState() == 0)
                throw new IllegalMonitorStateException();
            setExclusiveOwnerThread(null);
            setState(0);
            return true;
        }
        // 返回一个Condition，每个condition都包含了一个condition队列
        Condition newCondition() {
            return new ConditionObject();
        }
    }

    // 只需要将操作代理到Sync上即可
    private final Sync sync = new Sync();

    @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() {
        return sync.newCondition();
    }

    public boolean isLocked() {
        return sync.isHeldExclusively();
    }

    public boolean hasQueuedThreads() {
        return sync.hasQueuedThreads();
    }

    public static void withoutMutex() throws InterruptedException {
        System.out.println("Without mutex: ");
        int threadCount = 2;
        final Thread threads[] = new Thread[threadCount];
        for (int i = 0; i < threads.length; i++) {
            final int index = i;
            threads[i] = new Thread(() -> {
                for (int j = 0; j < 100000; j++) {
                    if (j % 20000 == 0) {
                        System.out.println("Thread-" + index + ": j =" + j);
                    }
                }
            });
        }

        for (int i = 0; i < threads.length; i++) {
            threads[i].start();
        }
        for (int i = 0; i < threads.length; i++) {
            threads[i].join();
        }
    }

    public static void withMutex() {
        System.out.println("With mutex: ");
        final Mutex mutex = new Mutex();
        int threadCount = 2;
        final Thread threads[] = new Thread[threadCount];
        for (int i = 0; i < threads.length; i++) {
            final int index = i;
            threads[i] = new Thread(() -> {

                mutex.lock();
                try {
                    for (int j = 0; j < 100000; j++) {
                        if (j % 20000 == 0) {
                            System.out.println("Thread-" + index + ": j =" + j);
                        }
                    }
                } finally {
                    mutex.unlock();
                }
            });
        }

        for (int i = 0; i < threads.length; i++) {
            threads[i].start();
        }
    }


    public static void main(String[] args) throws InterruptedException {
        withoutMutex();
        System.out.println();
        withMutex();
    }
}

以上说的是独占式获取同步状态，下面是共享式获取同步状态。

共享式与独占式的区别最主要在于同一时刻能否有多个线程同是获取到同步状态。写操作要求对资源的独占式访问，而读操作是共享式访问。共享式访问资源是，其他共享式的访问均被允许，而独占式访问将会被阻塞；独占式访问资源时，同一时刻其他访问资源均被阻塞。

通过调用同步器的 acquireShared(int) 方法可以共享式获取同步状态。在 acquireShared 方法中，tryAcquireShared 方法返回的是 int 型，大于等于 0 时，表示能够获取到同步状态。

    public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 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);
                    if (r >= 0) {　// 如果返回值获取的值大于等于0，表示获取同步状态成功并从自旋过程中返回
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        if (interrupted)
                            selfInterrupt();
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

在共享式获取的自旋过程中，成功获取到同步状态并退出自旋的条件就是 tryAcquireShared 的返回值大于等于 0。

和独占式一样，共享式也要释放同步状态，通过调用 releaseShared(int) 方法释放同步状态，将会唤醒后续处于等待状态的节点。

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

下面是一个自定义同步组件 TwinsLock，程序运行时每次都会同时打印两条语句，说同时有两个线程在执行。

package concurrent.lock;

import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;

/**
 * @program: MyPractice
 * @description: 自定义共享锁
 * @author: Mr.Wu
 * @create: 2019-09-19 20:45
 **/
public class TwinsLock implements Lock {

    private static class Sync extends AbstractQueuedSynchronizer {

        public Sync(int resourceCount) {
            if (resourceCount <= 0) {
                throw new IllegalArgumentException("resourceCount must be larger than zero.");
            }
            // 设置可以共享的资源总数
            setState(resourceCount);
        }


        @Override
        protected int tryAcquireShared(int reduceCount) {
            // 使用尝试获得资源，如果成功修改了状态变量（获得了资源）
            // 或者资源的总量小于 0（没有资源了），则返回。
            for (; ; ) {
                int lastCount = getState();
                int newCount = lastCount - reduceCount;
                if (newCount < 0 || compareAndSetState(lastCount, newCount)) {
                    return newCount;
                }
            }
        }

        @Override
        protected boolean tryReleaseShared(int returnCount) {
            // 释放共享资源，因为可能有多个线程同时执行，所以需要使用 CAS 操作来修改资源总数。
            for (; ; ) {
                int lastCount = getState();
                int newCount = lastCount + returnCount;
                if (compareAndSetState(lastCount, newCount)) {
                    return true;
                }
            }
        }
    }

    // 定义两个共享资源，说明同一时间内可以有两个线程同时运行
    private final Sync sync = new Sync(2);

    @Override
    public void lock() {
        sync.acquireShared(1);
    }

    @Override
    public void lockInterruptibly() throws InterruptedException {
        sync.acquireInterruptibly(1);
    }

    @Override
    public boolean tryLock() {
        return sync.tryAcquireShared(1) >= 0;
    }

    @Override
    public boolean tryLock(long time, TimeUnit unit) throws InterruptedException {
        return sync.tryAcquireNanos(1, unit.toNanos(time));
    }

    @Override
    public void unlock() {
        sync.releaseShared(1);
    }

    @Override
    public Condition newCondition() {
        throw new UnsupportedOperationException();
    }

    public static void main(String[] args) {
        final Lock lock = new TwinsLock();
        int threadCounts = 10;
        Thread threads[] = new Thread[threadCounts];
        for (int i = 0; i < threadCounts; i++) {
            final int index = i;
            threads[i] = new Thread(() -> {
                for (int i1 = 0; i1 < 5; i1++) {
                    lock.lock();
                    try {
                        TimeUnit.SECONDS.sleep(1);
                        System.out.println(Thread.currentThread().getName());
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    } finally {
                        lock.unlock();
                    }

                    try {
                        TimeUnit.SECONDS.sleep(1);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            });
        }

        for (int i = 0; i < threadCounts; i++) {
            threads[i].start();
        }
    }
}