[concurrency-interest] Is it a good idea to try manipulating theway JVM reorders?

Joe Bowbeer joe.bowbeer at gmail.com
Sat Dec 19 05:51:46 EST 2009


To clarify further, I hope:

1. The Atomic* methods such as decrementAndGet perform synchronization
actions, which do impose an inter-thread ordering.  The same goes for
Phaser's methods, such as advance().

2. Phaser is suitable for this class of problem, and I think would result in
more readable code.

3. One possible weakness in all these solutions is the HashMap.  Consider
using a ConcurrentHashMap.

--Joe

On Sat, Dec 19, 2009 at 2:32 AM, David Holmes wrote:

> > Maybe I'm not understanding the Java Memory Model correctly, but for
> > example, is there really a difference between methodA and methodB
> > below?
> >
> > class Sample {
> >      AtomicReference<Boolean> ref = new AtomicReference<Boolean>();
> >      Phaser phaser = getPhaser();
> >
> >      methodA(){
> >         ref.set(Boolean.TRUE);
> >         phaser.arrive();
> >      }
> >
> >      methodB(){
> >          phaser.arrive();
> >          ref.set(Boolean.TRUE);
> >      }
> > }//class
> >
> > I wonder because, according to Java Concurrency in Practice:
> > "There is no guarantee that operations in one thread will be performed
> > in the order given by the program, as long as the reordering is not
> > detectable from within that thread even if the reordering is apparent
> > to other threads.[1]"
> >
> > Doesn't this mean that the compiler is free to reorder
> > "phaser.arrive();" and "ref.set(Boolean.TRUE);" because indeed, that
> > reordering is not detectable within that thread, while it is apparent
> > to other threads? Thus, I thought you need to do something to prevent
> > that.
>
> You _have_ done something to prevent that: you've used a synchronization
> facility the introduces happens-before relationships that ensure the
> reordering can't take place (at least in the real example!)
>
> As you say, a thread calling methodA() can't tell if anything inside
> methodA() gets reordered, but another thread can tell. That's fine if that
> other thread hasn't executed anything that established a happens-before
> relationship with an action in the first thread, but if it has then the
> allowables reorderings are restricted - that is after-all what the memory
> model does.
>
> So in your real code each thread stores a result before decrementing the
> counter; and each decrement of the count to N+1 happens-before the
> decrement
> to N; hence the storage of the result by the thread that sets N+1,
> happens-before the decrement to N. (Note that you can't tell in what order
> the results actually happened, but they both happen before the decrement to
> N.)
>
> Hope that clarifies things.
>
> David Holmes
>
> >
> > On Sat, Dec 19, 2009 at 7:04 PM, David Holmes wrote:
> > > Enno Shioji writes:
> > >> Now, here is a naive optimization attempt that I think is not
> > thread-safe:
> > >>
> > >> class Task {
> > >>     //Populate with bunch of (Long, new AtomicReference()) pairs
> > >>     //Actual app uses read only HashMap
> > >>     Map<Id, AtomicReference<SubTaskResult>> subtasks = populatedMap();
> > >>     AtomicInteger counter = new AtomicInteger(subtasks.size());
> > >>
> > >>     public Task set(id, subTaskResult){
> > >>            //null check omitted
> > >>            subtasks.get(id).set(result);
> > >>            //In the actual app, if !compareAndSet(null, result)
> > >> return null;
> > >>            return check() ? this : null;
> > >>     }
> > >>
> > >>     private boolean check(){
> > >>            return counter.decrementAndGet() == 0;
> > >>     }
> > >>
> > >>   }//class
> > >>
> > >> I concluded a thread can observe a decremented counter (by another
> > >> thread) before the result is set in AtomicReference (by that other
> > >> thread) because of reordering.
> > >
> > > Which "another thread" are you referring to? The AtomicInteger
> > has volatile
> > > semantics and will be read and written by all threads storing a
> > result, so
> > > the results can not appear in the Map after the corresponding
> > decrement of
> > > the counter. For each thread the write to the map happens-before the
> > > decrement (program order) and each decrement to a non-zero value must
> > > happen-before the decrement to zero (counter acts as volatile).
> > Consequently
> > > all the results stores must happen-before a zero counter value
> > is seen. I'd
> > > go further and say that any thread that reads the counter value
> > N, must be
> > > able to see the results stored by threads that set a counter
> > value greater
> > > than N.
> > >
> > > David Holmes
> > >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20091219/2b101d9a/attachment.html>


More information about the Concurrency-interest mailing list