Yan Cheng CHEOK | 1 Feb 15:36 2011
Picon

Is it possible to prevent out of order execution by using reader writer lock?

Hello all,

>From http://java.sun.com/docs/books/jls/second_edition/html/memory.doc.html and
http://g.oswego.edu/dl/jmm/cookbook.html, it is possible to prevent out of order execution by using
"volatile" or "synchronized" method. 

However, may I know, is it possible to to use reader writer lock to prevent out of order execution?

Code which is having out of order execution problem
===================================================
void fun_by_thread_1() {
    this.isNuclearFactory = true;
    this.factory = new NuclearFactory();
}

void fun_by_thread_2() {
    Factory _factory = this.factory;
    if (this.isNuclearFactory) {
        // Do not operate nuclear factory!!!
        return;
    }
    // If out-of-order execution happens, _factory might 
    // be NuclearFactory instance.
    _factory.operate();
}

Factory factory = new FoodFactory();
boolean isNuclearFactory = false;

Solved by using volatile keyword
(Continue reading)

Niko Matsakis | 2 Feb 20:20 2011
Picon

"Volatile-like" guarantees

Hello everyone,

I have a question about the Java Memory Model.  I am trying to decide if 
it is possible to use a dummy volatile field, like the field v below, to 
get the same guarantees as an actual volatile field.  In other words, is 
the class Foo shown here equivalent to a class where the the field f is 
declared volatile:
>     class Foo {
>         private volatile int v;
>         private int f;
>
>         void setF(int x) {
>             v = 0;    // Wv
>             x = f;    // Wf
>         }
>
>         int getF() {
>             int x = f;     // Rf
>             int y = v;    // Rv
>             return x;
>         }
>     }
In particular, would code using the accessors shown above still be 
sequentially consistent, as it would be if "f" were volatile?

Clearly, the program is not data-race free as defined by the JMM, 
because the write Wf does not happen before Rf.  Nonetheless, I believe 
there is a guarantee very much like the one that volatile offers, which 
I will call "volatile-like":
> If Rf sees the value written by Wf, then no subsequent read will see a 
(Continue reading)

Vitaly Davidovich | 2 Feb 22:02 2011
Picon

Re: "Volatile-like" guarantees

In your example class Foo I think you meant setF to actually write x to f, not read it.

In any case, the code you have is not sequentially consistent because the write to non-volatile must happen before the volatile write, and the corresponding non-volatile read must happen after the volatile read.  If you do that, the JMM guarantees sequential consistency (data race is a separate issue, as you mentioned).

The "piggybacking" of non-volatile read/writes through volatile ones happens a lot in Java; it's just usually done indirectly by using some higher-level constructs (locks, Java.utility.concurrent classes, etc).

Also the compiler is not allowed to, amongst other things, eliminate reads or stores to volatile members so your assignment of zero shouldn't be a problem (for a compliant jvm and static compiler).

