JSR 166 Initial Aims and Scope

by Doug Lea

To join a mailing list discussing this JSR, go to: http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest .

This JSR focuses on creating APIs providing in-the-small frameworks, interfaces and implementations for commonly useful functionality. It also entails adding a few capablilities that cannot now be obtained in Java -- some new native methods that appear to be readily implementable on common JVMs/platforms. The APIs cover:

Here are brief discussions of the main ideas and rationales for the issues we will probably tackle in this JSR, along with pointers to javadocs of some (very!) preliminary versions of APIs and some notes about how and why these differ from those in: http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html

Atomic variables

These classes provide simple scalar variables supporting compareAndSwap (CAS). These are desparately needed. Not having them makes time-critical code much slower than possible in other languages and leads to complexity and contortions trying to simulate their effects. Of the ways to go about it, creating special classes seems the simplest and least controversial.

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/AtomicRef.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/AtomicInteger.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/AtomicLong.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/AtomicFloat.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/AtomicDouble.html

There's no reason to define versions of these classes for Boolean, Byte, Short, or Char. Since all implementations I know would need to reserve at least an int for CAS (or LL/SC or whatever), it would be useless and even deceptive to define these shorter types.

Also note that these classes do not strictly require JVM changes since it is possible to (more slowly) simulate effects via locks. The APIs would not strictly require lock-free implementations. However, we'd expect all JVMs capable of doing so to implement them using atomic instructions. On platforms that have CAS but not, say atomic-increment, "increment" operations would be done via CAS.

We need to decide whether and how to express DCAS (two-variable compare-and-swap). One solution is to support exactly three of the N^2 possible combinations (i.e., the ones that are actually known to be useful in non-blocking algorithms), in special CLASSES that can take two AtomicRefs, two AtomicIntegers, or a ref and int), and treat them as a DCAS-able pair. This isolates the time/space overhead of emulating DCAS using other instructions to applications that actually need it. This would involve a bit of VM trickery and some usage restrictions, but it would be worth it to get the functionality.

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/AtomicRefIntegerPair.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/AtomicRefPair.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/AtomicIntegerPair.html

Nanosecond Timing

