并发编程网 - ifeve.com

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

4 用法

AQS类将上述的功能结合到一起，并且作为一种基于“模版方法模式”^[6]的基类提供给同步器。子类只需定义状态的检查与更新相关的方法，这些方法控制着acquire和 release操作。然而，将AQS的子类作为同步器ADT并不适合，因为这个类必须提供方法在内部控制acquire和release的规则，这些都不应该被用户所看到。所有java.util.concurrent包中的同步器类都声明了一个私有的继承了AbstractQueuedSynchronizer的内部类，并且把所有同步方法都委托给这个内部类。这样各个同步器类的公开方法就可以使用适合自己的名称。

下面是一个最简单的Mutex类的实现，它使用同步状态0表示解锁，1表示锁定。这个类并不需要同步方法中的参数，因此这里在调用的时候使用0作为实参，方法实现里将其忽略。

[code lang=”java”]
class Mutex {
class Sync extends AbstractQueuedSynchronizer {
public boolean tryAcquire(int ignore) {
return compareAndSetState(0, 1);
}
public boolean tryRelease(int ignore) {
setState(0); return true;
}
}

private final Sync sync = new Sync();
public void lock() { sync.acquire(0); }
public void unlock() { sync.release(0); }
}
[/code]

这个例子的一个更完整的版本，以及其它用法指南，可以在J2SE的文档中找到。还可以有一些变体。如，tryAcquire可以使用一种“test-and-test-and-set”策略，即在改变状态值前先对状态进行校验。

令人诧异的是，像互斥锁这样性能敏感的东西也打算通过委托和虚方法结合的方式来定义。然而，这正是现代动态编译器一直在重点研究的面向对象设计结构。编译器擅长将这方面的开销优化掉，起码会优化频繁调用同步器的那些代码。

AbstractQueuedSynchronizer类也提供了一些方法用来协助策略控制。例如，基础的acquire方法有可超时和可中断的版本。虽然到目前为止，我们的讨论都集中在像锁这样的独占模式的同步器上，但AbstractQueuedSynchronizer类也包含另一组方法（如acquireShared），它们的不同点在于tryAcquireShared和tryReleaseShared方法能够告知框架（通过它们的返回值）尚能接受更多的请求，最终框架会通过级联的signal(cascading signals)唤醒多个线程。

虽然将同步器序列化（持久化存储或传输）一般来说没有太大意义，但这些类经常会被用于构造其它类，例如线程安全的集合，而这些集合通常是可序列化的。AbstractQueuedSynchronizer和ConditionObject类都提供了方法用于序列化同步状态，但不会序列化潜在的被阻塞的线程，也不会序列化其它内部暂时性的簿记（bookkeeping）变量。即使如此，在反序列化时，大部分同步器类也只仅将同步状态重置为初始值，这与内置锁的隐式策略一致 —— 总是反序列化到一个解锁状态。这相当于一个空操作，但仍必须显式地支持以便final字段能够反序列化。

4.1 公平调度的控制

尽管同步器是基于FIFO队列的，但它们并不一定就得是公平的。可以注意到，在基础的acquire算法（3.3节）中，tryAcquire是在入队前被执行的。因此一个新的acquire线程能够“窃取”本该属于队列头部第一个线程通过同步器的机会。

可闯入的FIFO策略通常会提供比其它技术更高的总吞吐率。当一个有竞争的锁已经空闲，而下一个准备获取锁的线程又正在解除阻塞的过程中，这时就没有线程可以获取到这个锁，如果使用闯入策略，则可减少这之间的时间间隔。与此同时，这种策略还可避免过分的，无效率的竞争，这种竞争是由于只允许一个（第一个）排队的线程被唤醒然后尝试acquire操作导致的。在只要求短时间持有同步器的场景中，创建同步器的开发者可以通过定义tryAcquire在控制权返回之前重复调用自己若干次，来进一步凸显闯入的效果。

可闯入的FIFO同步器只有概率性的公平属性。锁队列头部一个解除了阻塞的线程拥有一次无偏向的机会（译者注：即不会偏向队头的线程也不会偏向闯入的线程）来赢得与闯入的线程之间的竞争，如果竞争失败，要么重新阻塞要么进行重试。然而，如果闯入的线程到达的速度比队头的线程解除阻塞快，那么在队列中的第一个线程将很难赢得竞争，以至于几乎总要重新阻塞，并且它的后继节点也会一直保持阻塞。对于短暂持有的同步器来说，在队列中第一个线程被解除阻塞期间，多处理器上很可能发生过多次闯入（译者注：即闯入的线程的acquire操作）和release了。正如下文所提到的，最终结果就是保持一或多个线程的高进展速度的同时，仍至少在一定概率上避免了饥饿的发生。