On Feb 2, 2011 2:23 PM, "Niko Matsakis" <niko <at> alum.mit.edu> wrote:
> Hello everyone,
>
> I have a question about the Java Memory Model. I am trying to decide if
> it is possible to use a dummy volatile field, like the field v below, to
> get the same guarantees as an actual volatile field. In other words, is
> the class Foo shown here equivalent to a class where the the field f is
> declared volatile:
>> class Foo {
>> private volatile int v;
>> private int f;
>>
>> void setF(int x) {
>> v = 0; // Wv
>> x = f; // Wf
>> }
>>
>> int getF() {
>> int x = f; // Rf
>> int y = v; // Rv
>> return x;
>> }
>> }
> In particular, would code using the accessors shown above still be
> sequentially consistent, as it would be if "f" were volatile?
>
> Clearly, the program is not data-race free as defined by the JMM,
> because the write Wf does not happen before Rf. Nonetheless, I believe
> there is a guarantee very much like the one that volatile offers, which
> I will call "volatile-like":
>> If Rf sees the value written by Wf, then no subsequent read will see a
>> write that was overwritten before the write Wv occurred. More
>> formally, no read r that happens after Rv, which includes all reads in
>> the thread calling getF(), will see a write w that happens before Wv
>> where there exists another write w' such that w -> w' -> Wv.
> An informal argument can be found below [1]. I believe that this
> "volatile-like" guarantee implies sequential consistency, in the same
> way that the volatile guarantee would (argument [2] below). However, I
> ALSO believe that the JMM is fairly subtle, and I may well be missing
> something. :) Hence my e-mail to this list.
>
> One particular concern I have is the possibility that a compiler might
> observe that all the writes to the volatile field "v" are of the same
> value, 0, and therefore eliminated the field. (A similar example
> appears in the JMM paper I have been consulting). I believe however
> that this ought to be illegal by the JMM, as "v" is volatile and
> therefore induces happens-before relations in addition to carrying a value.
>
> I thank all of you in advance, both for taking the time to read this
> e-mail and for any insight you may provide.
>
>
> regards,
> Niko
>
> -----
>
> [1] The argument that Rf/Wf have a "volatile-like" relationship is as
> follows:
>
> First, the only important cases are those where Rf sees the write Wf.
> This is because the "volatile-like" guarantees described above only
> concern what happens when Rf sees the write Wf. As the volatile
> accesses Wv and Rv are both synchronization actions, one must happen
> before the other in any particular execution. If Rv happens before Wv,
> then at the time when field f is read, Wf cannot be visible, because Rf
> -> Rv -> Wv -> Wf. Therefore, Rf cannot see the write Wf, and this case
> is not important.
>
> If Wv happens before Rv, then when Rf executes, it is possible that Wf
> has already been committed. In that case, Rf may legally see the value
> written by Wf, as it would not violate happens-before consistency (Rf
> does not happen before Wf, nor is there a write w such that Wf -> w ->
> Rf). However, those same happens-before consistency requirements,
> combined with the happens-before relation from Wv to Rv, guarantee that
> any reads that happen after Rv will not see overwritten writes that
> happen before Wv.
>
> [2] A rather loose argument for sequential consistency is that if there
> were two instances of this class Foo f1 and f2, and thread T1 performed
> { f1.setF(w1); f2.setF(w2); } where another thread T2 performed { int r2
> = f2.getF(); int r1 = f1.getF(); }, it should be impossible for T2 to
> observe w2 but not w1. Why? Because the write of w1 happens before the
> write of w2 (presumably overwriting the value written by some previous
> write w). Therefore, by the "volatile-like" guarantee on f2.f, the
> subsequent read of f1.f cannot see the write w, as w -> write of w1 ->
> write of w2. A better argument would probably construct a sequentially
> consistent equivalent to any schedule, but I haven't tried writing such
> a thing out yet.
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest <at> cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest <at> cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Brian Goetz | 3 Feb 04:32 2011

Re: "Volatile-like" guarantees

I think you've got some things backwards in Foo.  You want to swap the 
statements in setF, and swap the Wf assignment.  Similarly, you want to 
swap the statements in getF:

     class Foo {
         private volatile int v;
         private int f;

         void setF(int x) {
             f = x;    // Wf
             v = 0;    // Wv
         }

         int getF() {
             int y = v;    // Rv
             return f;     // Rf
         }
     }

Now, calls to setF happen-before calls to getF, which is the ordering 
you want to expose.  But additionally, you no longer have a data race on 
f; the write to f really does happen-before the read of f in another thread:

   Program Order rule: write to f HB write to v
   Volatile rule: write of v HB subsequent read of v
   Program order rule: read of v HB read of f
   Transitivity: write to f HB read of f

The tricky part here is the meaning of subsequent.  Synchronization 
operations (lock/unlock, read/write volatile) are totally ordered.  So 
it makes sense to say "subsequent read of v".  Does it make sense to say 
"subsequent call to getF"?  I say yes; there is a 1:1 relationship 
between setf and Wf, as well as getF and Rf, so you can align the calls 
to getF/setF in the synchronization order.

Your question about compilers eliding the "stupid" write to v is a fair 
one.  But compilers are carefully trained to not be overeager on 
eliminating volatile writes, for this reason.

Cheers,
-Brian

