[concurrency-interest] ConcurrentMap consistencyrequirementsconfusion

Chris Dennis cdennis at terracottatech.com
Fri Dec 9 11:01:22 EST 2011

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.

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

More information about the Concurrency-interest mailing list