[concurrency-interest] ConcurrentMap consistencyrequirementsconfusion

Roland Kuhn rk at rkuhn.info
Sat Dec 10 15:53:39 EST 2011


On Dec 10, 2011, at 19:21 , Boehm, Hans wrote:

>> From: David Holmes
>> 
>> Chris,
>> 
>> You do have a point but are also a little off-base. :)
>> 
>> I was wrong in my comments about it being a "concurrently accessible
>> map" as
>> ConcurrentMap is not that at all. ConcurrentMap simply defines three
>> operations that must be performed atomically and adds the JMM
>> constraint as
>> noted. To query whether your Thread A and B example "works" you have to
>> look
>> at the actual implementation of the Map involved. So you need to
>> examine the
>> specs for ConcurrentHashMap if that is the map you want to use in which
>> case
>> a relevant statement (as you noted earlier) is:
>> 
>> "Retrievals reflect the results of the most recently completed update
>> operations holding upon their onset."
> My problem with this statement is that we don't really know what the "most recently completed" operation is.

I take that to mean the same as on page 12 of jsr133.pdf: “where subsequent is defined according to the synchronization order”, which page 17 defines as “total order over all synchronizations in A”, where A are the actions within an execution E. There may exist several consistent but different executions with different synchronization orders for the same program, I assume.

>  In general, the only ordering we have on arbitrary Java actions is happens-before.  I suspect that that you really want CHM operations to participate in the synchronization order.  

Do I understand correctly that my above assumption/interpretation is not correct?

> Are current implementations strong enough to make that correct?  If I encode Dekker's using CHMs, as in ("key" entries initially "0"):
> 
> Thread 1:
> a.put("key","1");
> r1 = b.get("key");
> 
> Thread 2:
> b.put("key","1");
> r2 = a.get("key");
> 
I do not fully understand what you want to demonstrate here wrt. synchronization order; allow me to rephrase with volatile vars:

Thread 1:
A) a = 1;
B) r1 = b;

Thread 2:
C) b = 1;
D) r2 = a;

If I read the spec correctly, the following synchronization order would be consistent:

start -> r.b -> r.a -> w.a -> w.b -> stop

There are no synchronizes-with relations in here, and the only happens-before relations are between start and each read and between each write and stop, respectively.

There is no write where a following read sees a write which sw/hb the write. Intra-thread semantics do not add anything since the write and the read in each thread are not related.

> Can I get r1 = r2 = "0"?  Presumably not.
> 
Well, please correct my reasoning above, but I think it would be legal. And if it would be legal for volatile vars, why should it not be for CHMs?

Regards,

Roland

