Standardized, efficient utility classes commonly encountered in concurrent
programming.
For the master version of this page (more up-to-date, more info) please go
to http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html)
Overview of package util.concurrent Release 1.3.0
by Doug Lea
This package provides standardized, efficient versions of utility
classes commonly encountered in concurrent Java programming. The
ideas behind and applications of several of these classes are
discussed in the second edition of Concurrent Programming in
Java. There are also pdf
slides providing an overview of the package.
The packege mainly consists of implementations of a few
interfaces:
Sync
-- locks, conditions
Channel
-- queues, buffers
Barrier
-- multi-party synchronization
SynchronizedVariable
-- atomic ints, refs etc
java.util.Collection
-- collections
Executor
-- replacements for direct use of Thread
Plus some utilities and frameworks that build upon these.
If you arrived at page
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html
following links from your local documentation, please check the
version number and get an update if you are running an outdated version.
Installation
This package, currently declared as
EDU.oswego.cs.dl.util.concurrent
is available in
(tar.gz format)
or
(zip format).
It is currently distributed in source form only. To build it, use
a Java 1.2 compiler to:
javac -d [SOMEWHERE IN YOUR CLASSPATH] *.java
The classes in the misc
directory can be built the same way.
To use it, add to java files:
import EDU.oswego.cs.dl.util.concurrent.*
You can also create a jar or zip file of the compiled classes
and add them to your classpath.
All
documentation except for this file was produced by (JDK1.2) javadoc,
which places some index and summary files outside the current
directory. This can cause some broken links on unpacked versions.
You can avoid this, and integrate with your local javadoc-produced
documentation by running:
javadoc -public -d [BASE OF SOME JAVADOC PATH] *.java
Contents
- Sync
- Interface for classes used as exclusion, resource management,
and related synchronization aids, supporting methods
acquire
, attempt(msecs)
, and
release
.
Implementations
- Semaphore
- Default implementation of Semaphores, providing no
special ordering guarantees.
- WaiterPreferenceSemaphore
- Provides protection against barging (infinite overtaking)
- FIFOSemaphore
- Provides first-in/first-out ordering
- PrioritySemaphore
- Prefers notifications to higher-priority threads
- Mutex
- Basic non-reentrant mutual exclusion lock
- ReentrantLock
- Java-style per-thread mutual exclusion lock
- Latch
- A condition that is acquirable forever more after the first release
- CountDown
- A condition that is acquirable forever more after the nth
release.
The following implementation classes do not themselves
perform any synchronization, but serve as adaptors, glue, and
extensibility hooks for those that do. They may also be helpful
when using Syncs in generic before/after constructions:
- NullSync
- A no-op implementation: acquire and attempt always succeed.
- TimeoutSync
- Routes all calls to acquire to use attempt with a predefined
timeout value.
- LayeredSync
- Cascades operations of two Syncs
- ObservableSync
- Issues calls to SyncObservers upon each acquire and release.
Related Classes
- CondVar
- Support for POSIX (pthreads) style condition variables
- TimeoutException
- A standardized time-out exception class
- ReadWriteLock
- Interface for pairs of locks, one for reading, and one for writing.
Implementations
- WriterPreferenceReadWriteLock
- The most useful and common policy
- ReentrantWriterPreferenceReadWriteLock
- Allows multiple lock holds as well as lock downgrading by writers.
- ReaderPreferenceReadWriteLock
- Prefers waiting readers to waiting writers.
- FIFOReadWriteLock
- Prefers either a writer or readers, depending on which one
arrived first.
- Barrier
- Synchronization points for groups of threads.
Implementations
- CyclicBarrier
- A tool to force multiple threads to synchronize at a given point
- Rendezvous
- A cyclic barrier that does not rely on there being
a predetermined number of participant threads, and allows
threads to exchange information at each barrier point.
Related Classes
- BrokenBarrierException
- A standardized exception for barrier synchronization failures
- Channel
- Interface for queues, buffers, conduits and pipes supporting
blocking
put
and take
,
as well as timeout-based offer
and poll
.
To assist efforts to use channels with somewhat
greater type safety, Channel
is defined as a subinterface of Puttable
and Takable, each defining only one side
of the channel.
Also, the BoundedChannel subinterface is used
for channels with finite capacities.
Implementations
- LinkedQueue
- An unbounded linked-list-based queue
- BoundedLinkedQueue
- A linked queue with a capacity bound
- BoundedBuffer
- An array-based bounded buffer
- Slot
- A one-slot bounded buffer. (Note that this can also
serve as a restricted form of Synchronized variable.)
- SynchronousChannel
- A zero-slot CSP/Ada-style channel in which every put must wait for a
take, and vice versa.
- BoundedPriorityQueue
- A channel based on a Heap data structure. Elements
must either be Comparable, or comparable using a supplied Comparator
- WaitFreeQueue
- An unbounded linked-list-based queue relying on atomic
commits and retries rather than wait/notify.
Related Classes
- DefaultChannelCapacity
- A utility class that makes
it easier to set default capacities for channels that have a
capacity that must otherwise be set in constructors.
- Executor
- Interface for objects that
execute
Runnable commands.
Implementations
- DirectExecutor
- An implementation that just directly runs command
in current thread.
- LockedExecutor
- An implementation that directly runs command
within a supplied Sync lock in current thread.
- ThreadedExecutor
- An implementation that runs each command
in a new thread.
- QueuedExecutor
- An implementation that queues commands for execution
by a single background thread.
- PooledExecutor
- A tunable, extensible thread pool class
Related classes
- Callable
- Interface for runnable actions that return results
- FutureResult
- Holder for results of actions that can be set by Callables.
- ThreadFactory
- Interface for objects that create Thread objects
- ThreadFactoryUser
- Convenient base for classes that use ThreadFactories.
- ClockDaemon
- A utility for executing commands at given times,
after given delays, or periodically with given cycles.
- TimedCallable
- Invokes a Callable in its own thread, but cancels it if not
completed by a given maximum time.
- Fork/Join Tasks
- A fast lightweight task framework built upon Java threads, and
geared for parallel computation.
- FJTask
- Abstract Base class for tasks.
- FJTaskRunnerGroup
- Control class for running Tasks.
- FJTaskRunner
- Underlying specialized Thread subclass for running Tasks.
- Demos and examples
- A directory of sample programs that use the Task framework.
(See also a paper on the design and
performance of this framework.)
- Collections
- Implementations of java.util.Collection and related classes that
can help solve concurrency problems.
- ConcurrentReaderHashMap
- An analog of java.util.Hashtable that allows retrievals
during updates.
- ConcurrentHashMap
- An analog of java.util.Hashtable that allows
both concurrent retrievals and concurrent updates.
- CopyOnWriteArrayList
- A copy-on-write analog of java.util.ArrayList
- CopyOnWriteArraySet
- A java.util.Set based on CopyOnWriteArrayList.
- SyncCollection
- A wrapper class placing either Syncs or ReadWriteLocks
around java.util.Collection
- SyncSet
- A wrapper around java.util.Set
- SyncSortedSet
- A wrapper around java.util.SortedSet
- SyncList
- A wrapper around java.util.List
- SyncMap
- A wrapper around java.util.Map
- SyncSortedMap
- A wrapper around java.util.SortedMap
- Related classes
-
- PropertyChangeMulticaster
- A copy-on-write replacement for java.beans.PropertyChangeSupport
- VetoableChangeMulticaster
- A copy-on-write replacement for java.beans.VetoableChangeSupport
- SynchronizedVariable
- Simple synchronized analogs of Number and Ref classes in
java.lang. Each has a subclass that in addition to
maintaining synchronization, also provides notifications
upon value changes and supports guarded waits.
- Miscellany
- There are some classes in the
misc
directory
that might be of interest but aren't really part of this
package. They include:
- SynchronizationTimer,
that can be used to experiment with different synchronization
schemes. It requires Swing (JFC).
- An immutable Fraction class.
- Other implementations of the above interfaces that
are not valuable or stable enough to include here.
Notes
- All classes are released to the public domain and may be used
for any purpose whatsoever without permission or
acknowledgment. Some of the CopyOnWriteArrayList class is adapted
from publicly available Sun JDK1.2 source code, and thus probably
falls under JDK copyright.
- Version numbers for this package are of the form
Major.minor.fix. Fix numbers reflect corrections of small errors
and release problems (missing files, portability enhancements,
etc). Minor numbers are incremented on additions. Major numbers
reflect serious incompatibilities and restructurings. I may also
sometimes make minor updates to this page and related files before
packaging up all files as a release. During early releases of added
classes, I expect to make frequent small changes and releases, as
soon as problems are noticed. Other ongoing changes are reflected
in individual source files, that you can get individual updates on
if you need them.
- Most of the interfaces and classes contain usage notes and
examples. I hope to add more. Please send suggestions to dl@cs.oswego.edu
- You can get e-mail notification when this page (or any other
URL for that matter) changes via NetMind or other such services.
- These have been tested with JDK1.2+, but all except those
relying on JDK1.2 java.util.collections (i.e., BoundedPriorityQueue
and CopyOnWriteArrayList) should also work with
JDK1.1.x. Workarounds exist for those relying on collections by
obtaining the backported
1.1 versions and follow the instructions.
You can the use "sed" or somesuch to replace all
occurrences of "java.util. with "com.sun.java.util". Also, I'm
told that some 1.1 compilers have some problems compiling some of
the blank finals used. And while the 1.1port of collections also
includes a 1.2-compliant version of Random, you can alternatively
use the follwoing version contributed by Andrew Cooke:
java.util.Random:
package EDU.oswego.cs.dl.util.concurrent ;
class Random extends java.util.Random {
public Random() {super() ;}
public Random(long l) {super(l) ;}
public int nextInt(int i) {
int ii = (int)(i * nextDouble()) ;
if (ii >= i) {ii = i-1 ;} // should (almost?) never happen...
return ii ;
}
}
Konstantin Läufer has generously placed a version compiled for JDK1.1
at http://www.cs.luc.edu/~laufer/courses/337/handouts/concurrent11.zip
- Many of these classes are adapted from versions described in
the second edition of
Concurrent Programming in Java (CPJ) and examples from
tutorials based on the book.
- Several classes were developed with the help of David Holmes and Joe
Bowbeer. Many have benefited from discussions and comments from
other people, including Tom Cargill, Tom May, Wayne
Boucher, Matthias Ernst, Michael Banks, Richard Emberson,
Piotr Kaminski, Alex Yiu-Man Chan, Andrew Kelly, Markos Kapes.
Some Questions and Answers about Design and Implementation
- Isn't it annoying that so many methods throw InterruptedException?
- Maybe, but synchronization points are among the best points to
detect interruption. Since this a package of synchronization aids,
most methods detect interruption as early and often as reasonable
to help avoid becoming stuck when the thread should be stopping
anyway. In particular, interruption is normally checked before
trying to obtain locks used in Syncs, which minimizes the
vulnerability window for getting stuck when an activity is cancelled.
(Between this and the finite durations that internal java synchronization
locks are held in Sync classes, it is normally impossible for threads to
become stuck waiting on internal locks when they have been interrupted.)
These classes fail cleanly upon interruption. Normally,
all you need to do upon catching an InterruptedException is
either rethrow it, or clean up and then set
Thread.currentThread().interrupt()
to propagate
status.
If you need to invoke such methods even when the thread is in an
interrupted state (for example, during recovery actions) you can do:
void quietlyAcquire(Sync sync) {
boolean wasInterrupted = Thread.interrupted(); // record and clear
for (;;) {
try {
sync.acquire(); // or any other method throwing InterruptedException
break;
}
catch (InterruptedException ex) { // re-interrupted; try again
wasInterrupted = true;
}
}
if (wasInterrupted) { // re-establish interrupted state
Thread.currentThread().interrupt();
}
}
The heavy use of InterruptedException makes it possible to write
very responsive and robust code, at the expense of forcing
class and method authors to contemplate possible exception handling
actions at each interruption (and time-out) point. See
the CPJ
supplement page on cancellation for more discussion of some
associated design issues.
- Why is there so much near-duplication of code?
- You'd think there would be some nice way to unify more classes
to share significant aspects of synchronization mechanics. But
standard lines of attack for doing this turn out unsatisfying at
best. The main reason for creating this package is that even
simple classes involving concurrency control mechanics are
sometimes tedious, repetitive, tricky, and/or error-prone to write,
so it is nice to have them written already.
- Why do most methods return false/null after timeouts rather
than throwing TimeoutException?
- Because I think it would normally be misleading to throw
exceptions. In Java, timeout arguments merely provide hints about
when threads should be woken to check out the state of the world.
Due to scheduling delays, threads need not resume immediately after
their timeouts elapse, so real-time-based timeout exceptions would
not be appropriate. The simplest course of action is just to report
whether the condition the thread is waiting for does hold after
waiting for at least this period. Returning false/null is not
necessarily an exceptional situation. In those classes where it is
exceptional (in some classes layered on top of basic Syncs and
Channels) failed timeouts are converted to TimeoutExceptions. You
can do the same in your own code using these classes. As of version
1.1.0, this is made simpler to carry out, since TimeoutException
now extends InterruptedException.
- Why aren't there deadlock-detecting Syncs or related classes for
detecting lockups?
- Because timeouts appear to be more generally useful. In fact,
it is hard to imagine contexts where deadlock detection is a
better option than timeouts in Java. A timeout can serve as a
heuristic deadlock detection device, but can also serve to detect
stalled IO, network partitions, and related failures. Program
responses to deadlock are hardly ever different than responses to
these other failures. So, it is usually a good idea to use timeouts as
general-purpose heuristic detectors for all liveness problems,
subdividing responses to particular failures (for example, by
subclassing TimeoutException), only when necessary. Additionally,
there are two problems with implementing deadlock-detecting Syncs
that make them unattractive choices: (1) They can only detect
deadlock among uses of the particular Sync classes being used, so
cannot deal with deadlocks involving builtin synchronization (2)
lock cycle detection adds overhead to each lock acquire and release.
The main context in which deadlock detection would be useful is
during program debugging, but here, it would be better to rely
on specially instrumented JVMs. (Note that it is easy to transform
code that relies on acquire to instead use timeouts via
the TimeoutSync class. This can be a good way to make code more
robust with respect to locking problems.)
- Why isn't there a distinct Lock or MutualExclusionLock interface?
- Because many objects implementing the Sync interface can be
used as locks if they are in appropriate states, but not all of
them can always be used as such. Additionally, there are several
senses of mutual exclusion (for example, reentrant vs
non-reentrant, full vs read/write). Since there is no way to say
that a given class only sometimes conforms to the intended sense of
a subinterface, the flexibility and simplicity of
only using a single principle interface (Sync) for all such types
outweighs the potential advantages of finer-grained
categorizations.
- Why do so many methods perform notify within InterruptedException
catches?
- Because when notify's and interrupt's happen at about the
same time, JVMs are currently free to treat them independently, so
a notified thread could return out as interrupted. In classes
using notify rather than notifyAll, the extra notify in the catch
clause is a safeguard to ensure that a non-interrupted thread, if
one exists, will be notified.
- How efficient are these classes?
- Most of these classes use the most efficient implementations I
know of for general-purpose concurrent programming, yet also try to
be conservative about differences across common JVMs, and to
minimize surprising limitations and side-effects. This is always a
bit of a trade-off though. Some could be made more efficient at the
cost of supporting fewer operations, relying on properties of
particular JVMs, or having more usage constraints. Conversely some
could support more contexts or operations, or simpler usage, at the
cost of efficiency.
You will almost surely trade off some cost in efficiency for the
flexibility of using Syncs and classes built out of them rather
than built-in synchronized
method/block locks. On
some JVMs the cost is very low. (You can check approximate impact
using SynchronizationTimer.)
But, while Java VMs are getting much faster about
synchronized
locks, most of the classes in this
package rely heavily on wait/notify and interruption mechanics,
which are not currently as heavily optimized. (Also, they seem to
be subject to more variation in behavior than other Java
constructs.) Class implementations generally ignore the fact
that the JVM overhead for these operations might be slower than
you'd wish they were on some JVMs.
- Are there any programming errors?
- I don't believe so. Please try to prove me wrong. If you
are the first person to discover a particular coding error in a
current release, I'll send you a free copy of my CPJ book.
Also, I would greatly appreciate receiving any sample
applications that can help serve as useful tests, so as to build
up a more extensive test suite.
- Should I worry about the use of volatile in these classes?
- Many JVMs are known not to correctly implement the JLS spec
(either the original or the upcoming revision) for volatile fields.
However, volatiles are used in conservative ways in this package,
that don't encounter problems at least on Sun JVMs on sparc and
intel.
- Why do classes declare practically all internal matters as
protected
?
- While probably 99% of the uses of most these classes should
just treat them as black-box utility components, these classes are
intended to be extensible, to allow more specialized
synchronization control to be customized for different
applications. However, it takes a lot of expertise to extend or
modify most of them via subclassing. If you do try to extend,
consider first running javadoc on these classes with switches that
generate documentation for non-public classes, methods, and
fields. Also, if you encounter problems making subclasses due to
inflexibility in base classes, I'd like to hear about it, so I can
try to come up with a better factoring.
- Why aren't most classes
Serializable
?
- I don't know what to about this. On one hand, it
wouldn't make sense in a lot of contexts to serialize, say,
a Semaphore. On the other hand, maybe it ought not be precluded.
Opinions welcome. One suggestion is to only declare as serializable
those classes specifically designed to work with other persistent
or distributed concurrency control frameworks. (No such classes
currently exist.)
- Are instances of these classes externally lockable -- that is, can I
control object
x
via synchronized(x) { ... }
?
- Not necessarily. Some objects rely on their own synchronization locks,
some rely on internal locks, some rely on other synchronization objects.
So in general, you cannot know the effect of
synchronized(x)
and so probably ought never use it.
- Why do I get strict alternation of producer and consumer threads
when using buffered channels such as BoundedBuffer?
- Although it depends on details of JVM scheduling policies,
this is the most likely result when producer and consumer actions
both take about the same amount of time to process, since both
put and take operations signal waiting threads. The point of
buffering is to decouple producers and consumers when one or the
other is bursty, so temporarily gets ahead or behind its average
rate. (If the average rates of producers and consumers are not
approximately equal, buffering is not of much use.) While it again
relies on JVM details, unbounded buffers (for example LinkedQueue)
typically do not result in alternation, allowing producers to get
arbitrarily ahead of consumers, at the expense of potential
resource exhaustion.
- Why aren't there timeout methods supporting nanosecond arguments?
- Because most JVMs only time to millisecond accuracy (at best) anyway.
If this changes, nanosecond versions could be added.
- Why is the package named
EDU
..., not edu
?
- I've been using the initially-recommended upper-case
EDU prefix for a long time for my packages. It would
take a lot of busy-work to convert everything to the
now-recommended practice
of using lower-case. Someday I will do this though.
- Why do you use those ugly underscores?!
- Because otherwise I tend to make coding mistakes surrounding
instance variables versus local variables. See my Sample
Java Coding Standard. But I think I've decided to reform :-)
The Task classes use a more JDK-like set of conventions.
- Why public domain?
- Because I work at a government institution (the State
University of New York). US government works are generally placed
into the public domain. This is not the preferred policy of SUNY
(which is a state, not federal institution), but I think it should
be, so I do it this way. The acknowlegdment to Sun Labs in
headers recognizes their generous donations of equipment and
release time support that help make this work possible. However,
this software is not in any way tied to Sun. At the most, it might
eventually form a basis for similar packages in JDK.
- Can I use this code in commercial products?
- Yes. Many people appear to do so.
- Can I get commercial support for this package?
- I don't know of any place to get it. I can't think of any
technical reason that you'd want it.
Sources
History
- 10Jul1998 1.0
- 11Jul1998 1.0.1: removed .class files from release, Fixed
documentation error, included Barrier interface.
- 12Jul1998 1.0.2: Fixed return value for swap; fixed documentation errors.
- 15Jul1998 1.0.3: Fixed more documentation errors; re-fixed swap;
other cosmetic improvements.
- 18Jul1998 1.0.4: Simplified some classes by removing
some alleged optimizations that do not actually help on some platforms;
improved SynchronizationTimer; added some documentation.
- 1Sep1998 version 1.1.0:
- Replace SynchronousChannel algorithm with fairer, more scalable one
- TimeoutException now extends InterruptedException
- Replace int counters with longs to avoid wrapping.
- new LayeredSync class
- new ObservableSync class
- new NullSync class
- new TimeoutSync class
- new SyncCollection classes
- new ReentrantWriterPreferenceReadWriteLock class
- peek added to Channel
- new ClockDaemon class
- Refactorings to standardize usage of thread factories
- removed reliance on ThreadGroups in PooledExecutor
- 7Jan 1999 Version 1.2
- ClockDaemon.shutdown allows immediate restart
- Callable.call throws Throwable, not Exception
- new Task, TaskRunner, TaskRunnerGroup classes
- new taskDemo subdirectory
- 13Jan1999 version 1.2.1
- Minor cleanup of Task classes
- 17Jan1999 version 1.2.2:
- Simplify Task classes; improve documentation;
add priority control; they are no longer labeled as `preliminary'.
- More sample programs in taskDemos
- Add warnings about reentrancy to RW locks
- Callable throws Exception again, but FutureResult handles Throwables
- 25Mar1999 version 1.2.3
- PooledExecutor -- allow pool to shrink when max size decreased
- Task -- add reset, array-based operations
- new PropertyChangeMulticaster, VetoableChangeMulticaster
- 21may1999 version 1.2.4
- PooledExecutor -- allow supplied Channel in constructor;
new methods createThreads(), drain()
- Task, TaskRunner, TaskRunnerGroup renamed to
FJTask, FJTaskRunner, FJTaskRunnerGroup to avoid
clashes with commonly used class name of `Task'.
- Misc documentation improvements
- WriterPreferenceReadWriteLock -- fix to notify on interrupt
- 23oct1999 version 1.2.5
- PooledExecutor -- add minimumPoolSize settings
- LU in taskDemo
- Minor improvements to LinkedQueue, FJTaskRunner
- 29dec1999 version 1.2.6
- FJTaskRunner -- now works on MP JVMs that do not
correctly implement read-after-write of volatiles.
- added TimedCallable
- 12jan2001 version 1.3.0
- new ConcurrentHashMap, ConcurrentReaderHashMap classes.
- BoundedLinkedQueue.setCapacity: immediately reconcile permits.
- ReentrantWriterPreferenceReadWriteLock: Both readers and writers
are now reentrant.
- PooledExecutor: policy now an interface, not abstract class.
- QueuedExecutor, PooledExecutor: new shutdown methods
- Coming attractions
- End-of-lifetime of ClockDaemon! A similar class is
included in JDK 1.3 release, so ClockDaemon will eventually
be removed from this package.
- InputTask framework for use with 1.4 java.nio
Doug Lea
Last modified: Fri Jan 12 10:00:04 EST 2001