On 2/2/2011 2:20 PM, Niko Matsakis wrote:
> Hello everyone,
>
> I have a question about the Java Memory Model. I am trying to decide if
> it is possible to use a dummy volatile field, like the field v below, to
> get the same guarantees as an actual volatile field. In other words, is
> the class Foo shown here equivalent to a class where the the field f is
> declared volatile:
>> class Foo {
>> private volatile int v;
>> private int f;
>>
>> void setF(int x) {
>> v = 0; // Wv
>> x = f; // Wf
>> }
>>
>> int getF() {
>> int x = f; // Rf
>> int y = v; // Rv
>> return x;
>> }
>> }
> In particular, would code using the accessors shown above still be
> sequentially consistent, as it would be if "f" were volatile?
>
> Clearly, the program is not data-race free as defined by the JMM,
> because the write Wf does not happen before Rf. Nonetheless, I believe
> there is a guarantee very much like the one that volatile offers, which
> I will call "volatile-like":
>> If Rf sees the value written by Wf, then no subsequent read will see a
>> write that was overwritten before the write Wv occurred. More
>> formally, no read r that happens after Rv, which includes all reads in
>> the thread calling getF(), will see a write w that happens before Wv
>> where there exists another write w' such that w -> w' -> Wv.
> An informal argument can be found below [1]. I believe that this
> "volatile-like" guarantee implies sequential consistency, in the same
> way that the volatile guarantee would (argument [2] below). However, I
> ALSO believe that the JMM is fairly subtle, and I may well be missing
> something. :) Hence my e-mail to this list.
>
> One particular concern I have is the possibility that a compiler might
> observe that all the writes to the volatile field "v" are of the same
> value, 0, and therefore eliminated the field. (A similar example appears
> in the JMM paper I have been consulting). I believe however that this
> ought to be illegal by the JMM, as "v" is volatile and therefore induces
> happens-before relations in addition to carrying a value.
>
> I thank all of you in advance, both for taking the time to read this
> e-mail and for any insight you may provide.
>
>
> regards,
> Niko
>
> -----
>
> [1] The argument that Rf/Wf have a "volatile-like" relationship is as
> follows:
>
> First, the only important cases are those where Rf sees the write Wf.
> This is because the "volatile-like" guarantees described above only
> concern what happens when Rf sees the write Wf. As the volatile accesses
> Wv and Rv are both synchronization actions, one must happen before the
> other in any particular execution. If Rv happens before Wv, then at the
> time when field f is read, Wf cannot be visible, because Rf -> Rv -> Wv
> -> Wf. Therefore, Rf cannot see the write Wf, and this case is not
> important.
>
> If Wv happens before Rv, then when Rf executes, it is possible that Wf
> has already been committed. In that case, Rf may legally see the value
> written by Wf, as it would not violate happens-before consistency (Rf
> does not happen before Wf, nor is there a write w such that Wf -> w ->
> Rf). However, those same happens-before consistency requirements,
> combined with the happens-before relation from Wv to Rv, guarantee that
> any reads that happen after Rv will not see overwritten writes that
> happen before Wv.
>
> [2] A rather loose argument for sequential consistency is that if there
> were two instances of this class Foo f1 and f2, and thread T1 performed
> { f1.setF(w1); f2.setF(w2); } where another thread T2 performed { int r2
> = f2.getF(); int r1 = f1.getF(); }, it should be impossible for T2 to
> observe w2 but not w1. Why? Because the write of w1 happens before the
> write of w2 (presumably overwriting the value written by some previous
> write w). Therefore, by the "volatile-like" guarantee on f2.f, the
> subsequent read of f1.f cannot see the write w, as w -> write of w1 ->
> write of w2. A better argument would probably construct a sequentially
> consistent equivalent to any schedule, but I haven't tried writing such
> a thing out yet.
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest <at> cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Niko Matsakis | 3 Feb 06:23 2011
Picon

Re: "Volatile-like" guarantees

Brian Goetz wrote:
> I think you've got some things backwards in Foo.  You want to swap the 
> statements in setF, and swap the Wf assignment.  Similarly, you want 
> to swap the statements in getF:
>
>     class Foo {
>         private volatile int v;
>         private int f;
>
>         void setF(int x) {
>             f = x;    // Wf
>             v = 0;    // Wv
>         }
>
>         int getF() {
>             int y = v;    // Rv
>             return f;     // Rf
>         }
>     }
>
> Now, calls to setF happen-before calls to getF, which is the ordering 
> you want to expose.  But additionally, you no longer have a data race 
> on f; the write to f really does happen-before the read of f in 
> another thread:
So, my first instinct was to place the volatile writes/reads in the 
order you show here, but I'm not sure that it provides the proper 
guarantees.  In particular, isn't it possible that in some program run 
Rv synchronizes with Wv, but Rf still sees the write from Wf? In that 
case, the reads that follow Rf would not happen after the writes that 
preceded Wf.

Certainly when using memory barriers/fences, the sequence is traditionally:
     Thread 1. perform dependent writes, memory barrier, perform 
significant write
     Thread 2. perform significant read, memory barrier, perform 
