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

Hanson Char hanson.char at gmail.com
Sun Dec 14 13:30:08 EST 2014


I think we have a great convergence.  Thanks!

On Sun, Dec 14, 2014 at 10:14 AM, Joe Bowbeer <joe.bowbeer at gmail.com> wrote:
>
> 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/bf03138f/attachment-0001.html>


More information about the Concurrency-interest mailing list