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

Joe Bowbeer joe.bowbeer at gmail.com
Sat Dec 19 01:47:06 EST 2009


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/20091218/d414e274/attachment.html>


More information about the Concurrency-interest mailing list