RE: JavaMemoryModel: Question about implementation of java.util.concurrent.ConcurrentHashMap

From: Evan Ireland (eireland@sybase.com)
Date: Thu Nov 13 2003 - 16:41:28 EST


Jeremy,

Suppose we have two statements executed by a thread:

    (1) x.f = a; (f is non-volatile, x is known not to be null)
    (2) y.v = b; (v is volatile field, y is known not to be null)

If statement (1) is executed before statement (2), then (1) hb (2),
and thereby any thread subsequently reading y.v should be certain of
seeing the modified value of x.f. I agree that this is implied by the
happens-before rules.

However, if statement (2) is executed before statement (1), due to
reordering, then visibility of the modified value of x.f seems not
to be assured by the happens-before rules.

The relevant parts of the document which might help us determine
if statement (2) can be executed before statement (1) seem to be:

  Program Order

  Among all the inter-thread actions performed by each thread t, the
  program order of t is a total order that re ects the order in which
  these actions would be performed according to the intra-thread semantics
of t.

  Intra-thread semantics

  Intra-thread semantics are the standard semantics for single threaded
programs,
  and allow the complete prediction of the behavior of a thread based on the
  values seen by read actions within the thread. To determine if the actions
of
  thread t in an execution are legal, we simply evaluate the implementation
of
  thread t as would be performed in a single threaded context, as defined in
the
  remainder of the Java Language Specification.

  Happens-Before Edges

  ... If x and y are actions of the same thread and x comes before y in
      program order, then x hb y.

The difficulty I am having is that I can't find any language in the
community draft 2 JMM or JLS documents which specify that performing
statement (2) before statement (1) would violate intra-thread
semantics, thereby ( (1) hb (2) ) might not be true (in this case),
thereby visibility of non-volatile field changes made before volatile
write might not be certain (in the general case).

It still seems that this may be a matter of the intentions not being
backed up by the formalism, which would be a real problem when we are
trying to get the model right this time.

But, I am a complete novice in this area and may have missed something
that is painfully obvious to other readers of the JMM / JLS specs :-)

> -----Original Message-----
> From: owner-javamemorymodel@cs.umd.edu
> [mailto:owner-javamemorymodel@cs.umd.edu]On Behalf Of Jeremy Manson
> Sent: Friday, 14 November 2003 9:18 a.m.
> To: eireland@sybase.com
> Cc: Bill Pugh; Java Memory Model
> Subject: Re: JavaMemoryModel: Question about implementation of
> java.util.concurrent.ConcurrentHashMap
>
>
> > Bill (and others),
> >
> > You wrote:
> >
> > "In general, a JVM is not allowed to reorder a volatile
> write with any
> > > preceding accesses to shared memory."
> >
> > Although I found reference to this in the JMM archives, I could not
> > find this statement in the community review 2 JMM document.
> >
> > Is it unintentionally missing from the document?
>
> It isn't a hard and fast rule. It is simply implied by the fact that all
> the actions before a volatile write have to be visible to any actions
> following a subsequent volatile read on the same variable; this is implied
> by the happens-before rules.
>
> So, for example, you can do the reordering if no other thread ever reads
> that volatile. Or if they read the volatile, but never see any
> results of
> the access being reordered.
>
> Jeremy
> -------------------------------
> JavaMemoryModel mailing list -
> http://www.cs.umd.edu/~pugh/java/memoryModel
>

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



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