I believe I have identified a major problem with CnC, what I might call the
smoking gun example. Bill agrees this is an issue, but we don't have
consensus on the severity of the implication yet. Here it is:
Example 1:
Initially everything is 0
Thread 1
r1 = A
if (r1 == 1)
B = 1
Thread 2
r2=B
if (r2 == 1)
A = 1
if (r2 == 0)
A = 1
Is r1 == r2 == 1 allowed?
Bill and Jeremy say this is allowed. So now consider how A=1 could have
occurred in this execution:
A=1 happens because r2==1, which happens because the read of B returned 1,
which happens because thread 1 wrote B=1, which happens because r1==1, which
happens because thread 1 read 1 for A, which happens because A=1. That is,
we caused A=1 to cause itself. This to me is a violation of any intuitive
notion of causality.
Suppose you say no, this isn't a violation of causality, because really, A=1
was going to happen anyway.
Ok, then consider a trivial variant of Example 1.
Example 2:
Thread 1
r1 = A
if (r1 == 1)
B = 1
Thread 2
r2=B
if (r2 == 1) {
A = 1
launch ICBM
}
if (r2 == 0)
A = 1
I don't think we can argue that r1 == r2 == 1 does not violate any intuitive
notion of causality.
I believe Bill's argument is going to be that this isn't their intuitive
notion of causality. I believe that once we give up on the above absolute
notion of causality, variants of SC- also guarantee other reasonable forms
of causality (including the one that I believe Bill is thinking about).
So where does that bring us:
I thought the biggest selling point of CnC was that it allowed programmers
to assume causality. I claim that isn't so for any reasonable intuition. On
the minus side, CnC is way too complex.
With SC-, the biggest problem was that it doesn't provide hb consistency and
causality. Please read the one pager at
http://www.cs.uiuc.edu/~sadve/JMM/sc-.pdf for variations of SC- that provide
hb consistency and various forms of causality (now that we aren't
constrained by absolute causality). In particular, the second variation
passes all five of Bill's causality tests so far.
The advantages of SC- are in its simplicity and close match with intuition
(SC everywhere other than data races, data races don't return out of thin
air values, the different versions constrain which values they can return).
As for which version of SC-to use, my preference is either SC-1 or SC-1 + hb
consistency. If people can't stomach allowing the result in causality test
5, then we can go to SC-2 with or without hb consistency. But we should wait
for all of this to sink in and for Bill to respond, before going further
into the pros and cons of different versions of SC-.
Sarita
-----------------------------------------------------------------------
Sarita Adve
Associate Professor
Department of Computer Science Email: sadve@cs.uiuc.edu
University of Illinois at Urbana-Champaign Office: 3302 DCL
1304 West Springfield Avenue Phone: 217-333-8461
Urbana, IL 61801-2987 Fax: 217-333-3501
WWW URL: http://www.cs.uiuc.edu/~sadve
-----------------------------------------------------------------------
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:49 EDT