Re: JavaMemoryModel: volatile arrays

From: David F. Bacon (dfb@watson.ibm.com)
Date: Fri Dec 03 1999 - 12:01:23 EST


> Accesses to different volatiles require sequential consistency to be
> enforced

where in the JMM does it say that?

> thus using atomic load/store ops to access them is only valid if
> that sequential consistency is maintained. Given that many atomic ops have
> no inherent memory barriers this implies that either memory barriers are
> needed in addition to the atomic ops or else the use of atomic ops on the
> architecture at hand acts as if memory barriers were used anyway. Thus
> using memory barriers instead of atomic ops is at worst as expensive and at
> best may be cheaper ;-)

let's assume that accesses to volatiles must be SC wrt each other. i still
don't understand why you would need the read barrier.

it would certainly be possible for a machine to execute two independent CAS
instructions out of order. but to implement volatiles, you need to test that
you in fact performed an atomic read. on powerpc, you perform

  lwarx r2, 0, r1 ; load word and reserve for volatile pointed to by r1
  stwcx. r2, 0, r1 ; store word conditionally, just replacing with same value
  bne .-8 ; if atomicity failure, retry

the branch creates a control dependence, so subsequent reads of other volatile
variables will be dependent on this read being successful. so we only have a
problem if (1) the processor is speculating across branches and (2) it is
performing reservations in parallel. i believe current powerpc processors only
have one reservation station, so i don't think this is an issue at all on
current hardware.

however, let's assume that the processor is performing both (1) and (2). then
for there to be a problem, some processor A is atomically reading volatiles X
and then Y, while some other processor B is "concurrently" accessing Y and then
X, with at least one access being a write (if they're all reads, there's no
issue). let's assume both operations by B are writes.

processor A will load and reserve the locations X and Y, but the reservation on
Y is dependent on the subsequent store of X succeeding and the branch falling
through. processor B will be similarly constrained: it can not commit its
operation on Y until the operation on X has succeeded. to violate SC,
processor A would have to be able to observe a "new" X and an "old" Y.

to successfully read the new X written by B, A's reservation must occur
strictly after B's conditional store of X succeeded (otherwise A's conditional
store would fail). for A to read the old Y, the reservation and the store must
occur strictly before B's successful store of Y. but the store of Y by A can
not commit until the store of X by A has committed, so the store of Y by A is
strictly afte rthe store of X by A, which is strictly after the store of X by
B. therefore, if the load of Y by A occurred before the store of Y by B, B's
store would cancel A's reservation on Y. therefore, A can't read B's writes
out of order.

so i think you can implement volatiles this way, even if they must be
sequentially consistent with respect to each other. or am i missing something
else?

david
-------------------------------
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