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

Joe Bowbeer joe.bowbeer at gmail.com
Sat Dec 19 04:29:05 EST 2009


Right.  CyclicBarrier will not do but Phaser would.

http://download.java.net/jdk7/docs/api/java/util/concurrent/Phaser.html

.. with Java 6 compatible version available from
http://gee.cs.oswego.edu/dl/concurrency-interest/

Each subtask would arrive (without waiting) until all have arrived and then
the Phaser's onAdvance action would notify the central server.

--Joe

On Sat, Dec 19, 2009 at 12:14 AM, Enno Shioji wrote:

> Hi Joe,
>
>
> Thank you for your answer!
>
> I fail to get though how a CyclicBarrier could be used here. I mean,
> we'll have bunch of threads waiting on a barrier for no good reason..
> In our app, we'll have thousands of Tasks with hundreds of subtasks
> per Task, so it will become a context switch nightmare..
>
> Or am I missing something?
>
>
> Regards,
> Enno
>
>
>
> On Sat, Dec 19, 2009 at 3:47 PM, Joe Bowbeer wrote:
> > By your description, this seems like a job for CyclicBarrier (or Phaser
> in
> > Java 7).
> >
> > The barrier task, triggered when all subtasks have completed, would
> report
> > to the central server.
> >
> > On Fri, Dec 18, 2009 at 10:21 PM, Enno Shioji wrote:
> >>
> >> Hi All,
> >>
> >> I came up with 2 kinds of solution to solve a particular problem, of
> >> which one seems to me simple enough. The other one however, attempts
> >> to manipulate the way JVM reorders using AtomicStampedReference to
> >> optimize, and I was wondering whether this is a good idea (in
> >> general).
> >>
> >> To give a little background, a bunch of servers will compute results
> >> of sub-tasks that belong to a single task and report them back to the
> >> central server. This piece of code is used to register the results,
> >> and also check whether all the subtasks for the task has completed and
> >> if so, report that fact only once. For simplicity, null checks, access
> >> level modifiers etc. are omitted.
> >>
> >> The important point is that, all task must be reported once and only
> >> once as soon as it is completed (completed means all subTaskResults
> >> are set).
> >>
> >>
> >>
> >> So, here is the first, simple solution:
> >>
> >> class Task {
> >>    //Populate with bunch of (Long, new AtomicReference()) pairs
> >>    //Actual app uses read only HashMap
> >>    Map<Id, AtomicReference<SubTaskResult>> subtasks = populatedMap();
> >>
> >>    Semaphore permission = new Semaphore(1);
> >>
> >>    public Task set(id, subTaskResult){
> >>           subtasks.get(id).set(result);
> >>           return check() ? this : null;
> >>    }
> >>
> >>    private boolean check(){
> >>          for(AtomicReference ref : subtasks){
> >>              if(ref.get()==null){
> >>                  return false;
> >>              }
> >>          }//for
> >>          return permission.tryAquire();
> >>    }
> >>
> >>  }//class
> >>
> >> 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.
> >>
> >>
> >> So, I thought for a while and came up with this idea:
> >> Solution III
> >>
> >> class Task {
> >>    //Populate with bunch of (Long, new AtomicStampedReference()) pairs
> >>    //Actual app uses read only HashMap
> >>    Map<Id, AtomicStampedReference<SubTaskResult>> subtasks =
> >> populatedMap();
> >>    AtomicInteger counter = new AtomicInteger(subtasks.size());
> >>
> >>    public Task set(id, subTaskResult){
> >>           AtomicStampedReference ref = subtasks.get(id);
> >>           ref.set(subTaskResult,-1);
> >>           int count = counter.decrementAndGet();
> >>           ref.attemptStamp(subTaskResult, count);
> >>           return count == 0;
> >>    }
> >>
> >>  }//class
> >>
> >> I reasoned that, because now there is a dependency (and reordering
> >> will be detectable), the JVM must call set(subTaskResult) before
> >> calling decrementAndGet(), and thus this implementation becomes thread
> >> safe.
> >>
> >> Am I reasoning right? Also, is it permissive to try manipulating
> >> reordering like this?
> >>
> >> Thank you.
> >>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20091219/0a501ec0/attachment-0001.html>


More information about the Concurrency-interest mailing list