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

Joe Bowbeer joe.bowbeer at gmail.com
Sun Dec 14 12:05:10 EST 2014


Even the simple implementation has a bug :-(

Should be:

  public OrderedExecutor() {
    getLock(0).release();
  }


On Sun, Dec 14, 2014 at 8:39 AM, Joe Bowbeer <joe.bowbeer at gmail.com> wrote:
>
> Below is a simple implementation where 'n' is not known in advance,
> assuming '0' is the starting order:
>
> class OrderedExecutor<T> {
>
>   private final List<Semaphore> locks = new ArrayList<>();
>
>   public OrderedExecutor() {
>     locks.add(0, new Semaphore(1));
>   }
>
>   public T execCallableInOrder(int order, Callable<T> callable)
>       throws InterruptedException, Exception {
>     getLock(order).acquire();
>     try {
>       return callable.call();
>     } finally {
>       getLock(order + 1).release();
>     }
>   }
>
>   private synchronized Semaphore getLock(int order) {
>     for (int i = locks.size(); i <= order; i++) {
>       locks.add(i, new Semaphore(0));
>     }
>     return locks.get(order);
>   }
> }
>
> If this were long-lived, I'd want to trim the locks array as they were
> consumed.
>
> On Sun, Dec 14, 2014 at 6:37 AM, Joe Bowbeer <joe.bowbeer at gmail.com>
> wrote:
>
>> Here's a "cyclic" version using Semaphore.  It resets when the last
>> callable execs.
>>
>> class OrderedExecutor<T> {
>>
>>   final Semaphore[] locks;
>>
>>   OrderedExecutor(int n) {
>>     locks = new Semaphore[n];
>>     for (int i = n; --i >= 0; ) {
>>       locks[i] = new Semaphore(0);
>>     }
>>     locks[0].release();
>>   }
>>
>>   public T execCallableInOrder(int order, Callable<T> callable)
>>       throws InterruptedException, Exception {
>>     locks[order].acquire();
>>     try {
>>       return callable.call();
>>     } finally {
>>       locks[(order + 1) % locks.length].release();
>>     }
>>   }
>> }
>>
>>
>> On Sat, Dec 13, 2014 at 8:26 PM, Hanson Char <hanson.char at gmail.com>
>> 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
>>> 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/e77938b4/attachment-0001.html>


More information about the Concurrency-interest mailing list