[concurrency-interest] Relativity of guarantees provided by volatile

Marko Topolnik mtopolnik at inge-mark.hr
Thu Aug 23 02:02:05 EDT 2012


On 23. kol. 2012., at 01:17, Zhong Yu wrote:

> On Wed, Aug 22, 2012 at 4:44 PM, Marko Topolnik <mtopolnik at inge-mark.hr> wrote:
>>>> 
>>>> 
>>>>   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."
> 
> W cannot say that, it's more like W wrote one after seeing t=3. That
> is not inconsistent with R reading zero after seeing t=6.
> 
> Note that the clock precision is not good here. For example, there is
> no paradox in "W wrote one before seeing t=6" and "R read zero after
> seeing t=6", because "t=6" can be seen in an extended time window.
> 
> A real paradox would be "W wrote one before seeing t=3" and "R read
> zero after seeing t=6", a timing error greater than clock precision.
> 
> JMM does not allow that paradox. If Rw2 sees t=3, Wt1<Rw2<Wt2 in sync
> order, therefore Ww1<Rw2 <Wt2<Rr0<Rr1, therefore Ww0<Ww1<Rr1, that
> forbids Rr1 seeing Ww0.

This would be the situation you describe:

                                /--> Rrt6 --/-> Rrt9 --> Rv0
    ---------------------------+------------+--------/
  /                            |     ------/
Wv0 ---> Rwt3 -> Wv1 --> Rwt6  |    /
        /                /   --|   /
       |                | /       /
       T3 ------------> T6 ----> T9


Notice I've fixed the naming somewhat. 

T3, T6, T9 -- writes to currentTime
Rwt0, Rwt1 -- reads of currentTime by writing thread
Rrt1, Rrt2 -- reads of currentTime by reading thread
Wv0, Wv1   -- writes to the sharedVar
Rv0        -- read of the sharedVar

initially t = 0 ms;
T3 writes t = 3 ms;
T6 writes t = 6 ms;
T9 writes t = 9 ms.

The program outputs

Writing 0 at t = 0 ms
Writing 1 at t = 3 ms
Reading 0 at t = 9 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.
> 
> You missed the arrows from a read to the write that comes after:)

Not sure what you mean, but there is no synchronizes-with edge going from a read to a write. No arrows extend from one thread reading to another thread writing.

-Marko





More information about the Concurrency-interest mailing list