Re: JavaMemoryModel: Idiom for safe, unsynchronized reads

From: William Pugh (pugh@cs.umd.edu)
Date: Sat Jun 26 1999 - 21:56:58 EDT


> > Provide a synchronization idiom that provides a safe way for a thread
> > to construct an object, perform a series of updates on the object,
> > and then publish the object (store a reference to the object in memory
> > read by other threads). Other threads should then be able to read that
> > reference and see an object that reflects all of the modifications.
>
>I cannot see how this can be implemented efficiently. The discussion so
>far has focused on putting memory barriers on the writer's side (the writer
>being the thread initializing and object). However, correct
>synchronization requires memory barriers by both the writer _and_ the
>readers (the readers being the "other threads" that, according to the quote
>above, "should be able to read that reference and see an object that
>reflects all of the modifications"). How can reader-side barriers be put
>in place efficiently?

Thanks for the note. Glad to see that other people have been thinking
about this problem.

The list of requirements I proposed is, in my opinion, a desired set
of requirements. If an efficient way to implement them cannot be
devised, then we may have to reconsider (although Josh may have a
different opinion :-) ).

It obviously isn't much of a problem to prevent the compiler from
reordering the reads. For the compiler to reorder the reads would be
a pretty good trick, beyond most existing compiler transformations
(although there is some work on value-prediction that may need to
take this into account).

So which processor models might reorder two reads, when the address
loaded by the second is determined by the value loaded by the first?
I looked over the Sparc RMO description and was pretty sure that it
couldn't. How about the Alpha?

Next, if we _are_ stuck with a processor that might reorder the
reads, we are going to have other problems. We can avoid problems
with seeing garbage in reference fields by allocating objects out of
pre-zeroed memory. However, what about the object header (things like
the class/vtbl pointer)? If we invoke a virtual method on a object
that is freshly allocated by another thread, it is possible we would
see a stale, null entry for the vtbl.

Now, it might be possible to program around that. We would need to
generate code to catch null-pointer exceptions caused by
dereferencing a null vtbl, reload the vtbl, and resume execution.
But sounds like a big pain. We also have to worry about all the other
components of the object header for which we might see stale,
uninitialized values.

I know some of the processor architecture people are thinking very
aggressively about memory models. But if they relax this constraint
(without providing an efficient way to selectively enforce it), I
don't see how it will be possible to implement a safe object oriented
language on that platform.

If it turns out that this is a real problem, then we will need to
find a way to enforce the constraints. Enforcing it for object
headers should also largely handle it for object fields. The naive
solution would be to put a memory barrier after each load of a
reference. But we could probably do much better (at get at least one
paper out of doing so). You only need to ensure that there exists a
memory barrier between the load of a reference and the first
examination of the header or a field of that object. You could
probably do a lot of things with coalescing memory barriers.

        Bill Pugh

-------------------------------
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:12 EDT