AbstractQueuedSynchronizer
@(Base)[JDK, locks, ReentrantLock, AbstractQueuedSynchronizer, AQS]
转载请写明：原文地址
系列文章：
-Java.concurrent.locks(1)-AQS
-Java.concurrent.locks(2)-ReentrantLock
Synchronize 最开始JDK只支持synchronize关键字来提供方法级别、同步块级别的同步。后续版本中提供了java.utils.concurrent.locks包，其中包括可重入锁，读写锁，信号量，Condition等等，都是基于一个基本的等待队列抽象完成的，在JDK的文档中，这个抽象的队列框架被称为AQS同步框架。
我们需要关注的类包括:
AbstractOwnableSynchronizer,AbstractQueuedSynchronizer其余的包括，可重入锁，读写锁，Condition，信号量都是通过上述两个抽象基类实现。
整个concurrent包源自于JSR-166，其作者就是大名鼎鼎的Doug Lea，说他是这个世界上对Java影响力最大的个人，一点也不为过。因为两次Java历史上的大变革，他都间接或直接的扮演了举足轻重的角色。一次是由JDK 1.1到JDK 1.2，JDK1.2很重要的一项新创举就是Collections，其Collections的概念可以说承袭自Doug Lea于1995年发布的第一个被广泛应用的collections；一次是2004年所推出的Tiger。Tiger广纳了15项JSRs(Java Specification Requests)的语法及标准，其中一项便是JSR-166。
What is Lock?
Lock 我们首先看wikipedia的定义:
In computer science, a lock or mutex (from mutual exclusion) is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. A lock is designed to enforce a mutual exclusion concurrency control policy.
在计算机科学中，锁或者互斥量是一种同步机制，用于限制共享资源的在多线程环境下访问。其次值得注意的是，不论是任何并发模型，其都是硬件的并发模型的抽象（进程线程模型），其只能更大程度的避免过度同步，以及提供了合理的抽象让你更容易在多线程环境下编程。而非使用了某种并发模型之后，你的程序就Lock-Free了。你看到的只是在语言层次的抽象上是无锁的，例如Actor-Model。
然后我们从使用的角度来看，一个锁对象需要具备什么功能。我们首先定义一个锁对象，叫做XLock（这是生造的一个概念）。如下代码大家应该经常看到。
private XLock lock = new Xlock();
public void someMethod() {
lock.lock();
try {
// do something
} finally {
lock.unlock();
}
}
我们从表现形式上来看，lock.lock()试着获取锁，如果有人占用的话就“等着”，直到获取的人释放锁。lock.unlock()写在final块中，意味着，无论是否异常，都需要释放锁。
其实，这个里面唯一神秘的概念就是“等着”。什么叫等着呢？如何实现等着呢？不明白的同学可能以为什么JVM会调度什么的。其实在计算机中，根本就没有任何神奇的事情。下面我们来解释如何“等着”。
首先回一下操作系统的mutex是如何实现的：
lock:
if(mutex > 0){
mutex = 0;
return 0;
} else
挂起等待;
goto lock;
unlock:
mutex = 1;
唤醒等待Mutex的线程;
return 0;
上述代码有一个小问题。例如lock的if可能两个线程都同时进入，如果两个线程同时调用lock，这时Mutex是1，两个线程都判断mutex>0成立，然后其中一个线程置mutex=0，而另一个线程并不知道这一情况，也置mutex=0，于是两个线程都以为自己获得了锁。
这里就需要注意的是，为了实现一个原子操作，必须要在CPU指令级别上支持才可以。在程序员看来就是需要一个原子的汇编指令。最早是交换内存地址和寄存器/内存与内存/寄存器与寄存器，这里称作swap，例如x86的xchgb指令，相当于抽象成setAndget()指令，使用方法如下代码：
lock:
movb $0, %al
xchgb %al, mutex
if(al寄存器的内容 > 0){
return 0;
} else
挂起等待;
goto lock;
unlock:
movb $1, mutex
唤醒等待Mutex的线程;
return 0;
另外值得注意的就是如何挂起和唤醒线程。在C语言中，我们可以直接调用系统API操作某个线程的状态，在内核中PC执行到挂起指令之后，就保存线程堆栈，直接切换。在调用系统API之前，我们需要记录已经挂起了哪些线程，也就是需要一个等待队列记录当前有多少线程挂起在这个lock上。当持有lock的线程执行完毕之后，通知等待队列的第一个线程。问题的关键在于如何通知，当然还是系统API，直接把线程的状态设置为可以执行即可，等待下一次线程调度的时候，该线程就会继续执行。
在上述代码中值得注意的是
goto lock这个语句。
根据上述说明，我们简单翻译成java的实现如下：
private AtomicBoolean on = new AtomicBoolean(false);
private Queue waiting = new Queue();
public void lock() {
while (true) {
if (on.compareAndSet(false, true)) { // get lock succeed
return;
}
waiting.add(Thread.currentThread()).
unsafe.park(Thread.currentThread()).
}
}
在上述代码中我们有三个比较特殊的点:
- 原子变量的操作
- 等待队列
- unsafe对象的park方法。
AtomicBoolean 底层实现也是需要CPU支持，是一个CPS操作。用来解决上述C伪码中的只能允许一个线程进入临界区问题，参考上述的xchgb操作。
Waiting Queue 我们通过一个普通的数组或者链表即可实现。
Unsafe Park Unsafe这个类是用于JDK类库使用的一个JNI调用。读者可以暂时理解成系统调用的一种抽象。park()方法会立即挂起某个线程，PC（程序计数器）保留在原来的位置。
当我们看完上述内容之后，我们明白了几个实现锁的重要步骤：第一，我们需要一个state来描述锁的状态（参考上述的原子变量）。第二，我们需要一个队列的数据结构。好了，到了这里有了基本的概念之后，我们再看在Java中各种锁是怎么实现的。
AbstractOwnableSynchronizer
可独占的同步器
A synchronizer that may be exclusively owned by a thread. This class provides a basis for creating locks and related synchronizers that may entail a notion of ownership. The
AbstractOwnableSynchronizerclass itself does not manage or use this information. However, subclasses and tools may use appropriately maintained values to help control and monitor access and provide diagnostics.
这个类作用就是提供了一种“独占”模式的基本实现，其代码非常简单：
public abstract class AbstractOwnableSynchronizer {
/** The current owner of exclusive mode synchronization. */
private transient Thread exclusiveOwnerThread;
protected final void setExclusiveOwnerThread(Thread t) {
exclusiveOwnerThread = t;
}
protected final Thread getExclusiveOwnerThread() {
return exclusiveOwnerThread;
}
}
通过一个私有域来保存当前占用这个“同步器”的线程（可认为是一个标志位），并且提供了get,set方法来改变这个独占的标志位。这里并没有使用任何同步的手段，因为只是个基类啦。
transient关键字是对java的serialization机制起作用的，意义是不要序列化这个字段。这里我们可以忽略，因为我也暂时想不到任何场景需要serialize一个同步器的场景。
独占的含义这里暂时不做解释，在之后的读写锁部分会详细说明。理解成mysql中的X锁和S锁就行了。
AbstractQueuedSynchronizer.acquire()
队列同步器框架 这个类就是所有的锁的精华所在。为了避免大家在阅读过程中的这个抽象类提供了5个方法需要子类继承，即可完成某种意义上的锁，如下：
tryAcquire();
tryRelease();
tryAcquireShared(); // 暂时不用关注
tryReleaseShared(); // 暂时不用关注
isHeldExclusively(); //暂时不用关注
看到这里可能一头雾水，其实在AbstractQueuedSynchronizer中已经规定出来了获取锁的步骤，和提供了基本的等待队列的实现。我们只需要实现每一个方法，即可完成一个同步器。
首先我们还是从，上文中提到的Lock.lock()语义的方法对应的就是AbstractQueuedSynchronizer的acquire(int)函数开始入手：
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
翻译一下上述的代码：
- 调用子类的tryAcquire方法，如果返回成功就说明获取锁成功
- 如果返回失败，则入队列。
interrupt的处理我们暂时忽略，这是java并发编程中的另外一个要点
其实对照我们上文中给出的java的lock的范例，tryAcquire函数其实就是compareAndSet，而acquireQueued()其实就是入队并且挂起线程的操作。
所以说如果一个子类想要实现，tryAcquire里面应该是原子的改变一个状态即可。那是不是说资历里面就必须要维护一个状态呢？答案是否定的。AbstractQueuedSynchronizer这个类已经提供了getState(),setState()以及compareAndSetState()来让子类控制这个表示sync的state。如下：
protected final int getState() {
return state;
}
protected final void setState(int newState) {
state = newState;
}
protected final boolean compareAndSetState(int expect, int update) {
// See below for intrinsics setup to support this
return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}
至于为什么不直接使用AtomicInteger，或者直接继承自AtomicInteger，而是自己在内部实现，原因如下：
Setup to support compareAndSet. We need to natively implement this here: For the sake of permitting future enhancements, we cannot explicitly subclass AtomicInteger, which would be efficient and useful otherwise. So, as the lesser of evils, we natively implement using hotspot intrinsics API. And while we are at it, we do the same for other CASable fields (which could otherwise be done with atomic field updaters).
Mutex.lock()
互斥量: 了解了AQS框架的Lock部分，我们可以试着利用AQS写一个互斥量。
Subclasses should be defined as non-public internal helper classes that are used to implement the synchronization properties of their enclosing class.
根据AQS类的推荐，我们需要用静态内部类来继承，在JDK中的大部分锁都遵循了这一模式:
class Mutex implements Lock, java.io.Serializable {
private static class Sync extends AbstractQueuedSynchronizer {
// Acquire the lock if state is zero
public boolean tryAcquire(int acquires) {
assert acquires == 1; // Otherwise unused
if (compareAndSetState(0, 1)) {
setExclusiveOwnerThread(Thread.currentThread());
return true;
}
return false;
}
// some other methods
}
// The sync object does all the hard work. We just forward to it.
private final Sync sync = new Sync();
public void lock() { sync.acquire(1); }
public boolean tryLock() { return sync.tryAcquire(1); }
public void lockInterruptibly() throws InterruptedException {
sync.acquireInterruptibly(1);
}
public boolean tryLock(long timeout, TimeUnit unit)
throws InterruptedException {
return sync.tryAcquireNanos(1, unit.toNanos(timeout));
}
// some other methods
}
上述代码中，最核心的就是tryAcquire方法，通过调用父类的compareAndSetState来改变状态，然后把独占线程设置为当前线程。根据上文中描述的父类中的运行模式，我们一个Lock.lock()的语义也就已经完成了。
lock.lock(timeout)这个语义其实类似，但是实际操作起来有更多的细节需要处理。底层使用unsafe.part(timeout)来处理。
AbstractQueuedSynchronizer.release()
同步器释放：与lock操作相对应的就是unlock，对应到同步器来说就是release()。我们首先看AbstractQueuedSynchronizer的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;
}
与前文中java代码的模式类似，tryRelease调用子类恢复状态，如果恢复成功，则获取链表头部，然后调用unsafe.unpark()方法唤醒线程。
我们再看Mutex中应该怎么实现tryRelease函数:
protected boolean tryRelease(int releases) {
assert releases == 1; // Otherwise unused
if (getState() == 0) throw new IllegalMonitorStateException();
setExclusiveOwnerThread(null);
setState(0);
return true;
}
这里只是个样例，我们只是完成语义，还有很多细节并没有确定，例如这里假设tryRelease函数一定只有acquire成功的线程才会调用。所以请勿直接使用于生产环境。
小结
看完上述内容之后，我们对AQS的大致流程有了一定的了解，也通过其编写了一个Mutex。在AQS中仍然有许多值得学习的细节。特别是读者应该自行了解一下内部的队列结构。因为在之后的Condition中也会有涉及到。
在之后的章节中，我们会陆续介绍ReentrantLock，Condition, ReentrantReadWriteLock，CountDownLatch，Semaphore的实现。
最后，下面是完整的Mutex示例。感谢阅读！
class Mutex implements Lock, java.io.Serializable {
// Our internal helper class
private static class Sync extends AbstractQueuedSynchronizer {
// Report whether in locked state
protected boolean isHeldExclusively() {
return getState() == 1;
}
// Acquire the lock if state is zero
public boolean tryAcquire(int acquires) {
assert acquires == 1; // Otherwise unused
if (compareAndSetState(0, 1)) {
setExclusiveOwnerThread(Thread.currentThread());
return true;
}
return false;
}
// Release the lock by setting state to zero
protected boolean tryRelease(int releases) {
assert releases == 1; // Otherwise unused
if (getState() == 0) throw new IllegalMonitorStateException();
setExclusiveOwnerThread(null);
setState(0);
return true;
}
// Provide a Condition
Condition newCondition() { return new ConditionObject(); }
// Deserialize properly
private void readObject(ObjectInputStream s)
throws IOException, ClassNotFoundException {
s.defaultReadObject();
setState(0); // reset to unlocked state
}
}
// The sync object does all the hard work. We just forward to it.
private final Sync sync = new Sync();
public void lock() { sync.acquire(1); }
public boolean tryLock() { return sync.tryAcquire(1); }
public void unlock() { sync.release(1); }
public Condition newCondition() { return sync.newCondition(); }
public boolean isLocked() { return sync.isHeldExclusively(); }
public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); }
public void lockInterruptibly() throws InterruptedException {
sync.acquireInterruptibly(1);
}
public boolean tryLock(long timeout, TimeUnit unit)
throws InterruptedException {
return sync.tryAcquireNanos(1, unit.toNanos(timeout));
}
}