[concurrency-interest] Relativity of guarantees provided by volatile

Zhong Yu zhong.j.yu at gmail.com
Wed Aug 22 19:17:39 EDT 2012


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.

> 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:)

> -Marko
>


More information about the Concurrency-interest mailing list