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

Hanson Char hanson.char at gmail.com
Sun Dec 14 12:11:30 EST 2014


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

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
>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141214/693efc75/attachment.html>


More information about the Concurrency-interest mailing list