JavaMemoryModel: Atomic classes (was: New function needed in java.lang.Thread?)

From: Doug Lea (dl@cs.oswego.edu)
Date: Thu Aug 23 2001 - 08:01:58 EDT


It's probably premature to mention this, but Josh Bloch and I plan to
introduce soon a new JSR that is a follow-up of sorts to JSR-133
(JMM), to address middle-level issues in concurrency support. These
may include changes to class Thread, possibly more flexible monitor
constructs, and official JDK versions of some of the common utilities
(queues, fancy locks, etc) found in my util.concurrent package. The
idea here is to fix things one layer at a time. With the JMM
solidified, it makes sense to move up (only!) one level.

I think that the proposed changes to class Thread about IDs and
isAlive probably belong in the Concurrency JSR. But there's one case
I'm less sure about, support for Atomic operations (compareAndSwap/CAS
etc). Because their semantics are closely tied to those of locks and
volatiles, I think there's a good argument for introducing them in
JSR-133. A secondary argument is that several people have suggested
these for inclusion in JSR-133 already, and want them to to appear
ASAP.

Here's a summary of my current thoughts on how to go about it. Reactions?

There are three ways I know to support atomic instructions in Java.
  1. Introduce javax.atomic.AtomicInt, AtomicReference, etc.
  2. Introduce methods relying on reflection to identify fields. As in:
       int cas(Field field, int oldval, int newVal)
     and then counting on the compiler to specially recognize it.
  3. Rely on compilers to specially recognize certain idioms
     and turn them into CAS's.

I think option (3) is out, because it can change visible semantics.
For example, holding a lock on an object would not block an attempt to
call a synch method that was converted to use CAS. So it would only be
legal in cases where the compiler could prove that this wouldn't
happen, which in the general case requires whole-program analysis.

Option (2) makes me very uncomfortable because it is so dependent on
quality of implementation, making it impossible for people to reason
even approximately about performance. I also worry (wrt GC etc) about
the consequences of anything that might introduce internal pointers
into objects. And I don't like the precedent of introducing
by-reference arguments in such a sleazy, statically uncheckable way,
in to-be-standard JDK classes.

Which leaves option (1), which has the advantage of lack of trickery.
Atomic classes would still need to be implemented "magically" within
JVMs, but even small interpretor-based JVMs could easily support them
using explicit private locks if they cannot use CAS, LL/SC. etc. But
it has some disadvantages: Introducing these as classes causes some
small overhead to indirect through an atomic variable rather than a
normal one. And makes it a little harder to retrofit -- you'd need to
redeclare scalar fields as AtomicX's. Also, extensions (probably via
sublassing) to support DCAS (atomic compareAndSwap of two different
fields, which is getting to be a very popular tool in nonblocking data
structure design) require deciding which of the pairwise types to
define. All possible pairings is too many.

Here's a mock-up of AtomicInt. Others would be similar

package javax.atomic; // or maybe just "javax.lang"

abstract class AtomicInt implements java.io.Serializable {

    /**
     * Factory method to create instance of underlying implementation.
     *
     */
    public static AtomicInt newAtomicInt(int initialValue) {
        return new AtomicIntImpl(initialValue); // some package-private impl
    }

    /**
     * Get the current value, with VOLATILE-ACQUIRE memory semantics.
     */
    public abstract int get();

    /**
     * Unconditionally set the current value.
     * Has VOLATILE-RELEASE memory semantics.
     */
    public abstract void set(int newValue);

    /**
     * Attempt to set the value to newValue only if it is currently oldValue.
     * This will always fail if another thread changes the value
     * to a different value between commencement and completion
     * of the attempted update, and MAY succeed otherwise.
     * If committed, the operation has VOLATILE-RELEASE semantics.
     *
     * Note:
     * This can be implemented using CAS or using locks in the
     * obvious way. It can be implemented using LL/SC via
     * if (LoadLLinked(&value) == oldValue)
     * StoreConditional(&value, newValue)
     *
     * @return new value if committed, else old value
     */
    public abstract int attemptUpdate(int oldValue, int newValue);

    /**
     * Behaviorally equivalent to:
     * <pre>
     * int v = get();
     * attemptUpdate(v, v+1);
     * </pre>
     *
     **/
    public abstract int attemptIncrememt();

    /**
     * Behaviorally equivalent to:
     * <pre>
     * int v = get();
     * attemptUpdate(v, v+k);
     * </pre>
     *
     **/
    public abstract int attemptAdd(int k);

   // maybe also method exchange(AtomicInt other);
}

-- 
Doug Lea, Computer Science Department, SUNY Oswego, Oswego, NY 13126 USA
dl@cs.oswego.edu 315-312-2688 FAX:315-312-5424 http://gee.cs.oswego.edu/  
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:34 EDT