JavaMemoryModel: recap: concurrent reads

From: Doug Lea (dl@altair.cs.oswego.edu)
Date: Fri Dec 03 1999 - 09:06:59 EST


Here's an attempt to summarize the issues in the last week or so of
posts on related topics.

"Multiple reader parallelism", often associated with "concurrently
readable data structures" is a style of concurrent programming that
seems problematic for the proposed LC-based memory model. This is a
concern to me because it is the ONLY problem I know of with LC. In all
other respects, adopting an LC-based model seems to solve all known
problems with current JLS model in the best way I know.

The basic programming tactic here is:

  * All data are always kept in a consistent enough state so that
    they can be read at any time. If update(s) are in progress,
    a reader will see either data reflecting the state before
    one or more updates or after any one of them.

  * Reader threads are only loosely coupled to updater threads.
    There is no reason to synchronize a given read with any given
    update for the sake of serializion/exclusion. (In other words, you
    can tolerate certain data races.) However, there is still a need to
    guarantee that the results of the read operation reflect
    "recent" updates (see below).

  * Not only is synchronization on reads unnecessary, it is undesirable,
    for the sake of liveness and/or performance.

  * There are two variant strategies (and a range of intermediate
    options) for the implementing update operations: using full locking or
    using CAS-like optimistic techniques.

The main problem is:

  The proposed model does not have any analog of general read barriers
  (except for those tied to locks). On machines that need them, read
  barriers are used to make good on requirements for obtaining the most
  recent committed data values upon onset of the read operation,
  which is a semantically desirable way of defining recency.

This is not an everyday programming practice. The main people who use
it are people like me trying to create efficient libraries and
utilities at the java level, as well as people writing infrastructure
code -- I suspect that most MP VM developers use such techniques fairly
regularly (although surely in C, not Java).

Question 1: Is this kind of construction worth supporting at all?

  Against:
     * Accommodating it may complicate the memory model and/or the language.
     * Support may introduce additional opportunities for programming errors.
     * Concurrent readability is already assured for scalar volatiles.
       We should challenge people to create algorithms that can
       somehow live within existing constraints.
     * On some machines, these techniques are likely to be slower
       than use of lock-based algorithms. (However, they
       may still apply when the main goal is to preserve liveness by
       avoiding use of certain locks.)

  For:
     * Such algorithms would otherwise only be implementable via native code.
     * There is otherwise no hook for strongly ordered machines
       to optimize away the read barriers to improve performance.
     * Concurrent readability, and the presence of barrier
       instructions, is a defining property of shared memory
       multiprocessors.

If most people think the answer here should be no, we should probably
just drop it.

But if you think that the answer should be yes, the next question is how.
None of the known options is very attractive:

1. Mandating that any read of any volatile reference/array be
   preceeded by a memory barrier.

   Advantages:
     * No changes to the language.

   Disadvantages:
     * Adds unwanted overhead by disallowing implementation of
       reads via atomic instructions.
     * Complicates the memory model by adding operational
       restrictions that I don't offhand see how to even state within
       the proposed model.
     * Disables some other otherwise legal optimizations for
       volatiles.
     * Because "volatile" applies to all uses of a field, not
       just the places where a barrier is actually needed, this is
       less controllable, and potentially results in slower code than
       other options.

2. Introducing natively implmented barrier functions in JDK, as in:

   class java.lang.MemoryBarrier { // or in class System
     static void readBarrier();
   }

   (As mentioned before, you can add up to four flavors of
   barrier here.)

   Advantages:
     * Relatively low impact on the language.
     * At least some uses can be optimized to no-ops on some machines.

   Disadvantages:
     * Requires a change in java libraries, which will take a
       while to adopt and implement.
     * Adds unwanted overhead on uniprocessors.
     * Complicates the memory model by forcing it to take account
       of special library functions.
     * Complicates the rules for optimizing code.

   
3. Introduce "scoped volatiles" :

   volatile(anObject) {
     // reads/writes
   }

   Advantages:
     * The semantics seem to be readily definable within LC model.
     * Usages seem amenable to mechanical sanity checking.
     * Supports the most controllable and optimizable code of all
       options.

   Disadvantages:
     * A major language change. Even if adopted, it would probably
       take several years before you could write portable code employing it.

4. Scrap LC-based approach. If JLS approach is preserved, then
     synchronized(new Object() { ... }
   suffices here.

   Advantages:
     * At least it is somehow expressible.

   Disadvantages:
     * Relies on clever optimizers to reduce this construction
       down to either a read barrier or no-op.
     * Requires a different solution to all the problems with JLS
       approach that LC solves.

I'm still hoping that there are better undiscovered options.

-Doug
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



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