Java队列同步器（AQS）

在java.util.concurrent.locks包中有很多Lock的实现类，常用的有ReentrantLock、ReadWriteLock（实现类ReentrantReadWriteLock），内部实现都依赖AbstractQueuedSynchronizer类。

队列同步器AQS是用来构建锁或其他同步组件的基础框架，内部使用一个int成员变量表示同步状态，通过内置的FIFO队列来完成资源获取线程的排队工作，其中内部状态state，等待队列的头节点head和尾节点head，都是通过volatile修饰，保证了多线程之间的可见。

public abstract class AbstractQueuedSynchronizer extends
    AbstractOwnableSynchronizer implements java.io.Serializable { 
    //等待队列的头节点
    private transient volatile Node head;
    //等待队列的尾节点
    private transient volatile Node tail;
    //同步状态
    private volatile int state;
    protected final int getState() { return state;}
    protected final void setState(int newState) { state = newState;}
    ...
}

AQS内部有一个FIFO的同步队列，用于完成同步状态的管理。

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;
    static final int CONDITION = -2;
    static final int PROPAGATE = -3;
    volatile int waitStatus;
    volatile Node prev;
    volatile Node next;
    volatile Thread thread;
    Node nextWaiter;
    ...
}

同步队列结构

头结点代表当前持有锁的线程，每当有线程竞争失败，就会插入到队列的尾部，tail节点始终指向队列中的最后一个元素。

每个节点中， 除了存储了当前线程，前后节点的引用以外，还有一个waitStatus变量，用于描述节点当前的状态。多线程并发执行时，队列中会有多个节点存在，这个waitStatus其实代表对应线程的状态：有的线程可能获取锁因为某些原因放弃竞争；有的线程在等待满足条件，满足之后才能执行等等。一共有4种状态：

1. CANCELLED 取消状态
2. SIGNAL 等待触发状态
3. CONDITION 等待条件状态
4. PROPAGATE 状态需要向后传播

1 独占模式获取锁操作

在将Node节点插入到尾部之后，并不是立即挂起该节点中线程，因为在插入它的过程中，前面的线程可能已经执行完成，所以它会先进行自旋操作acquireQueued(node, 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; // help GC
                failed = false;
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

如果没获取到锁，则判断是否应该挂起，而这个判断通过它的前驱节点的waitStatus来确定。

rivate static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
    int ws = pred.waitStatus;
    if (ws == Node.SIGNAL)
            return true;
    if (ws > 0) {
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {       
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
    return false;
}

如果前驱节点的waitStatus为：

• SIGNAL，则返回true表示应该挂起当前线程，挂起该线程，并等待被唤醒,被唤醒后进行中断检测,如果发现当前线程被中断，那么抛出InterruptedException并退出循环
• 大于0，将前驱节点踢出队列，返回false
• 小于0，也是返回false，不过先将前驱节点waitStatus设置为SIGNAL，使得下次判断时,将当前节点挂起

获取独占锁流程总结如下：
AQS的模板方法acquire通过调用子类自定义实现的tryAcquire获取同步状态失败后->将线程构造成Node节点(addWaiter)->将Node节点添加到同步队列对尾(addWaiter)->节点以自旋的方法获取同步状态(acquirQueued)。在节点自旋获取同步状态时，只有其前驱节点是头节点的时候才会尝试获取同步状态，如果该节点的前驱不是头节点或者该节点的前驱节点是头节点但获取同步状态失败，则判断当前线程是否需要阻塞，如果需要阻塞则在被唤醒过后才返回。

2 独占模式释放锁操作

既然是释放,那肯定是持有锁的该线程执行释放操作，即head节点中的线程释放锁。
AQS中的release释放同步状态和acquire获取同步状态一样，都是模板方法，tryRelease释放的具体操作都有子类去实现，父类AQS只提供一个算法模板。

public final boolean release(int arg) {
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}
/**如果node的后继节点不为空且不是作废状态,则唤醒这个后继节点,否则从末尾开始寻找合适的节点,如果找到,则唤醒*/
private void unparkSuccessor(Node node) {
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);
    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);
}

首先调用子类的tryRelease()方法释放锁，然后唤醒后继节点，在唤醒的过程中，需要判断后继节点是否满足情况，如果后继节点不是作废状态，则唤醒这个后继节点，否则从tail节点向前寻找合适的节点，如果找到，则唤醒之。

参考资料：

1. 深入浅出java同步器AQS
2. 深入学习java同步器AQS