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

Joe Bowbeer joe.bowbeer at gmail.com
Thu Dec 18 16:32:22 EST 2014


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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141218/acb4076a/attachment-0001.html>


More information about the Concurrency-interest mailing list