We had discussed the implementation of non-atomic volatile writes,
and come up with a design within the Java version of the simulator,
but it hadn't made it into the paper or the Haskell simulator. This
goes back to the 7/18/01 discussion on the mailing list.
We are working on putting it into both the paper and the Haskell
simulator. But I want to go over the features we have.
The basic property we have is that we don't impose a total order over
all volatile writes. Instead, we relax it by saying that if two
threads perform volatile writes to two different variables, then
other observer threads can see those writes in different orders.
However, if two threads write to the same variable, or if one thread
writes to two variables, then those writes are totally ordered and
are seen in that order by any reads.
EXAMPLE 1: non-atomic volatile writes
Initially, a = b = 0 (both a and b are volatile)
Thread 1:
a = 1
Thread 2:
b = 1
Thread 3:
w = a
x = b
Thread 4:
y = b
z = a
Because writes are non-atomic, this can result in w = y = 1 and x = z
= 0. In other words, to thread 3, it looks like the write to a was
performed before the write to b, and to thread 4, it looks like the
write to b was performed before the write to a.
This can happen in our semantics by having the writes in thread 1 and
2 both partially complete, and then allowing threads 3 and 4 to
execute.
EXAMPLE 2: volatile writes to any particular variable are atomic and
totally ordered
Initially, a = 0 (a is volatile)
Thread 1:
a = 1
Thread 2:
a = 2
Thread 3:
w = a
x = a
Thread 4:
y = a
z = a
It must not be possible for this fragment to result in w = 1 and x =
2 (in other words, thread 3 thinks a = 1 occurred first) and y = 2
and z = 1 (in other words, thread 4 thinks a = 2 occurred first).
The basic idea to how we have incorporated this in our semantics is
that a volatile write is a 2-part operation. After the first part,
other threads can see either the new or old value. Once a thread has
seen the new value of a partially completed volatile write, that
thread can no longer see the old value. Once the volatile write is
complete, only the new value is visible. While one thread has
partially completed a write to a particular volatile variable v, no
other thread may start a write to that same variable until the
partially completed write completes.
Comments?
Bill
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:36 EDT