dependent reads
is it not?  I guess the question is to what extent a volatile can be 
used like a memory barrier.

Niko
Niko Matsakis | 3 Feb 06:55 2011
Picon

Re: "Volatile-like" guarantees

Niko Matsakis wrote:
> So, my first instinct was to place the volatile writes/reads in the 
> order you show here, but I'm not sure that it provides the proper 
> guarantees.  In particular, isn't it possible that in some program run 
> Rv synchronizes with Wv, but Rf still sees the write from Wf? In that 
> case, the reads that follow Rf would not happen after the writes that 
> preceded Wf.
Sorry, I wrote "Rv synchronizes with Wv", but I meant "Rv appears before 
Wv in the total synchronization order".  (In other words, Wv does not 
happen before Rv.) I had the impression those were synonyms, but 
re-reading the POPL JMM paper [1] I see that is not the case.

Niko

[1] http://doi.acm.org/10.1145/1040305.1040336
David Holmes | 3 Feb 06:59 2011
Picon

Re: "Volatile-like" guarantees

So does this mean you are happy that Brian's explanation is correct?

Cheers,
David

> -----Original Message-----
> From: concurrency-interest-bounces <at> cs.oswego.edu
> [mailto:concurrency-interest-bounces <at> cs.oswego.edu]On Behalf Of Niko
> Matsakis
> Sent: Thursday, 3 February 2011 3:56 PM
> To: Brian Goetz
> Cc: concurrency-interest <at> cs.oswego.edu
> Subject: Re: [concurrency-interest] "Volatile-like" guarantees
> 
> 
> Niko Matsakis wrote:
> > So, my first instinct was to place the volatile writes/reads in the 
> > order you show here, but I'm not sure that it provides the proper 
> > guarantees.  In particular, isn't it possible that in some program run 
> > Rv synchronizes with Wv, but Rf still sees the write from Wf? In that 
> > case, the reads that follow Rf would not happen after the writes that 
> > preceded Wf.
> Sorry, I wrote "Rv synchronizes with Wv", but I meant "Rv appears before 
> Wv in the total synchronization order".  (In other words, Wv does not 
> happen before Rv.) I had the impression those were synonyms, but 
> re-reading the POPL JMM paper [1] I see that is not the case.
> 
> 
> 
> Niko
> 
> [1] http://doi.acm.org/10.1145/1040305.1040336
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest <at> cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> 
Niko Matsakis | 3 Feb 07:23 2011
Picon

Re: "Volatile-like" guarantees

David Holmes wrote:
> So does this mean you are happy that Brian's explanation is correct?
>    
No, it does not really change the question that I had.  Clearly, the 
volatile read in the getter (Rv) may precede the volatile write in the 
setter (Wv), in which case there would be no happens-before 
relationship.  However, unless I am mistaken, in that case it is still 
possible that the non-volatile read (Rf) sees the write from the 
non-volatile write (Wf).  Intuitively, in some execution, the reads in 
the getter may occur in between the two writes in the setter.  In that 
scenario, the write to f occurs first, then both reads, then the 
volatile write to v.  So there is no happens-before relationship, but 
the read may see the write to f (it also may not, as there is no 
happens-before relationship to force the issue).  Now reads which follow 
the getter are not guaranteed to the see writes which preceded the setter.

The difference between this scenario and the normal volatile example is 
that the volatile write is not the "significant" write.  In other words, 
the intended usage of volatile as I understand is that one performs 
various writes W, then writes a value to the volatile field that serves 
as a signal to the reader.  The reader, seeing that value, performs 
various dependent reads that would not be safe had the writes W not been 
completed.  In this scenario, though, it is not the write to the 
volatile that signals the reader, but rather the write to the 
non-volatile field f.  The question then is can a volatile read/write be 
used purely as a supplement and, if so, what is the right way to do it.

To motivate the question, I am working on a compiler for a parallel 
language.  The language generally guarantees data-race freedom, but in 
some cases it allows the user to signal that they permit data-races; in 
those cases I would still like to guarantee sequential consistency.  The 
problem is that a single class may be used both in a racy and non-racy 
context.  The conservative thing to do then is to mark all fields 
volatile, but that penalizes the non-racy context, which is by far the 
most common.  I could generate two versions of the class, and maybe 
eventually I will, but for the moment I'd like to use a simpler scheme.  
A final option, then, is to have a delegate class which optionally uses 
a volatile field in the way that I have shown here to add in memory 
barriers.  So, in that case, writes to a field "f" would be compiled as

     this.f = ...;
     this.delegate.synchronizeWrite();

