[concurrency-interest] Enforcing ordered execution of critical sections?

Peter Levart peter.levart at gmail.com
Sun Dec 21 06:37:34 EST 2014


Hi,

Here's a simple implementation (based on Suman Shil's idea) that stripes 
the waiting threads into multiple buckets:

public class StripedOrderedExecutor {

     private final MeetingPoint[] meetingPoints;

     public StripedOrderedExecutor(int stripeSize) {
         assert stripeSize > 0;
         meetingPoints = new MeetingPoint[stripeSize];
         for (int i = 0; i < stripeSize; i++) {
             meetingPoints[i] = new MeetingPoint();
         }
     }

     public <T> T execCriticalSectionInOrder(
         final int order,
         final Supplier<T> criticalSection
     ) throws InterruptedException {
         assert order >= 0;

         meetingPoints[order % meetingPoints.length].waitForGreen(order);
         try {
             return criticalSection.get();
         } finally {
             meetingPoints[(order + 1) % 
meetingPoints.length].notifyGreen(order + 1);
         }
     }

     private static class MeetingPoint {
         private int lastGreen;

         synchronized void waitForGreen(int order) throws 
InterruptedException {
             while (lastGreen != order) {
                 wait();
             }
         }

         synchronized void notifyGreen(int order) {
             lastGreen = order;
             notifyAll();
         }
     }
}


Regards, Peter





