Re: JavaMemoryModel: recap: concurrent reads

From: Adalberto Castelo (castelo@capsl.udel.edu)
Date: Mon Dec 13 1999 - 14:04:02 EST


Doug,

I've been following the Java list for a while, and I have a few comments
and questions on your most recent e-mail to the list ("recap: concurrent
reads").

You mentioned in that message that the proposed LC-based memory
consistency model "does not have any analog of general read barriers
(except for those tied to locks)". I am not sure what you mean with
the expression ``a read barrier not tied to lock''? Could you expand
on that? (BTW, the original LC document --- see the end of this mail
--- suggested ways to implement locks with the LC consistency related
operations).

I understand from your posts about volatile arrays that a read barrier
that is not associated with a lock would look like your example on the
post "volatile arrays":

class VolatileArray {

  private volatile int[] data;

  public VolatileArray(int cap) { data = new int[cap]; }

  public int get(int i) {
    int[] d = data;
    return d[i];
  }

  public void set(int i, int value) {
    int[] d = data;
    synchronized(d) { d[i] = value; }
  }
}

WRT the get method, you say that there's an implicit barrier, that
assures that the read of d[i] returns the most recent value written
(using your set method) to that position. Here's your explanation for
it, from that post:

  "the get() method will first perform a read barrier at "d = data",
   and so the d[i] returned is guaranteed to be no staler than the last
   committed write in set()".

But, isn't it the case that the volatile keyword applies only to the
reference of the array, and not to the elements? In other words, the
barrier created by the use of volatile applies to the array
reference. But, after the reference is read, when an element of the
array is accessed, its pomset will contain all the most recent written
values, and not only the last one committed to the memory.

Lets say that reads and writes on volatiles behave like the following:

acquire v
read/write v
release v

where v is volatile.

There will be a barrier when the get method executes "d = data", and
that
barrier will ensure that the set of most recent writes to data viewed by
this
read is always a singleton (remember, all accesses to data are made
inside an acquire/release pair).

There's one issue here: the location accessed in this way is that
which has the reference to the array. So, when doing return d[i], this
read refers to another position in the memory that was not sync'ed
here, i.e., an element of the array. The set of valid values to be
returned will contain the last write by the processor that has issued
this particular read, but it may also contain all writes done by any
other processors. The operations on the array reference and those on
the array elements should be in different pomsets. Therefore your
assumption of a read barrier for the array elements in the get method
doesn't seem to be correct.

If that's what you meant by read barriers not tied to locks, I have to
agree with you in that the LC model does not have any. And this leads to
my second point:

If the discussion is about whether to support or not to support this
kind of construction, my personal opinion is that the first three
points that you mentioned against it are very strong (refer to the
answer for Question 1 in the "recap: concurrent reads" message), and
should be followed. But, furthermore, it seems that the discussion
here somehow diverged from memory model issues, turning to what I
would call 'program model issues'. Isn't this issue related with the
mapping we should use from the language primitives to the memory
model? Or should we really incorporate this level of detail in the
memory model specification?

I recognize that it is not yet clear to me the boundary where the
specification of the memory model ends and the programming
model/language starts...

Adalberto

Note: a set of rules for memory operations in LC can be found in these
papers:
ACAPS TM-78 (1994)
ftp://ftp.capsl.udel.edu/pub/doc/acaps/memos/memo78.ps.gz
CAPSL TM-16 (1998) ftp://ftp.capsl.udel.edu/pub/doc/memos/memo016.ps.gz

-- 
Adalberto Castelo
Ph.D. Student - CAPSL
140 Evans Hall
Newark, DE 19716
302-831-2571
http://www.capsl.udel.edu/~castelo
-------------------------------
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