并发编程网 - ifeve.com

原文链接 作者：Doug Lea 译者：欧振聪 校对：丁一

3 设计与实现

同步器背后的基本思想非常简单。acquire操作如下：

[code lang=”java”]
while (synchronization state does not allow acquire) {
enqueue current thread if not already queued;
possibly block current thread;
}
dequeue current thread if it was queued;
[/code]

release操作如下：

[code lang=”java”]
update synchronization state;
if (state may permit a blocked thread to acquire)
unblock one or more queued threads;
[/code]

为了实现上述操作，需要下面三个基本组件的相互协作：

• 同步状态的原子性管理；
• 线程的阻塞与解除阻塞；
• 队列的管理；

创建一个框架分别实现这三个组件是有可能的。但是，这会让整个框架既难用又没效率。例如：存储在队列节点的信息必须与解除阻塞所需要的信息一致，而暴露出的方法的签名必须依赖于同步状态的特性。

同步器框架的核心决策是为这三个组件选择一个具体实现，同时在使用方式上又有大量选项可用。这里有意地限制了其适用范围，但是提供了足够的效率，使得实际上没有理由在合适的情况下不用这个框架而去重新建造一个。

3.1 同步状态

AQS类使用单个int（32位）来保存同步状态，并暴露出getState、setState以及compareAndSet操作来读取和更新这个状态。这些方法都依赖于j.u.c.atomic包的支持，这个包提供了兼容JSR133中volatile在读和写上的语义，并且通过使用本地的compare-and-swap或load-linked/store-conditional指令来实现compareAndSetState，使得仅当同步状态拥有一个期望值的时候，才会被原子地设置成新值。

将同步状态限制为一个32位的整形是出于实践上的考量。虽然JSR166也提供了64位long字段的原子性操作，但这些操作在很多平台上还是使用内部锁的方式来模拟实现的，这会使同步器的性能可能不会很理想。当然，将来可能会有一个类是专门使用64位的状态的。然而现在就引入这么一个类到这个包里并不是一个很好的决定（译者注：JDK1.6中已经包含java.util.concurrent.locks.AbstractQueuedLongSynchronizer类，即使用 long 形式维护同步状态的一个 AbstractQueuedSynchronizer 版本）。目前来说，32位的状态对大多数应用程序都是足够的。在j.u.c包中，只有一个同步器类可能需要多于32位来维持状态，那就是CyclicBarrier类，所以，它用了锁（该包中大多数更高层次的工具亦是如此）。

基于AQS的具体实现类必须根据暴露出的状态相关的方法定义tryAcquire和tryRelease方法，以控制acquire和release操作。当同步状态满足时，tryAcquire方法必须返回true，而当新的同步状态允许后续acquire时，tryRelease方法也必须返回true。这些方法都接受一个int类型的参数用于传递想要的状态。例如：可重入锁中，当某个线程从条件等待中返回，然后重新获取锁时，为了重新建立循环计数的场景。很多同步器并不需要这样一个参数，因此忽略它即可。

3.2 阻塞

在JSR166之前，阻塞线程和解除线程阻塞都是基于Java内置管程，没有其它非基于Java内置管程的API可以用来创建同步器。唯一可以选择的是Thread.suspend和Thread.resume，但是它们都有无法解决的竞态问题，所以也没法用：当一个非阻塞的线程在一个正准备阻塞的线程调用suspend前调用了resume，这个resume操作将不会有什么效果。

j.u.c包有一个LockSuport类，这个类中包含了解决这个问题的方法。方法LockSupport.park阻塞当前线程除非/直到有个LockSupport.unpark方法被调用（unpark方法被提前调用也是可以的）。unpark的调用是没有被计数的，因此在一个park调用前多次调用unpark方法只会解除一个park操作。另外，它们作用于每个线程而不是每个同步器。一个线程在一个新的同步器上调用park操作可能会立即返回，因为在此之前可能有“剩余的”unpark操作。但是，在缺少一个unpark操作时，下一次调用park就会阻塞。虽然可以显式地消除这个状态（译者注：就是多余的unpark调用），但并不值得这样做。在需要的时候多次调用park会更高效。

