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

Joe Bowbeer joe.bowbeer at gmail.com
Sun Dec 21 19:25:48 EST 2014


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/5ab5b25b/attachment-0001.html>


More information about the Concurrency-interest mailing list