> I wanted to apply the rules of "Semantics of Multithreaded Java" and the
> rules of "Improving the Java Memory Model Using CRF" to the idiom of
> optimistic reading, discussed in our OOPSLA paper "Guava: A Dialect of Java
> Without Data Races" (Bacon/Strom/Tarafdar)
Maybe it is worth asking a different set of questions: What techniques
that achieve the same sorts of effects DO work under current JMM
proposal? Do they suffice? If not, what can be done?
I'll start with one that works for sure: Encapsulate sets of values as
final fields of objects, pointed to by a volatile reference, and
then use pointer-swaps. For example, instead of:
> Writer thread:
> volatile v;
> /* Assume for this example that
> the first write has already begun, with v=1, a=any, b=any */
> ...
> a = 2;
> b = 3;
> v++;
> ... /* other operations between first and second write */
> v++;
> a=5;
> b=7;
> v++;
>
> Reader thread:
> t1 = v;
> x = a;
> y = b;
> r = a*b;
> t2 = v;
> if (t1 == t2 && t1%2 == 0) return(r);
> else /* redo */
Do
class Values
final int a;
final int b;
Values (int x, int y) { a = x; b = y; }
}
// ...
static volatile Values values = new Values(any, any);
Writer Thread:
...
values = new Values(2, 3);
... /* other operations between first and second write */
values = new Values(5, 7);
Reader thread:
Values v = values;
x = v.a;
y = v.b;
v = values;
nextx = v.a;
nexty = v.b;
...
This is not strictly an optimistic technique, but the natural
extension to handle updates involving both reads and writes is.
For example:
Update thread:
for (;;) {
Values v = values;
Values newv = new Values(v.a+17, v.b+23);
boolean success = false;
synchronized(someSharedlock) { // simulate CAS
if (values == v) {
values = newv;
success = true;
}
}
if (success) break;
}
The disadvantages compared to even-counter technique are:
1) It can generate a lot of garbage
2) It doesn't directly accommodate arbitrary sets of values -- you
must place all values of interest in a class.
I'm not convinced that (1) is a liability on SMPs with high
performance GC. (For example, my fork/join stuff generates massive
amounts of garbage, and still sometimes beats C frameworks that
don't.)
Problem (2) can be a major nuisance when you want to read fields that
would otherwise appear in several different classes. This is very
reminiscent of arguments for the use of generalized transactional
memory, Multi-word CAS (BTW, see some recent TRs on this by some
people on this list at http://www.sun.com/research/jtech/pubs/) and so
on. Further out, it is the basis for classic transaction systems.
I do agree that there are cases where, if nothing else, code is
massively simpler to write if you can lump together updates of an
arbitrary bunch of fields from possibly many objects. Even so,
ideally, it would be much nicer to somehow provide generalized
optimistic transactional memory constructs in a language rather than
to insist that any particular technique like the even-counter trick
works. Not that I even know where to start on this. Do you?
-- Doug Lea, Computer Science Department, SUNY Oswego, Oswego, NY 13126 USA dl@cs.oswego.edu 315-341-2688 FAX:315-341-5424 http://gee.cs.oswego.edu/ ------------------------------- JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:28 EDT