Below is one proposal for how to clarify or adjust some of the Java
semantics we have been discussing, so as to allow reasonable
implementation on machines with relaxed memory models. As previously
noted, the Alpha, PowerPC, and Merced memory models all allow
read-read reordering. Existing Alpha multiprocessors based on the
Alpha 21264 actually exploit this reordering, because they may delay
processing of invalidation requests.
We also describe a possible implementation on these types of machines.
These semantics also allow for reasonable implementation on machines
(such as Sparc or Pentium) with more strict memory models. See
Sanjay's message from earlier today for implementation details
relating to instruction coherency and more details on class
initialization.
1) The programmer should in general write programs without data races.
Accesses to shared object instances are guaranteed to be
consistent only in the absence of data races. Java does NOT
provide the proposed "initialization safety" in which readers of a
new object always see a fully initialized object, even without
synchronization. (Some people have proposed that this
initialization safety only applies for "immutable" objects.)
Implementation: Initialization code with data races in it must be
fixed by either adding full synchronization, or using #5 below.
2) However, type-safeness is maintained even in the presence of data
races between an object creator and a reader. If there are data
races, a thread may observe the object in an inconsistent state
and cause exceptions when using object data (as with any incorrect
program), but it will never gain improper access to objects or
methods.
Implementation: the garbage collector must guarantee that all
newly allocated objects have zeroes for their contents on all
processors. This may involve sending an interrupt to all
processors to force memory barriers after zeroing collected
memory, or may occur naturally if all threads are stopped and
resumed at GC time. A thread that accesses a new object without
synchronization may therefore unexpected null pointers and cause
NullPointerExceptions. It may also encounter a null method table
pointer, which should cause an exception as well (maybe something
like DataRaceException). In Bill Pugh's example of new arrays, an
array length of zero may be returned, which is not what the thread
is expecting, but does not violate type safety.
3) The Java Memory Model should be changed so that only writes occurring
between a lock and unlock are guaranteed to be performed before
the lock is released, and only reads between a lock and unlock are
guaranteed to be up-to-date (not stale) at the point of the lock
call.
Implementation: with this change, it is then possible to
completely eliminate synchronization, INCLUDING the memory
barrier, when all operations within the synchronization are known
to be on a non-shared object.
4) All threads must see class variables and class data structures
(such as method tables) in their initialized state.
Implementation: after a thread initializes a class (while holding
the class lock), it sends an interrupt to all processors that
forces the execution of a memory barrier. This is expensive, but
does not happen as often as object creation, and the interrupts
may potentially be combined for multiple class initializations.
5) One way to support the initialize-once idiom so that it is
reasonably efficient on all types of machines is to add a new
keyword 'sync' that qualifies variables. Any read of a 'sync'
variable acts as an acquire and any write of a 'sync' variable
acts as a release. If a reference to a newly constructed object
is stored in a sync variable, then other processors reading the
variable will be guaranteed to see the correct contents of the new
object.
Josh Bloch's example will work properly if we add the sync qualifier:
static sync String foo = null;
String getFoo() {
if (foo == null)
foo = new String(..whatever..);
return foo;
}
Implementation: a write of a 'sync' variable must be preceded by a
memory barrier and a read of a 'sync' variable must be followed by
a memory barrier. On machines which don't allow read-read
reordering, the memory barrier on the read side can be eliminated.
Dan Scales, Sanjay Ghemawat, Raymie Stata
Compaq WRL & SRC
p.s. As Sanjay noted in a posting on July 1st, the concept of "fresh
memory" is not a viable one for processors that do speculative
execution (all recent out-of-order processors) or hardware
prefetching. With these processor features, a processor may have a
stale version of a line in its cache, even if it has NEVER accessed
data in that line in its correct-path execution of a program. That is
why we do not use the idea of "fresh memory" in the implementations
above, but rather force all processors to execute memory barriers.
-------------------------------
This is the JavaMemoryModel mailing list, managed by Majordomo 1.94.4.
To send a message to the list, email JavaMemoryModel@cs.umd.edu
To send a request to the list, email majordomo@cs.umd.edu and put
your request in the body of the message (use the request "help" for help).
For more information, visit http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:16 EDT