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

suman shil suman_krec at yahoo.com
Wed Dec 17 09:07:15 EST 2014


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(); } }}
RegardsSuman
      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> 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 enforceordered execution of multiple critical sections, each calling from adifferent thread. The calling threads may run in parallel and may callthe execution method out of order. The perceived construct wouldtherefore be responsible for re-ordering the execution of thosethreads, so that their critical sections (and only the criticalsection) 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/20141217/9e6e6067/attachment-0001.html>


More information about the Concurrency-interest mailing list