[concurrency-interest] ConcurrentMap consistencyrequirementsconfusion

Boehm, Hans hans.boehm at hp.com
Thu Dec 8 20:06:24 EST 2011


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