前言

　　最近结合书籍《Java并发编程艺术》一直在看AQS的源码，发现AQS核心就是：利用内置的FIFO双向队列结构来实现线程排队获取int变量的同步状态，以此奠定了很多并发包中大部分实现基础，比如ReentranLock等。今天又是周末，便来总结下最近看的消化后的内容。

　　主要参考资料《Java并发编程艺术》（有需要的小伙伴可以找我，我这里只有电子PDF）结合ReentranLock、AQS等源码。

一、同步队列的结构与实现

1、同步队列的结构

（1）结构介绍

　　AQS使用的同步队列是基于一种CLH锁算法来实现（引用网上资料对CLH简单介绍）：

　　CLH锁也是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，它不断轮询前驱的状态，如果发现前驱释放了锁就结束自旋；

　　结点之间是通过隐形的链表相连，之所以叫隐形的链表是由于这些结点之间没有明显的next指针，而是通过myPred所指向的结点的变化情况来影响myNode的行为；

　　当一个线程须要获取锁时，会创建一个新的QNode。将当中的locked设置为true表示须要获取锁。然后线程对tail域调用getAndSet方法，使自己成为队列的尾部。同一时候获取一个指向其前趋的引用myPred,然后该线程就在前趋结点的locked字段上旋转。直到前趋结点释放锁。

　　当一个线程须要释放锁时，将当前结点的locked域设置为false，同一时候回收前趋结点。线程A须要获取锁。其myNode域为true。些时tail指向线程A的结点，然后线程B也增加到线程A后面。tail指向线程B的结点。然后线程A和B都在它的myPred域上旋转，一旦它的myPred结点的locked字段变为false，它就能够获取锁。

而在源码中也有这样的介绍：

