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

Joe Bowbeer joe.bowbeer at gmail.com
Sun Dec 14 13:14:28 EST 2014


I would use the latest Peter Levart version with park/unpark and a
ConcurrentMap that cleans itself.

On Sun, Dec 14, 2014 at 9:31 AM, Peter Levart <peter.levart at gmail.com>
wrote:
>
>
> 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>
> 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>
>> 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.eduhttp://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/20141214/63db4738/attachment.html>


More information about the Concurrency-interest mailing list