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

Enno Shioji eshioji at gmail.com
Sat Dec 19 03:14:36 EST 2009


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 <joe.bowbeer at gmail.com> 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.
>>
>
> _______________________________________________
> 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