On 12/21/2014 02:35 AM, Hanson Char wrote:
> Thanks, Joe. That's an interesting point about the long term memory 
> impact of TreeMap vs HashMap - similar to LinkedList vs ArrayList.
>
> Regards,
> Hanson
>
> On Sat, Dec 20, 2014 at 5:17 PM, Joe Bowbeer <joe.bowbeer at gmail.com 
> <mailto:joe.bowbeer at gmail.com>> wrote:
>
>     I see.  Yes, that addresses the removal problem, though note that
>     HashMap does not shrink when data is removed. Even if all keys are
>     removed from HashMap, the inner size of its table does not change.
>
>     So in this case maybe I would choose TreeMap as the
>     implementation. Its remove() method *does* remove all the memory
>     associated with an entry.
>
>     In general, I don't like Map<Integer, *> because it seems like a
>     hack, but really in this case it's a small trade-off.  Map is more
>     concise. PriorityQueue is a little clearer.
>
>     On Sat, Dec 20, 2014 at 4:50 PM, Hanson Char
>     <hanson.char at gmail.com <mailto:hanson.char at gmail.com>> wrote:
>
>         Hi Joe,
>
>         >A Queue should also retain less memory. A Map will tend to accumulate both Entry and Integer
>         instances over time.
>
>         Using a Map, the signalNext would look something like below. 
>         Doesn't each entry get eventually removed from the map?  Why
>         would they accumulate over time?
>
>         Regards,
>         Hanson
>
>             void signalNext(final int nextOrder) {
>               lock.lock();
>               try {
>                 this.nextOrder = nextOrder;
>                 Condition cond = map.remove(nextOrder);
>                 if (cond != null) {
>                     cond.signal();
>                 }
>               } finally {
>                 lock.unlock();
>               }
>             }
>           }
>
>
>         On Sat, Dec 20, 2014 at 4:39 PM, Joe Bowbeer
>         <joe.bowbeer at gmail.com <mailto:joe.bowbeer at gmail.com>> wrote:
>
>             I think PriorityQueue more clearly represents the function
>             than Map does in this case.
>
>             A Queue should also retain less memory. A Map will tend to
>             accumulate both Entry and Integer instances over time.
>
>             The ConcurrentMap does have the advantage of lock
>             striping, which might be more performant if there is high
>             contention.
>
>             I think this is an interesting problem because there are
>             quite a few different solutions, each with advantages and
>             disadvantages in terms of performance and maintainability.
>
>             If there were a PriorityQueue version of
>             AbstractQueuedSynchronizer, then we could have yet another
>             solution using the AQS's state to represent the next
>             available order.
>
>             On Sat, Dec 20, 2014 at 3:59 PM, Hanson Char
>             <hanson.char at gmail.com <mailto:hanson.char at gmail.com>> wrote:
>
>                 This one looks interesting and educational.  The use
>                 of condition enables us to suspend and resume
>                 specifically targeted threads without resorting to the
>                 use of LockSupport.{part, unpark}.  Instead of using a
>                 PriorityQueue, perhaps we can use a simple
>                 Map<Integer, Condition> instead so we can get away
>                 without the extra Waiter inner class?
>
>                 Regards,
>                 Hanson
>
>                 On Sat, Dec 20, 2014 at 3:12 PM, Joe Bowbeer
>                 <joe.bowbeer at gmail.com <mailto:joe.bowbeer at gmail.com>>
>                 wrote:
>
>                     To round out the selection, here's an
>                     implementation using a PriorityQueue of Conditions:
>
>                     class OrderedExecutor<T> {
>
>                       static class Waiter implements Comparable<Waiter> {
>
>                         final int order;
>                         final Condition condition;
>
>                     Waiter(int order, Condition condition) {
>                     this.order = order;
>                     this.condition = condition;
>                         }
>
>                     @Override
>                     public int compareTo(Waiter waiter) {
>                     return order - waiter.order;
>                         }
>                       }
>
>                       final Lock lock = new ReentrantLock();
>                       final Queue<Waiter> queue = new PriorityQueue<>();
>                       int nextOrder; // 0 is next
>
>                       public T execCallableInOrder(int order,
>                     Callable<T> callable) throws Exception {
>                     assert order >= 0;
>                     awaitTurn(order);
>                         try {
>                     return callable.call();
>                         } finally {
>                     signalNext(order + 1);
>                         }
>                       }
>
>                       void awaitTurn(int order) {
>                     lock.lock();
>                         try {
>                     Condition condition = null;
>                     while (nextOrder != order) {
>                     if (condition == null) {
>                     condition = lock.newCondition();
>                     queue.add(new Waiter(order, condition));
>                             }
>                     condition.awaitUninterruptibly();
>                           }
>                         } finally {
>                     lock.unlock();
>                         }
>                       }
>
>                       void signalNext(int nextOrder) {
>                     lock.lock();
>                         try {
>                     this.nextOrder = nextOrder;
>                     Waiter waiter = queue.peek();
>                           if (waiter != null && waiter.order ==
>                     nextOrder) {
>                     queue.remove();
>                     waiter.condition.signal();
>                           }
>                         } finally {
>                     lock.unlock();
>                         }
>                       }
>                     }
>
>                     On Sat, Dec 20, 2014 at 11:21 AM, Joe Bowbeer
>                     <joe.bowbeer at gmail.com
>                     <mailto:joe.bowbeer at gmail.com>> wrote:
>
>                         Suman,
>
>                         I would advise against using notify/wait. It
>                         raises a red flag for a lot of reviewers,
>                         including me.
>
>                         The problems I see in this implementation are:
>
>                         1. Pre-allocation of locks is prohibited by
>                         (revised) problem statement.
>
>                         Note that if pre-allocation were allowed, then
>                         an array would be more efficient than a Map.
>
>                         2. Access to currentAllowedOrder is not
>                         thread-safe but should be.
>
>
>                         On Sat, Dec 20, 2014 at 6:04 AM, suman shil
>                         <suman_krec at yahoo.com
>                         <mailto:suman_krec at yahoo.com>> wrote:
>
>                             I have modified my solution to avoid
>                             notifyAll(). Let me know your feedback.
>
>
>                             public class OrderedExecutor
>                             {
>                             private int maxOrder;
>                             private int currentAllowedOrder;
>                             private Map<Integer, Object> map = new
>                             HashMap<Integer, Object>();
>                             public OrderedExecutor(int n)
>                                 {
>                             this.maxOrder = n;
>                             this.currentAllowedOrder = 0;
>                             for(int i = 0 ; i < this.maxOrder ; i++)
>                             {
>                             map.put(i, new Object());
>                             }
>                                 }
>                             public  Object
>                             execCriticalSectionInOrder(int order,
>                             Callable<Object> callable)
>                                     throws Exception
>                                 {
>                             if (order >= this.maxOrder)
>                             {
>                             throw new Exception("Exceeds maximum order
>                             "+ maxOrder);
>                             }
>                             while(order != currentAllowedOrder)
>                             {
>                             synchronized (this.map.get(order))
>                             {
>                             this.map.get(order).wait();
>                             }
>                             }
>                             try
>                             {
>                             return callable.call();
>                             }
>                              finally
>                             {
>                             currentAllowedOrder = currentAllowedOrder+1;
>                             synchronized (this.map.get(order+1))
>                               {
>                             this.map.get(order+1).notify();
>                               }
>                              }
>                                 }
>                             }
>
>
>                             ------------------------------------------------------------------------
>                             *From:* Joe Bowbeer <joe.bowbeer at gmail.com
>                             <mailto:joe.bowbeer at gmail.com>>
>                             *To:* concurrency-interest
>                             <concurrency-interest at cs.oswego.edu
>                             <mailto:concurrency-interest at cs.oswego.edu>>
>                             *Sent:* Friday, December 19, 2014 3:33 AM
>
>                             *Subject:* Re: [concurrency-interest]
>                             Enforcing ordered execution of critical
>                             sections?
>
>                             That would be "Tom" Cargill; link to paper:
>
>                             http://www.profcon.com/profcon/cargill/jgf/9809/SpecificNotification.html
>
>
>
>                             On Thu, Dec 18, 2014 at 1:32 PM, Joe
>                             Bowbeer <joe.bowbeer at gmail.com
>                             <mailto:joe.bowbeer at gmail.com>> wrote:
>
>                                 I frown on use of notify[All]/wait
>                                 because they make the code hard to
>                                 maintain.
>
>                                 In this case, with potentially lots of
>                                 waiting threads, I would check out the
>                                 "Specific Notification" pattern if I
>                                 were determined to go the wait/notify
>                                 route:
>
>                                 Tim Cargill's paper is dated but still
>                                 worth reading.
>
>                                 Also see chapter 3.7.3 Specific
>                                 Notifications in Doug Lea's CPiJ and
>                                 Peter Haggar's article:
>
>                                 http://www.ibm.com/developerworks/java/library/j-spnotif.html
>
>                                 On Thu, Dec 18, 2014 at 1:02 PM,
>                                 Oleksandr Otenko
>                                 <oleksandr.otenko at oracle.com
>                                 <mailto:oleksandr.otenko at oracle.com>>
>                                 wrote:
>
>                                     Yes, no one said it is a good idea
>                                     to always do that. When it is
>                                     contended, most of the threads
>                                     will wake up to only go back to sleep.
>
>                                     The pattern you are after is
>                                     usually called sequencer. You can
>                                     see it used in TCP. I am not sure
>                                     why it wasn't implemented in
>                                     j.u.c. - maybe not that popular.
>
>                                     The best solution will be
>                                     lock-like, but the waiter nodes
>                                     will contain the value they are
>                                     waiting for - so only the specific
>                                     threads get woken up. The solution
>                                     with concurrent map is very
>                                     similar, only with larger overhead
>                                     from storing the index the thread
>                                     is waiting for.
>
>
>                                     Alex
>
>
>
>                                     On 18/12/2014 20:21, Hanson Char
>                                     wrote:
>>                                     Less overhead and simpler are a
>>                                     nice properties, even though at
>>                                     the expense of having to wake up
>>                                     all waiting threads just to find
>>                                     out the one with the right order
>>                                     to execute. Still, this seems
>>                                     like a good tradeoff.
>>
>>                                     Thanks,
>>                                     Hanson
>>
>>                                     On Wed, Dec 17, 2014 at 11:43 PM,
>>                                     Peter Levart
>>                                     <peter.levart at gmail.com
>>                                     <mailto:peter.levart at gmail.com>>
>>                                     wrote:
>>
>>                                         On 12/17/2014 08:15 PM,
>>                                         Oleksandr Otenko wrote:
>>
>>                                             No, there is no
>>                                             difference. Peter didn't
>>                                             spot your entire method
>>                                             is synchronized, so
>>                                             spurious wakeup won't
>>                                             make progress until the
>>                                             owner of the lock exits
>>                                             the method.
>>
>>                                             You could split the
>>                                             synchronization into two
>>                                             blocks - one encompassing
>>                                             the wait loop, the other
>>                                             in the finally block; but
>>                                             it may make no difference.
>>
>>                                             Alex
>>
>>
>>                                         You're right, Alex. I'm so
>>                                         infected with park/unpark
>>                                         virus that I missed that ;-)
>>
>>                                         Peter
>>
>>
>>                                             On 17/12/2014 18:36,
>>                                             suman shil wrote:
>>
>>                                                 Thanks peter for your
>>                                                 reply. You are right.
>>                                                 I should have
>>                                                 incremented
>>                                                 currentAllowedOrder
>>                                                 in finally block.
>>
>>                                                 Suman
>>                                                 ------------------------------------------------------------------------
>>                                                 *From:* Peter Levart
>>                                                 <peter.levart at gmail.com
>>                                                 <mailto:peter.levart at gmail.com>>
>>                                                 *To:* suman shil
>>                                                 <suman_krec at yahoo.com
>>                                                 <mailto:suman_krec at yahoo.com>>;
>>                                                 Oleksandr Otenko
>>                                                 <oleksandr.otenko at oracle.com
>>                                                 <mailto:oleksandr.otenko at oracle.com>>;
>>                                                 Concurrency-interest
>>                                                 <concurrency-interest at cs.oswego.edu
>>                                                 <mailto:concurrency-interest at cs.oswego.edu>>
>>                                                 *Sent:* Wednesday,
>>                                                 December 17, 2014
>>                                                 11:54 PM
>>                                                 *Subject:* Re:
>>                                                 [concurrency-interest] Enforcing
>>                                                 ordered execution of
>>                                                 critical sections?
>>
>>                                                 On 12/17/2014 06:46
>>                                                 PM, suman shil wrote:
>>
>>                                                     Thanks for your
>>                                                     response. Will
>>                                                     notifyAll()
>>                                                     instead of
>>                                                     notify() solve
>>                                                     the problem?
>>
>>
>>                                                 It will, but you
>>                                                 should also account
>>                                                 for "spurious"
>>                                                 wake-ups. You should
>>                                                 increment
>>                                                 currentAllowedOrder
>>                                                 only after return
>>                                                 from callable.call
>>                                                 (in finally block
>>                                                 just before notifyAll()).
>>
>>                                                 Otherwise a nice
>>                                                 solution - with
>>                                                 minimal state,
>>                                                 providing that not
>>                                                 many threads meet at
>>                                                 the same time...
>>
>>                                                 Regards, Peter
>>
>>                                                     RegardsSuman
>>                                                            From:
>>                                                     Oleksandr
>>                                                     Otenko<oleksandr.otenko at oracle.com
>>                                                     <mailto:oleksandr.otenko at oracle.com>>
>>                                                     <mailto:oleksandr.otenko at oracle.com
>>                                                     <mailto:oleksandr.otenko at oracle.com>>
>>                                                       To: suman
>>                                                     shil<suman_krec at yahoo.com
>>                                                     <mailto:suman_krec at yahoo.com>>
>>                                                     <mailto:suman_krec at yahoo.com
>>                                                     <mailto:suman_krec at yahoo.com>>;
>>                                                     Concurrency-interest<concurrency-interest at cs.oswego.edu
>>                                                     <mailto:concurrency-interest at cs.oswego.edu>>
>>                                                     <mailto:concurrency-interest at cs.oswego.edu
>>                                                     <mailto:concurrency-interest at cs.oswego.edu>> 
>>                                                       Sent:
>>                                                     Wednesday,
>>                                                     December 17, 2014
>>                                                     9:55 PM
>>                                                       Subject: Re:
>>                                                     [concurrency-interest]
>>                                                     Enforcing ordered
>>                                                     execution of
>>                                                     critical sections?
>>                                                           There is no
>>                                                     guarantee you'll
>>                                                     ever hand over
>>                                                     the control to
>>                                                     the right thread
>>                                                     upon notify()
>>                                                         Alex
>>
>>                                                     On 17/12/2014
>>                                                     14:07, suman shil
>>                                                     wrote:
>>                                                           Hi,
>>                                                     Following is my
>>                                                     solution to solve
>>                                                     this problem.
>>                                                     Please let me
>>                                                     know if I am
>>                                                     missing something.
>>                                                        public class
>>                                                     OrderedExecutor
>>                                                     {  private int
>>                                                     currentAllowedOrder
>>                                                     = 0;  private int
>>                                                     maxLength = 0; 
>>                                                     public
>>                                                     OrderedExecutor(int
>>                                                     n)  {
>>                                                     this.maxLength =
>>                                                     n;  } public
>>                                                     synchronized
>>                                                     Object
>>                                                     execCriticalSectionInOrder(
>>                                                     int order,
>>                                                     Callable<Object>
>>                                                     callable)  throws
>>                                                     Exception  { if
>>                                                     (order >=
>>                                                     maxLength)  {
>>                                                     throw new
>>                                                     Exception("Exceeds maximum
>>                                                     order "+
>>                                                     maxLength); }
>>                                                     while(order !=
>>                                                     currentAllowedOrder)
>>                                                     {  wait();  }  
>>                                                     try  {
>>                                                     currentAllowedOrder
>>                                                     =
>>                                                     currentAllowedOrder+1;
>>                                                     return
>>                                                     callable.call();
>>                                                     }  finally  {
>>                                                     notify();  } } }
>>                                                        Regards Suman
>>                                                      From: Peter
>>                                                     Levart<peter.levart at gmail.com
>>                                                     <mailto:peter.levart at gmail.com>>
>>                                                     <mailto:peter.levart at gmail.com
>>                                                     <mailto:peter.levart at gmail.com>>
>>                                                       To: Hanson
>>                                                     Char<hanson.char at gmail.com
>>                                                     <mailto:hanson.char at gmail.com>>
>>                                                     <mailto:hanson.char at gmail.com
>>                                                     <mailto:hanson.char at gmail.com>> 
>>                                                       Cc:
>>                                                     concurrency-interest<concurrency-interest at cs.oswego.edu
>>                                                     <mailto:concurrency-interest at cs.oswego.edu>>
>>                                                     <mailto:concurrency-interest at cs.oswego.edu
>>                                                     <mailto:concurrency-interest at cs.oswego.edu>> 
>>                                                       Sent: Sunday,
>>                                                     December 14, 2014
>>                                                     11:01 PM
>>                                                       Subject: Re:
>>                                                     [concurrency-interest]
>>                                                     Enforcing ordered
>>                                                     execution of
>>                                                     critical sections?
>>                                                               On
>>                                                     12/14/2014 06:11
>>                                                     PM, Hanson Char
>>                                                     wrote:
>>                                                          Hi Peter,
>>                                                        Thanks for
>>                                                     this proposed
>>                                                     idea of using
>>                                                     LockSupport. This
>>                                                     begs the
>>                                                     question: which
>>                                                     one would you
>>                                                     choose if you had
>>                                                     all three
>>                                                     (correct)
>>                                                     implementation
>>                                                     available?
>>                                                     (Semaphore,
>>                                                     CountDownLatch,
>>                                                     or LockSupport)?
>>                                                        Regards, Hanson
>>                                                         The
>>                                                     Semaphore/CountDownLatch
>>                                                     variants are
>>                                                     equivalent if you
>>                                                     don't need
>>                                                     re-use. So any
>>                                                     would do. They
>>                                                     lack invalid-use
>>                                                     detection. What
>>                                                     happens if they
>>                                                     are not used as
>>                                                     intended?
>>                                                     Semaphore variant
>>                                                     acts differently
>>                                                     than
>>                                                     CountDownLatch
>>                                                     variant. The
>>                                                     low-level variant
>>                                                     I proposed
>>                                                     detects invalid
>>                                                     usage. So I would
>>                                                     probably use this
>>                                                     one. But the low
>>                                                     level variant is
>>                                                     harder to reason
>>                                                     about it's
>>                                                     correctness. I
>>                                                     think it is
>>                                                     correct, but you
>>                                                     should show it to
>>                                                     somebody else to
>>                                                     confirm this.
>>                                                         Another
>>                                                     question is
>>                                                     whether you
>>                                                     actually need
>>                                                     this kind of
>>                                                     synchronizer.
>>                                                     Maybe if you
>>                                                     explained what
>>                                                     you are trying to
>>                                                     achieve, somebody
>>                                                     could have an
>>                                                     idea how to do
>>                                                     that even more
>>                                                     elegantly...
>>                                                         Regards, Peter
>>                                                          On Sun, Dec
>>                                                     14, 2014 at 9:01
>>                                                     AM, Peter
>>                                                     Levart<peter.levart at gmail.com
>>                                                     <mailto:peter.levart at gmail.com>>
>>                                                     <mailto:peter.levart at gmail.com
>>                                                     <mailto:peter.levart at gmail.com>> 
>>                                                     wrote:
>>                                                        Hi Hanson,
>>                                                         This one is
>>                                                     more low-level,
>>                                                     but catches some
>>                                                     invalid usages
>>                                                     and is more
>>                                                     resource-friendly:
>>                                                           public
>>                                                     class
>>                                                     OrderedExecutor {
>>                                                             public
>>                                                     <T> T
>>                                                     execCriticalSectionInOrder(
>>                                                     final int order,
>>                                                     final Supplier<T>
>>                                                     criticalSection
>>                                                           ) throws
>>                                                     InterruptedException
>>                                                     {
>>                                                               if
>>                                                     (order < 0) {
>>                                                      throw new
>>                                                     IllegalArgumentException("'order'
>>                                                     should be >= 0");
>>                                                               }
>>                                                               if
>>                                                     (order > 0) {
>>                                                     waitForDone(order
>>                                                     - 1);
>>                                                               }
>>                                                               try {
>>                                                     return
>>                                                     criticalSection.get();
>>                                                               } finally {
>>                                                     notifyDone(order);
>>                                                               }
>>                                                           }
>>                                                     private static
>>                                                     final Object DONE
>>                                                     = new Object();
>>                                                           private
>>                                                     final
>>                                                     ConcurrentMap<Integer,
>>                                                     Object> signals =
>>                                                     new
>>                                                     ConcurrentHashMap<>();
>>                                                     private void
>>                                                     waitForDone(int
>>                                                     order) throws
>>                                                     InterruptedException
>>                                                     {
>>                                                     Object sig =
>>                                                     signals.putIfAbsent(order,
>>                                                     Thread.currentThread());
>>                                                               if (sig
>>                                                     != null && sig !=
>>                                                     DONE) {
>>                                                     throw new
>>                                                     IllegalStateException();
>>                                                               }
>>                                                     while (sig != DONE) {
>>                                                     LockSupport.park();
>>                                                     if
>>                                                     (Thread.interrupted())
>>                                                     {
>>                                                         throw new
>>                                                     InterruptedException();
>>                                                     }
>>                                                     sig =
>>                                                     signals.get(order);
>>                                                               }
>>                                                           }
>>                                                     private void
>>                                                     notifyDone(int
>>                                                     order) {
>>                                                     Object sig =
>>                                                     signals.putIfAbsent(order,
>>                                                     DONE);
>>                                                               if (sig
>>                                                     instanceof Thread) {
>>                                                     if
>>                                                     (!signals.replace(order,
>>                                                     sig, DONE)) {
>>                                                         throw new
>>                                                     IllegalStateException();
>>                                                     }
>>                                                     LockSupport.unpark((Thread)
>>                                                     sig);
>>                                                               } else
>>                                                     if (sig != null) {
>>                                                     throw new
>>                                                     IllegalStateException();
>>                                                               }
>>                                                           }
>>                                                       }
>>                                                           Regards, Peter
>>                                                         On 12/14/2014
>>                                                     05:08 PM, Peter
>>                                                     Levart wrote:
>>                                                            On
>>                                                     12/14/2014 04:20
>>                                                     PM, Hanson Char
>>                                                     wrote:
>>                                                          Hi Peter,
>>                                                        Thanks for the
>>                                                     suggestion, and
>>                                                     sorry about not
>>                                                     being clear about
>>                                                     one important
>>                                                     detail: "n" is
>>                                                     not known a
>>                                                     priori when
>>                                                     constructing an
>>                                                     OrderedExecutor.
>>                                                     Does this mean
>>                                                     the use of
>>                                                     CountDownLatch is
>>                                                     ruled out?
>>                                                         If you know
>>                                                     at least the
>>                                                     upper bound of
>>                                                     'n', it can be
>>                                                     used with such
>>                                                     'n'. Otherwise
>>                                                     something that
>>                                                     dynamically
>>                                                     re-sizes the
>>                                                     array could be
>>                                                     devised. Or you
>>                                                     could simply use
>>                                                     a
>>                                                     ConcurrentHashMap
>>                                                     instead of array
>>                                                     where keys are
>>                                                     'order' values:
>>                                                           public
>>                                                     class
>>                                                     OrderedExecutor<T> {
>>                                                     private final
>>                                                     ConcurrentMap<Integer,
>>                                                     CountDownLatch>
>>                                                     latches = new
>>                                                     ConcurrentHashMap<>();
>>                                                             public T
>>                                                     execCriticalSectionInOrder(final
>>                                                     int order,
>>                                                     final Supplier<T>
>>                                                     criticalSection)
>>                                                     throws
>>                                                     InterruptedException
>>                                                     {
>>                                                               if
>>                                                     (order > 0) {
>>                                                     latches.computeIfAbsent(order
>>                                                     - 1, o -> new
>>                                                     CountDownLatch(1)).await();
>>                                                               }
>>                                                               try {
>>                                                     return
>>                                                     criticalSection.get();
>>                                                               } finally {
>>                                                     latches.computeIfAbsent(order,
>>                                                     o -> new
>>                                                     CountDownLatch(1)).countDown();
>>                                                               }
>>                                                           }
>>                                                       }
>>                                                           Regards, Peter
>>                                                               You
>>                                                     guessed right:
>>                                                     it's a one-shot
>>                                                     object for a
>>                                                     particular
>>                                                     OrderedExecutor
>>                                                     instance, and
>>                                                     "order" must be
>>                                                     called indeed at
>>                                                     most once.
>>                                                        Regards, Hanson
>>                                                       On Sun, Dec 14,
>>                                                     2014 at 2:21 AM,
>>                                                     Peter
>>                                                     Levart<peter.levart at gmail.com
>>                                                     <mailto:peter.levart at gmail.com>>
>>                                                     <mailto:peter.levart at gmail.com
>>                                                     <mailto:peter.levart at gmail.com>> 
>>                                                     wrote:
>>                                                        Hi Hanson,
>>                                                         I don't think
>>                                                     anything like
>>                                                     that readily
>>                                                     exists  in
>>                                                     java.lang.concurrent,
>>                                                     but what you
>>                                                     describe should
>>                                                     be possible to
>>                                                     achieve with
>>                                                     composition of
>>                                                     existing
>>                                                     primitives. You
>>                                                     haven't given any
>>                                                     additional hints
>>                                                     to what your
>>                                                     OrderedExecutor
>>                                                     should behave
>>                                                     like. Should it
>>                                                     be a one-shot
>>                                                     object (like
>>                                                     CountDownLatch)
>>                                                     or a re-usable
>>                                                     one (like
>>                                                     CyclicBarrier)?
>>                                                     Will
>>                                                     execCriticalSectionInOrder()
>>                                                     for a particular
>>                                                     OrderedExecutor
>>                                                     instance and
>>                                                     'order' value be
>>                                                     called at most
>>                                                     once? If yes (and
>>                                                     I think that only
>>                                                     a one-shot
>>                                                     object  makes
>>                                                     sense here), an
>>                                                     array of
>>                                                     CountDownLatch(es) could
>>                                                     be used:
>>                                                         public class
>>                                                     OrderedExecutor<T> {
>>                                                           private
>>                                                     final
>>                                                     CountDownLatch[]
>>                                                     latches;
>>                                                             public
>>                                                     OrderedExecutor(int
>>                                                     n) {
>>                                                               if (n <
>>                                                     1) throw new
>>                                                     IllegalArgumentException("'n'
>>                                                     should be >= 1");
>>                                                     latches = new
>>                                                     CountDownLatch[n
>>                                                     - 1];
>>                                                               for
>>                                                     (int i = 0; i <
>>                                                     latches.length;
>>                                                     i++) {
>>                                                     latches[i] = new
>>                                                     CountDownLatch(1);
>>                                                               }
>>                                                           }
>>                                                             public T
>>                                                     execCriticalSectionInOrder(final
>>                                                     int order,
>>                                                      final
>>                                                     Supplier<T>
>>                                                     criticalSection)
>>                                                     throws
>>                                                     InterruptedException
>>                                                     {
>>                                                               if
>>                                                     (order < 0 ||
>>                                                     order >
>>                                                     latches.length)
>>                                                     throw new
>>                                                     IllegalArgumentException("'order'
>>                                                     should be [0..."
>>                                                     + latches.length
>>                                                     + "]");
>>                                                               if
>>                                                     (order > 0) {
>>                                                     latches[order -
>>                                                     1].await();
>>                                                               }
>>                                                               try {
>>                                                     return
>>                                                     criticalSection.get();
>>                                                               } finally {
>>                                                     if (order <
>>                                                     latches.length) {
>>                                                     latches[order].countDown();
>>                                                     }
>>                                                               }
>>                                                           }
>>                                                       }
>>                                                           Regards, Peter
>>                                                         On 12/14/2014
>>                                                     05:26 AM, Hanson
>>                                                     Char wrote:
>>                                                       Hi, I am
>>                                                     looking for a
>>                                                     construct that
>>                                                     can  be used to
>>                                                     efficiently
>>                                                     enforce ordered
>>                                                     execution of
>>                                                     multiple critical
>>                                                     sections, each
>>                                                     calling from a 
>>                                                     different thread.
>>                                                     The calling
>>                                                     threads may run
>>                                                     in parallel and
>>                                                     may call the
>>                                                     execution method
>>                                                     out of order. The
>>                                                     perceived
>>                                                     construct would
>>                                                     therefore be
>>                                                     responsible for
>>                                                     re-ordering the
>>                                                     execution of
>>                                                     those threads, so
>>                                                     that their
>>                                                     critical sections
>>                                                     (and only the
>>                                                     critical section)
>>                                                     will be executed
>>                                                     in order. Would
>>                                                     something like
>>                                                     the following API
>>                                                     already exist?
>>                                                     /** * Used to
>>                                                     enforce ordered
>>                                                     execution of
>>                                                     critical sections
>>                                                     calling from
>>                                                     multiple *
>>                                                     threads, parking
>>                                                     and unparking the
>>                                                     threads as
>>                                                     necessary. */
>>                                                     public class
>>                                                     OrderedExecutor<T> {
>>                                                     /** * Executes a
>>                                                     critical section
>>                                                     at most once with
>>                                                     the given order,
>>                                                     parking * and
>>                                                     unparking the
>>                                                     current thread
>>                                                     as  necessary so
>>                                                     that all critical
>>                                                     * sections
>>                                                     executed  by
>>                                                     different threads
>>                                                     using this 
>>                                                     executor take
>>                                                     place in * the
>>                                                     order from 1 to n
>>                                                     consecutively. */
>>                                                     public T
>>                                                     execCriticalSectionInOrder
>>                                                     (  final int
>>                                                     order, final
>>                                                     Callable<T>
>>                                                     criticalSection)
>>                                                     throws
>>                                                     InterruptedException;
>>                                                     } Regards, Hanson
>>                                                     _______________________________________________Concurrency-interest
>>                                                     mailing
>>                                                     listConcurrency-interest at cs.oswego.edu
>>                                                     <mailto:listConcurrency-interest at cs.oswego.edu>
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu>>
>>                                                     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>                                                     _______________________________________________
>>                                                     Concurrency-interest
>>                                                     mailing list
>>                                                     Concurrency-interest at cs.oswego.edu
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu>
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu>>
>>                                                     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>                                                     _______________________________________________
>>                                                     Concurrency-interest
>>                                                     mailing list
>>                                                     Concurrency-interest at cs.oswego.edu
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu>
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu>>
>>                                                     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>
>>
>>
>>
>>                                                     _______________________________________________
>>                                                     Concurrency-interest
>>                                                     mailing list
>>                                                     Concurrency-interest at cs.oswego.edu
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu>
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu
>>                                                     <mailto:Concurrency-interest at cs.oswego.edu>>
>>                                                     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>
>>
>>
>>
>>
>>
>>                                         _______________________________________________
>>                                         Concurrency-interest mailing list
>>                                         Concurrency-interest at cs.oswego.edu
>>                                         <mailto:Concurrency-interest at cs.oswego.edu>
>>                                         http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>
>
>                                     _______________________________________________
>                                     Concurrency-interest mailing list
>                                     Concurrency-interest at cs.oswego.edu
>                                     <mailto:Concurrency-interest at cs.oswego.edu>
>                                     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>                             _______________________________________________
>                             Concurrency-interest mailing list
>                             Concurrency-interest at cs.oswego.edu
>                             <mailto:Concurrency-interest at cs.oswego.edu>
>                             http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
>                             _______________________________________________
>                             Concurrency-interest mailing list
>                             Concurrency-interest at cs.oswego.edu
>                             <mailto:Concurrency-interest at cs.oswego.edu>
>                             http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>                     _______________________________________________
>                     Concurrency-interest mailing list
>                     Concurrency-interest at cs.oswego.edu
>                     <mailto: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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141221/d86e3678/attachment-0001.html>


More information about the Concurrency-interest mailing list