这个简单的机制与有些用法在某种程度上是相似的，例如Solaris-9的线程库，WIN32中的“可消费事件”，以及Linux中的NPTL线程库。因此最常见的运行Java的平台上都有相对应的有效实现。（但目前Solaris和Linux上的Sun Hotspot JVM参考实现实际上是使用一个pthread的condvar来适应目前的运行时设计的）。park方法同样支持可选的相对或绝对的超时设置，以及与JVM的Thread.interrupt结合 —— 可通过中断来unpark一个线程。

3.3 队列

整个框架的关键就是如何管理被阻塞的线程的队列，该队列是严格的FIFO队列，因此，框架不支持基于优先级的同步。

同步队列的最佳选择是自身没有使用底层锁来构造的非阻塞数据结构，目前，业界对此很少有争议。而其中主要有两个选择：一个是Mellor-Crummey和Scott锁（MCS锁）^[9]的变体，另一个是Craig，Landin和Hagersten锁（CLH锁）^[5][8][10]的变体。一直以来，CLH锁仅被用于自旋锁。但是，在这个框架中，CLH锁显然比MCS锁更合适。因为CLH锁可以更容易地去实现“取消（cancellation）”和“超时”功能，因此我们选择了CLH锁作为实现的基础。但是最终的设计已经与原来的CLH锁有较大的出入，因此下文将对此做出解释。

CLH队列实际上并不那么像队列，因为它的入队和出队操作都与它的用途（即用作锁）紧密相关。它是一个链表队列，通过两个字段head和tail来存取，这两个字段是可原子更新的，两者在初始化时都指向了一个空节点。

一个新的节点，node，通过一个原子操作入队：

[code lang=”java”]
do {
pred = tail;
} while(!tail.compareAndSet(pred, node));
[/code]

每一个节点的“释放”状态都保存在其前驱节点中。因此，自旋锁的“自旋”操作就如下：

[code lang=”java”]
while (pred.status != RELEASED); // spin
[/code]

自旋后的出队操作只需将head字段指向刚刚得到锁的节点：

[code lang=”java”]
head = node;
[/code]

CLH锁的优点在于其入队和出队操作是快速、无锁的，以及无障碍的（即使在竞争下，某个线程总会赢得一次插入机会而能继续执行）；且探测是否有线程正在等待也很快（只要测试一下head是否与tail相等）；同时，“释放”状态是分散的（译者注：几乎每个节点都保存了这个状态，当前节点保存了其后驱节点的“释放”状态，因此它们是分散的，不是集中于一块的。），避免了一些不必要的内存竞争。

在原始版本的CLH锁中，节点间甚至都没有互相链接。自旋锁中，pred变量可以是一个局部变量。然而，Scott和Scherer证明了通过在节点中显式地维护前驱节点，CLH锁就可以处理“超时”和各种形式的“取消”：如果一个节点的前驱节点取消了，这个节点就可以滑动去使用前面一个节点的状态字段。

为了将CLH队列用于阻塞式同步器，需要做些额外的修改以提供一种高效的方式定位某个节点的后继节点。在自旋锁中，一个节点只需要改变其状态，下一次自旋中其后继节点就能注意到这个改变，所以节点间的链接并不是必须的。但在阻塞式同步器中，一个节点需要显式地唤醒（unpark）其后继节点。

AQS队列的节点包含一个next链接到它的后继节点。但是，由于没有针对双向链表节点的类似compareAndSet的原子性无锁插入指令，因此这个next链接的设置并非作为原子性插入操作的一部分，而仅是在节点被插入后简单地赋值：

[code lang=”java”]
pred.next = node;
[/code]

next链接仅是一种优化。如果通过某个节点的next字段发现其后继结点不存在（或看似被取消了），总是可以使用pred字段从尾部开始向前遍历来检查是否真的有后续节点。