Java has supported nanosecond versions of several native time-out-based methods (such as Object.wait), but no methods to actually perform timing in nanosecond units. This makes it impossible to support nanosecond timeouts in Java classes. One solution is to use the classes in the RTSJ (real-time) spec ( http://www.rtj.org/). But it is simpler is to create a NanoTimer class. This also avoids the packaging issue of introducing a dependency on javax.realtime. Here's one possibility:

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/NanoTimer.html

The API for nanosecond timing affects most other interfaces and classes. For this version I just have "Millis" vs "Nanos" versions for each method involving times.

Conditions

A Condition class can provide the kinds of condition variables associated with monitors in most other languages, as well as pthreads condvars. The main motivation is that it is exceedingly tricky and requires more overhead to implement many classic concurrent designs without them. Conditions can also address the annoying problem that Object.wait(msecs) does not return an indication of whether the wait timed out. This leads to error-prone code. Since this method is in class Object, the problem is basically unfixable.

The best way to express Conditions is to bind them to their host objects/locks upon construction. For uniformity though, we'd like to be able to attach conditions to either builtin locks or Lock objects, so should use factory methods for construction.

To avoid compatibility problems, the names of the methods need to be different than Object versions. The downside of this is that people can make the mistake of calling cond.notify instead of cond.signal. However, they will get IllegalMonitorState exceptions if they do, so they can detect the error if they ever run the code.

The implementation requires VM magic to atomically suspend and release lock. But it is unlikely to be very challenging for JVM providers, since most layer Java monitors on top of posix condvars or similar low-level functionality anyway.

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/Condition.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/TimeoutException.html

Lock classes

The main motivation is to allow implementations that differ in semantics (non-reentrant, semaphore-based, etc), and that can be used in non-block-structured contexts including hand-over-hand and lock reordering algorithms. This flexibility comes at the price of more awkward syntax, but this is probably tolerable.

In my u.c package, I abstracted locks into "Sync", which was a bad choice of name. Even though some implementations may not act as classic mutex locks, they are all locks of some kind. The main interface mistake to fix in u.c version is to separately support a pure nonblocking (and thus non-IE-throwing) "attempt" rather than lumping it into timed versions.

Implementations include Mutex Semaphore ReentrantMutex FIFOSemaphore, etc. Some implementations may throw IllegalStateExceptions in some cases for some methods.

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/Lock.html

The best interface for ReadWrite locks is return a pair of locks:

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/ReadWriteLock.html

And to support the standard implementations (writer-preference etc).

Back-port of Lock class capabilities to built-in locks

We'd like people to be able to get basic trylocks etc with builtin locks as well as Lock classes. We can express this with a Locks class, with methods that aren't exactly pretty, but get the job done. This is roughly analogous to java.util.Arrays, that provides collection-style functions for built-in arrays. It is also the right place to define the Condition factory method.

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/Locks.html

Even though this requires adding new capabilities to builtin locks inside JVMs, the implementations should be straightforward, so JVM builders ought not complain. Most (all?) underlying locking strategies involve some kind of nonblocking trylock anyway. The timeout version would be heavier and slightly tricky if implemented purely via posix, but not too hard.

Synchronization attributes

POSIX pthreads defines "attributes" for locks and condvars -- FIFO, Priority, etc. This approach fits in pretty well to Java too. While you cannot always control what attributes you get, you can at least know what they are. Among many other usages, this would allow people to make informative choices about using Lock classes only if builtin locks did not support required semantics.

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/SynchronizationAttributes.html

Queues

In my u.c, I called these "Channels", which is now a bad idea because of java.nio.Channel. Plus, it is nice to have a more concrete name. The main interface design issue is whether to separate bounded vs unbounded versions. Both kinds are equally needed. It is simplest to combine them into a single interface, with only two bits of awkardness: (1) capacity() must return a value (Long.MAX_VALUE is the only good choice) even for unbounded queues. (2) The "put" method must be declared to possibly block (hence throw IE) even though it never does so in unbounded versions.

Some care is needd in naming so that it will be possible (although not common) for people to create classes that implement both Queue and java.util.List, for implementations that can manipulate elements in the middle of the queue, not just the ends. Note however that these interfaces are intrinsically concurrent (thus thread-safe) since put() and take() block.

Since the target release is JDK1.5, and generics are slated to be in 1.5, Queue should be parametrized on element type. (Also some others below.) I'll ignore this for now.

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/Queue.html

Implementations include: LinkedQueue, BoundedArrayQueue (aka BoundedBuffer), HandOff (aka synchronous channel, CSP/Ada channel), PriorityQueue (also, BoundedPriorityQueue?), BoundedLinkedQueue.

Barriers

Barriers (multiway synch points) are very common in some circles (especially parallel programming), yet tricky to get right. The two most common flavors (CyclicBarriers and Exchangers) don't have much of an interface in common, and only have one standard implementation each, so maybe these should just be public classes rather than interfaces + implementations. On the other hand, I can image people wanting to implement fancier tree-based cyclic barriers on huge MPs someday, so maybe they deserve interfaces. For now, just classes though. These need a special exception type (BrokenBarrierException -- is there a better name?) that indicates that the barrier was aborted because some thread was interrupted.

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/CyclicBarrier.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/Exchanger.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/BrokenBarrierException.html

Executors

The main requirement is to provide a simple interface so that people can build custom thread-like subsystems -- especially thread pools, but also asynch-IO, lightweight task frameworks etc in which people shouldn't explicitly create threads in order to run asynchronous tasks. My u.c version defines execute to throw IE because it is usually right to fail if the thread spawning the task is interrupted. But this makes it asymmetrical with "new Thread(r).start()" which is what it is designed to replace, so should be dropped.

Executors are also the right place to standardize ways of calling threads that compute functions that return results via Futures. There are lots of Futures fans out there, it is simple to implement them once you have an Executor framework (all the mechanics can be done in an AbstractExecutor class), and it is worth standardizing conventions to avoid incompatibilities. I should have done it this way in u.c. Also, it is worth introducing a simple abstract Runnable implementation that contains a "done" bit so people don't keep reinventing this as well.

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/Executor.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/Callable.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/Future.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/AbstractExecutor.html

http://gee.cs.oswego.edu/dl/concurrent/java/util/concurrent/RunnableWithCompletionStatus.html

Implementations include:

ExecutionAttributes

By analogy with SynchronizationAttributes, and also in accord with posix pthreads, it seems like a good idea to explicitly represent various basic semantic (i.e., mainly scheduling) attributes of Executors. This requires some thought and discussion about whether to even do it.

Concurrent Collections

No new interfaces, but we will supply a few Collection implementations designed for use in multithreaded contexts. ConcurrentHashTable especially.

Thread class API review

Among other issues, we should discuss whether to tackle clean-up of interruption mechanics. The two main considerations are
Doug Lea