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

Oleksandr Otenko oleksandr.otenko at oracle.com
Tue Dec 30 08:05:54 EST 2014


What makes the code using wait/notify hard to maintain?

Alex

On 18/12/2014 21:32, Joe Bowbeer wrote:
> I frown on use of notify[All]/wait because they make the code hard to 
> maintain.
>
> In this case, with potentially lots of waiting threads, I would check 
> out the "Specific Notification" pattern if I were determined to go the 
> wait/notify route:
>
> Tim Cargill's paper is dated but still worth reading.
>
> Also see chapter 3.7.3 Specific Notifications in Doug Lea's CPiJ and 
> Peter Haggar's article:
>
> http://www.ibm.com/developerworks/java/library/j-spnotif.html
>
> On Thu, Dec 18, 2014 at 1:02 PM, Oleksandr Otenko 
> <oleksandr.otenko at oracle.com <mailto:oleksandr.otenko at oracle.com>> wrote:
>
>     Yes, no one said it is a good idea to always do that. When it is
>     contended, most of the threads will wake up to only go back to sleep.
>
>     The pattern you are after is usually called sequencer. You can see
>     it used in TCP. I am not sure why it wasn't implemented in j.u.c.
>     - maybe not that popular.
>
>     The best solution will be lock-like, but the waiter nodes will
>     contain the value they are waiting for - so only the specific
>     threads get woken up. The solution with concurrent map is very
>     similar, only with larger overhead from storing the index the
>     thread is waiting for.
>
>
>     Alex
>
>
>
>     On 18/12/2014 20:21, Hanson Char wrote:
>>     Less overhead and simpler are a nice properties, even though at
>>     the expense of having to wake up all waiting threads just to find
>>     out the one with the right order to execute.  Still, this seems
>>     like a good tradeoff.
>>
>>     Thanks,
>>     Hanson
>>
>>     On Wed, Dec 17, 2014 at 11:43 PM, Peter Levart
>>     <peter.levart at gmail.com <mailto:peter.levart at gmail.com>> wrote:
>>
>>         On 12/17/2014 08:15 PM, Oleksandr Otenko wrote:
>>
>>             No, there is no difference. Peter didn't spot your entire
>>             method is synchronized, so spurious wakeup won't make
>>             progress until the owner of the lock exits the method.
>>
>>             You could split the synchronization into two blocks - one
>>             encompassing the wait loop, the other in the finally
>>             block; but it may make no difference.
>>
>>             Alex
>>
>>
>>         You're right, Alex. I'm so infected with park/unpark virus
>>         that I missed that ;-)
>>
>>         Peter
>>
>>
>>             On 17/12/2014 18:36, suman shil wrote:
>>
>>                 Thanks peter for your reply. You are right. I should
>>                 have incremented currentAllowedOrder in finally block.
>>
>>                 Suman
>>                 ------------------------------------------------------------------------
>>                 *From:* Peter Levart <peter.levart at gmail.com
>>                 <mailto:peter.levart at gmail.com>>
>>                 *To:* suman shil <suman_krec at yahoo.com
>>                 <mailto:suman_krec at yahoo.com>>; Oleksandr Otenko
>>                 <oleksandr.otenko at oracle.com
>>                 <mailto:oleksandr.otenko at oracle.com>>;
>>                 Concurrency-interest
>>                 <concurrency-interest at cs.oswego.edu
>>                 <mailto:concurrency-interest at cs.oswego.edu>>
>>                 *Sent:* Wednesday, December 17, 2014 11:54 PM
>>                 *Subject:* Re: [concurrency-interest] Enforcing
>>                 ordered execution of critical sections?
>>
>>                 On 12/17/2014 06:46 PM, suman shil wrote:
>>
>>                     Thanks for your response. Will notifyAll()
>>                     instead of notify() solve the problem?
>>
>>
>>                 It will, but you should also account for "spurious"
>>                 wake-ups. You should increment currentAllowedOrder
>>                 only after return from callable.call (in finally
>>                 block just before notifyAll()).
>>
>>                 Otherwise a nice solution - with minimal state,
>>                 providing that not many threads meet at the same time...
>>
>>                 Regards, Peter
>>
>>                     RegardsSuman
>>                            From: Oleksandr
>>                     Otenko<oleksandr.otenko at oracle.com
>>                     <mailto:oleksandr.otenko at oracle.com>>
>>                     <mailto:oleksandr.otenko at oracle.com
>>                     <mailto:oleksandr.otenko at oracle.com>>
>>                       To: suman shil<suman_krec at yahoo.com
>>                     <mailto:suman_krec at yahoo.com>>
>>                     <mailto:suman_krec at yahoo.com
>>                     <mailto:suman_krec at yahoo.com>>;
>>                     Concurrency-interest<concurrency-interest at cs.oswego.edu
>>                     <mailto:concurrency-interest at cs.oswego.edu>>
>>                     <mailto:concurrency-interest at cs.oswego.edu
>>                     <mailto:concurrency-interest at cs.oswego.edu>>  
>>                     Sent: Wednesday, December 17, 2014 9:55 PM
>>                       Subject: Re: [concurrency-interest] Enforcing
>>                     ordered execution of critical sections?
>>                           There is no guarantee you'll ever hand over
>>                     the control to the right thread upon notify()
>>                         Alex
>>
>>                     On 17/12/2014 14:07, suman shil wrote:
>>                           Hi, Following is my solution to solve this
>>                     problem. Please let me know if I am missing
>>                     something.
>>                        public class OrderedExecutor { private int
>>                     currentAllowedOrder = 0; private int maxLength =
>>                     0;  public OrderedExecutor(int n)  {
>>                     this.maxLength = n;  } public synchronized Object
>>                     execCriticalSectionInOrder( int order,
>>                     Callable<Object> callable)                      
>>                          throws Exception  { if (order >= maxLength) 
>>                     {  throw new Exception("Exceeds maximum order "+
>>                     maxLength);  }    while(order !=
>>                     currentAllowedOrder)  {  wait();  } try  {
>>                     currentAllowedOrder = currentAllowedOrder+1; 
>>                     return callable.call();  }  finally  { notify(); 
>>                     }  } }
>>                        Regards Suman
>>                            From: Peter Levart<peter.levart at gmail.com
>>                     <mailto:peter.levart at gmail.com>>
>>                     <mailto:peter.levart at gmail.com
>>                     <mailto:peter.levart at gmail.com>>
>>                       To: Hanson Char<hanson.char at gmail.com
>>                     <mailto:hanson.char at gmail.com>>
>>                     <mailto:hanson.char at gmail.com
>>                     <mailto:hanson.char at gmail.com>>   Cc:
>>                     concurrency-interest<concurrency-interest at cs.oswego.edu
>>                     <mailto:concurrency-interest at cs.oswego.edu>>
>>                     <mailto:concurrency-interest at cs.oswego.edu
>>                     <mailto:concurrency-interest at cs.oswego.edu>>  
>>                     Sent: Sunday, December 14, 2014 11:01 PM
>>                       Subject: Re: [concurrency-interest] Enforcing
>>                     ordered execution of critical sections?
>>                               On 12/14/2014 06:11 PM, Hanson Char wrote:
>>                          Hi Peter,
>>                        Thanks for this proposed idea of using
>>                     LockSupport. This begs the question: which one
>>                     would you choose if you had all three (correct)
>>                     implementation available?  (Semaphore,
>>                     CountDownLatch, or LockSupport)?
>>                        Regards, Hanson
>>                         The Semaphore/CountDownLatch variants are
>>                     equivalent if you don't need re-use. So any would
>>                     do. They lack invalid-use detection. What happens
>>                     if they are not used as intended? Semaphore
>>                     variant acts differently than CountDownLatch
>>                     variant. The low-level variant I proposed detects
>>                     invalid usage. So I would probably use this one.
>>                     But the low level variant is harder to reason
>>                     about it's correctness. I think it is correct,
>>                     but you should show it to somebody else to
>>                     confirm this.
>>                         Another question is whether you actually need
>>                     this kind of synchronizer. Maybe if you explained
>>                     what you are trying to achieve, somebody could
>>                     have an idea how to do that even more elegantly...
>>                         Regards, Peter
>>                                  On Sun, Dec 14, 2014 at 9:01 AM,
>>                     Peter Levart<peter.levart at gmail.com
>>                     <mailto:peter.levart at gmail.com>>
>>                     <mailto:peter.levart at gmail.com
>>                     <mailto:peter.levart at gmail.com>> wrote:
>>                        Hi Hanson,
>>                         This one is more low-level, but catches some
>>                     invalid usages and is more resource-friendly:
>>                           public class OrderedExecutor {
>>                             public <T> T execCriticalSectionInOrder(
>>                               final int order,
>>                               final Supplier<T> criticalSection
>>                           ) throws InterruptedException {
>>                               if (order < 0) {
>>                                    throw new
>>                     IllegalArgumentException("'order' should be >= 0");
>>                               }
>>                               if (order > 0) {
>>                                   waitForDone(order - 1);
>>                               }
>>                               try {
>>                                   return criticalSection.get();
>>                               } finally {
>>                                   notifyDone(order);
>>                               }
>>                           }
>>                             private static final Object DONE = new
>>                     Object();
>>                           private final ConcurrentMap<Integer,
>>                     Object> signals = new ConcurrentHashMap<>();
>>                             private void waitForDone(int order)
>>                     throws InterruptedException {
>>                               Object sig = signals.putIfAbsent(order,
>>                     Thread.currentThread());
>>                               if (sig != null && sig != DONE) {
>>                                   throw new IllegalStateException();
>>                               }
>>                               while (sig != DONE) {
>>                                   LockSupport.park();
>>                                   if (Thread.interrupted()) {
>>                                       throw new InterruptedException();
>>                                   }
>>                                   sig = signals.get(order);
>>                               }
>>                           }
>>                             private void notifyDone(int order) {
>>                               Object sig = signals.putIfAbsent(order,
>>                     DONE);
>>                               if (sig instanceof Thread) {
>>                                   if (!signals.replace(order, sig,
>>                     DONE)) {
>>                                       throw new IllegalStateException();
>>                                   }
>>                     LockSupport.unpark((Thread) sig);
>>                               } else if (sig != null) {
>>                                   throw new IllegalStateException();
>>                               }
>>                           }
>>                       }
>>                           Regards, Peter
>>                         On 12/14/2014 05:08 PM, Peter Levart wrote:
>>                            On 12/14/2014 04:20 PM, Hanson Char wrote:
>>                          Hi Peter,
>>                        Thanks for the suggestion, and sorry about not
>>                     being clear about one important  detail: "n" is
>>                     not known a priori when constructing an
>>                     OrderedExecutor.  Does this mean the use of
>>                     CountDownLatch is ruled out?
>>                         If you know at least the upper bound of 'n',
>>                     it can be used with such 'n'. Otherwise something
>>                     that dynamically re-sizes the array could be
>>                     devised. Or you could simply use a
>>                     ConcurrentHashMap instead of array where keys are
>>                     'order' values:
>>                           public class OrderedExecutor<T> {
>>                             private final ConcurrentMap<Integer,
>>                     CountDownLatch> latches = new ConcurrentHashMap<>();
>>                             public T execCriticalSectionInOrder(final
>>                     int order,
>>                           final Supplier<T> criticalSection) throws
>>                     InterruptedException {
>>                               if (order > 0) {
>>                     latches.computeIfAbsent(order - 1, o -> new
>>                     CountDownLatch(1)).await();
>>                               }
>>                               try {
>>                                   return criticalSection.get();
>>                               } finally {
>>                     latches.computeIfAbsent(order, o -> new
>>                     CountDownLatch(1)).countDown();
>>                               }
>>                           }
>>                       }
>>                           Regards, Peter
>>                               You guessed right: it's a one-shot
>>                     object for a particular OrderedExecutor 
>>                     instance, and "order" must be called indeed at
>>                     most once.
>>                        Regards, Hanson
>>                       On Sun, Dec 14, 2014 at 2:21 AM, Peter
>>                     Levart<peter.levart at gmail.com
>>                     <mailto:peter.levart at gmail.com>>
>>                     <mailto:peter.levart at gmail.com
>>                     <mailto:peter.levart at gmail.com>> wrote:
>>                        Hi Hanson,
>>                         I don't think anything like that readily
>>                     exists  in java.lang.concurrent, but what you
>>                     describe should be possible to achieve with
>>                     composition of existing primitives.  You haven't
>>                     given any additional hints to what your
>>                     OrderedExecutor  should behave like. Should it be
>>                     a one-shot object (like CountDownLatch) or a
>>                     re-usable one (like CyclicBarrier)? Will
>>                     execCriticalSectionInOrder() for a particular
>>                     OrderedExecutor instance and 'order' value be
>>                     called at most once? If yes (and I think that
>>                     only a one-shot object  makes sense here), an
>>                     array of CountDownLatch(es) could be used:
>>                         public class OrderedExecutor<T> {
>>                           private final CountDownLatch[] latches;
>>                             public OrderedExecutor(int n) {
>>                               if (n < 1) throw new
>>                     IllegalArgumentException("'n'  should be >= 1");
>>                               latches = new CountDownLatch[n - 1];
>>                               for (int i = 0; i < latches.length; i++) {
>>                                   latches[i] = new CountDownLatch(1);
>>                               }
>>                           }
>>                             public T execCriticalSectionInOrder(final
>>                     int order,
>>                          final Supplier<T> criticalSection) throws
>>                     InterruptedException {
>>                               if (order < 0 || order > latches.length)
>>                                   throw new
>>                     IllegalArgumentException("'order' should be
>>                     [0..." +  latches.length + "]");
>>                               if (order > 0) {
>>                                   latches[order - 1].await();
>>                               }
>>                               try {
>>                                   return criticalSection.get();
>>                               } finally {
>>                                   if (order < latches.length) {
>>                     latches[order].countDown();
>>                                   }
>>                               }
>>                           }
>>                       }
>>                           Regards, Peter
>>                         On 12/14/2014 05:26 AM, Hanson Char wrote:
>>                             Hi, I am looking for a construct that
>>                     can  be used to efficiently enforce  ordered
>>                     execution of multiple critical sections, each
>>                     calling from a  different thread. The calling
>>                     threads may run in  parallel and may call the
>>                     execution method out of order. The  perceived
>>                     construct would therefore be responsible for
>>                     re-ordering the execution of those threads, so
>>                     that their critical  sections (and only the
>>                     critical section) will be executed in order.
>>                     Would something  like the following API already
>>                     exist? /** * Used to enforce ordered execution of
>>                     critical sections calling from multiple *
>>                     threads, parking and unparking the threads as
>>                     necessary. */ public class OrderedExecutor<T> {
>>                     /** * Executes a critical section at most once
>>                     with the given order, parking * and unparking the
>>                     current thread as necessary so that all critical
>>                     * sections executed  by different threads using
>>                     this  executor take place in * the order from 1
>>                     to n  consecutively. */ public T
>>                     execCriticalSectionInOrder
>>                     (  final int order, final Callable<T>
>>                     criticalSection) throws InterruptedException; }
>>                     Regards, Hanson
>>                     _______________________________________________Concurrency-interest
>>                     mailing listConcurrency-interest at cs.oswego.edu
>>                     <mailto:listConcurrency-interest at cs.oswego.edu>
>>                     <mailto:Concurrency-interest at cs.oswego.edu
>>                     <mailto:Concurrency-interest at cs.oswego.edu>>
>>                     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>                     _______________________________________________
>>                       Concurrency-interest mailing list
>>                     Concurrency-interest at cs.oswego.edu
>>                     <mailto:Concurrency-interest at cs.oswego.edu>
>>                     <mailto:Concurrency-interest at cs.oswego.edu
>>                     <mailto:Concurrency-interest at cs.oswego.edu>>
>>                     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>                     _______________________________________________
>>                     Concurrency-interest mailing list
>>                     Concurrency-interest at cs.oswego.edu
>>                     <mailto:Concurrency-interest at cs.oswego.edu>
>>                     <mailto:Concurrency-interest at cs.oswego.edu
>>                     <mailto:Concurrency-interest at cs.oswego.edu>>
>>                     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>
>>
>>
>>
>>                     _______________________________________________
>>                     Concurrency-interest mailing list
>>                     Concurrency-interest at cs.oswego.edu
>>                     <mailto:Concurrency-interest at cs.oswego.edu>
>>                     <mailto:Concurrency-interest at cs.oswego.edu
>>                     <mailto:Concurrency-interest at cs.oswego.edu>>
>>                     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>
>>
>>
>>
>>
>>
>>         _______________________________________________
>>         Concurrency-interest mailing list
>>         Concurrency-interest at cs.oswego.edu
>>         <mailto:Concurrency-interest at cs.oswego.edu>
>>         http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>
>
>     _______________________________________________
>     Concurrency-interest mailing list
>     Concurrency-interest at cs.oswego.edu
>     <mailto:Concurrency-interest at cs.oswego.edu>
>     http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141230/8e9fd0ce/attachment-0001.html>


More information about the Concurrency-interest mailing list