[concurrency-interest] ConcurrentMap consistencyrequirementsconfusion

Roland Kuhn rk at rkuhn.info
Fri Dec 9 11:50:28 EST 2011

On Dec 9, 2011, at 17:01 , Chris Dennis wrote:

> 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.  

There is a difference between a synchronization action and a happens-before relation: a synchronizes-with edge connects events in possibly different threads and implies happens-before relations, namely between all actions before the edge in thread A and all actions after the edge in thread B (since happens-before is transitive and intra-thread semantics have happens-before matching program order). So, the spec indirectly says that there is a synchronization edge between map.put and map.get somewhere, but the exact placement is irrelevant as all that matters is that everything that happened before the map.put in thread A happens-before everything that happens after the map.get in thread B.

BUT the spec cannot say anything about which put/get pairs are actually formed during execution of the program.

> 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.".
I think you are interpreting the scope of the JMM too widely: the JMM is about ordering guarantees of actions between threads. Given such an ordering, the spec cannot guarantee that the program is actually executed: someone might just pull the plug. The only sensible thing to do is that map.put will publish the new information correctly (i.e. using a synchronization action), which will happen as soon as that code is actually executed, i.e. after map.put returns the rest of the world will see the new state. How this matches up with where other threads are currently in their code has nothing to do with the JMM. The JMM then only guarantees that IF someone sees the new map state, he will also see the right value in “foo.bar”.

> 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.
As you might have guessed, I think it’s the former ;-)



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