[concurrency-interest] ConcurrentMap consistencyrequirementsconfusion

David Holmes davidcholmes at aapt.net.au
Thu Dec 8 19:33:49 EST 2011


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