第二个对CLH队列主要的修改是将每个节点都有的状态字段用于控制阻塞而非自旋。在同步器框架中，仅在线程调用具体子类中的tryAcquire方法返回true时，队列中的线程才能从acquire操作中返回；而单个“released”位是不够的。但仍然需要做些控制以确保当一个活动的线程位于队列头部时，仅允许其调用tryAcquire；这时的acquire可能会失败，然后（重新）阻塞。这种情况不需要读取状态标识，因为可以通过检查当前节点的前驱是否为head来确定权限。与自旋锁不同，读取head以保证复制时不会有太多的内存竞争（ there is not enough memory contention reading head to warrant replication.）。然而，“取消”状态必须存在于状态字段中。

队列节点的状态字段也用于避免没有必要的park和unpark调用。虽然这些方法跟阻塞原语一样快，但在跨越Java和JVM runtime以及操作系统边界时仍有可避免的开销。在调用park前，线程设置一个“唤醒（signal me）”位，然后再一次检查同步和节点状态。一个释放的线程会清空其自身状态。这样线程就不必频繁地尝试阻塞，特别是在锁相关的类中，这样会浪费时间等待下一个符合条件的线程去申请锁，从而加剧其它竞争的影响。除非后继节点设置了“唤醒”位（译者注：源码中为-1），否则这也可避免正在release的线程去判断其后继节点。这反过来也消除了这些情形：除非“唤醒”与“取消”同时发生，否则必须遍历多个节点来处理一个似乎为null的next字段。

同步框架中使用的CLH锁的变体与其他语言中的相比，主要区别可能是同步框架中使用的CLH锁需要依赖垃圾回收管理节点的内存，这就避免了一些复杂性和开销。但是，即使依赖GC也仍然需要在确定链接字段不再需要时将其置为null。这往往可以与出队操作一起完成。否则，无用的节点仍然可触及，它们就没法被回收。

其它一些更深入的微调，包括CLH队列首次遇到竞争时才需要的初始空节点的延迟初始化等，都可以在J2SE1.5的版本的源代码文档中找到相应的描述。

抛开这些细节，基本的acquire操作的最终实现的一般形式如下（互斥，非中断，无超时）：

[code lang=”java”]
if(!tryAcquire(arg)) {
node = create and enqueue new node;
pred = node’s effective predecessor;
while (pred is not head node || !tryAcquire(arg)) {
if (pred’s signal bit is set)
pard()
else
compareAndSet pred’s signal bit to true;
pred = node’s effective predecessor;
}
head = node;
}
[/code]

release操作：

if(tryRelease(arg) && head node's signal bit is set) {
    compareAndSet head's bit to false;
    unpark head's successor, if one exist
}

acquire操作的主循环次数依赖于具体实现类中tryAcquire的实现方式。另一方面，在没有“取消”操作的情况下，每一个组件的acquire和release都是一个O(1)的操作，忽略park中发生的所有操作系统线程调度。

支持“取消”操作主要是要在acquire循环里的park返回时检查中断或超时。由超时或中断而被取消等待的线程会设置其节点状态，然后unpark其后继节点。在有“取消”的情况下，判断其前驱节点和后继节点以及重置状态可能需要O(n)的遍历（n是队列的长度）。由于“取消”操作，该线程再也不会被阻塞，节点的链接和状态字段可以被快速重建。

3.4 条件队列

AQS框架提供了一个ConditionObject类，给维护独占同步的类以及实现Lock接口的类使用。一个锁对象可以关联任意数目的条件对象，可以提供典型的管程风格的await、signal和signalAll操作，包括带有超时的，以及一些检测、监控的方法。

通过修正一些设计决策，ConditionObject类有效地将条件（conditions）与其它同步操作结合到了一起。该类只支持Java风格的管程访问规则，这些规则中，仅当当前线程持有锁且要操作的条件（condition）属于该锁时，条件操作才是合法的（一些替代操作的讨论参考^[4]）。这样，一个ConditionObject关联到一个ReentrantLock上就表现的跟内置的管程（通过Object.wait等）一样了。两者的不同仅仅在于方法的名称、额外的功能以及用户可以为每个锁声明多个条件。

