[concurrency-interest] ConcurrentMap consistency requirementsconfusion

Boehm, Hans hans.boehm at hp.com
Thu Dec 8 19:26:54 EST 2011


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