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

Peter Levart peter.levart at gmail.com
Sun Dec 21 16:12:11 EST 2014


On 12/21/2014 07:03 PM, Hanson Char wrote:
> Interesting - now that each order is associated with a different 
> object monitor, the wait/notifyAll would at most wake up one thread 
> instead of all.  In fact, it seems the use of notify (instead of 
> notifyAll) would suffice.  Simple and clever, but it does require the 
> "stripeSize" to be known a priori.

Not exactly. Each object monitor is associated with multiple orders. For 
example, if stripeSize is 4, the 1st object monitor is associated with 
orders: 0, 4, 8, 12, 16, ... the 2nd with orders 1, 5, 9, 13, 17, ... etc.

But it also means that each object monitor is associated statistically 
with just N/stripeSize threads that wait instead of N. So notifyAll is 
still needed, but it wakes up less threads - how much less depends on 
chosen stripeSize.

Regards, Peter

>
> Regards,
> Hanson
>
> On Sun, Dec 21, 2014 at 3:37 AM, Peter Levart <peter.levart at gmail.com 
> <mailto:peter.levart at gmail.com>> wrote:
>
>     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  <mailto: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/0921452f/attachment-0001.html>


More information about the Concurrency-interest mailing list