RE: JavaMemoryModel: Question about the semantics of volatile

From: Sarita Adve (sadve@cs.uiuc.edu)
Date: Thu Mar 18 2004 - 00:40:39 EST


I was very, very surprised to read that Pete said Treadmarks obeys the
stronger interpretation. So I sent an email to the rest of the Treadmarks
group. That conversation is still going on, but I wanted to send an update
of the confirmation received so far.

Sandhya Dwarkadas (key post-doc on the project then and on the faculty at
Rochester now) confirmed that Treadmarks does not support programs that
allow concurrent synchronization writes to the same variable. Based on this
confirmation, Bill's example is an illegal program for Treadmarks, and there
is no distinction between the stronger and weaker interpretations for
programs allowed by Treadmarks!

My only explanation of Pete's response (and this is mere speculation) is
that he looked at Bill's example, tried to think about what Treadmarks might
do if it did run that example, and then (correctly) concluded that the
behavior would not be allowed. The catch is that the obvious extension of
Treadmarks for this program would not allow this behavior for either the
strong or the weak interpretation!

The reason Treadmarks wouldn't allow the behavior with the weak
interpretation is that lacking a happens-before relationship between the two
threads, it is not obligated to propagate any updates between threads. So it
would not see r1==r3==1. But neither would it see r1==1, r3==0, nor would it
see r1==0, r3==1. It would only see r1==r3==0!

I believe an example more meaningful in the Treadmarks context is the one
below (flips the read and write in Bill's example):

Initially, X = Y = S = 0.
S is a synchronization variable.

Thread 1:
X = 1
S = 0
r1 = S
r2 = Y

Thread 2:
Y = 1
S = 0
r3 = S
r4 = X

The question is whether the behavior r2 == r4 == 0 is possible?

I have sent this example to Sandhya and others and will report back when I
hear from them. Regardless of what they say, one thing to take back from
here is that this is a rather subtle issue!

Sarita

> -----Original Message-----
> From: owner-javamemorymodel@cs.umd.edu
> [mailto:owner-javamemorymodel@cs.umd.edu] On Behalf Of Bill Pugh
> Sent: Wednesday, March 17, 2004 4:07 PM
> To: Bill Pugh
> Cc: javamemorymodel-cs.umd.edu
> Subject: Re: JavaMemoryModel: Question about the semantics of volatile
>
>
> I corresponded with Pete Keleher (Lazy Release Consistency,
> Treadmarks, Software DSM guy).
>
> He said that Treadmarks (which is a software DSM system)
> implements the strong interpretation, so choosing the
> strong interpretation wouldn't make it any harder to
> implement Java on top of Treadmarks (which doesn't mean
> it will be easy).
>
> Bill
>
> -------------------------------
> JavaMemoryModel mailing list -
> http://www.cs.umd.edu/~pugh/java/memoryModel
>

-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:01:00 EDT