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

Hanson Char hanson.char at gmail.com
Sun Dec 21 20:39:52 EST 2014


Hi Joe,

Looks like a bug with Semaphore to me too. Even though a sufficient number
of permits are released for one of the threads already waiting, the waiting
thread still cannot make progress.  Otherwise, I think this is the niftiest
solution so far.  Sad it doesn't work out.

Regards,
Hanson

On Sun, Dec 21, 2014 at 4:25 PM, Joe Bowbeer <joe.bowbeer at gmail.com> wrote:

> Below is the most concise implementation I can imagine, using a single
> Semaphore, which is legal AFAICT according to the javadoc, but which
> deadlocks in my tests.
>
> class OrderedExecutor<T> {
>
>   private final Semaphore semaphore = new Semaphore(1);
>
>   @Override
>   public T execCallableInOrder(int order, Callable<T> callable)
>       throws InterruptedException, Exception {
>     assert order >= 0;
>     int acquires = order + 1;
>     semaphore.acquire(acquires);
>     try {
>       return callable.call();
>     } finally {
>       semaphore.release(acquires + 1);
>     }
>   }
> }
>
>
> testOrderedExecutorSynchronizer
> Waiting 2
> Waiting 1
> Waiting 8
> Waiting 7
> Waiting 9
> Waiting 0
> Executing 0
> Executing 1
> Executing 2
> Waiting 6
> Waiting 4
> Waiting 3
> Waiting 5
> Executing 3
> ... crickets ...
>
>
> A bug?
>
> On Sun, Dec 21, 2014 at 1:12 PM, Peter Levart <peter.levart at gmail.com>
> wrote:
>>
>>
>> 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>
>> 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>
>>> 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>
>>>> 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>
>>>>> 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>
>>>>>> 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>
>>>>>>> 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> 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>
>>>>>>>>> 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>
>>>>>>>>>> *To:* concurrency-interest <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> 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> 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> 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>
>>>>>>>>>> *To:* suman shil <suman_krec at yahoo.com>; Oleksandr Otenko <
>>>>>>>>>> oleksandr.otenko at oracle.com>; Concurrency-interest <
>>>>>>>>>> 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>
>>>>>>>>>>   To: suman shil<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>    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>
>>>>>>>>>>   To: Hanson Char<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>    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>  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>  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:
>>>>>>>>>> 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
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> _______________________________________________
>>>>>>>>>> Concurrency-interest mailing list
>>>>>>>>>> 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
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> _______________________________________________
>>>>>>>>>> Concurrency-interest mailing list
>>>>>>>>>> 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
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>
>>>
>>>
>>> _______________________________________________
>>> Concurrency-interest mailing listConcurrency-interest at cs.oswego.eduhttp://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>>
>>>
>>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141221/fd168ab4/attachment-0001.html>


More information about the Concurrency-interest mailing list