[concurrency-interest] Relativity of guarantees provided byvolatile

Zhong Yu zhong.j.yu at gmail.com
Sat Aug 18 12:33:25 EDT 2012


On Sat, Aug 18, 2012 at 12:00 AM, Yuval Shavit <yshavit at akiban.com> wrote:
> On Aug 18, 2012, at 12:43 AM, Zhong Yu <zhong.j.yu at gmail.com> wrote:
>
>> On Fri, Aug 17, 2012 at 9:29 PM, David Holmes <davidcholmes at aapt.net.au> wrote:
>>> Well that's your choice, but it makes more sense temporally to consider
>>> completetion when the actual result of the action is available, in my
>>> opinion.
>>
>> We can consider another model:
>>
>> A write must wait for confirmation mail from V.
>>
>> V receives a write Wi, updates its state to Vi, sends mails containing
>> Vi to all threads. The mail is also the confirmation mail to the
>> writer.
>>
>> Threads locally cache the last Vi it receives. A read checks the
>> locally cached Vi only, therefore reads are very short.
>>
>> Sync order can be defined mainly based on the 'i's of actions. This
>> also appears to be a valid JMM model.
>>
>> Then we move V close to W, far away from R. On day#1, W writes v=1 to
>> V. That change reaches R on day#3. On day#2 R reads v=0. Once again,
>> we have read<write in sync order, yet write<read in temporal order.
>
> Except that in this metaphor, if v is volatile, wouldn't R's read of v
> on day 2 require sending V a note requesting v's value -- at which
> point V know about the letter from W on day 1?

In my 2nd model, read only consults the local cache, so it's very fast.

> This model has V being the sole timekeeper. An action A' is subsequent
> to another action A iff V processes A before A'. V seems like quite
> the bottleneck here. In particular, two sets of actions, each with HB
> relations within them but with no HBs between them, will both have to
> synchronize on the same V.

I'm not trying to design a realistic model. I'm seeking a simple
physical model that conforms to JMM and demonstrate that OP's example
can be realized on this model, therefore OP's example is legal under
JMM; and in general, sync order and temporal order can differ.

However the discrepancy becomes less and less when the message
transmission speed approaches the speed of light, so we don't really
need to worry too much about it on real computer hardware.

>
>
>>
>>
>>
>>>
>>> David
>>>
>>>> -----Original Message-----
>>>> From: Zhong Yu [mailto:zhong.j.yu at gmail.com]
>>>> Sent: Saturday, 18 August 2012 12:21 PM
>>>> To: dholmes at ieee.org
>>>> Cc: concurrency-interest at cs.oswego.edu
>>>> Subject: Re: [concurrency-interest] Relativity of guarantees provided
>>>> byvolatile
>>>>
>>>>
>>>> In the model, a write completes as soon as the mail is sent, the same
>>>> thread can immediately make another write. A read completes when the
>>>> return mail is received; the reading thread is suspended during the
>>>> wait.
>>>>
>>>> The example is designed so that reads are short too, so we can treat
>>>> actions as points in time, to order them easily.
>>>>
>>>> On Fri, Aug 17, 2012 at 8:55 PM, David Holmes
>>>> <davidcholmes at aapt.net.au> wrote:
>>>>> As I keep saying, for this to "make sense" you have to make temporal
>>>>> measurements when an action completes.
>>>>>
>>>>> David
>>>>>
>>>>>> -----Original Message-----
>>>>>> From: concurrency-interest-bounces at cs.oswego.edu
>>>>>> [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf
>>>> Of Zhong Yu
>>>>>> Sent: Saturday, 18 August 2012 11:34 AM
>>>>>> To: Yuval Shavit
>>>>>> Cc: concurrency-interest at cs.oswego.edu; dholmes at ieee.org
>>>>>> Subject: Re: [concurrency-interest] Relativity of guarantees provided
>>>>>> byvolatile
>>>>>>
>>>>>>
>>>>>> Consider this physical model:
>>>>>>
>>>>>> Each thread is a person Tx.
>>>>>>
>>>>>> There's a person V managing all variables.
>>>>>>
>>>>>> To make a write, Tx sends a paper mail to V. No return mail is
>>>>>> required, therefore a write is very short.
>>>>>>
>>>>>> To make a read, Tx sends a paper mail to V, and waits for return mail.
>>>>>>
>>>>>> The synchronization order is the order the mails received by V.
>>>>>>
>>>>>> This seems to be a valid JMM model.
>>>>>>
>>>>>> --
>>>>>>
>>>>>> Now suppose thread R is very close to V, therefor reads are also very
>>>>>> short. (it's easier to talk about temporal order between short
>>>>>> actions) Suppose thread W is very far away from V.
>>>>>>
>>>>>> To realize OP's example, consider the numbers are in hours, and route
>>>>>> W -> V takes 48 hours.
>>>>>>
>>>>>> On Monday, W writes v=1, it reaches V on Wednesday. On Tuesday R reads
>>>>>> v=0. So the write is after read in sync order, yet write is before
>>>>>> read in temporal order(even considering relativity - all persons are
>>>>>> on Earth)
>>>>>>
>>>>>> Therefore sync order doesn't have to be consistent with temporal order.
>>>>>> _______________________________________________
>>>>>> 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


More information about the Concurrency-interest mailing list