ABSTRACT Most synchronizers (locks, barriers, etc。) in the J2SE1。5 java。util。concurrent package are constructed using a small framework based on class AbstractQueuedSynchro- nizer。 This framework provides common mechanics for atomically managing synchronization state, blocking and unblocking threads, and queuing。 The paper describes the rationale, design, implementation, usage, and performance of this framework。84000

Categories and Subject Descriptors

D。1。3 [Programming Techniques]: Concurrent Programming – Parallel Programming

General Terms Algorithms, Measurement, Performance, Design。

Keywords Synchronization, Java

1。INTRODUCTION

Javatm release J2SE-1。5 introduces package java。util。concurrent, a collection of medium-level concurrency support  classes created via Java Community Process (JCP) Java Specification Request (JSR) 166。 Among these components are a set of synchronizers – abstract data type (ADT) classes that maintain an internal synchronization state (for example, representing  whether  a lock is locked or unlocked), operations to update and  inspect  that state, and at least one method that will cause a calling thread to block if the state requires it, resuming when some other thread changes the synchronization state to permit it。 Examples include various forms of mutual exclusion locks, read-write locks, semaphores, barriers, futures, event indicators, and handoff queues。

As is well-known (see e。g。, [2]) nearly any synchronizer can be used to implement nearly any other。 For example, it is possible to build semaphores from reentrant locks, and vice versa。 However, doing so often entails enough complexity, overhead, and inflexibility to be at best a second-rate engineering option。 Further, it is conceptually unattractive。 If none of these constructs are intrinsically more primitive than  the  others, developers should not be compelled to arbitrarily choose one of them as a basis for building others。 Instead, JSR166 establishes a small framework centered on class AbstractQueuedSynchro- nizer, that provides common mechanics that are used by    most

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page。 To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior  specific  permission  and/or a fee。

CSJP’04, July 26, 2004, St John's, Newfoundland, CA。

of the provided synchronizers in the package, as well as other classes that users may define themselves。

The remainder of this paper discusses the requirements for this framework, the main ideas behind its design and implementation, sample usages, and some measurements showing its performance characteristics。

2。REQUIREMENTS

2。1Functionality

Synchronizers possess two kinds of methods [7]: at least one acquire operation that blocks the calling thread unless/until the synchronization state allows it to proceed, and at  least  one release operation that changes synchronization state in a way that may allow one or more blocked threads to unblock。

The java。util。concurrent package does not define a single unified API for synchronizers。 Some are defined via common interfaces (e。g。, Lock), but others contain only specialized versions。 So, acquire and release operations take a range of names and forms across different classes。 For example, methods Lock。lock, Semaphore。acquire, CountDownLatch。await, and FutureTask。get all map to acquire operations in the framework。 However, the package does maintain consistent conventions across classes to support a range of common usage options。 When meaningful, each synchronizer supports: