concurrency puzzle

classic Classic list List threaded Threaded
39 messages Options
12
Reply | Threaded
Open this post in threaded view
|

concurrency puzzle

alarmnummer
I'm playing with the Java Memory Model documentation. And to check if
my understanding is correct, I'm interested in the following example:

public class A{
   private int x = 10;

   public void foo(){
      x = 20;
      synchronized(this){
         System.out.println( x );
      }
   }
}

If this class is used in a multithreaded environment, what could the
output be? (foo is called only once to make it easy)

20: if the x=20 is written to main memory, the read for println( x )
will return 20.

10: if x=20 isn't written to main memory, but only in local memory,
the write (x=20) could get lost. This is because the local memory is
invalidated when the lock on this is acquired. When x is read for the
println, it will return the value in main memory (and that is 10).

0: the 10 value doesn't need to be visible in main memory because it
isn't published safely. So for the same reasons 10 could be read for
the println, the default value for int (that is a 0) could be read for
the println.

0: a different thread could obtain a partially initialized reference
to A because of reordening. So 0 could be the value of x when it is
read for the println statement. So this is another way the 0 value
could be found.

So my bet would be

20 or 10 or 0.

Is my understanding correct?
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

Jeremy Manson-2
I'm not sure what you mean by multithreaded environment, because all
Java code runs in a multithreaded environment.  If the object is
constructed and foo() runs in a single thread, this program will print
20.  This is because the write to 20 is the last write to x that
happens-before the print.  If another thread sneaks in a write to x,
then it might print something else, but there is no other thread in this
example.

If, on the other hand, you are worried about the case where one thread
constructs the object and passes it to another thread via a data race:

Thread 1:
global.a = new A();

Thread 2:
if (global.a != null)
   global.a.foo();

Then it will either print 20 or 10.  It can't print 0 because the write
of the default value (conceptually) happens-before the first action of
every thread.  This means that Thread 2's write of 20 to x will
overwrite the value of 0.

This can be avoided by making global.a volatile, although you still
might get a NullPointerException in Thread 2.

I'm not sure which JMM documentation you have been examining, if it
talks about local memory and invalidation.  The old one had kind-of a
notion of local memory, but it hasn't been the "active" JMM for a good
while.  Certainly, that JMM didn't talk about safe publication.

And speaking of safe publication - the write of 10 to x happens in the
constructor, according to the semantics of the Java programming
language.  If it were a final field (which is where the notion of safe
publication is important), then it would be considered to be published
safely, unless a reference to the object escapes an otherwise-unseen
constructor.

Now, a /different/ thread could see 0 or 10 or 20 for x:

Thread 1:
global.a = new A();
global.a.foo();

Thread 2:
r1 = global.a.x;

r1 can be 0, 10 or 20

It can avoid this by synchronizing properly.

                                        Jeremy

Peter Veentjer wrote:

> I'm playing with the Java Memory Model documentation. And to check if
> my understanding is correct, I'm interested in the following example:
>
> public class A{
>    private int x = 10;
>
>    public void foo(){
>       x = 20;
>       synchronized(this){
>          System.out.println( x );
>       }
>    }
> }
>
> If this class is used in a multithreaded environment, what could the
> output be? (foo is called only once to make it easy)
>
> 20: if the x=20 is written to main memory, the read for println( x )
> will return 20.
>
> 10: if x=20 isn't written to main memory, but only in local memory,
> the write (x=20) could get lost. This is because the local memory is
> invalidated when the lock on this is acquired. When x is read for the
> println, it will return the value in main memory (and that is 10).
>
> 0: the 10 value doesn't need to be visible in main memory because it
> isn't published safely. So for the same reasons 10 could be read for
> the println, the default value for int (that is a 0) could be read for
> the println.
>
> 0: a different thread could obtain a partially initialized reference
> to A because of reordening. So 0 could be the value of x when it is
> read for the println statement. So this is another way the 0 value
> could be found.
>
> So my bet would be
>
> 20 or 10 or 0.
>
> Is my understanding correct?
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

alarmnummer
On 9/10/06, Jeremy Manson <[hidden email]> wrote:
> I'm not sure what you mean by multithreaded environment, because all
> Java code runs in a multithreaded environment.

True. But I mean that the object is used by multiple threads.

> Then it will either print 20 or 10.  It can't print 0 because the write
> of the default value (conceptually) happens-before the first action of
> every thread.
I was not sure about this one. I thought the following would happen
1) a stackframe is allocated with all defaults for the fields (x=0)
2) the initilization for the fields is called (so the x=10)
3) constructor call

I have been looking through the documentation, but the initialisation
(x=10) felt the same as a constructor.

So there is a difference between:

public class A{
    private int a;
    public A(){
       a = 10;
    }
    ...
}

and

public class A{
    private int a = 10;
    ...
}

Is there a difference?

> This can be avoided by making global.a volatile, although you still
> might get a NullPointerException in Thread 2.
I know, but I'm trying to understand what is allowed by the JMM.

> I'm not sure which JMM documentation you have been examining, if it
> talks about local memory and invalidation.  The old one had kind-of a
> notion of local memory, but it hasn't been the "active" JMM for a good
> while.  Certainly, that JMM didn't talk about safe publication.
JSR133, JCIP and Concurrent and Realtime programming in Java.

> And speaking of safe publication - the write of 10 to x happens in the
> constructor, according to the semantics of the Java programming
> language.  If it were a final field (which is where the notion of safe
> publication is important), then it would be considered to be published
> safely, unless a reference to the object escapes an otherwise-unseen
> constructor.
Instruction reordering makes it possible to see a partially constructed object

reg = alloc(A)
reg.x=10
global.a = reg

This could be reordened to:

reg = alloc(A)
global.a = reg
reg.x=10

If another thread picks up a and calls foo before the ref.x=10 is
called, the println could see a zero.

> It can avoid this by synchronizing properly.
Ofcourse... but I'm trying to understand what can happen if programs
are not synchronized propertly. I want to understand how the JMM works
and that is why I made up this example.

>
>                                         Jeremy

Thanks for your reply.

>
> Peter Veentjer wrote:
> > I'm playing with the Java Memory Model documentation. And to check if
> > my understanding is correct, I'm interested in the following example:
> >
> > public class A{
> >    private int x = 10;
> >
> >    public void foo(){
> >       x = 20;
> >       synchronized(this){
> >          System.out.println( x );
> >       }
> >    }
> > }
> >
> > If this class is used in a multithreaded environment, what could the
> > output be? (foo is called only once to make it easy)
> >
> > 20: if the x=20 is written to main memory, the read for println( x )
> > will return 20.
> >
> > 10: if x=20 isn't written to main memory, but only in local memory,
> > the write (x=20) could get lost. This is because the local memory is
> > invalidated when the lock on this is acquired. When x is read for the
> > println, it will return the value in main memory (and that is 10).
> >
> > 0: the 10 value doesn't need to be visible in main memory because it
> > isn't published safely. So for the same reasons 10 could be read for
> > the println, the default value for int (that is a 0) could be read for
> > the println.
> >
> > 0: a different thread could obtain a partially initialized reference
> > to A because of reordening. So 0 could be the value of x when it is
> > read for the println statement. So this is another way the 0 value
> > could be found.
> >
> > So my bet would be
> >
> > 20 or 10 or 0.
> >
> > Is my understanding correct?
> > _______________________________________________
> > Concurrency-interest mailing list
> > [hidden email]
> > http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

Jeremy Manson-2
Peter Veentjer wrote:
> On 9/10/06, Jeremy Manson <[hidden email]> wrote:
>> Then it will either print 20 or 10.  It can't print 0 because the write
>> of the default value (conceptually) happens-before the first action of
>> every thread.
> I was not sure about this one. I thought the following would happen
> 1) a stackframe is allocated with all defaults for the fields (x=0)
> 2) the initilization for the fields is called (so the x=10)
> 3) constructor call

[snip]

 > I have been looking through the documentation, but the initialisation
 > (x=10) felt the same as a constructor.

The initialization is the same as the constructor.  If you look at the
bytecode generated by javac, you will see that field initializers
actually occur in the object's constructor.  That was what I meant in my
previous message, when I said, "the write of 10 to x happens in the
constructor, according to the semantics of the Java programming
language".

Having said that, the fact that print() can't write out 0 has nothing to
do with the constructing thread.  Basically, there is a conceptual write
of 0 to x that happens-before every other action in the program, at "The
Dawn of Time" (this corresponds to the GC zeroing out memory).  Your
program can be abstracted in the following way:

"The Dawn of Time":
// zeroes out all memory, including:
f.x = 0;

Thread 1:
// The dawn of time happens-before this:
f.x = 10;
global.a = f;

Thread 2:
// The dawn of time happens-before this:
g = global.a;
g.x = 20;
print(g.x);

The execution engine for Thread 2 will know that the write of 20 has
overwritten the write of 0, because it knows that the write of 0
occurred at the dawn of time.  It won't print 0.

What you said about Thread 1 is true in general, though: the accesses in
Thread 1 can be reordered, so that the write to f.x may not be visible
to Thread 2 when it performs its print.

I hope that is a little clearer than my last message.  It is longer, any
way.  :)

>> I'm not sure which JMM documentation you have been examining, if it
>> talks about local memory and invalidation.  The old one had kind-of a
>> notion of local memory, but it hasn't been the "active" JMM for a good
>> while.  Certainly, that JMM didn't talk about safe publication.
> JSR133, JCIP and Concurrent and Realtime programming in Java.

JSR 133, which is the official definition, doesn't make mention of local
memory or invalidation.  If JCiP does (I don't remember), it is only to
explain the concepts of the official memory model.


> Instruction reordering makes it possible to see a partially constructed
> object

Yes.  This is why there are additional semantics for final fields.  If x
were final, even though there would be no write of 20, it would be
impossible for Thread 2 to print 0.   This is because the correctly
constructed value of the final field is guaranteed to be seen regardless
of data races, cache effects and instruction reordering.

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

alarmnummer
  That was what I meant in my
> previous message, when I said, "the write of 10 to x happens in the
> constructor, according to the semantics of the Java programming
> language".
If A was used by a single thread, this would be the case. But if A is
used by multiple threads I'm not sure. This is the reason why double
checked locking doesn't work for example:

Let me create another example:

class B{
   private int y = 10;

  public void print(){
       System.out.println(y);
  }
}

What do you expect for output (if an instance of B also is used by
different threads)

I would say 0 or 10.

Maybe we can get this issue out of the way because I think it is the
cause misunderstanding.


>
> Having said that, the fact that print() can't write out 0 has nothing to
> do with the constructing thread.  Basically, there is a conceptual write
> of 0 to x that happens-before every other action in the program, at "The
> Dawn of Time" (this corresponds to the GC zeroing out memory).  Your
> program can be abstracted in the following way:
>
> "The Dawn of Time":
> // zeroes out all memory, including:
> f.x = 0;
>
> Thread 1:
> // The dawn of time happens-before this:
> f.x = 10;
> global.a = f;
>
> Thread 2:
> // The dawn of time happens-before this:
> g = global.a;
> g.x = 20;
> print(g.x);
>
> The execution engine for Thread 2 will know that the write of 20 has
> overwritten the write of 0, because it knows that the write of 0
> occurred at the dawn of time.  It won't print 0.
>
> What you said about Thread 1 is true in general, though: the accesses in
> Thread 1 can be reordered, so that the write to f.x may not be visible
> to Thread 2 when it performs its print.
>
> I hope that is a little clearer than my last message.  It is longer, any
> way.  :)
>
> >> I'm not sure which JMM documentation you have been examining, if it
> >> talks about local memory and invalidation.  The old one had kind-of a
> >> notion of local memory, but it hasn't been the "active" JMM for a good
> >> while.  Certainly, that JMM didn't talk about safe publication.
> > JSR133, JCIP and Concurrent and Realtime programming in Java.
>
> JSR 133, which is the official definition, doesn't make mention of local
> memory or invalidation.  If JCiP does (I don't remember), it is only to
> explain the concepts of the official memory model.
>
>
> > Instruction reordering makes it possible to see a partially constructed
> > object
>
> Yes.  This is why there are additional semantics for final fields.  If x
> were final, even though there would be no write of 20, it would be
> impossible for Thread 2 to print 0.   This is because the correctly
> constructed value of the final field is guaranteed to be seen regardless
> of data races, cache effects and instruction reordering.
>
>                                         Jeremy
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

Jeremy Manson-2
Peter Veentjer wrote:
>  That was what I meant in my
>> previous message, when I said, "the write of 10 to x happens in the
>> constructor, according to the semantics of the Java programming
>> language".
> If A was used by a single thread, this would be the case. But if A is
> used by multiple threads I'm not sure. This is the reason why double
> checked locking doesn't work for example:

We must be having some crossed communication lines somewhere, because I
don't think we are talking about the same thing.  All I meant by the
above was that this:

class A {
   int x = 10;
}

is the same as this:

class A {
   int x;
   public A() {
     x = 10;
   }
}

All javac does with the first is to turn it into the second.  It is
relatively clear that this is the intention of the JLS, if you read
Section 8.3.2.  It is what we intended when we wrote JSR-133.

None of this has anything to do with double-checked locking, which won't
work regardless of whether the singleton object is constructed with its
fields assigned in variable initializers or in a constructor.

So I'm pretty sure I'm not quite getting what you are saying.

> Let me create another example:
>
> class B{
>   private int y = 10;
>
>  public void print(){
>       System.out.println(y);
>  }
> }
>
> What do you expect for output (if an instance of B also is used by
> different threads)
>
> I would say 0 or 10.

If one thread constructs an object of type B, and passes a reference to
that object to another thread via a data race, and that other thread
invokes print(), then that print statement may emit either 0 or 10.

If, on the other hand, the print() method assigns a value to y before
the println() statement, thus:

public void print() {
   y = 42;
   System.out.println(y);
}

then the same program would either print out 10 or 42, but not 0.  This
is because the write of the value 0 to y is deemed to have taken place
before the invocation of print().  In other words, the write of 0 to y
is not in a data race with the accesses of y in the print method.  The
write of 42 is considered to overwrite the value 0.

This is the intent of the fourth bullet point in Section 17.4.4 of the
JLS, where we say "The write of the default value (zero, false or null)
to each variable synchronizes-with the first action in every thread".

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

David Holmes-3
Jeremy,

Now you've confused me :)

> If, on the other hand, the print() method assigns a value to y before
> the println() statement, thus:
>
> public void print() {
>    y = 42;
>    System.out.println(y);
> }
>
> then the same program would either print out 10 or 42, but not 0.

Ummm if the assignment occurs in the print method then the subsequent
println must print 42 regardless because the assignment occurred in the same
thread.

Cheers,
David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

David Holmes-3
In reply to this post by alarmnummer
Peter,

Some confusion seems to have arisen.

>    public void foo(){
>       x = 20;
>       synchronized(this){
>          System.out.println( x );
>       }
>    }
> }
>
> If this class is used in a multithreaded environment, what could the
> output be? (foo is called only once to make it easy)

In the absence of any other methods that write to x then the value of x is
always 20 when the println is invoked. It is irrelevant whether the write to
x is visible to some other thread at that time as no other thread has access
to x. Any thread that executes foo() will do the assignment x=20 and then
print out the value 20 because in program order the write to x
happens-before the read of x used by the println.

It would be a different matter if there was a seperate setter method that
could be called. I think you need to reconsider your example.

Cheers,
David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

Jeremy Manson-2
In reply to this post by David Holmes-3
David Holmes wrote:
> Jeremy,
>
> Now you've confused me :)

I do seem to be doing more harm than good here...  :)

>> If, on the other hand, the print() method assigns a value to y before
>> the println() statement, thus:
>>
>> public void print() {
>>    y = 42;
>>    System.out.println(y);
>> }
>>
>> then the same program would either print out 10 or 42, but not 0.
>
> Ummm if the assignment occurs in the print method then the subsequent
> println must print 42 regardless because the assignment occurred in the same
> thread.

This is why I don't like the way we've been phrasing this example.  We
haven't actually been showing both threads.  I'll do it a little
differently (Maybe this will clarify?).  If the class is this:

public class A{
    private int x = 10;
    public static A a;

    public void foo(){
       x = 20;
       synchronized(this){
          System.out.println( x );
       }
    }

    public void bar(){
       synchronized(this){
          System.out.println( x );
       }
    }

}


This is one of the examples we have been discussing:

Thread 1:
A o = new A();
A.a = o;

Thread 2:
A r1 = A.a;
assert r1 != null;
r1.foo(); // can print out 10 or 20

This is the other:

Thread 1:
A o = new A();
A.a = o;

Thread 2:
A r1 = A.a;
assert r1 != null;
A r1.bar(); // can print out 10 or 0


                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

David Holmes-3
In reply to this post by David Holmes-3
I wrote:
> Ummm if the assignment occurs in the print method then the subsequent
> println must print 42 regardless because the assignment occurred
> in the same thread.

As Jeremy has been pointing out you need to see how multiple threads come to
access the instance of the class. What I wrote above is incorrect if the
instance was unsafely published because the write in the constructor due to
the initialization statement could "appear" after the assignment within the
print method.

Sorry for adding to the confusion.

Cheers,
David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

David Holmes-3
In reply to this post by Jeremy Manson-2
Jeremy Manson wrote:

> Having said that, the fact that print() can't write out 0 has nothing to
> do with the constructing thread.  Basically, there is a conceptual write
> of 0 to x that happens-before every other action in the program, at "The
> Dawn of Time" (this corresponds to the GC zeroing out memory).  Your
> program can be abstracted in the following way:
>
> "The Dawn of Time":
> // zeroes out all memory, including:
> f.x = 0;
>
> Thread 1:
> // The dawn of time happens-before this:
> f.x = 10;
> global.a = f;
>
> Thread 2:
> // The dawn of time happens-before this:
> g = global.a;
> g.x = 20;
> print(g.x);
>
> The execution engine for Thread 2 will know that the write of 20 has
> overwritten the write of 0, because it knows that the write of 0
> occurred at the dawn of time.  It won't print 0.

So this means that:

   class A {
       int x;
       ...
   }

is semantically different to:

   class A {
       int x = 0;
       ...
   }

because the explicit write of zero to x could "appear" later (even though it
is overwriting a zero value in main memory) just as the value 10 could
"appear" later.

Wow! That is a very subtle distinction. I'm not sure there are any practical
consequences arising from it but I find it disconcerting to have this
difference.

Cheers,
David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

yangjs
In reply to this post by David Holmes-3
 >
> Some confusion seems to have arisen.
>
>>    public void foo(){
>>       x = 20;
>>       synchronized(this){
>>          System.out.println( x );
>>       }
>>    }
>> }
.According to JLS ,
    "Each action in a thread happens-before every action in that thread that
comes later in the program order".

  so the println out only have one result :20






Best regards,


 ???(yangjs)
Tel:0571-85022088-3021
Email:[hidden email]
http://www.alibaba.com
----- Original Message -----
From: "David Holmes" <[hidden email]>
To: "Peter Veentjer" <[hidden email]>;
<[hidden email]>
Sent: Monday, September 11, 2006 7:22 AM
Subject: Re: [concurrency-interest] concurrency puzzle


> Peter,
>
> Some confusion seems to have arisen.
>
>>    public void foo(){
>>       x = 20;
>>       synchronized(this){
>>          System.out.println( x );
>>       }
>>    }
>> }
>>
>> If this class is used in a multithreaded environment, what could the
>> output be? (foo is called only once to make it easy)
>
> In the absence of any other methods that write to x then the value of x is
> always 20 when the println is invoked. It is irrelevant whether the write
> to
> x is visible to some other thread at that time as no other thread has
> access
> to x. Any thread that executes foo() will do the assignment x=20 and then
> print out the value 20 because in program order the write to x
> happens-before the read of x used by the println.
>
> It would be a different matter if there was a seperate setter method that
> could be called. I think you need to reconsider your example.
>
> Cheers,
> David Holmes
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

David Holmes-3
yangjs writes:

> >>    public void foo(){
> >>       x = 20;
> >>       synchronized(this){
> >>          System.out.println( x );
> >>       }
> >>    }
> >> }
> .According to JLS ,
>     "Each action in a thread happens-before every action in that
> thread that comes later in the program order".

Yes

>   so the println out only have one result :20

Not necessarily. If the instance was constructed in a different thread then
the write of x=10 from the constructor can occur after the x=20 and before
the println(x), hence the output can be 10 or 20.

David Holmes

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

Jeremy Manson-2
In reply to this post by yangjs
yangjs wrote:

>  >
>> Some confusion seems to have arisen.
>>
>>>    public void foo(){
>>>       x = 20;
>>>       synchronized(this){
>>>          System.out.println( x );
>>>       }
>>>    }
>>> }
> .According to JLS ,
>     "Each action in a thread happens-before every action in that thread that
> comes later in the program order".
>
>   so the println out only have one result :20
>
>

This is not correct.  In the examples, as I gave them, there is a write
in the constructor of 10 to the field x.  That write is in a data race
with this read of x.  Therefore, the read can see 10, as well.

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

Jeremy Manson-2
In reply to this post by David Holmes-3
This is off list, as it is probably a little more obscure than most
people will want to tackle.

David Holmes wrote:

> Wow! That is a very subtle distinction. I'm not sure there are any practical
> consequences arising from it but I find it disconcerting to have this
> difference.

I think it is the least disconcerting of the possible alternatives:

If we picked the semantics of the variable initializer, and gave it to
the default write, then the default write wouldn't be guaranteed to be
seen by every thread that reads a reference to that object via a data
race.  You can't see a garbage value, so what value do you see?

If we picked the semantics of the default write, and gave it to the
variable initializer, then writes made in constructors would have to
propagate to every thread that sees a reference to the object.  This
would have a pretty big performance impact.

If we picked the semantics of the default write, and gave it to only the
variable initializers that write out default values, then you have far
worse problems, because you are
        a) creating yet another obscure corner case for Java;
        b) in practice, relying on the compiler or virtual machine to detect
and remove writes of the default value in a variable initializer, so
that other threads don't see them out of order.  Not only is this not
always possible, but it is bad for the spec to require certain
optimizations to occur; and
        c) (and possibly worst of all) changing the memory semantics based on
which value is written out to a field.

These are all straw men, but I can't really think of a better "fifth
way" to do this.

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

David Holmes-3
Jeremy writes:
> These are all straw men, but I can't really think of a better "fifth
> way" to do this.

I agree there is no better solution. I still find it disconcerting though.
:)

Cheers,
David

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

alarmnummer
In reply to this post by Jeremy Manson-2
But what about the behaviour of the synchronized statement? If a lock
is obtained, local memory (for that thread) is invalidated and the
next read is going to access main memory.

That is why the assignment of x=20 could get lost. If the x=20 isn't
written to main memory (and in this case there is no need to) but only
to cache, the value is 'dropped' when the cache is invalidated.

Is this correct? I'm trying to understand the memory behaviour of the
synchronized statement: that is the reason why I made this example.

On 9/11/06, Jeremy Manson <[hidden email]> wrote:

> This is off list, as it is probably a little more obscure than most
> people will want to tackle.
>
> David Holmes wrote:
>
> > Wow! That is a very subtle distinction. I'm not sure there are any practical
> > consequences arising from it but I find it disconcerting to have this
> > difference.
>
> I think it is the least disconcerting of the possible alternatives:
>
> If we picked the semantics of the variable initializer, and gave it to
> the default write, then the default write wouldn't be guaranteed to be
> seen by every thread that reads a reference to that object via a data
> race.  You can't see a garbage value, so what value do you see?
>
> If we picked the semantics of the default write, and gave it to the
> variable initializer, then writes made in constructors would have to
> propagate to every thread that sees a reference to the object.  This
> would have a pretty big performance impact.
>
> If we picked the semantics of the default write, and gave it to only the
> variable initializers that write out default values, then you have far
> worse problems, because you are
>        a) creating yet another obscure corner case for Java;
>        b) in practice, relying on the compiler or virtual machine to detect
> and remove writes of the default value in a variable initializer, so
> that other threads don't see them out of order.  Not only is this not
> always possible, but it is bad for the spec to require certain
> optimizations to occur; and
>        c) (and possibly worst of all) changing the memory semantics based on
> which value is written out to a field.
>
> These are all straw men, but I can't really think of a better "fifth
> way" to do this.
>
>                                        Jeremy
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

Vijay Saraswat
In reply to this post by David Holmes-3
David Holmes wrote:

> So this means that:
>
>   class A {
>       int x;
>       ...
>   }
>
>is semantically different to:
>
>   class A {
>       int x = 0;
>       ...
>   }
>
>because the explicit write of zero to x could "appear" later (even though it
>is overwriting a zero value in main memory) just as the value 10 could
>"appear" later.
>
>Wow! That is a very subtle distinction. I'm not sure there are any practical
>consequences arising from it but I find it disconcerting to have this
>difference.
>  
>
The difference could be huge.

Question: Is there some argument for why any Java code has a race with
the second fragment iff it has a race with the first?

That would be a very interesting global property of the Java language.

If not, then one would need some interesting results about JSR 133 rules
to be certain that there are no practical consequences arising from this
distinction -- since the presence of races has such a huge impact on the
semantics. For instance one would need *at least* the following to be
true (and in reality much more general forms of this would need to be true):

Claim: Suppose the only race in a program is between a read action and a
write action on x that writes the same value as the hb-value of x at the
read operation. Then all executions of the program are SC.

Unfortunately, JSR 133 rules are complex and not mathematically precise.
So I cant figure out if this is true.

If someone can provide some precise reasoning based on JSR133 for why
the question or the claim above is true (or false!), I would be very
grateful.

Best,
Vijay


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

Jeremy Manson-2
In reply to this post by alarmnummer
Oops!  I guess "off list" is a concept I am having trouble with today
:).  Oh, well, if people are interested...

Peter Veentjer wrote:

> But what about the behaviour of the synchronized statement? If a lock
> is obtained, local memory (for that thread) is invalidated and the
> next read is going to access main memory.
>
> That is why the assignment of x=20 could get lost. If the x=20 isn't
> written to main memory (and in this case there is no need to) but only
> to cache, the value is 'dropped' when the cache is invalidated.
>
> Is this correct? I'm trying to understand the memory behaviour of the
> synchronized statement: that is the reason why I made this example.
>

Peter,

First, the example again:

> public class A{
>     private int x = 10;
>     public static A a;
>
>     public void foo(){
>        x = 20;
>        synchronized(this){
>           System.out.println( x );
>        }
>     }
>
> }
>
> Thread 1:
> A o = new A();
> A.a = o;
>
> Thread 2:
> A r1 = A.a;
> assert r1 != null;
> r1.foo(); // can print out 10 or 20


You are still thinking about this in terms of local memory for a given
thread, and invalidation.  A Java thread doesn't have local memory, and
doesn't perform invalidation.  Processors have caches, and their caches
can be invalidated.  However, if 20 was written out to x earlier in the
same thread, there are no processors that will then allow this print
statement to write the older value 0.  That's not how memory coherence
works.

Even if it were how memory coherence worked in some processor (which it
wouldn't be), it would be a violation of the Java memory model, which,
as we have discussed, disallows a read of the value 0.  So a Java
implementation would have to find a way around it.

                                        Jeremy
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: concurrency puzzle

Kevin Condon
In reply to this post by David Holmes-3
> Wow! That is a very subtle distinction. I'm not sure there are any practical
> consequences arising from it but I find it disconcerting to have this
> difference.

This isn't *exactly* the same thing, but I think there is a practical
consequence for a similar situation when populating non-serialized
fields in readObject().  For some Serializable class MyObject:

  private transient Object mutex;  // needs to be volatile
  private int f;

  public MyObject() {
    initTransient();
  }

  private void readObject(ObjectInputStream in) throws ... {
    initTransient();
    synchronized (mutex) {
      in.defaultReadObject();
    }
  }

  private void initTransient() {
    // bad, no synchronization on the non-volatile field init
    mutex = new Object();
  }

  private void writeObject(ObjectOutputStream out) throws ... {
    // NPE, mutex init visiblility not guaranteed in all threads
    synchronized (mutex) {
      out.defaultWriteObject();
    }
  }

  public int getF() {
    // NPE, mutex init visiblility not guaranteed in all threads
    synchronized (mutex) {
      return f;
    }
  }

  public void setF(int f) {
    // NPE, mutex init visiblility not guaranteed in all threads
    synchronized (mutex) {
      this.f = f;
    }
  }

T1:
  volatile MyObject o;
  ...
  o = (MyObject) in.readObject();

T2:
  int v = o.getF();  // might get a NPE due to race on mutex value
  // same NPE potential with o.setF() and with serializing the object ...

If I didn't have to serialize, I'd just make mutex final.  I think
making mutex volatile fixes the problem with potential NPEs, but then
you incur performance costs for both synchronization and volatile
semantics.  Is there some other option that I'm missing?  (Please
assume I don't want to do synchronize (this), because more complex
classes might not want to expose internal locks to avoid deadlock.)

This scares me because it's so easy to forget to do (I definitely
have) and because of the performance costs imposed (even if they may
be small).  In general remembering to synchronize properly during
construction and deserialization is just too easy to forget.

Regards,
Kevin
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
12