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

Joe Bowbeer joe.bowbeer at gmail.com
Mon Dec 22 02:31:59 EST 2014


I pushed some test code to:

https://bitbucket.org/joebowbeer/semaphorebug


On Sun, Dec 21, 2014 at 10:15 PM, Hanson Char <hanson.char at gmail.com> wrote:
>
> Hi Martin,
>
> Please find attached a modified version Joe's OrderedExecutor.java which
> assumes the order to start at 1 (rather than zero), and an
> OrderedExecutorTest.java that can be used to sanity check the correct
> behavior.
>
> Hope this helps.
>
> Regards,
> Hanson
>
>
> On Sun, Dec 21, 2014 at 9:57 PM, Martin Buchholz <martinrb at google.com>
> wrote:
>
>> It looks to me as well like a bug in Semaphore or AQS.
>> Where can we find the complete test program so we can debug?
>>
>> 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 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
>> >
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141221/58a32e2d/attachment-0001.html>


More information about the Concurrency-interest mailing list