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

Peter Levart peter.levart at gmail.com
Thu Dec 18 02:43:44 EST 2014


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
>>
>>
>>
>
>



More information about the Concurrency-interest mailing list