where synchronizeWrite() would either do nothing (non-ract case) or 
write a dummy value to a volatile field (racy case).  The question is, 
will a scheme like this work?  (Of course, it may also prove to be slow, 
if the cost of the method call is too high, but that could be optimized 
in various ways)

Niko
David Holmes | 3 Feb 07:42 2011
Picon

Re: "Volatile-like" guarantees

Niko Matsakis writes:
> David Holmes wrote:
> > So does this mean you are happy that Brian's explanation is correct?
> >
> No, it does not really change the question that I had.

That's a shame as I had a response to that email nearly finished when your
clarification came in. :) But I'll try to respond to how you have expressed
things below. For reference let me rewrite the code:

        void setF(int x) {
            f = x;    // Wf
            v = 0;    // Wv
        }
        int getF() {
           int y = v;    // Rv
           return f;     // Rf

> Clearly, the
> volatile read in the getter (Rv) may precede the volatile write in the
> setter (Wv), in which case there would be no happens-before
> relationship.

Correct.

> However, unless I am mistaken, in that case it is still
> possible that the non-volatile read (Rf) sees the write from the
> non-volatile write (Wf).  Intuitively, in some execution, the reads in
> the getter may occur in between the two writes in the setter.  In that
> scenario, the write to f occurs first, then both reads, then the
> volatile write to v.  So there is no happens-before relationship, but
> the read may see the write to f (it also may not, as there is no
> happens-before relationship to force the issue).

Correct. Writes can become immediately visible and be totally ordered.
Barriers are only needed to establish visibility and ordering properties
when that is not the case.

> Now reads which follow
> the getter are not guaranteed to the see writes which preceded the setter.

I see. Yes the transitive HB relationship does not apply. But you have
arbitrary racing between the two threads so I don't see how you define
correctness here.

> The difference between this scenario and the normal volatile example is
> that the volatile write is not the "significant" write.  In other words,
> the intended usage of volatile as I understand is that one performs
> various writes W, then writes a value to the volatile field that serves
> as a signal to the reader.  The reader, seeing that value, performs
> various dependent reads that would not be safe had the writes W not been
> completed.

Correct.

> In this scenario, though, it is not the write to the
> volatile that signals the reader, but rather the write to the
> non-volatile field f.  The question then is can a volatile read/write be
> used purely as a supplement and, if so, what is the right way to do it.

But the non-volatile write can't be used as a signal to the reader as it is
unordered - only the volatile accesses impose a limited ordering on the
accesses in the program.

> To motivate the question, I am working on a compiler for a parallel
> language.  The language generally guarantees data-race freedom, but in
> some cases it allows the user to signal that they permit data-races; in
> those cases I would still like to guarantee sequential consistency.

Given that the Java Memory Model does not guarantee sequential consistency
in the face of data races, I don't see how you can construct a
sequentially-consistent but racy implementation on top of it.

But this is something better discussed on the JMM mailing list.

Cheers,
David Holmes

 The
> problem is that a single class may be used both in a racy and non-racy
> context.  The conservative thing to do then is to mark all fields
> volatile, but that penalizes the non-racy context, which is by far the
> most common.  I could generate two versions of the class, and maybe
> eventually I will, but for the moment I'd like to use a simpler scheme.
> A final option, then, is to have a delegate class which optionally uses
> a volatile field in the way that I have shown here to add in memory
> barriers.  So, in that case, writes to a field "f" would be compiled as
>
>      this.f = ...;
>      this.delegate.synchronizeWrite();
>
> where synchronizeWrite() would either do nothing (non-ract case) or
> write a dummy value to a volatile field (racy case).  The question is,
> will a scheme like this work?  (Of course, it may also prove to be slow,
> if the cost of the method call is too high, but that could be optimized
> in various ways)
>
>
>
> Niko
>
Niko Matsakis | 3 Feb 08:43 2011
Picon

Re: "Volatile-like" guarantees


> Given that the Java Memory Model does not guarantee sequential consistency
> in the face of data races, I don't see how you can construct a
> sequentially-consistent but racy implementation on top of it.
>
> But this is something better discussed on the JMM mailing list.
>    
Indeed, I didn't realize there was such a mailing list.  I will move the 
discussion over there.

Thanks,

Niko

Gmane