I'm going to assume that in all reasonable semantics for volatile,
volatile variables exhibit the following behaviors:
- Total store order (TSO) : it is impossible to reorder two memory
accesses on distinct volatile variables except for the case tested in
V6.
- Coherence : it is impossible to reorder two memory access of the
same volatile variable
A couple of litmus tests. I believe that proposals for volatile
variables can largely be broken down based on which of these tests
they pass?
I use the following class in some of these examples:
class Node {
int x;
Node next;
}
V1
// Does a volatile read always have to be done from main memory?
Initially:
volatile boolean a = false;
Thread 1:
a = true;
Thread 2:
while (!a);
Question: Is it possible that thread 2 will never terminate?
V2
// Can a write of a volatile and a following read of a different volatile
// variable be reordered? (E.g., can we write Dekker's algorithm?)
Initially:
volatile boolean a = false;
volatile boolean b = false;
Thread 1:
a = true
boolean tmp1 = b;
Thread 2:
b = true;
boolean tmp2 = a;
Question: Is it possible that tmp1 == false && tmp2 == false?
V3
// Does volatile guarantee fresh values for direct contents of referenced
// object?
Initially:
volatile Node p;
Thread 1:
Node tmp1 = new Node()
tmp1.x = 1;
p = tmp1;
Thread 2:
Node tmp2 = p;
int tmp3 = tmp2.x;
Question: Is it possible that thread 2 gets a value of 0 in tmp3?
V4
// Does volatile guarantee fresh values for direct contents of referenced
// object even if referenced through a different name?
Initially:
volatile Node p;
volatile Node q;
Thread 1:
Node tmp1 = new Node();
q = tmp1;
tmp1.x = 1;
p = tmp1;
Thread 2:
Node tmp2 = p;
int tmp3 = q.x;
Question: Is it possible that thread 2 gets a value of 0 in tmp3?
V5
// Does volatile guarantee fresh values for direct contents of
referenced object
// through multiple levels of indirection?
Initially:
volatile Node p;
Thread 1:
Node tmp1 = new Node();
Node tmp2 = new Node();
tmp1.next = tmp2;
tmp2.x = 1;
p = tmp1;
Thread 2:
int tmp3 = p.next.x;
Question: Is it possible that thread 2 gets a value of 0 in tmp3?
V6
// Does a volatile variable guard unrelated fields?
Initially:
boolean a = false;
volatile boolean b = false;
Thread 1:
a = true
b = true
Thread 2:
while (!b);
boolean tmp = a;
Question: Is it possible that thread 2 gets a value of false in tmp?
Commentary:
When I say that a rule/feature/semantics enforces Vx, I mean that it
guarantees a false answer to Vx.
Assuming that a read of a volatile variable acts as an acquire and a
write to a volatile variable acts as a release enforces TSO order and
V3 - V6.
Maessen, Arvind and Shen have a proposal that, I believe, enforce
V1-V4, but not V5 - V6.
ftp://csg-ftp.lcs.mit.edu/pub/papers/csgmemo/memo-428.ps.gz
I believe that it would be desirable to enforce at least V1 and V3 -
V6. I have some reservations about V2, because it will require
additional memory barriers on a number of processors. However, in the
interests of having a "simple memory model for the masses", I think
we should probably enforce V2 as well.
Overall, I would like to have the following semantics
* volatiles variables always go directly to memory
* access to volatile variables are sequentially consistent
* reads of volatile variables act as acquires matching
releases by other threads writing to that same volatile variable
This is simple enough, and powerful enough so that many
synchronization problems can be fixed by simply declaring a variable
volatile.
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:24 EDT