当有更高的公平性需求时，实现起来也很简单。如果需要严格的公平性，程序员可以把tryAcquire方法定义为，若当前线程不是队列的头节点（可通过getFirstQueuedThread方法检查，这是框架提供的为数不多的几个检测方法之一），则立即失败（返回false）。

一个更快，但非严格公平的变体可以这样做，若队列为空（判断的瞬间），仍然允许tryAcquire执行成功。在这种情况下，多个线程同时遇到一个空队列时可能会去竞争以使自己第一个获得锁，这样，通常至少有一个线程是无需入队列的。java.util.concurrent包中所有支持公平模式的同步器都采用了这种策略。

尽管公平性设置在实践中很有用，但是它们并没有保障，因为Java Language Specification没有提供这样的调度保证。例如：即使是严格公平的同步器，如果一组线程永远不需要阻塞来达到互相等待，那么JVM可能会决定纯粹以顺序方式运行它们。在实际中，单处理器上，在抢占式上下文切换之前，这样的线程有可能是各自运行了一段时间。如果这样一个线程正持有某个互斥锁，它将很快会被切换回来，仅是为了释放其持有的锁，然后会继续阻塞，因为它知道有另外一个线程需要这把锁，这更增加了同步器可用但没有线程能来获取之间的间隔。同步器公平性设置在多处理器上的影响可能会更大，因为在这种环境下会产生更多的交错，因此一个线程就会有更多的机会发现锁被另一个线程请求。

在高竞争下，当保护的是短暂持有锁的代码体时，尽管性能可能会较差，但公平锁仍然能有效地工作。例如，当公平性锁保护的是相对长的代码体和/或有着相对长的锁间(inter-lock)间隔，在这种情况下，闯入只能带来很小的性能优势，但却可能会大大增加无限等待的风险。同步器框架将这些工程决策留给用户来确定。

4.2 同步器

下面是java.util.concurrent包中同步器定义方式的概述：

ReentrantLock类使用AQS同步状态来保存锁（重复）持有的次数。当锁被一个线程获取时，ReentrantLock也会记录下当前获得锁的线程标识，以便检查是否是重复获取，以及当错误的线程（译者注：如果线程不是锁的持有者，在此线程中执行该锁的unlock操作就是非法的）试图进行解锁操作时检测是否存在非法状态异常。ReentrantLock也使用了AQS提供的ConditionObject，还向外暴露了其它监控和监测相关的方法。ReentrantLock通过在内部声明两个不同的AbstractQueuedSynchronizer实现类（提供公平模式的那个禁用了闯入策略）来实现可选的公平模式，在创建ReentrantLock实例的时候根据设置（译者注：即ReentrantLock构造方法中的fair参数）使用相应的AbstractQueuedSynchronizer实现类。

ReentrantReadWriteLock类使用AQS同步状态中的16位来保存写锁持有的次数，剩下的16位用来保存读锁的持有次数。WriteLock的构建方式同ReentrantLock。ReadLock则通过使用acquireShared方法来支持同时允许多个读线程。

Semaphore类（计数信号量）使用AQS同步状态来保存信号量的当前计数。它里面定义的acquireShared方法会减少计数，或当计数为非正值时阻塞线程；tryRelease方法会增加计数，可能在计数为正值时还要解除线程的阻塞。

CountDownLatch类使用AQS同步状态来表示计数。当该计数为0时，所有的acquire操作（译者注：acquire操作是从aqs的角度说的，对应到CountDownLatch中就是await方法）才能通过。

FutureTask类使用AQS同步状态来表示某个异步计算任务的运行状态（初始化、运行中、被取消和完成）。设置（译者注：FutureTask的set方法）或取消（译者注：FutureTask的cancel方法）一个FutureTask时会调用AQS的release操作，等待计算结果的线程的阻塞解除是通过AQS的acquire操作实现的。

SynchronousQueues类（一种CSP（Communicating Sequential Processes）形式的传递）使用了内部的等待节点，这些节点可以用于协调生产者和消费者。同时，它使用AQS同步状态来控制当某个消费者消费当前一项时，允许一个生产者继续生产，反之亦然。

java.util.concurrent包的使用者当然也可以为自定义的应用定义自己的同步器。例如，那些曾考虑到过的，但没有采纳进这个包的同步器包括提供WIN32事件各种风格的语义类，二元信号量，集中管理的锁以及基于树的屏障。

5 性能

虽然AQS框架除了支持互斥锁外，还支持其它形式的同步方式，但锁的性能是最容易测量和比较的。即使如此，也还存在许多不同的测量方式。这里的实验主要是设计来展示锁的开销和吞吐量。

