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

Oleksandr Otenko oleksandr.otenko at oracle.com
Wed Dec 17 11:25:59 EST 2014


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>
> *To:* Hanson Char <hanson.char at gmail.com>
> *Cc:* concurrency-interest <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 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/20141217/7a290cd9/attachment-0001.html>


More information about the Concurrency-interest mailing list