[concurrency-interest] Relativity of guarantees provided by volatile

Boehm, Hans hans.boehm at hp.com
Wed Aug 22 19:46:45 EDT 2012



> -----Original Message-----
> From: Marko Topolnik [mailto:mtopolnik at inge-mark.hr]
> Sent: Wednesday, August 22, 2012 2:44 PM
> To: Zhong Yu
> Cc: Boehm, Hans; concurrency-interest at cs.oswego.edu
> Subject: Re: [concurrency-interest] Relativity of guarantees provided
> by volatile
> 
> >>
> >>
> >>    Thread R                                  /--> Rr0 --> Rr1
> >>                                  -----------+--------/
> >>                                /            |
> >>    Thread W        --> Rw0 -> Ww0 ---> Rw1 -+--> Ww1
> >>                  /                /  ------/
> >>                 |                | /
> >>    Thread T    Wt0 -----------> Wt1
> >
> > Suppose W writes v=1, then observes t=1; R observes t=2, then read v.
> > The last read cannot see v=0.
> >
> > Therefore if R/W actions are sandwiched with reading the timing
> > variable, we will not detect any apparent timing paradoxes.
> >
> > Since we are not talking about physical time (beyond JMM) any more,
> > instead just a variable (within JMM), JMM guarantees that any
> > execution of the program appears to be sequentially consistent.
> 
> 
> I was trying to form a minimal example to demonstrate the point, it
> seems still lacking. Consider the following graph, now there's three
> wall-clock writes involved:
> 
> 
> Thread R                                         /--> Rr0 --> Rr1
>                               ------------------+---------/
>                             /                   |
> Thread W        --> Rw0 -> Ww0 ---> Rw1 -> Ww1  |
>               /                /                |
>              |                |                 |
> Thread T    Wt0 -----------> Wt1 ------------> Wt2
> 
> 
> Say Wt0 writes t = 0 ms, Wt1 writes t = 3 ms, Wt2 writes t = 6 ms.
> 
> Also say Ww0 writes zero and Ww1 writes one.
> 
> Thread W says "I wrote zero at t = 0 ms and one at t = 3 ms."
> 
> Thread R says "I read zero at t = 6 ms."
> 
> Note also the general pattern: there are no constraints imposed by the
> arrows from T to R on the arrows from W to R.
> 
> -Marko
I'm having a bit of trouble interpreting your notation.  Rw1 refers to a timer read?  Why is this not exactly what you expect if Ww1 actually happened at 7 ms due to some scheduling delay?  Is it strange just because of the way you drew the diagram?  It seems to me that to be problematic, thread W would have to read the timer AFTER the second write, but that's no longer sequentially consistent.


Hans



More information about the Concurrency-interest mailing list