在每个测试中，所有线程都重复的更新一个伪随机数，该随机数由nextRandom(int seed)方法计算：

[code lang=”java”]
int t = (seed % 127773) * 16807 – (seed / 127773) * 2836;
return (t > 0) ? t : t + 0x7fffffff;
[/code]

在每次迭代中，线程以概率S在一个互斥锁下更新共享的生成器，否则（译者注：概率为1-S）更新其自己局部的生成器，此时是不需要锁的。如此，锁占用区域的耗时是短暂的，这就使线程持有锁期间被抢占时的外界干扰降到了最小。这个函数的随机性主要是为了两个目的：确定是否需要使用锁（这个生成器足以应付这里的需求），以及使循环中的代码不可能被轻易地优化掉。

这里比较了四种锁：内置锁，用的是synchronized块；互斥锁，用的是像第四节例子中的那样简单的Mutex类；可重入锁，用的是ReentrantLock；以及公平锁，用的是ReentrantLock的公平模式。所有测试都运行在J2SE1.5 JDK build46（大致与beta2相同）的server模式下。在收集测试数据前，测试程序先运行20次非竞争的测试，以排除JVM“预热”（译者注：更多关于“预热”的内容，参见：Java 理论与实践: 动态编译与性能测量）过程的影响。除了公平模式下的测试只跑了一百万次迭代，其它每个线程中的测试都运行了一千万次迭代。

该测试运行在四个X86机器和四个UltraSparc机器上。所有X86机器都运行的是RedHat基于NPTL 2.4内核和库的Linux系统。所有的UltraSparc机器都运行的是Solaris-9。测试时所有系统的负载都很轻。根据该测试的特征，并不要求系统完全空闲（译者注：即测试时操作系统上有其它较轻的负载也不会影响本次测试的结果。）。“4P”这个名字反映出双核超线程的Xeon更像是4路机器，而不是2路机器。这里没有将测试数据规范化。如下所示，同步的相对开销与处理器的数量、类型、速度之间不具备简单的关系。

表1 测试的平台

名字	处理器数量	类型	速度(Mhz)
1P	1	Pentium3	900
2P	2	Pentium3	1400
2A	2	Athlon	2000
4P	2HT	Pentium4/Xeon	2400
1U	1	UltraSparc2	650
4U	4	UltraSparc2	450
8U	8	UltraSparc3	750
24U	24	UltraSparc3	750

5.1 开销

无竞争情况下的开销是通过仅运行一个线程，将概率S为1时的每次迭代时间减去概率S为0（访问共享内存的概率为0）时的每次迭代时间得到的（译者注：这里的“概率S”即前文提到的“概率S”，概率为0时是没有锁操作的，概率为1时是每次都有锁操作，因此将概率为1时的耗时减去概率为0时的耗时就是整个锁操作的开销。）。表2以纳秒为单位显示了非竞争场景下每次锁操作的开销。Mutex类最接近于框架的基本耗时，可重入锁的额外开销是记录当前所有者线程和错误检查的耗时，对于公平锁来说还包含开始时检查队列是否为空的耗时。

表格2也展示与内置锁的“快速路径（fast path）”对比，tryAcquire的耗时。这里的差异主要反映出了各锁和机器中使用的不同的原子指令以及内存屏障的耗时。在多处理器上，这些指令常常是完全优于所有其它指令的。内置锁和同步器类之间的主要差别，显然是由于Hotspot锁在锁定和解锁时都使用了一次compareAndSet，而同步器的acquire操作使用了一次compareAndSet，但release操作用的是一次volatile写（即，多处理器上的一次内存屏障以及所有处理器上的重排序限制）。每个锁的绝对的和相对耗时因机器的不同而不同。

表2 无竞争时的单锁开销（单位：纳秒）

机器	内置	互斥	可重入	公平可重入
1P	18	9	31	37
2P	58	71	77	81
2A	13	21	31	30
4P	116	95	109	117
1U	90	40	58	67
4U	122	82	100	115
8U	160	83	103	123
24U	161	84	108	119

从另一个极端看，表3展示了概率S为1，运行256个并发线程时产生了大规模的锁竞争下每个锁的开销。在完全饱和的情况下，可闯入的FIFO锁比内置锁的开销少了一个数量级（也就是更大的吞吐量），比公平锁更是少了两个数量级。这表现出即使有着极大的竞争，在维持线程进展方面可闯入FIFO策略的效率。

表3也说明了即使在内部开销比较低的情况下，公平锁的性能也完全是由上下文切换的时间所决定的。列出的时间大致上都与各平台上线程阻塞和解除线程阻塞的时间相称。