/** * Wait queue node class. * * <p>The wait queue is a variant of a "" (Craig, Landin, and * Hagersten) lock queue. CLH locks are normally used for * spinlocks.  * ........... * <p>To enqueue into a CLH lock, you atomically splice it in as new * tail. To dequeue, you just set the head field. * <pre> *      +------+  prev +-----+       +-----+ * head |      | <---- |     | <---- |     |  tail *      +------+       +-----+       +-----+ * </pre> * ..............

在AQS中的同步队列结构以及获取/释放锁都是基于此实现的，这里我们先放一个我画的基本结构来理解AQS同步队列，再进一步介绍一些细节。

根据以上图我们看到：

该队列是双向FIFO队列，每个节点都有pre、next域；
同步器包含了两个节点类型的引用，一个指向头结点，一个指向尾节点；
新加入线程被构造成Node通过调用compareAndSetTail加入同步队列中；
使用setHead(Node node)设置头结点，指向队列头。使用compareAndSetTail(Node exceptNode, Node updateNode)指向队列尾节点。

在源码中我们可以看到：

// 内部类Node节点static final class Node{...}// 同步队列的head引用private transient volatile Node head;// 同步队列的tail引用private transient volatile Node tail;

（2）节点构成

那么Node结构的具体构成是什么呢？我们具体看内部类Node的源码：

static final class Node {/** Marker to indicate a node is waiting in shared mode */static final Node SHARED = new Node();/** Marker to indicate a node is waiting in exclusive mode */static final Node EXCLUSIVE = null;/** waitStatus value to indicate thread has cancelled */static final int CANCELLED =  1;/** waitStatus value to indicate successor's thread needs unparking */static final int SIGNAL    = -1;/** waitStatus value to indicate thread is waiting on condition */static final int CONDITION = -2;/** * waitStatus value to indicate the next acquireShared should         * unconditionally propagate         */static final int PROPAGATE = -3;/** 等待状态：         * 0 INITAIL： 初始状态         * 1 CANCELLED: 由于等待超时或者被中断，需要从同步队列中取消等待，节点进入该状态不会被改变         * -1 SIGNAL: 当前节点释放同步状态或被取消，则等待状态的后继节点被通知         * -2 CONDITION: 节点在等待队列中，线程在Condition上，需要其它线程调用Condition的signal()方法才能从等待队转移到同步队列         * -3 PROPAGATE: 表示下一个共享式同步状态将会无条件被传播下去         */volatile int waitStatus;/** 前驱结点 */volatile Node prev;/** 后继节点 */volatile Node next; /** 获取同步状态的线程 */volatile Thread thread;/** 等待队列中的后继节点 */Node nextWaiter;      /** 判断Node是否是共享模式 */final boolean isShared() {return nextWaiter == SHARED;        } /** 返回前驱结点 */final Node predecessor() throws NullPointerException {            Node p = prev;if (p == null)throw new NullPointerException();elsereturn p;        }        Node() {    // Used to establish initial head or SHARED marker        }        Node(Thread thread, Node mode) {     // Used by addWaiterthis.nextWaiter = mode;this.thread = thread;        }        Node(Thread thread, int waitStatus) { // Used by Conditionthis.waitStatus = waitStatus;this.thread = thread;        }    }

从源码中可以发现：同步队列中的节点Node用来保存获取同步状态失败的线程引用、等待状态以及前驱和后继节点。

节点是构成同步队列的基础，没有成功获取同步状态的线程将成为节点加入该队列的尾部。当一个线程无法获取同步状态时，会被构造成节点并加入同步队列中，通过CAS保证设置尾节点这一步是线程安全的，此时才能认为当前节点（线程）成功加入同步队列与尾节点建立联系。具体的实现逻辑请看下面介绍！

2、同步状态获取与释放

（1）独占式同步状态获取与释放

通过调用同步器acquire(int arg)方法可以获取同步状态，该方法中断不敏感，也就是由于线程获取同步状态失败后进入同步队列中，后序线程对进行中断操作时，线程不会从同步队列中移出

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

同步状态获取主要的流程步骤：

1）首先调用自定义同步器实现tryAcquire(int arg)方法，该方法保证线程安全的获取同步状态。

2）如果获取失败则构造同步节点（独占式Node.EXCLUSIVE）并通过addWaiter(Node ndoe)方法将该节点加入到同步队列的尾部，同时enq(node)通过for(;;)循环保证安全设置尾节点。

private Node addWaiter(Node mode) {// 根据给定模式构造NodeNode node = new Node(Thread.currentThread(), mode);// Try the fast path of enq; backup to full enq on failureNode pred = tail; // 尝试在尾部添加if (pred != null) {            node.prev = pred;// cas方式保证正确添加尾节点if (compareAndSetTail(pred, node)) {                pred.next = node;return node;            }        }// enq主要是通过for(;;)死循环来确保节点正确添加// 在for(;;)死循环中，通过cas将节点设置为尾节点时，才返回；否则一直尝试设置        enq(node);return node;    } private Node enq(final Node node) {for (;;) {            Node t = tail;if (t == null) { // Must initialize  当tail节点为null时，必须初始化构造好    head节点if (compareAndSetHead(new Node()))                    tail = head;            } else { // 否则就通过cas开始添加尾节点node.prev = t;if (compareAndSetTail(t, node)) {                    t.next = node;return t;                }            }        }    }

假设原队列中存在Node-1到Node-4节点，此时某个线程获取同步状态失败则构成成Node-5通过CAS方式加入队列（下图忽略自旋环节）。

3）节点进入同步队列之后“自旋”，即acquireQueued(final Node node, int arg)方法，在这个方法中，当前node死循环尝试获取锁状态，但是只有node的前驱结点是Head才能尝试获取同步状态，获取成功之后立即设置当前节点为Head，并成功返回。否则就会一直自旋。

final boolean acquireQueued(final Node node, int arg) {boolean failed = true;try {boolean interrupted = false;for (;;) {final Node p = node.predecessor();// 当前node节点的前驱是Head时（p == head），才能有资格去尝试获取同步状态（tryAcquire(arg)）// 这是因为当前节点的前驱结点获得同步状态，才能唤醒后继节点，即当前节点if (p == head && tryAcquire(arg)) { // 以上条件满足之后setHead(node); // 设置当前节点为Headp.next = null; // help GC // 释放ndoe的前驱节点failed = false;return interrupted;                }// 线程被中断或者前驱结点被释放，则继续进入检查：p == head && tryAcquire(argif (shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt())                    interrupted = true;            }        } finally {if (failed)                cancelAcquire(node);        }    }

此时新加入的Node-5节点也开始自旋，此时的Head（Node-1）已经获取到了同步状态，而Node-2退出了自旋，成为了新的Head。

文字总结：

1）同步器会维护一个双向FIFO队列，获取同步失败的线程将会被构造成Node加入队尾（并且做自旋检查：检查前驱结点是否是Head）；

2）当前线程想要获得同步状态，前提是其前驱结点是头结点，并且获得了同步状态；

3）当Head调用release(int arg)释放锁的同时会唤醒后继节点（即当前节点），后继节点结束自旋

流程图总结：

同步器的release方法：释放锁的同时，唤醒后继节点（进而时后继节点重新获取同步状态）

public final boolean release(int arg) {if (tryRelease(arg)) {            Node h = head;if (h != null && h.waitStatus != 0)// 该方法会唤醒Head节点的后继节点，使其重试尝试获取同步状态                unparkSuccessor(h);return true;        }return false;    }

UnparkSuccessor(Node node)方法使用LookSupport（LockSupport.unpark）唤醒处于等待状态的线程（之后会慢慢看源码介绍）。

（2）共享式同步状态获取与释放

共享锁跟独占式锁最大的不同就是：某一时刻有多个线程同时获取到同步状态，获取判断是否获取同步状态成功的关键，获取到的同步状态要大于等于0。而其他步骤基本都是一致的，还是从源码开始分析起：带后缀Share都为共享式同步方法。

1）acquireShared(int arg)获取同步状态：如果获取失败则加入队尾，并且检查是否具备退出自旋的条件（前驱结点是头结点并且能成功获取同步状态）

public final void acquireShared(int arg) {// tryAcquireShared 获取同步状态，大于0才是获取状态成功，否则就是失败if (tryAcquireShared(arg) < 0)// 获取状态失败则构造共享Node，加入队列；// 并且检查是否具备退出自旋的条件：即preNode为head，并且能获取到同步状态            doAcquireShared(arg);    }

2）doAcquireShared(arg)：获取失败的Node加入队列，如果当前节点的前驱结点是头结点的话，尝试获取同步状态，如果大于等于0则在for(;;)中退出（退出自旋）。

private void doAcquireShared(int arg) {// 构造共享模式的Nodefinal 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);// 前驱节点是头结点，并且能获取状态成功，则return返回，退出死循环（自旋）if (r >= 0) {                        setHeadAndPropagate(node, r);                        p.next = null; // help GCif (interrupted)                            selfInterrupt();                        failed = false;return;                    }                }if (shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt())                    interrupted = true;            }        } finally {if (failed)                cancelAcquire(node);        }    }

3）releaseShared(int arg)：释放同步状态，通过loop+CAS方式释放多个线程的同步状态。

public final boolean releaseShared(int arg) {if (tryReleaseShared(arg)) {// 通过loop+CAS方式释放多个线程的同步状态            doReleaseShared();return true;        }return false;    }

二、自定义同步组件（实现Lock，内部类Sync继承AQS）

1、实现一个不可重入的互斥锁Mutex

2、实现指定共享数量的共享锁MyShareLock

学习JUC源码（1）——AQS同步队列（源码分析结合图文理解）

前言