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

Peter Levart peter.levart at gmail.com
Sun Dec 14 12:01:26 EST 2014


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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141214/973ca46a/attachment.html>


More information about the Concurrency-interest mailing list