此外，后面增加的一个实验（仅使用机器4P）表明，对于这里用到的短暂持有的锁，公平参数的设置在总差异中的影响很小。这里将线程终止时间间的差异记录成一个粗粒度的离散量数。在4P的机器上，公平锁的时间度量的标准差平均为0.7%，可重入锁平均为6.0%。作为对比，为模拟一个长时间持有锁的场景，测试中使每个线程在持有锁的情况下计算了16K次随机数。这时，总运行时间几乎是相同的（公平锁：9.79s，可重入锁：9.72s）。公平模式下的差异依然很小，标准差平均为0.1%，而可重入锁上升到了平均29.5%。

表格3 饱和时的单锁开销（单位：纳秒）

机器	内置	互斥	可重入	公平可重入
1P	521	46	67	8327
2P	930	108	132	14967
2A	748	79	84	33910
4P	1146	188	247	15328
1U	879	153	177	41394
4U	2590	347	368	30004
8U	1274	157	174	31084
24U	1983	160	182	32291

5.2 吞吐量

大部分同步器都是用于无竞争和极大竞争之间的。这可以用实验在两个方面进行检查，通过修改固定个线程的竞争概率，和/或通过往拥有固定竞争概率的线程集合里增加更多的线程。为了说明这些影响，测试运行在不同的竞争概率和不同的线程数目下，都用的是可重入锁。附图使用了一个slowdown度量标准。

这里，t是总运行时间，b是一个线程在没有竞争或同步下的基线时间，n是线程数，p是处理器数，S是共享访问的比例（译者注：即前面的竞争概率S）。计算结果是实际执行时间与理想执行时间（通常是无法得到的）的比率，理想执行时间是通过使用Amdahl’s法则计算出来的。理想时间模拟了一次没有同步开销，没有因锁争用而导致线程阻塞的执行过程。即使这样，在很低的竞争下，相比理想时间，有一些测试结果却表现出了很小的速度增长，大概是由于基线和测试之间的优化、流水线等方面有着轻微的差别。

图中用以2为底的对数为比例进行了缩放。例如，值为1表示实际时间是理想时间的两倍，4表示慢16倍。使用对数就不需要依赖一个随意的基线时间（这里指的是计算随机数的时间），因此，基于不同底数计算的结果表现出的趋势应该是类似的。这些测试使用的竞争概率从1/128（标识为“0.008”）到1，以2的幂为步长，线程的数量从1到1024，以2的幂的一半为步长。

在单处理器（1P和1U）上，性能随着竞争的上升而下降，但不会随着线程数的增加而下降。多处理器在遭遇竞争时，性能下降的更快。根据多处理器相关的图表显示，开始出现的峰值处虽然只有几个线程的竞争，但相对性能通常却最差。这反映出了一个性能的过渡区域，在这里闯入的线程和被唤醒的线程都准备获取锁，这会让它们频繁的迫使对方阻塞。在大部分时候，过渡区域后面会紧接着一个平滑区域，因为此时几乎没有空闲的锁，所以会与单处理器上顺序执行的模式差不多；在多处理器机器上会较早进入平滑区域。例如，请注意，在满竞争（标识为“1.000”）下这些值表示，在处理器越少的机器上，会有更糟糕的相对速度下降。

根据这些结果，可以针对阻塞（park/unpark）做进一步调优以减少上下文切换和相关的开销，这会给本框架带来小但显著的提升。此外，在多处理器上为短时间持有的但高竞争的锁采用某种形式的适应性自旋，可以避免这里看到的一些波动，这对同步器类大有裨益。虽然在跨不同上下文时适应性自旋很难很好的工作，但可以使用本框架为遇到这类使用配置的特定应用构建一个自定义形式的锁。

6 总结

本文撰写之时，java.util.concurrent包中的同步器框架还太新所以还不能在实践中使用。因此在J2SE 1.5最终版本发布之前都很难看到其大范围的使用，并且，它的设计，API实现以及性能肯定还有无法预料的后果。但是，此时，这个框架明显能胜任其基本的目标，即为创建新的同步器提供一个高效的基础。

7 致谢

Thanks to Dave Dice for countless ideas and advice during the development of this framework, to Mark Moir and Michael Scott for urging consideration of CLH queues, to David Holmes for critiquing early versions of the code and API, to Victor Luchangco and Bill Scherer for reviewing previous incarnations of the source code, and to the other members of the JSR166 Expert Group (Joe Bowbeer, Josh Bloch, Brian Goetz, David Holmes, and Tim Peierls) as well as Bill Pugh, for helping with design and specifications and commenting on drafts of this paper. Portions of this work were made possible by a DARPA PCES grant, NSF grant EIA-0080206 (for access to the 24way Sparc) and a Sun Collaborative Research Grant.

参考文献

• [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.