ConditionObject使用了与同步器一样的内部队列节点。但是，是在一个单独的条件队列中维护这些节点的。signal操作是通过将节点从条件队列转移到锁队列中来实现的，而没有必要在需要唤醒的线程重新获取到锁之前将其唤醒。

基本的await操作如下：

[code lang=”java”]
create and add new node to conditon queue;
release lock;
block until node is on lock queue;
re-acquire lock;
[/code]

signal操作如下：

[code lang=”java”]
transfer the first node from condition queue to lock queue;
[/code]

因为只有在持有锁的时候才能执行这些操作，因此他们可以使用顺序链表队列操作来维护条件队列（在节点中用一个nextWaiter字段）。转移操作仅仅把第一个节点从条件队列中的链接解除，然后通过CLH插入操作将其插入到锁队列上。

实现这些操作主要复杂在，因超时或Thread.interrupt导致取消了条件等待时，该如何处理。“取消”和“唤醒”几乎同时发生就会有竞态问题，最终的结果遵照内置管程相关的规范。JSR133修订以后，就要求如果中断发生在signal操作之前，await方法必须在重新获取到锁后，抛出InterruptedException。但是，如果中断发生在signal后，await必须返回且不抛异常，同时设置线程的中断状态。

为了维护适当的顺序，队列节点状态变量中的一个位记录了该节点是否已经（或正在）被转移。“唤醒”和“取消”相关的代码都会尝试用compareAndSet修改这个状态。如果某次signal操作修改失败，就会转移队列中的下一个节点（如果存在的话）。如果某次“取消”操作修改失败，就必须中止此次转移，然后等待重新获得锁。后面的情况采用了一个潜在的无限的自旋等待。在节点成功的被插到锁队列之前，被“取消”的等待不能重新获得锁，所以必须自旋等待CLH队列插入（即compareAndSet操作）被“唤醒”线程成功执行。这里极少需要自旋，且自旋里使用Thread.yield来提示应该调度某一其它线程，理想情况下就是执行signal的那个线程。虽然有可能在这里为“取消”实现一个帮助策略以帮助插入节点，但这种情况实在太少，找不到合适的理由来增加这些开销。在其它所有的情况下，这个基本的机制都不需要自旋或yield，因此在单处理器上保持着合理的性能。

参考文献

• [1] Agesen, O., D. Detlefs, A. Garthwaite, R. Knippel, Y. S.Ramakrishna, and D. White. An Efficient Meta-lock for Implementing Ubiquitous Synchronization. ACM OOPSLA Proceedings, 1999.
• [2] Andrews, G. Concurrent Programming. Wiley, 1991.
• [3] Bacon, D. Thin Locks: Featherweight Synchronization for Java. ACM PLDI Proceedings, 1998.
• [4] Buhr, P. M. Fortier, and M. Coffin. Monitor Classification,ACM Computing Surveys, March 1995.
• [5] Craig, T. S. Building FIFO and priority-queueing spin locks from atomic swap. Technical Report TR 93-02-02,Department of Computer Science, University of Washington, Feb. 1993.
• [6] Gamma, E., R. Helm, R. Johnson, and J. Vlissides. Design Patterns, Addison Wesley, 1996.
• [7] Holmes, D. Synchronisation Rings, PhD Thesis, Macquarie University, 1999.
• [8] Magnussen, P., A. Landin, and E. Hagersten. Queue locks on cache coherent multiprocessors. 8th Intl. Parallel Processing Symposium, Cancun, Mexico, Apr. 1994.
• [9] Mellor-Crummey, J.M., and M. L. Scott. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Trans. on Computer Systems,February 1991
• [10] M. L. Scott and W N. Scherer III. Scalable Queue-Based Spin Locks with Timeout. 8th ACM Symp. on Principles and Practice of Parallel Programming, Snowbird, UT, June 2001.
• [11] Sun Microsystems. Multithreading in the Solaris Operating Environment. White paper available at http://wwws.sun.com/software/solaris/whitepapers.html 2002.
• [12] Zhang, H., S. Liang, and L. Bak. Monitor Conversion in a Multithreaded Computer System. United States Patent 6,691,304. 2004.