Java面试之AbstractQueuedSynchronizer

AbstractQueuedSynchronizer翻译为抽象同步队列，简称AQS。它是一个用于构建锁和同步器的框架，许多同步器都可以通过AQS很容易并且高效的构造出来。在J.U.C包中有许多同步器类都是基于AQS实现的，如ReentrantLock、ReentrantReadWriteLock、CountDownLatch、CyclicBarrier、Semaphore、SynchronousQueue、FutureTask等。

由上图可以看到，AQS是一个FIFO的双向队列，其内部通过节点head和tail记录队首和队尾元素，队列元素的类型为Node。其中Node中的thread变量用来存放进入AQS队列里面的线程；Node节点内部的SHARED用来标记该线程是获取共享资源时被阻塞挂起后放入AQS队列的，EXCLUSIVE用来标记线程是获取独占资源时被挂起后放入AQS队列的；waitStatus记录当前线程等待状态，可以为CANCELLED(线程被取消了)、SINGAL(线程需要被唤醒)、CONDITION(线程在条件队列里面等待)、PROPAGATE(释放共享资源时需要通知其他节点)；prev记录当前节点的前驱节点，next记录当前节点的后继节点。

简单总结来说就是，AQS中提供了一个由volatile修饰，并且采用CAS方式修改的int类型的state变量。

对于ReentrantLock，state可以用来表示当前线程获取锁的可重入次数。

当一个线程获取了ReentantLock的锁后，在AQS内部会首先使用CAS操作把state状态值从0变为1，然后设置当前锁的持有者为当前线程。当该线程再次获取锁时发现它就是锁的持有者，则会把状态值从1变为2，也就是设置可重入次数。当另外一个线程获取锁时发现自己并不是该锁的持有者就会被放入AQS阻塞队列后挂起。

对于ReentranReadWriteLock，state的高16位表示读状态，也就是获取该读锁的次数，低16位表示获取到写锁的线程的可重入次数。

对于Semaphore，state用来表示当前可用信号的个数。

对于CountDownLatch，state用来表示计数器当前的值。

其次，AQS中维护了一个双向链表，有head和tail记录队首和队尾元素，并且队列元素为Node对象。

其中Node中的thread变量用来存放进入AQS队列里面的线程。Node节点内部的SHARED用来标记该线程是获取共享资源时被阻塞挂起后放入AQS队列的。EXCLUSIVE用来标记线程是获取独占资源时被挂起后放入AQS队列的。waitStatus记录当前线程等待状态，可以为CANCELLED(线程被取消了)、SIGNAL(线程需要被唤醒)、CONDITION(线程在条件队列里面等待)、PROPAGATE(释放共享资源时需要通知其他节点)，prev记录当前节点的前驱节点，next记录当前节点的后继节点。

AQS使用锁来实现线程同步，而线程同步的关键是对状态值state进行操作，然而操作state的方式分为：

独占方式：获取的资源是与具体线程绑定的，就是多个线程中只有一个线程获得锁资源，比如ReentrantLock。

共享方式：获取的资源与具体线程不相关的，当多个线程去请求资源时通过CAS方式竞争获取资源，比如CyclicBarrier、Semaphore。

AQS的双向链表

首先，双向链表的特点是它有两个指针，一个指针指向前置节点，一个指针指向后继节点。

所以，双向链表可以支持常量O(1)时间复杂度的情况下找到前驱节点，基于这样的特点，双向链表在插入和删除操作的时候，要比单向链表简单、高效。因此，从双向链表的特性来看，有三方面的考虑

第一方面，没有竞争到锁的线程加入阻塞队列，并且阻塞等待的前提是，当前线程所在节点的前置节点是正常状态，这样设计是为了避免链表中存在异常线程导致无法唤醒后续线程的问题。

所以线程阻塞之前需要判断前置节点的状态，如果没有指针指向前置节点，就需要从head节点开始遍历，性能非常低

第二个方面，在Lock接口里面有一个lockInterruptibly()方法，这个方法表示处于锁阻塞的线程允许被中断。

也就是说，没有竞争到锁的线程加入到同步队列等待以后，是允许外部线程通过interrupt()方法触发唤醒并中断的。

这个时候，被中断的线程的状态会修改成CANCELLED。被标记为这个状态的线程，是不需要去竞争锁的，但是它仍然存在于双向链表里面。意味着在后续的锁竞争中，需要把这个节点从链表里面移除，否则会导致阻塞的线程无法被正常唤醒。

在这种情况下，如果是单向链表，就需要从head节点开始往下逐个遍历，找到并移除异常状态的节点。同样效率也比较低，还会导致锁唤醒的操作和遍历操作之间的竞争。

第三方面，为了避免线程阻塞和唤醒的开销，比如刚加入到链表的线程，首先会通过自旋的方式尝试去竞争锁。

但是实际上按照公平锁的设计，只有头节点的下一个节点才有必要去竞争锁，后续的节点竞争锁的意义不大。否则，就会造成羊群效应，也就是大量的线程在阻塞之前尝试去竞争锁带来比较大的性能开销。

所以，为了避免这个问题，加入到链表中的节点在尝试竞争锁之前，需要判断前置节点是不是头节点，如果不是头节点，就没必要再去触发锁竞争的动作。所以这里会涉及到前置节点的查找，如果是单向链表，那么这个功能的实现会非常复杂。