> Hans
> 
>> 
>> So that provides the basic guarantee that Thread B will see the item
>> added
>> by Thread A (provided they both get a chance to execute the relevant
>> code,
>> no thread C removes it in between, no one calls system.exit, the
>> computer is
>> not rebooted, the universe does not end etc :) )
>> 
>> Cheers,
>> David
>> 
>>> -----Original Message-----
>>> From: Chris Dennis [mailto:cdennis at terracottatech.com]
>>> Sent: Saturday, 10 December 2011 2:01 AM
>>> To: Boehm, Hans
>>> Cc: dholmes at ieee.org; concurrency-interest at cs.oswego.edu
>>> Subject: Re: [concurrency-interest] ConcurrentMap
>>> consistencyrequirementsconfusion
>>> 
>>> 
>>> Although Hans' observations are interesting and I agree that
>>> pathological scheduling could prevent the code from ever
>>> terminating my question was intended to be explicitly about the
>>> JMM and exactly where the synchronizes-with edge must be placed
>>> in a spec compliant ConcurrentMap implementation.  As an example:
>>> 
>>> Thread A:
>>> foo.bar = "baz";
>>> map.put("key", value);
>>> 
>>> Thread B:
>>> while (map.get("key") != value);
>>> assert foo.bar == "baz";
>>> 
>>> What I'm trying to say (in a probably none too clear way) is that
>>> the spec seems to say there is a happens-before relationship
>>> between the action immediately preceding the installation of a
>>> mapping (the write to foo.bar in my example) and any actions
>>> occurring in a thread that accesses that mapping (the assert) but
>>> that the spec falls short of guaranteeing that the get in this
>>> case actually ever sees the value.  In my example it seems to me
>>> that the ConcurrentMap specification only enforces that the
>>> assert not fail *if* the mapping is observed, not that the
>>> mapping itself must be observed within any given timeframe (or at
>>> all).  While I understand David's sentiment that such a map would
>>> not be very useful - I don't see that the current specification
>>> actually excludes it.  ConcurrentHashMap actually elaborates in
>>> it's javadoc and includes the statement: "Retrievals reflect the
>>> results of the most recently completed update operations holding
>>> upon their onset.".
>>> 
>>> Maybe I'm splitting hairs with this argument, or maybe I'm just
>>> plain wrong, but the specification on ConcurrentMap imho seems to
>>> fall short of requiring the behavior that David (and I) would
>>> expect out of a sensible implementation.
>>> 
>>> Chris
>>> 
>>> On Dec 8, 2011, at 8:06 PM, Boehm, Hans wrote:
>>> 
>>>> Agreed about muddying the waters.  And I should have been
>>> clearer.  The problem is that "scheduling pathologies" are
>>> somewhere between very hard and impossible to distinguish from
>>> the sort of question about progress guarantees that I think was
>>> really being asked here.
>>>> 
>>>> The original question claimed to be about happens-before and
>>> visibility, but I don't think it was really intended to be.  If
>>> you try to make it precise, the notion of "subsequently
>>> attempting to read" is not defined nor, I think, definable in
>>> this context.  I interpreted the question as really asking
>>> whether the put was guaranteed to eventually become visible to
>>> the first thread.   I think that question inherently has nothing
>>> to do with happens-before, and everything to do with progress
>>> guarantees.  The answer to that question is "no", for the reasons
>>> I gave.  But I may have misinterpreted the question.
>>>> 
>>>> Hans
>>>> 
>>>>> -----Original Message-----
>>>>> From: David Holmes [mailto:davidcholmes at aapt.net.au]
>>>>> Sent: Thursday, December 08, 2011 4:34 PM
>>>>> To: Boehm, Hans; Chris Dennis; concurrency-interest at cs.oswego.edu
>>>>> Subject: RE: [concurrency-interest] ConcurrentMap
>>>>> consistencyrequirementsconfusion
>>>>> 
>>>>> Hans,
>>>>> 
>>>>> I don't think scheduling pathologies were intended to be
>> considered
>>>>> here.
>>>>> The question was more on JMM visbility guarantees. Lets not muddy
>> the
>>>>> waters
>>>>> further. :)
>>>>> 
>>>>> Cheers,
>>>>> David
>>>>> 
>>>>>> -----Original Message-----
>>>>>> From: Boehm, Hans [mailto:hans.boehm at hp.com]
>>>>>> Sent: Friday, 9 December 2011 10:27 AM
>>>>>> To: dholmes at ieee.org; Chris Dennis; concurrency-
>>>>> interest at cs.oswego.edu
>>>>>> Subject: RE: [concurrency-interest] ConcurrentMap
>>>>>> consistencyrequirementsconfusion
>>>>>> 
>>>>>> 
>>>>>> Kind of.  The Java memory model makes very weak progress
>>>>>> guarantees.  I do not believe that the program below is
>>>>>> guaranteed to terminate.  For example, on a uniprocessor, the
>>>>>> thread running the loop is allowed to get all the cycles, causing
>>>>>> TRUE to never get added to the map.  The analogous statement
>>>>>> would still be true if you just set and read a volatile rather
>>>>>> than adding to a map.
>>>>>> 
>>>>>> My impression is that there exist JVMs for which this program may
>>>>>> not terminate.  (When this was discussed as part of JSR133, I
>>>>>> think execution of stored procedures in an Oracle DB was proposed
>>>>>> as an example.  I have no idea whether that's still an issue, or
>>>>>> possibly was even only hypothetical even at the time.  Old green
>>>>>> threads JVMs are another, probably uninteresting, example.  Old
>>>>>> Solaris-style mxn thread implementations may sometimes have
>>>>>> similar issues.)
>>>>>> 
>>>>>> There are reasons for not making such guarantees, though they can
>>>>>> be debated.  They include:
>>>>>> 
>>>>>> - In some special purpose contexts, a nonpreemptive thread
>>>>>> implementation may be adequate.  (Some people even believe that's
>>>>>> true in a general purpose context.  I don't, though I think I
>>>>>> believe the special purpose claim.)
>>>>>> 
>>>>>> - I think we still have some open issues about whether all
>>>>>> hardware guarantees that if you issue a store instruction, the
>>>>>> result makes it out of the store buffer in a bounded amount of
>>>>>> time.  Without such a guarantee, it's difficult for the
>>>>>> implementation to guarantee any substantial progress guarantee.
>>>>>> Architecture manuals usually don't discuss this.
>>>>>> 
>>>>>> I don't think these are the only issues, but hopefully you get
>>>>>> the idea ...
>>>>>> 
>>>>>> Hans
>>>>>> 
>>>>>>> -----Original Message-----
>>>>>>> From: concurrency-interest-bounces at cs.oswego.edu
>>>>> [mailto:concurrency-
>>>>>>> interest-bounces at cs.oswego.edu] On Behalf Of David Holmes
>>>>>>> Sent: Thursday, December 08, 2011 2:58 PM
>>>>>>> To: Chris Dennis; concurrency-interest at cs.oswego.edu
>>>>>>> Subject: Re: [concurrency-interest] ConcurrentMap consistency
>>>>>>> requirementsconfusion
>>>>>>> 
>>>>>>> Chris,
>>>>>>> 
>>>>>>> The ConcurrentMap itself must fulfill its basic function of
>> being a
>>>>>>> concurrently accessible map. If thread A adds an entry then
>> thread
>>>>> B
>>>>>>> will
>>>>>>> see that entry. The additional memory consistency docs are to
>>>>> clarify
>>>>>>> what
>>>>>>> else you can infer once you have seen an entry put in by another
>>>>>>> thread.
>>>>>>> 
>>>>>>> Hope that clarifies things.
>>>>>>> 
>>>>>>> David Holmes
>>>>>>> 
>>>>>>>> -----Original Message-----
>>>>>>>> From: concurrency-interest-bounces at cs.oswego.edu
>>>>>>>> [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of
>>>>> Chris
>>>>>>>> Dennis
>>>>>>>> Sent: Friday, 9 December 2011 7:43 AM
>>>>>>>> To: concurrency-interest at cs.oswego.edu
>>>>>>>> Subject: [concurrency-interest] ConcurrentMap consistency
>>>>>>>> requirementsconfusion
>>>>>>>> 
>>>>>>>> 
>>>>>>>> Hi All,
>>>>>>>> 
>>>>>>>> This question may be born out of an inability to parse the
>>>>>>>> English language, fully understand the JVM, me being a pedant,
>> or
>>>>>>>> it may have an interesting story behind it.  I wondered if
>>>>>>>> someone on this list could enlighten me regardless.
>>>>>>>> 
>>>>>>>> The javadoc for ConcurrentMap (the interface *not* CHM) states:
>>>>>>>> 
>>>>>>>> "Memory consistency effects: As with other concurrent
>>>>>>>> collections, actions in a thread prior to placing an object
>> into
>>>>>>>> a ConcurrentMap as a key or value happen-before actions
>>>>>>>> subsequent to the access or removal of that object from the
>>>>>>>> ConcurrentMap in another thread."
>>>>>>>> 
>>>>>>>> This seems to imply to me by saying "...actions in a thread
>> prior
>>>>>>>> to placing an..." rather than "...actions in a thread prior to
>>>>>>>> and including the action of placing an..." that there is no
>>>>>>>> requirement in a ConcurrentMap for there to be a happens-before
>>>>>>>> relationship between the action of putting the mapping in to
>> the
>>>>>>>> map and subsequently attempting to read that mapping.
>>>>>>>> 
>>>>>>>> Does that mean that a valid ConcurrentMap implementation could
>>>>>>>> cause the following method to never terminate?
>>>>>>>> 
>>>>>>>> ========================================
>>>>>>>> public static void foreverRead(final ConcurrentMap<Boolean,
>>>>>>>> Boolean> map) throws InterruptedException {
>>>>>>>>   Thread t = new Thread() {
>>>>>>>>     @Override
>>>>>>>>     public void run() {
>>>>>>>>       while (!map.containsKey(Boolean.TRUE));
>>>>>>>>     }
>>>>>>>>   };
>>>>>>>>   t.start();
>>>>>>>> 
>>>>>>>>   map.put(Boolean.TRUE, Boolean.TRUE);
>>>>>>>> 
>>>>>>>>   t.join();
>>>>>>>> }
>>>>>>>> ========================================
>>>>>>>> 
>>>>>>>> CHM obviously does terminate here due to it's implementation,
>> as
>>>>>>>> I imagine most (if not all) possible implementations would.
>>>>>>>> 
>>>>>>>> Thanks in advance for any information or education.
>>>>>>>> 
>>>>>>>> Chris
>>>>>>>> _______________________________________________
>>>>>>>> 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
>>>>>> 
>>>> 
>>> 
>>> 
>> 
>> _______________________________________________
>> 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

--
I'm a physicist: I have a basic working knowledge of the universe and everything it contains!
    - Sheldon Cooper (The Big Bang Theory)




More information about the Concurrency-interest mailing list