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

Aleksey Shipilev aleksey.shipilev at oracle.com
Mon Dec 22 11:46:02 EST 2014


On 12/22/2014 05:36 PM, Doug Lea wrote:
> On 12/21/2014 07:25 PM, Joe Bowbeer wrote:
>> Below is the most concise implementation I can imagine, using a single
>> Semaphore, which is legal AFAICT according to the javadoc, but which
>> deadlocks
>> in my tests.
> 
> This makes a too-strong assumption about Semaphore.acquire(n), that
> waiters do not independently try to accumulate permits.
> I suppose that we don't explicitly rule this out, but do state...
> 
> "This class also provides convenience methods to acquire and release
> multiple permits at a time. Beware of the increased risk of indefinite
> postponement when these methods are used without fairness set true. "
> 
> The acquire(n) spec should probably be clarified that it promises
> no more than the equivalent of
>   for (int i = 0; i < n; ++i) acquire();

Wait, what. If fairness only applies to individual acquire() calls, that
definition would mean that even with fair Semaphore two threads can
deadlock in:

 Semaphore s = new Semaphore(5, true);

 Thread 1:
   s.acquire(5);

 Thread 2:
   s.acquire(5);

Most people I talked to assume a Semaphore does the CAS for the entire
batch when multiple permits are requested. I think we better fix the
implementation to do the same even in non-fair case, owing to the
Principle of Least Astonishment. People rightfully expect the starvation
with non-fair Semaphores, but not the deadlock.

Thanks,
-Aleksey.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20141222/36d5b1e6/attachment.bin>


More information about the Concurrency-interest mailing list